David Kurokawa

Thesis Title: Algorithms in Fair Division
Degree Type: Ph.D. in Computer Science
Advisor(s): Ariel Procaccia
Graduated: August 2017

Abstract:

This thesis covers various aspects of fair division: allocating goods/items among interested parties while maintaining axiomatic or quantitative properties. The difficulty arises from the heterogeneous valuations of the agents. That is, agents do not necessarily agree on the value of a set of goods. We consider four settings in depth.

First, we dissect the problem of allocating k equal rewards to the best k of n agents when our only information comes from the agents evaluating each other. We give an an algorithm to accurately do so while disincentivizing agents from strategically lying to benefit themselves (a property called impartiality). We further show our accuracy is best possible under our metric.

Second, we expand the previous setting to when we wish to rank the agents instead of merely producing the top k of them. Here too, we give algorithms to accurately perform this task while maintaining impartiality. We expand on the connection to the first setting by extrapolating the generalization further and demonstrating several impossibility results.

Third, we consider the setting of cake cutting: allocating a single divisible good. We examine the classic problem of envy-free cake cutting when the agents have restricted valuations – specifically, they have piecewise uniform/constant/linear densities. We show that the restriction is no restriction at all, but when parametrizing the complexity of the densities, yields a significant reduction in difficulty. We further examine the cake cutting setting when agents are strategic and demonstrate the existence of standard equilibrium concepts in the space (despite infinite action spaces).

Finally, we expand upon the concept of the maximin share guarantee (a property seen in the study of indivisible goods). We give several results on the existence of the property and approximations to it in various settings.

Thesis Committee:
Ariel D. Procaccia (Chair)
Manuel Blum
Zico Kolter
Tuomas Sandholm
Ioannis Caragiannis (Univesity of Patras)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Algorithmic game theory, fair division, mechanism design, cake cutting, indivisible goods, maximin share