Computational Fair Division

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch


Fair division is a fundamental problem in economic theory and one of the oldest questions faced through the history of human society. The high level scenario is that of several participants having to divide a collection of resources such that everyone is satisfied with their allocation -- e.g. two heirs dividing a car, house, and piece of land inherited. The literature on fair division was developed in the 20th century in mathematics and economics, but computational work on fair division is still sparse.

This thesis can be seen as an excursion in computational fair division divided in two parts. The first part tackles the cake cutting problem, where the cake is a metaphor for a heterogeneous divisible resource such as land, time, mineral deposits, and computer memory. We study the equilibria of classical protocols and design an algorithmic framework for reasoning about their game theoretic properties. In our framework, the protocols are built from simple instructions that can be executed on a computer. Moreover, we prove an impossibility theorem for truthful mechanisms in the classical query model, which is similar in spirit to the Gibbard-Satterthwaite theorem of social choice theory. We also study alternative and richer models, such as externalities in cake cutting, simultaneous cake cutting, and envy-free cake cutting.

The second part of the thesis tackles the fair allocation of multiple goods, divisible and indivisible. In the realm of divisible goods, we investigate the well known Adjusted Winner procedure, obtaining several novel characterizations of the protocol and giving a complete picture of its pure Nash equilibria and their efficiency.
For indivisible goods, we study the competitive equilibrium from equal incomes solution concept for valuations
with perfect complements and valuations with perfect substitutes. We obtain characterizations of when competitive equilibria exist, as well as polynomial time algorithms and hardness results
for computing the equilibria.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages170
Publication statusPublished - 2015

Bibliographical note

Main Supervisor: Peter Bro Miltersen

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 85228897