arXiv:2610.19690 · v2
PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations
摘要
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 the values $λ$ and $2λ$ for some $λ>0$ common to all agents and has at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, even under the same density restrictions. 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 allocation of indivisible goods on a path that is envy-free up to $c$ goods (EF$c$) is PPAD-complete for additive valuations, and this remains true even for $c=\lfloor m^α\rfloor$ with any fixed rational $0<α<1$, where $m$ is the number of goods. This 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. All these results extend to chores. Our results answer three open questions at once: whether contiguous envy-free cake cutting is PPAD-hard for additive valuations, the complexity of computing contiguous EF1 and EF2 allocations of goods on a path, and the corresponding question for EF1 allocations of chores.
作者备注：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)