PaperfootJoin free
arXiv

Fair cake cutting is possible in polynomial expected queries

The authors proved that a randomized protocol can divide a resource completely and without envy in a polynomial expected number of queries.

Paper by Simon Mackenzie, Mashbat Suzuki
Preprint: method

Edited by Boris Djordjevic · Paperfoot

Paper

In a theory preprint, the authors proved that a randomized protocol can divide a resource without envy using a polynomial expected number of queries. Envy-free cake cutting asks how to divide a shared resource so that no agent prefers another agent's share. Earlier deterministic methods required queries that grew exponentially with the number of agents. The authors designed a protocol that uses independent, uniformly sampled points from the cake as its source of randomness. For all agents with nonnegative, additive, and nonatomic valuations, the protocol provides three guarantees. It terminates with probability one. Every allocation it returns is complete and exactly envy-free. Its expected number of Robertson-Webb preference queries is bounded by the number of agents raised to the thirtieth power. The expectation depends solely on the protocol's random choices, with no distributional assumptions on preferences.

Why it matters

The proof shows that an expected polynomial query bound is possible for envy-free cake cutting, where deterministic methods had required an exponential number of queries. It proves that a randomized protocol can achieve an exact, envy-free division without assuming any probability distribution over agent preferences.

Caveats

The theoretical proof assumes that agent valuations are nonnegative, additive, and nonatomic, and it guarantees an expected query bound rather than a deterministic one. Additionally, the paper is a preprint that has not yet undergone peer review.

In this paper

envy-free cake cutting

Methods
Repair (this paper)Shrink (this paper)Snapshot (this paper)

Results

Repair, expected number of Robertson-Webb queries, for every profile of n agents with nonnegative, additive, nonatomic valuations: O(n30)

(3) Its expected number of Robertson-Webb queries is O(n30).

Abstract

Repair, probability of returning, conditional on every history at its start: above 0.98

Conditional on every history at its start, it returns with probability above 0.98.

Theorem 3.1 (Partial allocation and whole-bundle repair).

Snapshot, success probability, conditional on any history at its start: at least 1/(64k)

Each attempt uses O(Ns^{24}) queries and succeeds with probability at least 1/(64k), conditional on any history at its start.

Theorem 3.3 (A margin relative to the residue).

Snapshot, expected query cost: O(Nks^{24})

Repeating rejected attempts gives expected query cost O(Nks^{24}).

Theorem 3.3 (A margin relative to the residue).

What it shows

A polynomial expected query bound is possible for envy-free cake cutting with independent, uniformly sampled points from the cake as the source of randomness.

We show that a polynomial expected query bound is possible.

Abstract

One trial of Repair either rejects without allocating cake or returns an envy-free allocation with additions using at most a quarter of the buffer in every participant's valuation.

Under (3.1), one trial of \operatorname{Repair} either rejects without allocating cake, or returns a permutation \pi and disjoint finite-union additions Y_{i}\subseteq B.

Theorem 3.1 (Partial allocation and whole-bundle repair).

Snapshot terminates almost surely and returns either a complete envy-free allocation or an envy-free partial allocation with an advantage relative to the residue.

For k≥ 1 agents and a finite union U with recorded endpoint values, the procedure \operatorname{Snapshot} terminates almost surely and returns either a complete envy-free allocation, or an envy-free partial allocation X with residue T and distinct agents a,b such that

Theorem 3.3 (A margin relative to the residue).

Repair, Shrink and Snapshot yield a protocol that completely and envy-freely allocates any finite union with recorded endpoint values among the N agents.

Repair, Shrink and Snapshot yield a protocol that completely and envy-freely allocates any finite union C with recorded endpoint values among the N agents.

Theorem 4.1 (Completion).

Quoted word for word from the full text on arXiv.

The paper

Exact Envy-Free Cake Cutting with Polynomial Expected Queries

Simon Mackenzie, Mashbat Suzuki

arXiv, Oct 20, 2026, Open access, CC BY, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.28535

arXiv:2610.28535v1 in cs.GT, also cs.CC

AbstractPDFHTML

Comments: 56 pages, 4 figures. Preliminary version

Cite as BibTeX
@misc{mackenzie2026exact,
  title = {Exact Envy-Free Cake Cutting with Polynomial Expected Queries},
  author = {Mackenzie, Simon and Suzuki, Mashbat},
  year = {2026},
  eprint = {2610.28535},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  doi = {10.48550/arxiv.2610.28535},
  url = {https://arxiv.org/abs/2610.28535}
}

More in Theory