ICES: Small: Computational Fair Division: From Cake Cutting to Cloud Computing

点击翻译按钮获取中文摘要

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.