Exact Envy-Free Cake Cutting with Polynomial Expected Queries

Simon Mackenzie, Mashbat Suzuki

Oct 20, 2026arXiv:2610.28535v1

cs.GTcs.CC

Scorecard· 16/16

8.5/10 impact

First polynomial-query algorithm for exact complete envy-free cake cutting, resolving a central open question (in expectation) with a thorough, carefully verified construction; tempered by n^30, randomisation, and verification risk.

Abstract

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^n$ . A large gap remains between this deterministic upper bound and Procaccia's general lower bound of $Ω (n^{2})$ . 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 $\widetilde{O}(n^{30})$ . The expectation is taken solely over the protocol's random choices, with no distributional assumptions on preferences.

AI Impact Assessments

(1 model)

Core Contribution

The paper gives a randomised Robertson-Webb protocol that returns a complete, exactly envy-free division of a cake for any number of agents. It uses Õ(n^30) expected queries for every fixed profile of hungry, additive, nonatomic valuations, with no distributional assumptions on preferences. The only randomness comes from independent uniform draws. This is the first polynomial query bound of any kind for exact, complete envy-free cake cutting. Earlier bounds went from Aziz-Mackenzie's tower of six n's, to Sokolov's n^{O(n²)}, to Ye and Bai's n^{O(1)}·2^n. Procaccia's Ω(n²) lower bound leaves a large remaining gap, but polynomial versus exponential was described as a central open question.

Technically, the paper keeps the Brams-Taylor/Aziz-Mackenzie/Ye-Bai completion framework: saved snapshots, shrinking the residue, permitted-graph reassignments, and a group that stops once it dominates the residue. It replaces the exponential Core/SubCore machinery with three local randomised procedures: Repair, Shrink and Snapshot. The key new ingredient is whole-bundle repair that pays envious agents with actual cake. It builds on Halpern-Shah subsidies and the cake-payment idea of Aziz-Lu-Mackenzie-Suzuki. Because a cake piece is valued differently by different agents, the payments are made exact for the recipient and bounded for every observer. The tools for this are:

reserve cells chosen at random;

isolation-lemma-style random additions that separate assignment optima;

circular crops with a fresh uniform start;

an insertion-deletion sampling bound on interpolation error at adaptively chosen cuts.

Disagreement-proportional margins keep the bound independent of how close valuations are.

Methodological Rigor

The paper is a long, fully formalised proof with explicit constants. It covers measure-theoretic conventions, conditional-history success probabilities, retry lemmas, a confidence-capped version, and an operation-count bound. Several design choices are careful:

Every output is verified exactly, so correctness never depends on probability.

Failed attempts still count their queries.

Probabilistic claims are phrased conditional on arbitrary histories.

Remark C.7 explicitly flags the subtlety that the sampling bound is joint rather than conditional on the observed table.

The proofs read as internally coherent: the permitted-graph lemma, domination argument, credit affordability via longest paths, and assignment-gap separation all hang together. The 30th-power exponent is clearly an artefact of loose parameter choices (s = 2^20·n, with s^24 queries per attempt). It makes the result a feasibility proof, not a practical bound.

Risks:

The paper is very long and intricate, with many interacting parameters, so a subtle error is plausible and hard to detect without careful community vetting.

The AI-methodology statement says the proofs were substantially developed with AI systems. That raises both the need for independent verification and some uncertainty about correctness, though the paper reports that checks were used.

The model assumes exact real-valued queries and uniform real draws at unit cost. This is standard for Robertson-Webb but means the result says nothing about bit complexity.

Potential Impact

For fair-division theory this is a landmark result if correct. It resolves, at least in expectation and with randomisation, the long-standing question of whether envy-free cake cutting is polynomial-query. This likely sets up a new research agenda:

derandomisation, which the authors flag as open and which would answer the original deterministic question;

reducing the exponent toward n² or n³;

coin-flip-only randomness;

bit complexity;

extensions to chores, mixed goods and general (non-hungry) cases.

The cake-payment technique with controlled observer error, and the sampling-error proposition for adaptive cuts, are reusable primitives. Practical impact is minimal: n^30 is not deployable, and the protocol is extremely complex. The conceptual message, that polynomial-time fair division in the query model is possible with randomness, is the main contribution. Adjacent communities (computational social choice, algorithmic game theory, query-complexity theory) will take notice, but applications beyond theory are not near.

Timeliness & Relevance

The result directly follows a rapid sequence of improvements (Aziz-Mackenzie, Sokolov, Ye-Bai) and addresses the best-known open problem in cake-cutting complexity. It uses Ye and Bai's framework, so timing is ideal. It also reflects an emerging trend of AI-assisted proof development, which draws extra attention and scrutiny.

Strengths

It settles a central open question, at least with randomisation, going from exponential to polynomial.

The guarantees are strong: exact envy-freeness, complete allocation, termination with probability one, a bound for every valuation profile, a confidence-capped variant, and a polynomial computation bound.

The decomposition into reusable local procedures is clean.

The paper is honest about its limitations and open problems, and positions itself carefully against Chèze, Mehra-Psomas, the free-disposal protocols, and the randomised lower bounds.

Limitations

The exponent of 30 is large and the construction is baroque.

The protocol is randomised, so deterministic polynomial bounds remain open, which was the original question.

It assumes unit-cost exact real arithmetic and uniform real draws.

It assumes hungriness, with the relaxation only asserted in a remark.

It has no lower-bound progress or practical evaluation.

The paper is hard to verify, which is a risk for acceptance.

Overall

If correct, this is a major theoretical advance in fair division and likely to be widely cited and built on. Its practical reach is minimal, and the verification burden is high.

```json

{

"score": 8.5,

"score_reason": "First polynomial-query algorithm for exact complete envy-free cake cutting, resolving a central open question (in expectation) with a thorough, carefully verified construction; tempered by n^30, randomisation, and verification risk.",

"significance": 8.5,

"significance_reason": "Moves the best known bound from n^{O(1)}2^n to polynomial in expectation, reshaping the open-problem landscape and opening derandomisation and exponent-reduction directions.",

"rigor": 8.0,

"rigor_reason": "Fully formal proofs with conditional-history probability handling, exact output verification, explicit constants, and flagged subtleties (Remark C.7), though sheer complexity leaves some residual risk of undetected error.",

"novelty": 8.5,

"novelty_reason": "Replaces exponential Core/SubCore machinery with randomised cake-payment repair, isolation-style separation, and adaptive-cut sampling bounds, a combination experts would not have predicted.",

"clarity": 6.5,

"clarity_reason": "Good roadmap, figures, and examples for an extremely intricate construction, but the paper is very long with dense parameter bookkeeping that requires heavy rereading.",

"difficulty": 9.0,

"difficulty_reason": "Requires deep expertise in cake-cutting protocols, probabilistic analysis with adaptive cuts, isolation lemmas, and subsidy/payment arguments.",

"surprisingness": 7.5,

"surprisingness_reason": "Polynomial expected queries for exact envy-free division was widely open and many expected exponential barriers, so randomisation sufficing is a notable surprise.",

"reproducibility": 7.0,

"reproducibility_reason": "Algorithm, parameters, and proofs are specified in full detail and checkable, but no code is given and implementation would be laborious.",

"translational_potential": 2.0,

"translational_potential_reason": "n^30 queries and a very complex protocol make direct deployment infeasible; value is conceptual.",

"evidence_strength": 8.0,

"evidence_strength_reason": "Complete proofs for all stated guarantees including termination, exact envy-freeness, expected query and operation bounds, and a confidence-capped variant, with exact checks on outputs.",

"generalisability": 7.0,

"generalisability_reason": "Holds for every additive, nonatomic valuation profile and any n, with hungriness relaxable by remark, though restricted to the Robertson-Webb exact-real model.",

"interdisciplinarity": 3.5,

"interdisciplinarity_reason": "Mainly relevant to fair division, algorithmic game theory, and query complexity, with some links to randomised algorithms and optimisation.",

"refutation_value": 2.0,

"refutation_value_reason": "Does not refute a specific claim but undermines the presumption that exponential bounds were needed.",

"replication_value": 1.0,

"replication_value_reason": "Presents new results rather than corroborating prior findings.",

"resource_intensity": 2.0,

"resource_intensity_reason": "Pure theory requiring no compute; the cost is expert time and the intricate verification effort.",

"foundationality": 7.0,

"foundationality_reason": "Repair, Shrink, Snapshot, cake payments with bounded observer error, and the adaptive-cut sampling proposition are reusable primitives for follow-up fair-division work."

}

```

Rating:8.5/ 10

Significance 8.5Rigor 8Novelty 8.5Clarity 6.5

Generated Oct 21, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

8.5/10 impact