Speaker: Kirk Pruhs, University of Pittsburgh

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Cake cutting is and is not a piece of cake

Abstract: 

The setting for the classic cake cutting problem is a collection of self-interested entities who
desire to partition a disparate collection of items of value.  Imagine heirs of an estate wanting
to divide the possessions of the newly departed. Or imagine the creditors of a bankrupt company,
such as Enron, wanting to split up the company's remaining assets. The entities may well value the
items differently.  For example, one can imagine different heirs of an estate not necessarily
agreeing on the relative value a baseball signed by Pete Rose, a worn leather lazy boy recliner, a
mint condition classic Farrah Fawcett poster, etc.  The goal is devise a protocol to split up the
items fairly, that is, so every entity believes that he/she gets a fair share based on how he/she
values the objects.  Achieving this goal is potentially complicated by the fact that the entities
may well be greedy, deceitful, treacherous, etc. They may not be honest about how they value the
objects, they may collude together to cheat another entity, etc.

The cake cutting problem dates from the 1940's school of Polish mathematics. This problem is
frequently discussed in algorithms and discrete mathematics courses, for example CMU 15-451.

In 1948 Steinhaus gave a deterministic protocol with query complexity Theta(n^2). In 1984, Evan
and Paz gave a deterministic divide and conquer protocol with query complexity Theta(n log n). We
show that every deterministic protocol for this problem has query complexity Omega(n log n). This
lower bound also applies even if the deterministic protocol need only be approximately fair. We
then show that there is a randomized algorithm that is approximately fair and has query complexity
O(n).

This is joint work with Jeff Edmonds.