Metraipolis › archive › dc_3bc0139e626d
Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting — arXiv:2609.05191
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05191
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T22:45:41.966Z
- SHA-256 of the archived text
3fefe46cf34560d3c160f98bb8e9c46d81e0f54c553fc1cb3a9781dc8d024a81- Stable URL of this page
https://metraipolis.com/documento/dc_3bc0139e626d
How to cite
Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting — arXiv:2609.05191 — arXiv (en), https://arxiv.org/abs/2609.05191 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3bc0139e626d (Metraipolis archive dc_3bc0139e626d, sha256 3fefe46cf34560d3c160f98bb8e9c46d81e0f54c553fc1cb3a9781dc8d024a81)
BibTeX
@misc{dc3bc0139e626d,
title = {Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting — arXiv:2609.05191},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05191},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3bc0139e626d; sha256 3fefe46cf34560d3c160f98bb8e9c46d81e0f54c553fc1cb3a9781dc8d024a81},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05191. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Envy-free cake cutting is a central problem in fair division with a striking divide between existence and computation. Classical topology guarantees that envy-free allocations exist, yet finding one efficiently turned out to be much harder, and this problem has resisted decades of work. A well-known result by Aziz and Mackenzie established the existence of a bounded protocol for every $n$, but its query bound is $n^{n^{n^{n^{n^n}}}}$. A tighter analysis by Sokolov subsequently reduced this upper bound to $n^{8n^2(1+o(1))}$, the best known prior to this work. In contrast, the general lower bound, due to Procaccia, is merely $\Omega(n^2)$. We close much of this massive gap with a protocol using at most $n^{O(1)}2^n$ queries. At a high level, our protocol repeatedly allocates some cake without creating envy until the remaining problem involves fewer agents. The main difficulty is to ensure that, when we later put these allocations together, we neither assign any cake twice nor create envy. To overcome this difficulty, we develop a new construction using only polynomially many partial allocations, replacing the $n^{n^{n^n}}$ partial allocations used in previous work. Overall, our protocol gives the first single-exponential query bound for finding a complete envy-free allocation with arbitrary nonatomic, additive valuations.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-07 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.05191 — 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-16T22:29:53.698Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).