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.