CS 298-2
Theory Seminar

Amin Saberi
Stanford University

An algorithmic approach to fair division

Monday, October 29, 2007
4pm-5pm
The Wozniak Lounge, on the fourth floor of Soda Hall


The problem of fair division--dividing resources among entities in an impartial and equitable way--is a central problem in economic theory and has been studied by mathematicians such as Banach and Steinhaus since the 1940's. In this talk, I will focus on algorithmic questions posed in this context. I will talk about approximation algorithms for fair allocation of indivisible goods and their connections to job scheduling. The study of some of these problems has resulted in the development of new techniques in approximation algorithms: as a part of our approximation algorithm, I will talk about a message passing method for rounding a fractional matching on a tree. I will also talk briefly about a cake-cutting problem in which we are looking for a polynomial-time algorithm for finding an envy-free allocation. Currently there are only fixed-point arguments known for the existence of such an allocation.