OpenAlex ·
Online Fair Division with Upgrade Recourse
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.16943
- Original
- Read it at the publisher
- Topics
Abstract
We study the online fair division of indivisible goods. In the standard model, where assignments are irrevocable, no algorithm can guarantee any positive fraction of the maximin share (MMS). Reassigning earlier goods can restore fairness, but it may take value away from agents who already hold them. We ask how much fairness can be maintained if every reassignment must leave each affected agent at least as well off. We consider two forms of such upgrade recourse. Under item-level upgrades, each good an agent holds must be kept or replaced by a distinct good she values at least as much; under bundle-level upgrades, only her total value must not decrease. For item-level upgrades, we show that the optimal MMS factor is essentially $1/H_n \approx 1/\ln n$, where $H_n$ is the $n$-th harmonic number, and that fixed picking sequences nearly attain it. Since these sequences use only the agents' rankings of individual goods, knowing the actual values cannot improve the optimal factor for up to 33 agents, and improves it by at most a vanishing margin as $n$ grows. Bundle-level upgrades allow substantially stronger guarantees. By permitting several-for-one exchanges, they turn this vanishing factor into a constant: we achieve exact MMS for two agents and more than half of MMS for any number of agents, in both cases together with relaxations of envy-freeness. Finally, we show that predictions about future goods let online algorithms inherit any offline MMS guarantee, losing only an additive term bounded by the prediction error. Under item-level upgrades, however, insisting on exact MMS when predictions are correct leaves no positive guarantee when they are wrong.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
The Buffett Effect
How language model agents reshape price competition
Estimation of Rational Inattention--Additive Random Utility Models
Market Efficiency in a Changing Asset Population: Mobility, Entry, and Survival over Cryptocurrency's Full History
TRACE: Governing AI-Assisted Research with Principles from Computer Science
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.