2 November 2007, Computational Social Choice Seminar, Vangelis Markakis

Abstract:
In this talk we will address the complexity of cake cutting within a certain model of computation. Viewing the cake as the interval [0,1], we will first formalize what are the allowable operations that an algorithm can perform. In particular we will focus on algorithms that can perform 2 types of operations, namely cut and evaluation operations. With a cut operation, the algorithm asks a player to cut a piece of cake that is worth a certain value. In an evaluation operation, the algorithm can ask a player to report his value for a piece of the cake.

We will then review some upper and lower bounds that have been established for such types of algorithms and for the concept of proportional fairness. Finally, we will see an algorithm that produces an epsilon-envy-free partition with a linear number of cuts (O(n/epsilon)) for any constant epsilon >0. Here epsilon-envy-free means that the envy of any player for the rest is at most epsilon.

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