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

ICES：小型：计算公平分部：从切蛋糕到云计算

• 批准号: 1215883
• 负责人: Ariel Procaccia
• 金额: $ 39万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1215883&HistoricalAwards=false
• 关键词: ICES; Small; Computational; Fair; Division

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.

几千年来，思想家们一直在努力解决一个看似简单的问题：一个人如何在几个人之间公平地分配商品？20世纪，人们开始转向用严格的数学方法来研究公平问题;经济学家、数学家和政治学家都为大量关于公平分配的文献做出了贡献。相比之下，到目前为止，算法经济学中关于公平分配的工作很少，相对于微观经济理论中该领域的权重。特别是，公平分配可分割商品（如土地、时间或计算机内存）的计算工作相当稀少。该提案的主题是计算思维可以改变可分割商品公平分配的研究，而可分割商品公平分配的新研究可以在计算机科学中找到引人注目的应用。这一主题在两个领域进行了探索：（i）在切蛋糕中-一个异构可分商品分配的隐喻-所提出的研究重点是复杂性，表示和优化等问题;（ii）在云计算中，需要分配多个同质可分商品（例如，CPU，RAM），所提出的研究旨在设计和验证算法，表现出上级性能在实践中。该提案通过四个主要活动将算法经济学社区的注意力集中在公平分配上：一本书，一个暑期学校，杂志文章和教程。反过来，增加的计算注意力可能导致公平划分方法的部署应用激增。

项目成果

Leximin Allocations in the Real World

• DOI: 10.1145/3274641
• 发表时间: 2018-11-01
• 期刊: ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION
• 影响因子: 1.2
• 作者: Kurokawa, David;Procaccia, Ariel D.;Shah, Nisarg
• 通讯作者: Shah, Nisarg