Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting

Qilin Ye; Yannan Bai

Source-linked AI summary

Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting

Qilin Ye, Yannan Bai

arXiv:2609.05191v1Sep 4, 2026cs.GT

TL;DR

Efficiently finding envy-free cake allocations remains difficult despite their guaranteed existence and prior bounded protocols with enormous query complexity. This paper uses recursive allocations, pruning, and polynomially many partial allocations to obtain a complete envy-free allocation with a single-exponential query bound for arbitrary nonatomic additive valuations.

Problem
Envy-free allocations exist, but finding one through bounded Robertson–Webb queries has remained difficult, with prior general bounds far above the Ω(n^2) lower bound.
Method
The protocol recursively allocates envy-free pieces, reduces the active-agent set, and uses polynomially many pruned partial allocations to prevent conflicting assignments.
Results
Theorem 1.1 gives a deterministic bounded protocol using at most n^O(1)2^n queries for complete envy-free allocation under nonnegative, additive, nonatomic valuations.
Takeaways & Limitations
The construction achieves the first single-exponential query bound for complete envy-free allocation with arbitrary nonatomic additive valuations.
Takeaways & Limitations
The remaining exponential cost comes from Core and SubCore calls involving Θ(n) agents, and subexponential or polynomial bounds remain open.

Abstract

from arXiv · show

Envy-free cake cutting is a central problem in fair division with a striking divide between existence and computation. Classical topology guarantees that envy-free allocations exist, yet finding one efficiently turned out to be much harder, and this problem has resisted decades of work. A well-known result by Aziz and Mackenzie established the existence of a bounded protocol for every $n$, but its query bound is $n^{n^{n^{n^{n^n}}}}$. A tighter analysis by Sokolov subsequently reduced this upper bound to $n^{8n^2(1+o(1))}$, the best known prior to this work. In contrast, the general lower bound, due to Procaccia, is merely $Ω(n^2)$. We close much of this massive gap with a protocol using at most $n^{O(1)}2^n$ queries. At a high level, our protocol repeatedly allocates some cake without creating envy until the remaining problem involves fewer agents. The main difficulty is to ensure that, when we later put these allocations together, we neither assign any cake twice nor create envy. To overcome this difficulty, we develop a new construction using only polynomially many partial allocations, replacing the $n^{n^{n^n}}$ partial allocations used in previous work. Overall, our protocol gives the first single-exponential query bound for finding a complete envy-free allocation with arbitrary nonatomic, additive valuations.

1 Introduction

Envy-free allocations are easy to prove existent but difficult to compute through bounded Robertson–Webb protocols. This paper replaces prior enormous constructions with polynomially many partial allocations and obtains a single-exponential query bound.

Motivation: Envy-free allocations exist, but Robertson–Webb protocols must access valuations through evaluation and cut queries rather than reading them entirely.The computational challenge is therefore query complexity, not existence alone.
Prior bounds: Procaccia’s lower bound is Ω(n^2), while earlier bounded-protocol upper bounds were substantially larger.Aziz and Mackenzie established boundedness, and Sokolov later sharpened their analysis to n^8n^2(1+o(1)).
Main result: The paper proves a bounded protocol using at most n^O(1)2^n Robertson–Webb queries for every collection of nonnegative, additive, nonatomic valuations.This is stated as the main theorem for every n≥1.
Protocol idea: The protocol recursively allocates cake without envy, removes a dominated group of agents, and recurses on the residue with fewer active agents.The omitted agents retain their pieces while the remaining group divides the residue.
Technical novelty: Polynomially many partial allocations replace the enormous family used previously, while pruning prevents conflicting assignments and avoids assigning any cake twice.The construction reserves safe allocations so different agents’ needs can be met by distinct allocations.
Query analysis: 2^O(n) queries arise from tracing the protocol’s recurrence after combining partial allocations adds only polynomial overhead.The remaining exponential cost is concentrated in Core and SubCore calls involving Θ(n) agents.

2 Preliminaries

The paper models cake as an interval with additive, nonatomic valuations and defines allocations through disjoint pieces and an unallocated residue. Robertson–Webb protocols interact with these valuations through cut and evaluation operations, while domination enables safe recursive composition.

Model: The cake is modeled as [0,1], agents have nonnegative additive nonatomic valuations, and pieces may be finite unions of intervals.Additivity applies to disjoint pieces, and nonatomicity permits cutting intervals to any intermediate value.
Allocations: An allocation assigns pairwise disjoint pieces to agents, with the residue consisting of the unallocated part of the subcake.An allocation is complete when the residue is empty up to cut endpoints.
Fairness: An allocation is envy-free when every agent values her own piece at least as much as every other agent’s piece.Formally, V_i(X_i) ≥ V_i(X_j) for every pair of agents.
Query model: Robertson–Webb protocols access valuations through cut and evaluation queries, and boundedness requires a query bound depending only on the number of agents.The cut operation returns a point whose interval from a specified endpoint has a prescribed value.
Domination: If an envy-free partial allocation has agents outside E dominating every agent in E, any envy-free allocation of the residue within E can be safely combined with it.Domination means outside agents would not envy E even if E received the entire residue.

3 The Protocol at a High Level

The protocol recursively reduces the active-agent set by constructing envy-free partial allocations and a dominated group that can divide the residue. Its high-level construction preprocesses value differences, creates witness snapshots, and reserves nonconflicting reassignments.

3. The Protocol at a High Level: Each recursive call seeks an envy-free partial allocation whose residue can be assigned to a proper subset of active agents without creating envy.Agents outside the subset keep their pieces while the subset recursively divides the residue.
3. The Protocol at a High Level: Core has a designated cutter divide the residue into equally valued pieces, after which SubCore allocates whole or partial pieces and returns leftover cake to the residue.SubCore is also used later to redistribute pieces subject to agents’ minimum required values.
Stage 1: Stage 1 preprocesses bonuses so every difference between an agent’s own piece and another piece becomes either small or large, eliminating intermediate cases.Polynomially many Core calls with each agent as cutter shrink the residue when intermediate bonuses occur.
Stage 2: Stage 2 cuts the residue into cells whose value is at most γV_i(R) for every agent, enabling comparisons across agents’ snapshot pieces.Agents who value the residue positively make cuts, and all agents’ cell values are recorded.
Witnesses: A witness snapshot identifies a label marked by one agent but not another, indicating a piece that can be reassigned to the latter without satisfying the former.A reassignment gives each agent a distinct snapshot piece.
Conflict avoidance: Different reassignments can conflict on one snapshot, so the protocol prunes bad snapshots until witness pairs can reserve distinct snapshots.Pairs left without witnesses no longer require reservations, while surviving witnesses support nonconflicting assignments.
Stage 3: For strongly connected snapshot graphs, directed cycles and self-loops yield perfect matchings that pair agents with distinct labels they do not mark.A reserved witness snapshot pairs the relevant agent with the desired label, and small attached pieces make the recipient willing to accept it.

4 Proof of the Main Theorem

The proof combines envy-free partial allocations and recursive reduction while preserving disjointness, envy-freeness, and bounded query complexity. Its snapshot construction and Stage 3 allocation establish the theorem’s single-exponential protocol bound.

Preservation properties: Disjoint envy-free partial allocations can be combined without decreasing pairwise value differences, and dominance persists through later residue allocations.These preservation properties justify combining allocations and completing recursive branches.
Core and SubCore: Core returns envy-free partial allocations, while SubCore allocates suffixes of distinct pieces meeting agents’ required minima.Core operates on a residue with a designated cutter; SubCore may trim pieces and return unused prefixes to the residue.
Snapshot construction: The construction creates snapshots and a partial allocation whose pieces, snapshots, and residue partition the cake, with every snapshot and the partial allocation envy-free.The construction stores the first nQ^2 allocations as snapshots and adds later allocations to H.
Snapshot preprocessing: At most nQ^3 later steps are needed because each step permanently makes one of at most nQ^3 intermediate bonuses large.Thus no intermediate bonus remains after preprocessing.
Constructing the partial allocation: Stage 3 uses additions, rank pieces, and SubCore redistribution to prevent envy across and within profile classes.The additions make pieces sufficiently valuable to agents outside a label while keeping them worse for agents marking that label.
Recursion and query complexity: Recursion applies to a nonempty proper subset of agents, and the main call uses at most Λ_n = K n^d 2^n queries aside from its recursive call.The induction therefore yields a deterministic bounded protocol using at most n^O(1)2^n queries.

5 Discussion and Concluding Remarks

The protocol’s exponential dependence is concentrated in Core and SubCore calls involving Θ(n) agents, while combining partial allocations adds no further exponential factor. The discussion identifies computation and subexponential improvements as open directions.

Open directions: Replacing exhaustive cell assignment with randomized assignment could reduce computation between queries while preserving high-probability success and allowing verification from known cell values.
Source of the exponential cost: Polynomially many partial allocations, Core and SubCore calls, and other queries keep the protocol’s overhead polynomial outside its main subroutine calls.Thus, up to polynomial factors, the full protocol costs no more than one n-agent Core or SubCore call.
Source of the exponential cost: Combining the partial allocations does not add another exponential factor.
Open directions: The remaining exponential cost comes from Core and SubCore calls involving Θ(n) agents.
Open directions: Avoiding large-agent subroutine calls or improving their query bounds could potentially yield subexponential or polynomial protocols, but these questions remain open.

A AI Usage Disclosure

The authors describe extensive early-stage ChatGPT assistance in developing a protocol and structural ideas, while stating that they refined the approach and take responsibility for the final work.

ChatGPT suggested replacing the computationally heavy GoLeft protocol with a more efficient approach and developed it into a complete protocol.The disclosed protocol used 22n(n−1)+O(n log n) Robertson–Webb queries.
The authors used GPT-generated structural ideas as the conceptual backbone of their work and as prototypes for several paper ideas.
The refined construction uses marks, witnesses, profiles, and ranks to choose and redistribute snapshot pieces.
The authors attribute GPT’s quadratic exponent to exponentially many snapshots and sequential construction with repeated rollback across stored snapshots.Together, these choices made the cost grow like the square of the number of snapshots.
Polynomially many pruned snapshots and a simultaneous-cutting lemma reduce the bound to 2^O(n) and simplify the recursion logic.
GPT was also used for identifying some related work and generating Appendix E’s pseudocode, while the authors developed the protocol, proofs, and remaining paper.

B Additional Related Work

The related work covers impossibility results, query and approximation methods, valuation-restricted algorithms, simplified bounded protocols, graph-based fairness, and probabilistic query analyses.

Stromquist showed that no finite protocol guarantees a complete envy-free allocation with one interval per agent for three or more agents.
For additive valuations, prior work studies query bounds, approximation algorithms, and welfare optimization for connected pieces.
Structural valuation restrictions yield stronger algorithms, including bounds for piecewise-linear densities and protocols for polynomial or piecewise-constant valuations.The piecewise-linear result uses O(n^6 k log k) queries when densities have at most k total breakpoints.
Other work simplifies bounded protocols, studies graph-based local envy-freeness, and analyzes query complexity beyond worst-case guarantees.For four agents, one bounded protocol’s query bound was reduced by a factor of 3.4; another result gives fewer than n^12 queries with high probability under a specified model.

C Robertson–Webb Implementation Details

The appendix explains how ordinary Robertson–Webb queries support pieces with multiple interval components and records the protocol’s deterministic conventions.

The appendix addresses multi-component pieces and documents deterministic conventions used by the protocol.

C.1 Queries on Ordered Pieces

Ordered pieces concatenate disjoint components in a fixed order, allowing prefixes and suffixes to be queried with ordinary Robertson–Webb operations while maintaining component values.

The protocol ignores finitely many cut-endpoint overlaps and treats exact arithmetic, comparisons, and finite computation on oracle answers as free.It does not bound the number of bits needed to represent arbitrary real answers.
An ordered piece stores multiple interval components in a fixed order, and prefixes or suffixes follow that order.For unions [P,A,D], components of P precede those of A and D.
The example concatenates components of P, A, and D, then splits the component [0.2, 0.3] at x = 0.25 into a prefix and suffix.
Queries to an ordered piece require at most one ordinary cut query and O(|N|) evaluation queries for a requested prefix or suffix.This bound is independent of the number of components.
Previously queried component values are summed to evaluate any ordered piece without further queries.
To obtain a requested prefix or suffix, the protocol accumulates component values and cuts inside the boundary component only when needed.
After splitting a component, one agent’s two resulting values follow from subtraction, while every other agent evaluates one interval and obtains the other by subtraction.

C.2 Deterministic Choices

The protocol resolves all finite choices deterministically, including ties, recursive ordering, and zero-valued residues. Ordered-piece conventions also make prefix and suffix selection deterministic, including degenerate zero-value cases.

Finite choices use fixed rules, with AM tie-breaking inside both subroutines and consistent ordering in recursive SubCore calls.
Zero-valued residue division assigns one possibly empty piece per active agent by a fixed rule.
Prefix and suffix requests scan ordered component boundaries first, using one ordinary cut inside a component only when necessary.
If an agent values an ordered piece at zero, the convention returns an empty prefix and full suffix.

D Omitted Proofs for Section 4

The omitted proofs establish that the modified SubCore preserves envy-freeness and benchmarks while avoiding a final recursive call and leaving an empty piece unallocated. They also derive polynomial-size query bounds for SubCore and Core.

The modified SubCore skips AM’s final recursive call when |W| = m−1, while retaining the benchmark-based allocation structure.
Induction shows each iteration adds an agent to W while preserving an envy-free tentative allocation in which every agent meets her benchmark.
SubCore uses O(m^2^m) evaluation queries, while Core first creates n equal-value pieces and then invokes SubCore on n−1 agents.
The modified and zero-minimum SubCore calls make identical choices because required minima do not affect trims, yielding the same recursive execution.
Each agent receives a suffix of a different input piece, with value at least her benchmark q_i.
The empty piece remains unallocated because a whole contested piece is always at least as valuable and recursive calls use only contested pieces.
The addition-size bounds imply Lemma 4.6 applies, with each agent’s allocated auxiliary value bounded by η_i.
When V_i(R*) = 0, the small bonus is zero; when ℓ_h = 0, P_h is empty, and the number of pieces and 1/δ remain polynomial in n.

E Full Pseudocode

The pseudocode assembles the protocol from preprocessing, snapshot pruning, partial-allocation construction, redistribution, and recursive allocation routines. It specifies both the main input-output interfaces and the deterministic subprocedures used at each stage.

Shrink repeatedly calls Core on successive residues, adds the resulting allocations, and stops after at most D calls or when the cutter values the residue at zero.
The complete-allocation procedure takes an active agent set and finitely many-interval subcake, using a separate base case when n ≤ 3.
Snapshot pruning removes witness groups, constructs directed graphs from excessive bonuses, and processes sink strongly connected components when a graph is not strongly connected.
Stage 3 forms profile classes, reserves witness snapshots and perfect matchings, then calls Allocate and redistributes cake within each profile class.
Preprocess constructs an envy-free partial allocation H, snapshots S, final residue R*, and bonuses d from an active set and subcake.
Allocate ranks pieces and cuts additions using residue-relative thresholds, while SubCore assigns the resulting pieces under class-specific benchmarks.
Lemma 4.6 constructs disjoint pieces whose values approximate prescribed fractions of an ordered piece within δ, by cutting cells and searching their labelings.
The approximation routine computes each labeled piece C_j(τ) and returns a labeling when every agent’s value meets the prescribed δ tolerance.