CS 298-2
Theory Seminar
Amin Saberi
Stanford University
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.