Nearly Settling the Complexity of Connected $\varepsilon$-Envy-Free Cake Cutting
Simon Mackenzie, Mashbat Suzuki
cs.GT
Nov 16, 2026 · v2
cs.CC
TL;DR
A Lean 4 development using Mathlib verifies the paper's query-complexity theorems (upper bounds for four and five agents, lower bound for seven or more).
Abstract
Envy-free cake cutting has been one of the central problems in fair division. In cake cutting, agents' preferences over the cake are accessed through Robertson–Webb (RW) queries. For three or more agents, no algorithm that makes finitely many RW queries can always find a contiguous, exactly envy-free allocation. For contiguous $\varepsilon$-envy-free allocations, however, Hollender and Rubinstein (JACM, 2025) showed that $\poly(\log(1/\varepsilon))$ RW queries suffice for four agents, leaving open whether such a bound is possible for five or more agents. In this paper, we establish a striking change in query complexity: $\poly(\log(1/\varepsilon))$ RW queries suffice for up to five agents, whereas $(1/\varepsilon)^{Ω(1)}$ queries are necessary for seven or more agents, even when valuations are additive. Thus, we resolve the five-agent case and, more broadly, determine whether polylogarithmic query complexity is possible for every number of agents except six. We also explore the computational complexity of finding contiguous $\varepsilon$-envy-free allocations. When monotone Lipschitz valuations are given by polynomial-time evaluation procedures (e.g., arithmetic circuits and efficiently computable Turing machines), we show that an $\varepsilon$-envy-free division can be computed in polynomial time for five agents. In contrast, even for additive valuations, finding an $\varepsilon$-envy-free division is UEOPL-hard for every fixed number of agents $n\ge7$ and PPAD-complete for every fixed $n\ge13$.
Problem
For contiguous ε-envy-free cake cutting under Robertson–Webb queries, poly(log(1/ε)) query bounds were known only for up to four agents. Whether such bounds hold for five or more agents, and what the computational complexity of the problem is, remained open.
Approach
A geometric construction places two adjacent pieces that two distinct agents can receive without envy. A planar search then balances the three remaining agents, implemented either with quantile queries or by rational interpolation of polynomial-time interval values. Lower bounds encode the endpoint of a hidden path in every approximately envy-free allocation, and polynomial-time reductions establish computational hardness. AI systems (Codex, Claude) developed the proofs and wrote a Lean 4/Mathlib formalisation of the query theorems.
Results
Five agents admit O(log²(1/ε)) RW queries, and a polynomial-time algorithm exists for monotone Lipschitz valuations. Seven or more agents require Ω(ε^{-1/3}) queries, and the computational problem is UEOPL-hard for n≥7 and PPAD-complete for n≥13. The query theorems are verified in Lean using only standard axioms; the computational statements are not part of the Lean development.
| Agents n | Upper bound | Lower bound | Regime |
|---|
| 3 | O(log(1/ε)) | Ω(log(1/ε)) | Logarithmic, tight |
| 4 | O(log(1/ε)) | Ω(log(1/ε)) | Logarithmic, tight |
| 5 | O(log²(1/ε)) | Ω(log(1/ε)) | Polylogarithmic |
| 6 | O(1/ε) | Ω(log(1/ε)) | Open |
| n≥7 | O(1/ε) | Ω(ε^{-1/3}) | Polynomial |
Query complexity of connected ε-envy-free cake cutting by number of agents