Abstract
This paper investigates the feasibility and cost of maintaining envy-free allocations in an online setting where items arrive sequentially and subsidies are used to compensate agents. We characterize the conditions under which envy-freeness can be maintained across various valuation classes, including additive, submodular, and $k$-demand valuations. Our results reveal a significant "online tax," where the required subsidy in the online setting often scales linearly with the number of items, contrasting with the bounded subsidies possible in offline scenarios. We provide a comprehensive map of valuation classes that allow for online envy-freeness and identify those where the subsidy remains independent of the item count.
Introduction
Fair division is a fundamental problem in resource allocation, aiming to distribute items among agents such that no agent envies another's bundle—a condition known as envy-freeness (EF). When items are indivisible, EF allocations may not exist. To address this, researchers introduce subsidies (monetary payments) to achieve fairness. While previous literature has extensively studied the offline setting where all items are known in advance, this paper explores the online setting: items arrive one by one and must be allocated immediately and irrevocably.
The research focuses on two primary questions:
- Existence: For which valuation classes can envy-freeness be maintained as items arrive?
- Cost: What is the subsidy required to ensure fairness, and how does it scale with the number of items?
Methodology
The authors establish that an allocation can be made envy-free with subsidies if and only if it is locally efficient (LE). An allocation is LE if no simple swap or reassignment of existing bundles can increase the total social welfare.
To analyze these properties, the study employs:
- Envy Graphs: Directed graphs where nodes represent agents and edge weights denote the degree of envy. The minimum required subsidy is derived from the "heaviest paths" in these graphs.
- Adversarial Constructions: Used to prove impossibility results by designing item sequences that force any online algorithm to lose local efficiency.
- Greedy Algorithms: Developed for positive results to assign items in a way that preserves LE at every step, often by maintaining specific invariants like sorted bundle values.
The analysis covers several valuation classes, ranging from simple Additive valuations to more complex Submodular, Supermodular, and k-Demand preferences.
Key Results and Insights
The paper provides a comprehensive classification of which valuation types allow for online envy-freeness and the magnitude of the resulting "online tax."
The Welfare-Efficiency Gap and the Online Tax
A key finding is the separation between welfare maximization and local efficiency. For additive valuations, maximizing social welfare online maintains LE. However, for $k$-demand valuations, maximizing welfare online is impossible, yet local efficiency (and thus EF with subsidies) can still be maintained.
Furthermore, the authors identify a significant "online tax." In offline settings, a subsidy of $O(n)$ (where $n$ is the number of agents) suffices for additive valuations. In the online setting, the required subsidy jumps to $\Omega(mn)$, scaling with the number of items $m$.
Mapping Fairness Online
The results are summarized in the following table, which delineates the boundaries of online fair division.
As shown in the table, envy-freeness can be maintained for Additive, SPLC, and $k$-Demand valuations. Conversely, it is mathematically impossible for more complex classes like Budget-Additive, Submodular, or Supermodular valuations, even with binary marginals.
Small Subsidy Bounds
For certain structured classes, the authors show that the subsidy can remain "small" (independent of $m$):
- Rank-One and Restricted Additive: $O(n^2)$ total subsidy.
- Identical Monotone: $O(n)$ total subsidy.
- k-Demand: $O(kn)$ total subsidy.
Discussion and Future Work
While this work provides a detailed map of online fairness, several avenues remain open. The bounds for "personalized $k$-valued" valuations are likely not tight, presenting an opportunity for refinement. Additionally, while the paper delineates several classes, a single unifying property that determines whether a valuation class allows for online local efficiency has yet to be identified. Finally, extending these results to "chore division" (allocating items with negative value) involves different subsidy dynamics that warrant further investigation.
Summary updated