Metraipolis › archive › dc_ec45c818a883

From Cake-Cutting and Necklace-Splitting to Fair Division of Indivisible Items — arXiv:2608.04340

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.04340
License (as archived)
CC0-1.0
Archived
2026-10-31T11:26:19.719Z
SHA-256 of the archived text
1691dae25ea1c75a550dce565dd5009d6fbf38fa6d85ed20a09007bfd645792d
Stable URL of this page
https://metraipolis.com/documento/dc_ec45c818a883

How to cite

From Cake-Cutting and Necklace-Splitting to Fair Division of Indivisible Items — arXiv:2608.04340 — arXiv (en), https://arxiv.org/abs/2608.04340 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ec45c818a883 (Metraipolis archive dc_ec45c818a883, sha256 1691dae25ea1c75a550dce565dd5009d6fbf38fa6d85ed20a09007bfd645792d)
BibTeX
@misc{dcec45c818a883,
  title = {From Cake-Cutting and Necklace-Splitting to Fair Division of Indivisible Items — arXiv:2608.04340},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04340},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ec45c818a883; sha256 1691dae25ea1c75a550dce565dd5009d6fbf38fa6d85ed20a09007bfd645792d},
  year = {2026}
}

Archived text

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

We give an existential transfer framework for converting continuous fair division theorems into guarantees for indivisible items arranged on a path. This allows continuous envy-freeness and consensus results to translate directly into EF$k$-type guarantees for indivisible allocations. Combining this method with connected cake-cutting theorems, we obtain connected allocations satisfying envy-freeness up to one good and one chore for identical valuations and for arbitrary valuations when the number of agents is a prime power. Combining this method with the equicardinal necklace-splitting theorem of Jojić et al., we show that, for any prime-power number $r$ of bundles and $n$ arbitrary valuation functions, there exists an allocation in which every bundle is the union of at most $n$ intervals, and the bundles satisfy consensus up to $n$ goods and $n$ chores. This result is the first EF$k$-type guarantee for consensus fair division with non-additive valuations beyond the halving case. Envy-freeness constraints can be imposed simultaneously at the cost of one additional interval and one additional item in each guarantee. As a consequence, when the number of agents is a prime power, every instance with monotone valuations admits an EF$2$ allocation whose bundle sizes differ by at most two.

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