Institute for Logic, Language and Computation

2 November 2007, Computational Social Choice Seminar, Vangelis Markakis

Speaker: Vangelis Markakis (CWI)
Title: On the Complexity of Computing Approximately Envy-free Allocations
Date: Friday 2 November 2007
Time: 16:00
Location: P-016 (<em>changed</em>), Euclides Building, Plantage Muidergracht 24, Amsterdam

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, or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X