A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents
Haris Aziz, Simon Mackenzie · 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. Even if we do not run our protocol to completion, it can find in at most nn+1queries an envy-free partial allocation of the cake in which each agent gets at least 1/n of the value of the whole cake.