A Bounded and Envy-Free Cake Cutting Algorithm

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation of a divisible resource based on queries from agents. The problem has received attention in mathematics, economics, and computer science. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We report on our algorithm that resolved the open problem.

Back to Top

1. Introduction

The cake cutting problem is a fundamental mathematical problem in which the 'cake' is a metaphor for a heterogeneous divisible resource represented by the unit interval [0, 1].⁴ The resource could represent time, land, or some computational resources. The goal is to allocate the cake among n entities that are referred to as 'agents.' Each agent's allocation consists of a collection of subintervals. Each of the agents is assumed to have additive and nonnegative valuations over segments of the interval. A cake-cutting algorithm/protocol interacts with the agents in order to identify a fair allocation.

One of the most important criteria for fairness is envy-freeness. An agent envies another if she would have preferred to receive the other's piece rather than hers. A cake cutting protocol/algorithm is called envy-free if each agent is guaranteed to be nonenvious if she reports her real valuations. If a protocol is envy-free, then an honest agent will not be envious even if other agents misreport their valuations.