Metraipolis › archive › dc_029c503f2b95
Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals — arXiv:2611.04884
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04884
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T12:36:43.003Z
- SHA-256 of the archived text
6c78a808e3ed87608323968ab78e23261ce126ff25f0e11aa5ae6281efa76630- Stable URL of this page
https://metraipolis.com/documento/dc_029c503f2b95
How to cite
Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals — arXiv:2611.04884 — arXiv (en), https://arxiv.org/abs/2611.04884 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_029c503f2b95 (Metraipolis archive dc_029c503f2b95, sha256 6c78a808e3ed87608323968ab78e23261ce126ff25f0e11aa5ae6281efa76630)
BibTeX
@misc{dc029c503f2b95,
title = {Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals — arXiv:2611.04884},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04884},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_029c503f2b95; sha256 6c78a808e3ed87608323968ab78e23261ce126ff25f0e11aa5ae6281efa76630},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04884. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2611.04884 — 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-04T12:28:17.112Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).