Computer Science Thesis Oral
- Gates Hillman Centers
- DAVID KUROKAWA
- Ph.D. Student
- Computer Science Department
- Carnegie Mellon University
Algorithms in Fair Division
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.
Ariel Procaccia (Chair)
Ioannis Caragiannis (University of Patras)