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

arXiv: https://arxiv.org/abs/2610.19690 · HTML: https://mlsanity.com/paper/2610.19690/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 25 references that are in the map.
- First posted on arXiv 14 Oct 2026.

## Builds on (most cited first, 16 of 16)

- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [Almost Envy-Free Allocations with Connected Bundles](https://mlsanity.com/paper/1808.09406/) (2018)
- [Contiguous Cake Cutting: Hardness Results and Approximation Algorithms](https://mlsanity.com/paper/1911.05416/) (2019)
- [Fairly Allocating Contiguous Blocks of Indivisible Items](https://mlsanity.com/paper/1707.00345/) (2017)
- [Computational Hardness of the Hylland-Zeckhauser Scheme](https://mlsanity.com/paper/2107.05746/) (2021)
- [Public Goods Games in Directed Networks](https://mlsanity.com/paper/2106.00718/) (2021)
- [PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization](https://mlsanity.com/paper/2312.01237/) (2023)
- [Consensus Halving is PPA-Complete](https://mlsanity.com/paper/1711.04503/) (2017)
- [Consensus-Halving: Does It Ever Get Easier?](https://mlsanity.com/paper/2002.11437/) (2020)
- [Approximation Algorithms for Envy-Free Cake Division with Connected Pieces](https://mlsanity.com/paper/2208.08670/) (2022)
- [How to cut a discrete cake fairly](https://mlsanity.com/paper/2209.01348/) (2022)
- [Envy-Free Cake-Cutting for Four Agents](https://mlsanity.com/paper/2311.02075/) (2023)
- [Contiguous Allocation of Indivisible Items on a Path](https://mlsanity.com/paper/2401.04318/) (2024)
- [Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting](https://mlsanity.com/paper/2409.15713/) (2024)
- [Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations](https://mlsanity.com/paper/2503.05695/) (2025)
- [On Cutting Cakes and Crossing Curves](https://mlsanity.com/paper/2606.13980/) (2026)

## Abstract (arXiv)

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≥1, computing a contiguous EFc 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.