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

Abstract: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.

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)

Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA)

arXiv:2610.19690 [cs.GT]

(or arXiv:2610.19690v1 [cs.GT] for this version)

https://doi.org/10.48550/arXiv.2610.19690 arXiv-issued DOI via DataCite (pending registration)