Metraipolis › archive › dc_ef740b956f76

Maximin share allocations for two types of items — arXiv:2610.19099

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19099
License (as archived)
CC0-1.0
Archived
2026-10-15T14:12:27.568Z
SHA-256 of the archived text
b2c075c5815ca6dfff1babc788778dc72c4d6b4b4da980053d797b3c34fced46
Stable URL of this page
https://metraipolis.com/documento/dc_ef740b956f76

How to cite

Maximin share allocations for two types of items — arXiv:2610.19099 — arXiv (en), https://arxiv.org/abs/2610.19099 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ef740b956f76 (Metraipolis archive dc_ef740b956f76, sha256 b2c075c5815ca6dfff1babc788778dc72c4d6b4b4da980053d797b3c34fced46)
BibTeX
@misc{dcef740b956f76,
  title = {Maximin share allocations for two types of items — arXiv:2610.19099},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19099},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ef740b956f76; sha256 b2c075c5815ca6dfff1babc788778dc72c4d6b4b4da980053d797b3c34fced46},
  year = {2026}
}

Archived text

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

We study the fair allocation of indivisible items among $n$ agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when $n > 2$, one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.

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.19099 — 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-15T13:52:05.399Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).