Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores

Jiawei Qiu, Xiaowei Wu, Cong Zhang, Shengwei ZhouarXiv 2024 · DOI · arXiv

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.

Figure 1: An MMS-feasibility graph illustrating a subset of agents $S^*$ and their neighboring bundles $L(S^*)$, used to identify bottlenecks via Hall’s Marriage Theorem.

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.

Figure 2: Algorithm 3 for the 3-agent case, which achieves a 9/8-AMMS allocation by combining MMS reduction and load-balancing.

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

Abstract

We study the problem of allocating $m$ indivisible chores to $n$ agents with additive cost functions under the fairness notion of maximin share (MMS). In this work, we propose a notion called $\alpha$-approximate all-but-one maximin share ($\alpha$-AMMS) which is a stronger version of $\alpha$-approximate MMS. An allocation is called $\alpha$-AMMS if $n-1$ agents are guaranteed their MMS values and the remaining agent is guaranteed $\alpha$-approximation of her MMS value. We show that there exist $\alpha$-AMMS allocations, with $\alpha = 9/8$ for three agents; $\alpha = 4/3$ for four agents; and $\alpha = (n+1)^2/4n$ for $n\geq 5$ agents.
BibTeX
@misc{qiu2024guaranteeing,
  author = {Jiawei Qiu and Xiaowei Wu and Cong Zhang and Shengwei Zhou},
  title = {{Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores}},
  year = {2024},
  eprint = {2410.12347},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.12347},
}
Figure