Fair online item allocation improves equality without losing much value
Prophet Inequalities Beyond Utilitarian Social Welfare
Computer Science and Game Theory
Summary
This paper looks at how to share items fairly among people who arrive one after another and reveal what they want. Instead of only trying to make the total value as big as possible, the authors measure fairness using various averages that balance overall value and individual fairness. They find that you can get close to the best fairness possible even when deciding who gets items on the spot. Their work shows that focusing more on fairness does not cost much compared to just maximizing total value, but some technical assumptions are needed for good performance.
What this means in practice
- •For online marketplaces: Design rules to allocate limited items fairly to sequential buyers while maintaining close to optimal overall satisfaction.
- •For cloud resource schedulers: Implement fair online scheduling policies that balance efficiency and fairness when assigning resources to incoming tasks.
Authors
Daniel Halpern, Abhiram Manohara, Alexandros Psomas
Abstract
In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of $n$ agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating $m$ indivisible items to sequentially arriving agents with i.i.d.\ additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized $p$-mean welfare, which includes utilitarian welfare at $p=1$, Nash welfare (the geometric mean of utilities) at $p=0$, and egalitarian welfare (the minimum utility) as $p\to-\infty$. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet problem evaluated by the $p$-mean of agents' expected utilities. We characterize this single-item problem: every online rule is weakly Pareto dominated by a quantile-threshold rule, and an optimal egalitarian rule equalizes agents' expected utilities. We prove that for every $n$, the online optimum is at least $Γ\approx0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le1$. Further, for egalitarian welfare, the optimal ratio converges to $Γ$ as $n\to\infty$. Thus, asymptotically, optimizing egalitarian rather than utilitarian welfare costs only about four percentage points relative to the classical utilitarian ratio of $0.7451$. Finally, when $m=n$, the worst-case competitive ratio converges to zero as $n\to\infty$ for every $p\le0$, showing that the large-item assumption is necessary.