Metraipolis › archive › dc_dd1efb10dae8

Fair Share Allocations for Almost All Agents — arXiv:2609.33234

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33234
License (as archived)
CC0-1.0
Archived
2026-10-07T22:13:59.996Z
SHA-256 of the archived text
f2704118043aaee85019e3835ef90a7af08edd2c970913a5bcbeab86a0e29374
Stable URL of this page
https://metraipolis.com/documento/dc_dd1efb10dae8

How to cite

Fair Share Allocations for Almost All Agents — arXiv:2609.33234 — arXiv (en), https://arxiv.org/abs/2609.33234 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dd1efb10dae8 (Metraipolis archive dc_dd1efb10dae8, sha256 f2704118043aaee85019e3835ef90a7af08edd2c970913a5bcbeab86a0e29374)
BibTeX
@misc{dcdd1efb10dae8,
  title = {Fair Share Allocations for Almost All Agents — arXiv:2609.33234},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33234},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dd1efb10dae8; sha256 f2704118043aaee85019e3835ef90a7af08edd2c970913a5bcbeab86a0e29374},
  year = {2026}
}

Archived text

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

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-29 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.33234 — 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-07T21:55:21.817Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).