Online fair division of chores improving fairness and efficiency
Online Fair Division of Chores with Upgrade Recourse
Computer Science and Game TheoryArtificial Intelligence
Summary
This paper looks at how to fairly share chores among people when chores arrive over time and assignments can be changed. The authors found a simple way to keep the sharing fair up to one chore and give each person nearly their fair share based on their worst-case scenario. They also show that without extra information, no method can do better. The work contrasts with dividing good things and shows that knowing some timing information helps improve fairness. However, achieving stronger fairness guarantees requires very precise information about chores.
What this means in practice
- •For resource allocation teams: Manage dynamically arriving tasks among workers fairly while ensuring each task reassignment does not reduce individual fairness significantly.
- •For scheduling system designers: Design online task schedulers that can revise previous assignments to improve fairness without knowing full future task details.
A theory result. No direct application yet.
Authors
Yichen Huang, Nicholas Teh
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$.