PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations

cs.GT, cs.AI, cs.MA

Submitted: 2026-10-14

Updated: 2026-10-14

Comments: We prove that computing a contiguous envy-free cake division is PPAD-complete for additive valuations, and that computing a contiguous EF$c$ allocation of goods on a path is PPAD-complete for every fixed $c \geq 1$, resolving open questions of Goldberg, Hollender and Suksompong (JAIR 2020) and Bilò et al.\ (ITCS 2019)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Related papers

• Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
• In-Context Credit Assignment via the Core
• Optimal Regret for Online Market Making with Limit Order Book
• Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
• Enhancing Affine Maximizer Auctions with Correlation-Aware Payment
• LLM Bidders Preserve the Mechanism-Level Orderings of Human Bidders