arXiv preprint ·
Online Fair Division of Chores with Upgrade Recourse
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the online fair division of indivisible chores among $n$ agents under upgrade recourse, where earlier assignments may be revised but each chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. We show that a simple adaptation of round robin maintains envy-freeness up to one chore (EF1) together with a $(2-1/n)$-approximation of the maximin share (MMS), and that no deterministic algorithm without predictions can do better, even when all agents rank the chores in the same order. This stands in contrast to the allocation of goods, where the optimal MMS factor vanishes as $n$ grows and cannot be achieved together with EF1. Moreover, knowing only the number of chores modulo a period of length $O(n)$ (and nothing about the costs) suffices to improve upon this factor at the final configuration, while the same algorithm retains a factor below $3$ even if this information is wrong. On the other hand, envy-freeness up to any chore (EFX) essentially requires the exact number of chores: uncertainty between two consecutive values already rules out every finite approximation, and even exact knowledge does not allow EFX to be combined with an MMS guarantee better than the trivial factor of $n$.
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 Computer Science & Game Theory
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
How Much Can Approximate Equilibria Change the Social Cost of Selfish Routing?
When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning
A Compute Center Anyone Can Join: A Peer-to-Peer System for AI Inference
Strategic Tanking in Stable Matching Markets
Get the few papers worth your time in Computer Science & Game Theory 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.