2026-08-21T18:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27415 2026-08-21T14:42:39Z ddc:004 open_access

Exact Cut Complexity of Equal-Length Proportional Cake Cutting Kawase, Yasushi Sanpui, Mohammad Azharuddin cake cutting fair division cut complexity proportionality envy-freeness We study proportional cake cutting on the interval [0,1] under an equal-length constraint requiring each of the n agents to receive a bundle of length exactly 1/n and to assign value at least 1/n to that bundle. We determine the exact worst-case cut complexity of this problem. The exact value is 2n-2 cuts for every n ≥ 1. The lower bound follows from a simple identical-valuation instance, and the main contribution is the matching upper bound, since the only all-n upper bound previously available for this problem was quadratic. Our upper-bound proof starts from the constrained necklace-splitting theorem of Jojić, Panina, and Živaljević, which gives the required partition into equal-length bundles when the number of bundles is a prime power. The main difficulty is to convert this prime-power input into an exact all-n cut bound while preserving the equal-length constraint. When r is a prime-power divisor of n and s = n/r, our transfer principle constructs r equal-length bundles, builds a balanced fractional assignment of agents to bundles, rounds it by Hall’s theorem to an assignment in which each bundle receives exactly s agents, and recurses inside the bundles without additional overhead beyond the recursive cuts. Using the same constrained necklace-splitting theorem, we also show that 2n-2 cuts suffice for equal-length envy-freeness when n is a prime power. For all n, we give an O(n^1.525) upper bound via a peeling argument based on the Stromquist-Woodall exact-share theorem. The exact all-n envy-free cut complexity remains open. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasushi Kawase and Mohammad Azharuddin Sanpui 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.34 urn:nbn:de:0030-drops-274158 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.34 eng https://creativecommons.org/licenses/by/4.0/legalcode