Improved limits for fair division of indivisible items among agents
Improved Impossibility Bounds for Maximin Share Allocations
Computer Science and Game Theory
Summary
Fairly dividing indivisible items among many people is tricky because sometimes no perfect solution exists. This paper shows stronger mathematical limits on how close any allocation can get to a fair benchmark called maximin share (MMS) for both desirable items (goods) and undesirable tasks (chores). The authors demonstrate that as the number of people grows, the shortfall from perfect fairness worsens in a specific, predictable way. They also improve exact bounds for smaller cases with four people and eleven items.
What this means in practice
- •For algorithm designers: Understand theoretical limits on approximating maximin share fairness under additive preferences for goods and chores.
- •For resource allocation engineers: Use improved impossibility bounds to assess when near-fair allocation solutions are feasible or impossible in systems distributing indivisible items.
A theory result. No direct application yet.
Authors
Tomer Ezra, Tamar Garbuz
Abstract
The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall, an exponential improvement on the logarithmic scale of $n$. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.