# A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2016.

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

- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Fair Division with Market Values](https://mlsanity.com/paper/2410.23137/) (2024)
- [Cherry on the Cake: Fairness is NOT an Optimization Problem](https://mlsanity.com/paper/2406.16606/) (2024)
- [Resource Allocation under the Latin Square Constraint](https://mlsanity.com/paper/2501.06506/) (2025)
- [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)
- [Exact Cut Complexity of Equal-Length Proportional Cake Cutting](https://mlsanity.com/paper/2610.19733/) (2026)

## Abstract (arXiv)

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from n agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents. The maximum number of queries required by the protocol is n^n^n^nnn. We additionally show that even if we do not run our protocol to completion, it can find in at most n3(n2)n queries a partial allocation of the cake that achieves proportionality (each agent gets at least 1/n of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in at most n3(n2)n queries such that each agent gets a connected piece that gives the agent at least 1/(3n) of the value of the whole cake.