# Exact Cut Complexity of Equal-Length Proportional Cake Cutting

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

## Key facts

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

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

- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Fair Division Under Cardinality Constraints](https://mlsanity.com/paper/1804.09521/) (2018)
- [A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents](https://mlsanity.com/paper/1604.03655/) (2016)
- [Fair Division with Allocator's Preference](https://mlsanity.com/paper/2310.03475/) (2023)
- [Fair Division with Market Values](https://mlsanity.com/paper/2410.23137/) (2024)
- [Cake-Cutting with Different Entitlements: How Many Cuts are Needed?](https://mlsanity.com/paper/1803.05470/) (2018)
- [Disproportionate division](https://mlsanity.com/paper/1909.07141/) (2019)
- [Consensus Division in an Arbitrary Ratio](https://mlsanity.com/paper/2202.06949/) (2022)
- [Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions](https://mlsanity.com/paper/2506.21727/) (2025)
- [Fair Division Among Couples and Small Groups](https://mlsanity.com/paper/2508.13432/) (2025)
- [Fair and Efficient Balanced Allocation for Indivisible Goods](https://mlsanity.com/paper/2603.05956/) (2026)
- [No, Cake Cutting Really is a Piece of Cake](https://mlsanity.com/paper/2606.07238/) (2026)

## Abstract (arXiv)

We study proportional cake cutting under an equal-length constraint, where each of n agents must receive a bundle of length exactly 1/n that is worth at least 1/n to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely 2n-2 for every n. This improves on the previously known quadratic upper bound. The proof combines the constrained necklace-splitting theorem with a recursive assignment argument based on Hall's theorem. The same bound extends to the stronger requirement of envy-freeness when n is a prime power, and an O(n1.525) upper bound holds for arbitrary n. We then ask whether such allocations can be computed. We first show that no deterministic protocol in the Robertson--Webb model terminates after finitely many queries on every instance and always returns an exact equal-length proportional allocation, even for two agents with identical valuations. For every varepsilon>0, however, O(n2/varepsilon) queries suffice to produce an allocation in which every agent receives a bundle of length exactly 1/n and value at least 1/n-varepsilon, again using at most 2n-2 cuts. Finally, we augment the Robertson--Webb model with two-knife queries. We show that recursive balanced halving attains the optimal bound of 2n-2 cuts when n is a power of two. For arbitrary n, we give a procedure using O(nlog n) cuts.