Wednesday, October 19, 2016 - 1:00pm
Location:1507 Newell-Simon Hall
Speaker:DAVID KUROKAWA, Ph.D. Student http://www.cs.cmu.edu/~dkurokaw
Fairly dividing goods among several (possibly strategic) parties is a common problem both in economics and computer science. For instance, a government may wish to divide tracts of land to various organizations or a cloud computing environment may wish to divide computing time among several users. Often, such situations are dealt with via the use of monetary transfers — such as in auctioning o the desired goods; however we are concerned with the case where such transfers are not allowed.
In this proposal we expound upon our work in both the divisible setting as well as the indivisible. We start with an examination of our work and future problems to tackle in classical envy-free cake-cutting, as well as the often ignored game-theoretic aspects of this area. We then move onto the indivisible setting and present our results on the MMS guarantee, and two new properties we coin as PMMS and EFX. The improvement of guaranteeable approximations is the main open problem regarding these properties. We end with a discussion on our applications of fair division techniques and research to real world problems: classroom allocation among schools, and the peer review process.
Thesis Committee: Ariel Procaccia (Chair) Manuel Blum Tuomas Sandholm Ioannis Caragiannis (University of Patras)
Copy of Thesis Summary