# The Query Complexity of Cake Cutting

arXiv: https://arxiv.org/abs/1705.02946 · HTML: https://mlsanity.com/paper/1705.02946/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2017.

## Built on by (most cited first, 3 of 3)

- [Fair Division of Multi-layered Cakes](https://mlsanity.com/paper/2208.00726/) (2022)
- [Chore Cutting: Envy and Truth](https://mlsanity.com/paper/2301.09306/) (2023)
- [Externalities in Chore Division](https://mlsanity.com/paper/2303.12446/) (2023)

## Abstract (arXiv)

We study the query complexity of cake cutting 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 connected envy-free allocations among n=3 players and for computing perfect and equitable allocations with minimum number of cuts between n=2 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.