# Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2019.

## Built on by (most cited first, 4 of 4)

- [Reforming an Envy-Free Matching](https://mlsanity.com/paper/2207.02641/) (2022)
- [Resource Allocation under the Latin Square Constraint](https://mlsanity.com/paper/2501.06506/) (2025)
- [The Complexity of Envy-Free Graph Cutting](https://mlsanity.com/paper/2312.07043/) (2023)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.