How to Split Things Fairly When They Show Up One at a Time
The math could shape how gig apps and shops hand out scarce stuff.
Two researchers, Yingjian Du and Ankang Sun, take on online fair division: indivisible resources arrive over time and must be assigned before future resources are known, with allocation decisions immediate and irrevocable. Their setting is deterministic online allocation among n agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous decisions.
Focusing on proportionality up to one good (PROP1), they answer an open question from Choo et al. about whether a nontrivial deterministic approximation for PROP1 exists. Without extra information, they give a deterministic algorithm guaranteeing Ω(1/log(nm))-PROP1, where m is the number of goods — and show that for every fixed n and sufficiently large m, every deterministic algorithm has an instance whose PROP1 factor is O(log log m / log m).
If the algorithm knows each agent's maximum item value in advance, they give a deterministic algorithm with competitive ratio 1/2, improving the 1/n guarantee in Choo et al. They also show no deterministic algorithm can get arbitrarily close to a ratio of one, even for two agents with exact MIV information.
- It's a math paper about dividing things fairly when they arrive one at a time and choices can't be undone.
- Their method guarantees each person gets near their fair share — within one item — even if the order is stacked against them.
- Getting one small peek ahead (the value of the priciest item per person) boosts fairness to 'half,' up from a tiny fraction when many people share.
Why It Matters
It caps how fair real systems — delivery dispatch, cloud resources, ticket releases — can ever promise to be.