Monday, April 14, 2008
11:00 AM
315 Upson Hall
  Theory Seminar
Spring 2008

CS 789

Amin Saberi
Stanford University


 An Algorithmic Approach to Fair Division

The fair division problem is the problem of dividing resources among entities in an impartial and equitable way. Economists and political economists have given many different formalizations for this notion. There is also a vast literature on this subject in mathematics starting with beautiful results of Steinhaus, Banach and Knaster in 1940's.

In this talk, I will focus on algorithmic questions posed in this context. I will explore interesting connections between the problems in this literature and central problems in approximation algorithms like minimum makespan job scheduling or complexity of finding a Brouwer's fixed point.

The study of some of the problems in fair division literature has resulted in the development of new techniques in approximation algorithms: as a part of our work, I will talk about a message passing method for rounding a fractional matching on a tree.