Metraipolis › archive › dc_8e5ee697107f

PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations — arXiv:2610.19690

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.19690
License (as archived)
CC0-1.0
Archived
2026-10-15T13:50:44.334Z
SHA-256 of the archived text
d2fd976d22dd055db133ec4d6bd256443b9537a98e7c5693719ad6e67b5b26f4
Stable URL of this page
https://metraipolis.com/documento/dc_8e5ee697107f

How to cite

PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations — arXiv:2610.19690 — arXiv (en), https://arxiv.org/abs/2610.19690 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8e5ee697107f (Metraipolis archive dc_8e5ee697107f, sha256 d2fd976d22dd055db133ec4d6bd256443b9537a98e7c5693719ad6e67b5b26f4)
BibTeX
@misc{dc8e5ee697107f,
  title = {PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations — arXiv:2610.19690},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.19690},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8e5ee697107f; sha256 d2fd976d22dd055db133ec4d6bd256443b9537a98e7c5693719ad6e67b5b26f4},
  year = {2026}
}

Archived text

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

We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness holds even when $\varepsilon$ is given in unary, and even when every density takes only two values, which are the same for all agents, and is piecewise constant with at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, and the hardness holds under the same restrictions on the densities. Our key ingredient is to assign prices to the pieces so that, in every approximately envy-free allocation, all prices are nearly equal, regardless of how the pieces are assigned to the agents. We further show that, for every fixed integer $c\ge1$, computing a contiguous EF$c$ allocation of indivisible goods on a path is PPAD-complete for additive valuations, and the hardness holds even for binary valuations in which each good is valued by exactly one agent and all agents value the same number of goods.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA).
Pagina del lavoro: https://arxiv.org/abs/2610.19690 — 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:48:35.457Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).