Papers › A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Haris Aziz, Simon Mackenzie
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^(n^(nⁿ)))). We additionally show that even if we do not run our protocol to completion, it can find in at most n³(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 n³(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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections