arXiv · Oct 20, 2026
Exact Envy-Free Cake Cutting with Polynomial Expected Queries
By Simon Mackenzie, Mashbat Suzuki
Envy-free cake cutting asks how to divide a resource so that no agent prefers another agent's share. Finding such a division with few queries about preferences has been a longstanding challenge. Aziz and Mackenzie gave the first query bound depending only on the number n of agents: a tower of six n's. Subsequent improvements culminated in Ye and Bai's single-exponential bound of n^(O(1))2ⁿ. A large gap remains between this deterministic upper bound and Procaccia's general lower bound of Ω(n²). Whether polynomially many queries suffice is a central open question in fair division. We show that a polynomial expected query bound is possible. Our randomised protocol uses only independent, uniformly sampled points from the cake as its source of randomness. For every profile of n agents with nonnegative, additive, nonatomic valuations, the protocol has the following guarantees: (1) It terminates with probability one. (2) Every allocation it returns is complete and exactly envy-free. (3) Its expected number of Robertson-Webb queries is O(n³⁰). The expectation is taken solely over the protocol's random choices, with no distributional assumptions on preferences.