ICS Theory Group

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


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.