Upper bounds for cake cutting

Abstract

In this thesis 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. First we show present a protocol for $4$ agents which solves the problem using $203$ cuts. We then generalise this 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^n}}}}$. We additionally show that even if we do not run our protocol to completion, it can find in at most $n^3{(n^2)}^n$ queries a partial allocation of the cake that achieves proportionality (each agent gets at least $\frac{1}{n}$ of the value of the whole cake) and envy-freeness. We also show that an envy-free partial allocation can be computed in at most $n^3{(n^2)}^n$ queries such that each agent gets a connected piece that gives the agent at least $\frac{1}{3n}$ of the value of the whole cake. Finally we give a new lower bound of $\Omega(n^3)$ on the number of queries required to allocate cake in an envy-free way.