PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations
Cake cutting asks how to divide a resource so that every agent values their own share at least as much as any other's, but when each agent must receive a single connected piece the computational complexity has been stubbornly open. This paper resolves the question by proving that computing an $\varepsilon$-envy-free contiguous allocation is PPAD-complete for normalized rational piecewise-constant additive valuations, even when densities take only two values and have at most six breakpoints. It also settles that finding contiguous EF$c$ allocations of indivisible goods on a path is PPAD-complete for any fixed $c\ge1$, using a novel pricing gadget that forces nearly equal prices regardless of how pieces are permuted among agents.
The paper makes a significant and timely contribution by closing a long-standing open problem. The central insight—a price-based encoding that decouples the envy constraints from the assignment permutation—is elegant and seems likely to influence future fair-division hardness results. The authors also deserve credit for pushing the hardness down to extremely restricted densities and for handling both cake cutting and indivisible goods on a path in one unified attack.
The pricing lemma (Lemma 7) is the linchpin and it holds up cleanly: given a single-cycle permutation $\pi$ and an envy-like condition $q_{\sigma(i)} \ge \max\{q_i,q_{\pi(i)}\}-\eta$, the price spread is bounded by $N\eta$. This absorbs the arbitrary piece-to-agent assignment and lets the reduction work for any bijection $\sigma$. The construction is also admirably tight in its restrictions—hardness already applies when every density takes only two common values and is piecewise constant with at most six breakpoints, and the indivisible-goods reduction uses only binary valuations in which each good is valued by exactly one agent.
The main limitation is the large gap between the hardness scale and positive results: the hard instances need $\varepsilon=\Theta(n^{-4})$, whereas polynomial-time algorithms are known for $(1/4+o(1))$-envy-freeness, leaving the entire intermediate regime open. The reduction also suffers from a quadratic blowup in the number of agents ($N=32(s+1)^2$), which means the constructed instances are large and the constants in the gadget are chosen somewhat magically; this does not invalidate the theorem, but it makes the construction feel brittle and harder to digest. Finally, for indivisible goods the membership argument essentially delegates to an existing existence proof by Igarashi, with the paper noting only that the steps can be carried out in PPAD rather than providing a self-contained verification.
The related-work discussion is accurate and fair. The authors correctly distinguish their setting from PPAD-hardness for non-additive or non-contiguous valuations [8, 15], from NP-hardness of the fixed-order decision problem [13], and from the tractable cases of a constant number of agents or four monotone agents. They explicitly note the results of Barman and Kulkarni [2] and Goldberg, Hollender, and Suksompong [13] that their hardness does not contradict, and they honestly flag that five monotone agents under general valuations remains open.
No code, data, or pseudocode is provided, and the reduction is dense enough that an independent reproduction would be laborious. The paper states that solutions can be verified in polynomial time because rational cuts can be rounded to multiples of $1/\lceil 8M/\varepsilon\rceil$, but actually instantiating the threshold-game-to-cake mapping requires carefully tracking the cyclic order $\pi$, the set families $S_v$, the bonus intervals of lengths $2$, $5/2$, and $3$, and the normalization constants. The authors acknowledge that an initial version of the reduction was obtained with ChatGPT and then verified and corrected by the authors, which may raise eyebrows about how non-obvious the construction is, though they take full responsibility for the final proofs.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.