Metraipolis › archive › dc_2b04acdac4e1

Maximin Share Allocations Beyond Weakly Lexicographic Valuations — arXiv:2610.00159

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.00159
License (as archived)
CC0-1.0
Archived
2026-10-06T14:08:02.811Z
SHA-256 of the archived text
b823756162bd35bcfb56292071252068ebaa84281663bbf6a3fdc77a26efdb69
Stable URL of this page
https://metraipolis.com/documento/dc_2b04acdac4e1

How to cite

Maximin Share Allocations Beyond Weakly Lexicographic Valuations — arXiv:2610.00159 — arXiv (en), https://arxiv.org/abs/2610.00159 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2b04acdac4e1 (Metraipolis archive dc_2b04acdac4e1, sha256 b823756162bd35bcfb56292071252068ebaa84281663bbf6a3fdc77a26efdb69)
BibTeX
@misc{dc2b04acdac4e1,
  title = {Maximin Share Allocations Beyond Weakly Lexicographic Valuations — arXiv:2610.00159},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.00159},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2b04acdac4e1; sha256 b823756162bd35bcfb56292071252068ebaa84281663bbf6a3fdc77a26efdb69},
  year = {2026}
}

Archived text

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

We study the fair division of indivisible goods among agents with nonnegative additive valuations. An agent's maximin share (MMS) is the value she can guarantee by partitioning the goods into as many bundles as there are agents and receiving a least-valued bundle. We prove the existence of exact MMS allocations for a valuation domain that generalizes several few-valued domains as well as weakly lexicographic valuations. For each agent, the lower-valued goods, after a positive rescaling, may take values in $\{0,1,d,d+1\}$, $\{0,1,2,2e\}$, or $\{0,1,2,3,4\}$, where $d,e\ge 2$ are integers. Above these goods, the valuation may contain arbitrarily many value classes, subject to the condition that a single good in each class is worth at least the total value of all strictly lower-valued goods. The value classes, scaling factors, and parameters may vary across agents. We give an algorithm that computes an MMS allocation in $O(nm\log^2(2+m))$ time, where $n$ is the number of agents and $m$ is the number of goods.

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