For millennia thinkers have struggled with a seemingly simple question: how does one fairly divide goods among several people? The 20th century has seen a shift towards mathematically rigorous approaches to fairness; economists, mathematicians, and political scientists have all contributed to the large body of literature on fair division. In contrast, to date there is little work in algorithmic economics on fair division, relative to this field's weight in microeconomic theory. In particular, computational work on the fair allocation of divisible goods (such as land, time, or computer memory) is rather sparse.

The theme of this proposal is that computational thinking can transform research on the fair allocation of divisible goods, while novel research on the fair allocation of divisible goods can find compelling applications in computer science. This theme is explored in two domains: (i) in cake cutting --- a metaphor for the allocation of a heterogeneous divisible good --- the proposed research focuses on issues such as complexity, representation, and optimization; (ii) in cloud computing, where one needs to allocate multiple homogeneous divisible goods (e.g., CPU, RAM), the proposed research aims to design and validate algorithms that exhibit superior performance in practice.

This proposal focuses the attention of the algorithmic economics community on fair division via four main activities: a book, a summer school, magazine articles, and tutorials. In turn, the increased computational attention can lead to a surge of deployed applications of fair division methods.

Project Start
Project End
Budget Start
2012-07-01
Budget End
2016-06-30
Support Year
Fiscal Year
2012
Total Cost
$390,000
Indirect Cost
Name
Carnegie-Mellon University
Department
Type
DUNS #
City
Pittsburgh
State
PA
Country
United States
Zip Code
15213