Online fair division improves shared resource allocation fairness
Online Fair Division: Pushing the Frontier of Approximate Proportionality
Computer Science and Game Theory
Summary
Fairly dividing things that come in one by one, like toys or tasks, is hard when you must decide who gets what right away. This paper looks at how well fairness can be guaranteed when decisions can’t be changed later and future items are unknown. The authors offer new ways to share fairly, improving past methods and showing limits on what is possible when item values are known in advance or completely unknown. Their work answers open questions about how fair division can be done when resources arrive over time.
What this means in practice
- •For cloud resource schedulers: Allocate computing resources arriving unpredictably to users fairly without knowing future demands, improving user satisfaction and resource usage.
- •For online advertising platforms: Assign ad impressions that appear over time fairly across advertisers despite uncertain future availability, enhancing revenue fairness.
Authors
Yingjian Du, Ankang Sun
Abstract
Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study deterministic online allocation among $n$ agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous allocation decisions. We focus on proportionality up to one good (PROP1) and examine how advance future information affects the achievable guarantees. In the setting without additional information, we answer an open question in Choo et al. that asks whether a nontrivial deterministic approximation for PROP1 can be obtained. In particular, we present a deterministic algorithm that guarantees $Ω(1/\log(nm))$-PROP1, where $m$ is the number of goods. Moreover, we complement this result by showing that, for every fixed $n$ and all sufficiently large $m$, every deterministic algorithm has an instance with $m$ goods on which its PROP1 factor is $O(\log\log m/\log m)$. We also study the setting where the algorithm knows in advance the maximum item value (MIV) for every agent. With MIV information, we give a deterministic algorithm with competitive ratio 1/2, improving the $1/n$ guarantee in Choo et al. We also show that no deterministic algorithm can achieve a competitive ratio arbitrarily close to one, even for two agents with exact MIV information.