TL;DR
This paper introduces "upgrade recourse" to online fair division, allowing chores to be reassigned only if the new task is no more costly for the agent than the old one. The authors prove that a simple "round-robin insertion" algorithm achieves optimal fairness guarantees (EF1 and $(2-1/n)$-MMS) without needing to know the future, though even a tiny bit of information about the total number of tasks can further boost these results.
What Problem Does This Paper Address?
Fairly dividing tasks (chores) is hard, especially when they arrive one by one ("online"). If you assign a task and can never change it, a single unlucky person might end up with everything if the algorithm makes a bad guess about future arrivals. Conversely, if you allow unlimited reassignments, you might constantly "bait and switch" workers, replacing a quick 10-minute task with a grueling 5-hour one.
The authors propose a middle ground called upgrade recourse. In this model, the system can reassign chores, but with a strict rule: every chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. It’s the algorithmic equivalent of saying, "I'm swapping your difficult bug fix for an easier documentation update."
The goal is to maintain fairness—specifically Envy-Freeness up to one chore (EF1) and a good approximation of the Maximin Share (MMS)—in this online setting.
Methods
The core technical contribution is the Chore Insertion algorithm. This is an online implementation of a "least-cost picking" strategy.
- Fixed Sequence: The algorithm starts with a fixed sequence of "turns" (e.g., a repeating round-robin order: Agent 1, Agent 2, Agent 3...).
- Insertion Procedure: When a new chore arrives, the owner of the first turn compares it to the chore they currently hold. They keep the "cheaper" one and pass the more expensive one to the next turn in the sequence. This continues down the line until the last chore is placed in a new turn at the end.
- Upgrade Guarantee: Because each agent only ever swaps a chore for one they find less (or equally) costly, the "upgrade recourse" condition is always satisfied.
The authors analyze this algorithm under different information regimes: no knowledge of the future, knowledge of the total number of chores modulo some period, and exact knowledge of the total number of chores.
Datasets
This is a theoretical paper in the field of computational social choice and algorithmic game theory. As such, it does not use empirical datasets. Instead, it uses mathematical proofs and worst-case analysis (adversarial models) to establish bounds on fairness.
Key Insights and Ideas
- Chores vs. Goods: Fairly dividing chores is fundamentally different from dividing goods. For goods, the fairness gap (MMS factor) vanishes as the number of agents grows. For chores, the gap stays constant (around 2), meaning chores are inherently "harder" to divide fairly online.
- The Power of "Modulo" Predictions: You don't need a crystal ball to improve fairness. The authors show that just knowing the total number of chores modulo a small number (related to the number of agents) allows the algorithm to pick a better starting point in its sequence, significantly improving the final outcome.
- EFX is the "Hard" Limit: While EF1 (envy-freeness up to one chore) is easy to maintain, EFX (envy-freeness up to any chore) is nearly impossible. Even a tiny bit of uncertainty about whether there are $n$ or $n+1$ chores total makes a finite EFX approximation impossible without exact horizon knowledge.
Key Results
The paper establishes a hierarchy of results based on how much information the algorithm has and what type of recourse is allowed. These are summarized in the table below:
- Optimal Prediction-Free Bound: With no information about the future, round-robin insertion achieves a $(2 - 1/n)$-MMS guarantee. The authors prove this is the absolute best any deterministic algorithm can do.
- Consistency vs. Robustness: When given a "residue" (the total count modulo $L$), the algorithm achieves a better factor if the prediction is correct (Consistency) while staying below a factor of 3 even if the prediction is completely wrong (Robustness).
- EFX Impossibility: Without knowing the exact number of chores ($m$), no algorithm can guarantee a finite EFX factor. If $m$ is known, the best factor is $m-n$.
Limitations and Future Work
- Deterministic Focus: The lower bounds in this paper apply to deterministic algorithms. The authors note that for goods, randomization doesn't help much against an oblivious adversary, but the potential for randomized chore allocation remains an open question.
- Reassignment Volume: While the algorithm respects the "upgrade" rule, it doesn't strictly limit the number of times a chore might be moved. In a system with $m$ chores, a single arrival could trigger many swaps. Future work could look at balancing fairness with a "budget" on the total number of reassignments.
- Bundle-level vs. Item-level: The paper distinguishes between protecting each chore individually (item-level) vs. just protecting the agent's total cost (bundle-level). While they provide some bounds for the weaker bundle-level rule, the optimal factor for $n \geq 4$ agents remains an open problem.
Summary updated