Metraipolis › archive › dc_bb24f1e6aa33
Asymptotic Subsidies for Envy-Free Allocation — arXiv:2610.10272
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10272
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T11:35:00.370Z
- SHA-256 of the archived text
d5f3e80a75dc04f63810b9eb665911a3cf60bdb1dcc51885e2698ecabba777f1- Stable URL of this page
https://metraipolis.com/documento/dc_bb24f1e6aa33
How to cite
Asymptotic Subsidies for Envy-Free Allocation — arXiv:2610.10272 — arXiv (en), https://arxiv.org/abs/2610.10272 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb24f1e6aa33 (Metraipolis archive dc_bb24f1e6aa33, sha256 d5f3e80a75dc04f63810b9eb665911a3cf60bdb1dcc51885e2698ecabba777f1)
BibTeX
@misc{dcbb24f1e6aa33,
title = {Asymptotic Subsidies for Envy-Free Allocation — arXiv:2610.10272},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10272},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb24f1e6aa33; sha256 d5f3e80a75dc04f63810b9eb665911a3cf60bdb1dcc51885e2698ecabba777f1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10272. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the minimum monetary subsidy required for exact envy-freeness in allocating $m_n$ indivisible goods to $n$ agents. Valuations are additive, item values are i.i.d. from a distribution on $[0,1]$ with density bounded above and away from zero, and all agents value money equally. We consider $n\to\infty$ with $m_n=qn+r_n$, where $q\ge0$ is a fixed integer and $0\le r_n<n$. For the nonzero-remainder case where $1\le r_n<n$, we give a cubic-time algorithm based on a maximum-weight matching of balanced bundles and complementary dual prices. It returns an envy-free outcome for every instance. Under the random model, both its payment and the unrestricted minimum are $n-r_n+o_p(n)$ for $q\ge1$. When $q=0$ and $r_n/n$ converges to a limit below one, the error term improves to $O_p(1)$. For exact divisibility, where $r_n=0$, prior work gives zero subsidy with high probability for $q\ge2$. The square case $q=1$ is exceptional. Its minimum subsidy is $\Theta_p(\log n)$ and, with high probability, equals the optimum over allocations in which every agent receives exactly one good. This restricted optimum can be computed in cubic time using a maximum-weight perfect matching and all-pairs shortest paths. Together, these results provide a unified asymptotic characterization of the minimum subsidy. 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/2610.10272 — 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-10-08T10:34:51.749Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).