Research output: Book/anthology/dissertation/report › Ph.D. thesis › Research

- Computational Fair Division
Final published version, 1 MB, PDF document

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.

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 language | English |
---|

Publisher | Department of Computer Science, Aarhus University |
---|---|

Number of pages | 170 |

Publication status | Published - 2015 |

Main Supervisor: Peter Bro Miltersen

See relations at Aarhus University Citationformats

No data available

ID: 85228897