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），所提出的研究旨在设计和验证在实践中表现出卓越性能的算法。该提案通过四项主要活动将算法经济学界的注意力集中在公平分配上：一本书、暑期学校、杂志文章和教程。反过来，计算注意力的增加可能导致公平划分方法的部署应用激增。

项目成果

Fair Enough: Guaranteeing Approximate Maximin Shares

足够公平：保证大约最大最小份额

• DOI: 10.1145/3140756
• 发表时间: 2018-03
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Kurokawa, David;Procaccia, Ariel D.;Wang, Junxing
• 通讯作者: Wang, Junxing

Leximin Allocations in the Real World

现实世界中的 Leximin 分配

• DOI: 10.1145/2764468.2764490
• 发表时间: 2015-06-15
• 期刊: Proceedings of the Sixteenth ACM Conference on Economics and Computation
• 作者: David Kurokawa;Ariel D. Procaccia;Nisarg Shah
• 通讯作者: Nisarg Shah