September 21, 2016

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 nnnnnn. We additionally show that even if we do not run our protocol to completion, it can find in at most nn+1 queries a partial allocation of the cake that achieves proportionality (each agent gets at least 1n of the value of the whole cake) and envy-freeness. Finally we show that an envy-free partial allocation can be computed in nn+1 queries such that each agent gets a connected piece that gives the agent at least 13n of the value of the whole cake.