Metraipolis › archive › dc_72cf7e5d0b8a

Almost-MMS allocations with small agent redundancy — arXiv:2611.05360

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05360
License (as archived)
CC0-1.0
Archived
2026-11-04T21:46:26.587Z
SHA-256 of the archived text
03181f718322a7e1fc546383e469320be51d78c26d17b461dbcec9f2bde11393
Stable URL of this page
https://metraipolis.com/documento/dc_72cf7e5d0b8a

How to cite

Almost-MMS allocations with small agent redundancy — arXiv:2611.05360 — arXiv (en), https://arxiv.org/abs/2611.05360 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_72cf7e5d0b8a (Metraipolis archive dc_72cf7e5d0b8a, sha256 03181f718322a7e1fc546383e469320be51d78c26d17b461dbcec9f2bde11393)
BibTeX
@misc{dc72cf7e5d0b8a,
  title = {Almost-MMS allocations with small agent redundancy — arXiv:2611.05360},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05360},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_72cf7e5d0b8a; sha256 03181f718322a7e1fc546383e469320be51d78c26d17b461dbcec9f2bde11393},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05360. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For a fixed $\epsilon \ge 0$, let $\rho_{\epsilon, n}$ be the maximum value of $\rho_n$ such that, in every allocation instance with $m$ indivisible goods and $(1 + \epsilon)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 $\rho_n$-fraction of her $n$-maximin share (MMS). When $\epsilon > 0$ we refer to $\epsilon n$ as the {\em agent redundancy}. The case $\epsilon = 0$ is the standard setting without agent redundancy, and we use $\rho_{0,n}$ and $\rho_n$ interchangeably. For allocation instances with additive valuations, % agents, it is known that $\frac{7}{9} \le \rho_n < 1-\Omega(\frac{1}{\log^2 n})$ for every $n \ge 2$ (with stronger lower bounds for small $n$). It is an open question whether $\rho_n$ tends to~1 as $n$ grows. We show that with agent redundancy, the answer to this question is positive. That is, for every $\epsilon> 0$, $\rho_{\epsilon, 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 $\rho_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.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.05360 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:37:19.383Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).