Computer Science Thesis Proposal

Wednesday, October 19, 2016 - 1:00pm

Location:

1507 Newell-Simon Hall

Speaker:

DAVID KUROKAWA, Ph.D. Student http://www.cs.cmu.edu/~dkurokaw

For More Information, Contact:

deb@cs.cmu.edu

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

Keywords:

Thesis Proposal