Fair item division improves with extra agents and limited goods
Almost-MMS allocations with small agent redundancy
Computer Science and Game Theory
Summary
Dividing items fairly among people who value them differently is tricky, especially when items can't be split. The authors study a fairness measure called the maximin share (MMS), which tries to guarantee each person a fair fraction of what they could secure if dividing items themselves. They find that adding extra people (agent redundancy) helps ensure almost everyone gets close to their fair share. They also show that when there aren’t too many items compared to people, good fairness without extra agents is possible. This improves understanding of fair division in settings where resources and participants vary.
What this means in practice
- •For resource allocation teams: Design algorithms for dividing indivisible resources fairly when there are slightly more participants than needed, improving fairness guarantees.
- •For supply chain managers: Allocate limited goods among competing agents ensuring near-fair shares when the total number of items is not significantly larger than participants.
A theory result. No direct application yet.
Authors
Uriel Feige, Vadim Grinberg
Abstract
For a fixed $ε\ge 0$, let $ρ_{ε, n}$ be the maximum value of $ρ_n$ such that, in every allocation instance with $m$ indivisible goods and $(1 + ε)n$ agents, there is a subset of $n$ agents with the following property. The allocation instance restricted to only this subset of $n$ agents has an allocation that gives each agent at least $ρ_n$-fraction of her $n$-maximin share (MMS). When $ε> 0$ we refer to $εn$ as the {\em agent redundancy}. The case $ε= 0$ is the standard setting without agent redundancy, and we use $ρ_{0,n}$ and $ρ_n$ interchangeably. For allocation instances with additive valuations, % agents, it is known that $\frac{7}{9} \le ρ_n < 1-Ω(\frac{1}{\log^2 n})$ for every $n \ge 2$ (with stronger lower bounds for small $n$). It is an open question whether $ρ_n$ tends to~1 as $n$ grows. We show that with agent redundancy, the answer to this question is positive. That is, for every $ε> 0$, $ρ_{ε, n}$ tends to~1 as $n$ grows. A straightforward corollary of this result is that for every $c > 0$, if the number of items satisfies $m \le (2 - c)n$, then the answer is positive also for $ρ_n$ (with no agent redundancy). Adapting our techniques to a related setting, we also improve a recent result of Ezra and Garbuz, and show that without agent redundancy, there always exists an allocation that gives $n - O(\log^2 n)$ agents their full MMS.