Exact Cut Complexity of Equal-Length Proportional Cake Cutting

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.