13 June 2008, Computational Social Choice Seminar, Ulle Endriss

Abstract

A tree-based cake-cutting procedure is a procedure for dividing a cake amongst ever smaller groups of players, following the structure of a tree. For instance, if the root of the tree has three children, then we first divide into three pieces and assign as many players to each piece as the corresponding node has descendants that are leaf nodes. The divide-and-conquer procedure of Even and Paz (Discrete Applied Mathematics, 1984) is an example for a tree-based procedure. Here the underlying tree is binary and has branches of (roughly) equal length. In this talk, I shall discuss some of the properties of the procedures we obtain when we lift the restriction to binary trees. In this context, an interesting question to ask is to what extent properties of the local procedures used to make preliminary divisions among groups of players transfer to the final division of the cake. This requires giving suitable definitions of concepts such as proportional fairness and envy-freeness for groups. An example for a positive result is that if the local procedures guarantee proportionality with respect to groups, then the overall procedure will guarantee proportionality for individual players. Envy-freeness, on the other hand, clearly does not transfer in this sense. Instead, following up on work by Brams, Jones and Klamler (presented by Steve Brams at a COMSOC Seminar at the ILLC in early 2007), I shall discuss various bounds on the degree of envy of the final division. This is joint work with Eric Pacuit.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle at illc.uva.nl).