DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Cakes, and Pies, and Fair Division

Speaker: Walter Stromquist, Swarthmore College

Date: Thursday, October 4, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Mathematicians enjoy cakes for their own sake and as a metaphor for more general fair division problems. We describe the state of the art of cake cutting, including some new results on computational complexity.

Suppose that a cake is to be divided by parallel planes into n pieces, one for each of n players whose preferences are defined by separate measures. We show that there is always an "envy-free" division, meaning that no player prefers another player's piece, and that such a division is always Pareto optimal. Alas, such a division cannot always be found by a finite procedure. Even assuring each player 1/n of the cake seems to require n log n steps.

Pies, of course, have their own attractions. We cut them radially into wedges. It turns out that pie cutters, unlike cake cutters, may be forced to choose between envy-freeness and Pareto optimality.