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

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.