Randomized online fair division algorithms achieve improved fairness guarantees
Randomized Online Fair Division: High-Probability and Expected Realized Fairness
Computer Science and Game Theory
Summary
The paper studies how to fairly share items that arrive one by one among several people when you have to give each item away immediately and can’t change decisions later. The authors find ways to guarantee that everyone gets a mostly fair share, better than just random assignment, with high probability and on average. They show that some fairness goals can’t be reliably met in this setting, highlighting limits on what online methods can achieve. The results provide new bounds on fairness measures called proportionality and envy freeness under these real-world constraints.
What this means in practice
- •For cloud resource managers: Assign computing or storage resources one at a time to users fairly without knowing future requests in advance.
- •For advertising platform operators: Allocate ad slots arriving over time to advertisers to maintain fairness in exposure probabilistically better than random assignment.
Authors
Tianqi Chen, Jingxiao Long
Abstract
We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive one by one and must be allocated immediately and irrevocably. Nothing is known in advance except the number of agents. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm that achieves an $Ω(\sqrt{\log n}/\log(n/δ))$-approximation to proportionality up to one good (PROP1) with probability at least $1-δ$ for every $δ\in(0,1)$, and an expected realized PROP1 factor of $Ω(1/\sqrt{\log n})$. Compared with independent uniform allocation (Rand), these guarantees yield an $Ω(\sqrt{\log n})$ improvement under both the high-probability and expected realized criteria. For envy freeness up to any good (EFX), the success probability of any positive factor can be made arbitrarily small, even for identical valuations. Consequently, the expected realized factor of every randomized fully online algorithm is zero. For envy freeness up to one good (EF1), no randomized fully online algorithm can guarantee a positive factor with confidence exceeding $\frac{n+1}{2n}$. The expected realized EF1 guarantee is also at most $\frac{n+1}{2n}$.