Introduction
Fairly dividing resources among agents is a cornerstone of computational social choice. While much research focuses on the allocation of "goods," the problem of indivisible chore allocation—where items represent burdens or costs—presents unique challenges. The standard fairness benchmark, Maximin Share (MMS), defines a fair share as the cost of the most expensive bundle an agent would receive if they were to partition all chores into $n$ bundles themselves. Unfortunately, an MMS-fair allocation is not guaranteed to exist for more than two agents when chores cannot be split.
This paper introduces a novel relaxation: $\alpha$-approximate all-but-one maximin share ($\alpha$-AMMS). Instead of seeking a mediocre approximation for everyone, the authors investigate whether it is possible to satisfy $n-1$ agents perfectly (giving them their full MMS) while bounding the cost for the final agent by a factor of $\alpha$.
The $\alpha$-AMMS Framework
The "all-but-one" shift recognizes that in many practical scenarios, satisfying the vast majority of participants perfectly is preferable to a solution where everyone feels slightly slighted. In the context of chores, this means $n-1$ agents receive bundles with costs no greater than their MMS value, while the $n$-th agent receives a bundle with a cost at most $\alpha \cdot MMS$.
Methodology: Graphs and Reductions
The authors utilize MMS-feasibility graphs to model the problem. These are bipartite graphs where one set of nodes represents agents and the other represents bundles from a specific agent's ideal partition. A perfectly fair allocation corresponds to a perfect matching in this graph.
When a perfect matching does not exist, the authors apply Hall’s Marriage Theorem to identify "bottlenecks"—subsets of agents who collectively value too few bundles. This allows for valid reductions, where a subset of agents and chores are removed from the problem without increasing the proportional burden on the remaining participants.
For specific cases, such as $n=3$, the authors propose specialized algorithms that combine these graph-theoretic reductions with techniques like "divide-and-choose" and load-balancing to achieve tight approximation ratios.
Key Results
The paper establishes the existence of $\alpha$-AMMS allocations for various group sizes. The approximation factor $\alpha$ represents the maximum relative overhead for the single agent who does not receive their full MMS:
- 3 Agents: A ratio of $9/8$ (1.125x MMS) is always achievable.
- 4 Agents: A ratio of $4/3$ (~1.33x MMS) is guaranteed.
- General $n$ Agents: The authors prove a ratio of $(n+1)^2 / 4n$ using techniques like Partition-Merging and Capped-Bag-Filling.
These results demonstrate that for small groups, the "penalty" for the last agent is remarkably low. For instance, with three agents, two can be perfectly satisfied while the third does only 12.5% more work than their theoretical fair share.
Conclusion and Future Work
This research provides a new lens through which to view fairness in chore allocation. By prioritizing perfect fairness for the majority, the $\alpha$-AMMS concept offers a practical alternative to traditional approximation methods.
Future work remains in narrowing the gap for the general $n$ case, where the current ratio grows linearly with the number of agents. Additionally, exploring the strategy-proofness of these algorithms—ensuring agents cannot benefit by misreporting their costs—remains a significant open challenge in the field.
Summary updated