OpenAlex ·

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

Qilin Ye and Yang Bai

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.05191
Original
Read it at the publisher
Topics
Computational ComplexityEconometricsGeneral Economics

Abstract

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 (in the Robertson-Webb query model) has resisted decades of work. The seminal work 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}}}}$. Subsequently, Sokolov modified their protocol and sharpened its analysis, obtaining a bound of $n^{8n^2(1+o(1))}$ queries, the best deterministic upper bound known before this work. In contrast, the general lower bound, due to Procaccia, is merely $Ω(n^2)$. We close much of this gap with a deterministic protocol using $n^{O(1)}2^n$ queries, the first single-exponential bound for general valuations. Like Aziz and Mackenzie, we repeatedly allocate cake without envy until some agents can leave with their pieces, guaranteed not to envy anyone who stays, even if a staying agent receives all the remaining cake. To reach this state, Aziz and Mackenzie generate $n^{n^{n^n}}$ partial allocations so that enough of them can be redistributed without conflict. Instead, we show that only polynomially many partial allocations suffice. Our key idea is to ``prune'' scarce allocations upfront: if only a few allocations can help a certain pair of agents, we discard them and handle that pair another way, leaving plenty of allocations for every remaining pair so each gets a distinct one. As a result, we make only polynomially many calls to Aziz and Mackenzie's subroutines, and this gives us our $n^{O(1)}2^n$ bound.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computational Complexity

Get the few papers worth your time in Computational Complexity every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics