The Query Complexity of Cake Cutting

Simina Branzei, Noam NisanNeurIPS 2022 · OpenReview

Introduction

In the realm of fair division theory, "cake cutting" serves as a classic metaphor for dividing a single, heterogeneous resource—such as land, time, or computational power—among multiple players with distinct preferences. The ultimate goal is to find an allocation that satisfies specific fairness criteria:

  • Envy-freeness: No player prefers another's piece over their own.
  • Proportionality: Every player receives a piece they value at least at $1/n$ of the total.
  • Equitability: Every player receives the exact same subjective value.

While exact fair allocations are mathematically proven to exist, computing them using a finite number of discrete queries is notoriously difficult. In the standard Robertson-Webb (RW) query model, a mediator interacts with players using only two types of queries:

  1. Cut: "Where is the point that gives you a specific value $\alpha$?"
  2. Eval: "How much do you value the interval between $x$ and $y$?"

This paper investigates the "query complexity" of achieving approximate fairness (or $\epsilon$-fairness). It explores how many queries are required to get "close enough" to a perfectly fair division and demonstrates how continuous "moving knife" protocols can be efficiently simulated within discrete query models.

Methodology

The researchers tackle the problem using two primary analytical strategies:

1. Lower Bound Constructions via Rigid Measure Systems To prove that finding a fair allocation is computationally hard, the authors construct specific, adversarial player valuations known as "rigid measure systems." Under these valuations, any protocol is forced to "hunt" for a fair allocation within a continuously shrinking interval. Because these systems maintain a self-reducible structure, each query can only reduce the mediator's uncertainty by a constant factor. This mathematical trap proves that a minimum of $\Omega(\log 1/\epsilon)$ queries is strictly necessary.

2. Moving Knife Simulation "Moving knife" protocols are continuous procedures where a mediator slowly slides one or more knives across the cake until a player yells "Stop!" Historically, these continuous procedures were considered fundamentally distinct from the discrete RW model. The authors formalize these procedures and prove they can be simulated in the RW model using a binary search-like approach. As long as player value densities are bounded, the mediator can pinpoint the "stopping point" of a moving knife to within an $\epsilon$ error margin using only $O(\log 1/\epsilon)$ queries.

Key Insights

  • The Logarithmic Barrier: For many fundamental scenarios—such as $n=3$ players seeking envy-freeness, or $n=2$ players seeking perfect or equitable allocations—the query complexity is exactly $\Theta(\log 1/\epsilon)$. This reveals that approximate fairness is computationally "cheap" in terms of information extraction compared to exact fairness.
  • Unifying Two Worlds: The paper's most significant conceptual leap is the formalization and simulation of moving knife protocols. By proving that these continuous processes can be discretized efficiently, the authors bridge a major gap between two previously separate branches of fair division literature.
  • The "Hungry" Player Requirement: The moving knife simulation functions best when players are "hungry," meaning they assign strictly positive value to every tiny sliver of the cake. If a player has "dead zones" (valuing a segment at zero), the continuous knife could slide over it instantly, complicating the discrete protocol's ability to track the stopping point.

Key Results

The paper establishes tight upper and lower bounds for various fairness notions, summarized in the table below:

Summary of upper and lower bounds for different fairness notions and player counts.
  • Envy-Free Allocations (Contiguous pieces): For $n=3$ players, the complexity is tightly bound at $\Theta(\log 1/\epsilon)$. For $n \ge 4$, the authors establish an upper bound of $O(n/\epsilon)$ and a lower bound of $\Omega(\log 1/\epsilon)$.
  • Perfect & Equitable Allocations: For $n=2$ players, finding an $\epsilon$-perfect or $\epsilon$-equitable allocation with the minimum number of cuts requires exactly $\Theta(\log 1/\epsilon)$ queries.
  • Simulation Power: Any moving knife procedure utilizing a constant number of cuts can be simulated in the RW model with $O(\log 1/\epsilon)$ queries, assuming value densities are bounded above and below.
  • New Equitable Protocol: The authors also introduce a novel, simplified moving knife protocol for equitable allocations that scales to any number of players.

Limitations and Future Work

While the paper resolves several long-standing questions, it leaves a few open challenges:

  • The $n \ge 4$ Gap: There remains a significant gap between the $O(n/\epsilon)$ upper bound and the $\Omega(\log 1/\epsilon)$ lower bound for envy-free allocations involving four or more players. The authors conjecture that the true complexity might be closer to $1/\epsilon$.
  • Perfect Allocations for $n \ge 3$: The complexity of finding perfect allocations (where every player believes every piece is worth exactly $1/n$) for three or more players remains an open question.
  • Density Bounds: Currently, the simulation of moving knife protocols requires player value densities to be strictly bounded. Extending this framework to accommodate more general valuations—specifically those where players might have zero-value "dead zones"—is a key area for future research.

Summary updated

Abstract

We consider the query complexity of cake cutting in the standard query model and give lower and upper bounds for computing approximately envy-free, perfect, and equitable allocations with the minimum number of cuts. The lower bounds are tight for computing contiguous envy-free allocations among $n=3$ players and for computing perfect and equitable allocations with minimum number of cuts between $n=2$ players. For $\epsilon$-envy-free allocations with contiguous pieces, we also give an upper bound of $O(n/\epsilon)$ and lower bound of $\Omega(\log(1/\epsilon))$ queries for any number $n \geq 3$ of players. We also formalize moving knife procedures and show that a large subclass of this family, which captures all the known moving knife procedures, can be simulated efficiently with arbitrarily small error in the Robertson-Webb query model.
BibTeX
@inproceedings{branzei2022query,
  author = {Simina Branzei and Noam Nisan},
  title = {{The Query Complexity of Cake Cutting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=u_7qyNFwkP8},
}
Figure