Cake-Cutting for 3 Agents Tied to Jordan Curve Problem, Proves Hard

The classic envy-free cake-cutting problem asks how to divide a divisible resource (like a cake) among agents so no one envies another's piece. For continuous valuation functions, an envy-free solution with contiguous pieces always exists, but computing it efficiently has been an open challenge. While the cut-and-choose algorithm handles two agents easily, the problem for four or more agents is known to be hard. The case of three agents remained a long-standing open question.

Now, a new paper on arXiv (June 2026) by Alexandros Hollender, Gilbert Maystre, and Kilian Risse finally settles it: three-agent envy-free cake-cutting with contiguous pieces is intractable. The authors uncover a novel connection to the Jordan curve problem introduced by Adler, Daskalakis, and Demaine (2016). Their main technical contributions are the first lower bounds for that geometric problem—a query lower bound and a proof of hardness for the class UEOPL, a subclass of PPAD that includes notoriously difficult problems like Simple Stochastic Games and the P-matrix Linear Complementarity Problem. This result closes a major gap in computational complexity theory and has implications for algorithmic fair division.