## ICS 269, Winter 2006: Theory Seminar

### Feb 24, 2006, in CS 253

# Cake Cutting Really is Not a Piece of Cake

## Authored by:Jeff Edmonds and Kirk Pruhs

### In SODA 2006

## Presented by Kevin Wortman

Abstract:

We consider the well-known cake cutting problem in which a protocol wants
to divide a cake among *n*≥2 players in such a way that each player
believes that they got a fair share. The standard Robertson-Webb model
allows the protocol to make two types of queries, Evaluation and Cut, to
the players. A deterministic divide-and-conquer protocol with complexity
*O*(*n* log *n*) is known. We provide the first Ω(*n* log *n*) lower bound on
the complexity of any deterministic protocol in the standard model.