Ariel Provaccia在经济学和计算上

路加福音Muehlhauser你的工作很重要机制设计列昂尼德·赫维奇和斯坦利·瑞特曾在这里工作过描述简洁:

在[机制]设计问题中，目标函数是主要的“给定”，而机制是未知的。因此，设计问题是传统经济理论的“逆”，通常致力于分析给定机制的性能。

在Brânzei＆provaccia（2014），你和你的合著者继续解释说:

可以说，(一种机制)最受欢迎的特性是真实性，更正式被称为激励兼容性或strategyproofness：代理人不能从不诚实地揭示其私人信息中受益。

但更重要的是，如果代理能够以一种计算效率高的方式为自己验证机制的真实性，那就更好了。您如何描述(有效地)可验证的真实机制问题的当前进展状况?

阿里尔Procaccia关于可验证的真实机制的工作相当零散。在过去的十年里，几个研究小组已经利用模型检查技术来解决这个问题。亚博体育官网模型检查方法的主要缺点是计算密集，特别是不能导致可证明的计算效率。康与帕克斯(2006)研究了“被动”验证算法，这些算法不直接分析机制本身，而是观察其输入和输出序列。

在您提到的Simina Brânzei的工作中，我们采用了一种新颖的、三步走的方法:(i)我们提供了一种形式主义，允许我们指定机制的结构，(ii)我们构建了一个真实性验证算法，接收使用步骤(i)的形式主义指定的输入机制，(iii)我们分析地衡量机构的质量，其真实性可以使用步骤(ii)的算法有效地验证。作为概念证明，我们将我们的方法应用于特定领域(实际线上的设施位置)的真实可验证机构的设计。虽然我认为我们的方法非常令人兴奋，但现在就说它是否可以扩展到更丰富的领域还为时过早。

总而言之，对可验证的真实机制的研究仍处于起步阶段;还有很多工作要做!

路加福音：你最近的一些工作审查了“蛋糕切割”（公平分裂的良好）。根据你的调查的文章为CACM.在美国，关于切蛋糕的现代计算工作源于早期娱乐数学和微观经济学中关于公平的工作。据你所知，在关于公平的哲学著作(例如:罗尔斯)以及在数学、经济学和计算机科学方面的亚博体育官网公平研究?(连同斯科特Aaronson在美国，我通常对哲学问题在哲学之外被研究的动力感到好奇。我经常觉得，在哲学期刊之外研究一个问题，进步会更快。)

爱丽儿：公平部门的工作受到哲学的启发，我相信，提出了新的哲学问题。例如，你提到了提倡的着名哲学家约翰罗尔斯（在他的书中正义理论公平的最大原则:社会应该最大限度地照顾最不幸成员的前途。系统社区采用了这一原则。亚博体育苹果app官方下载的确,Demers等。（1989）写入：“MaxMin公平标准......指出，如果（1）没有用户超过其请求，则分配是公平的，（2）没有其他分配方案令人满意的条件1的分配方案具有更高的最小分配，并且（3）条件2递归仍然保持递归当我们删除最小用户并相应地减少总资源时，真实。CS理论社区也致力于对相关算法问题进行了相当的关注不可分割的商品使任何玩家的最小价值最大化。事实上，一些理论家认为圣诞老人用这种公平的概念来分配玩具!

相比之下，蛋糕切割文学更常见地研究“布尔”公平标准。也许是最引人注目的和直观的公理嫉妒 - 狂喜：每个玩家应该至少重视他的分配，因为他重视任何其他球员的分配。但AUMANN和DOMBB（2010）表明这两种不同的方法是不一致的。具体来说，他们正式构造了一个蛋糕切割实例，在这个实例中，限制分配为无嫉妒，将显著降低最不快乐玩家在最优分配下的快乐程度。我认为很有趣的是，这个数学结果提示了关于公平的基本哲学问题，例如，哪个更好，一个更富有的社会，一些人嫉妒其他人，还是一个更贫穷的社会，一个人满足于自己的份额?当公平分配被灌输的时候哲学课程在美国，就我所知，最近的数学结果对正义和公平理论的潜在贡献尚未被探索。

更奇怪的是，你看我的博客在公平部门与哲学之间的替代联系。

路加福音当前位置您还参与了公平部门的工作不可分割的商品。在Procaccia & Wang (2014)，您和您的合著者写道:

在典型的现实世界中，公平是首要考虑的问题，尤其是离婚协议和继承人之间的财产分配，涉及不可分割的财产(例如，房子、汽车和艺术品)——这通常排除了无嫉妒分配，甚至是比例分配。举个简单的例子，如果有几个玩家，但只有一件不可分割的道具可以分配，那么分配就不可能是比例分配或免费分配。

你会如何总结当前解决不可分割商品公平分配问题的方法?

爱丽儿：正如你所指出的那样，除以剥夺不可分割的商品是棘手的，因为像嫉妒的公平的经典概念（我们之前讨论过）显然是不可行的。我们知道，如果玩家的货物价值是随机绘制的，则在温和的假设下存在无常见的概率（见迪克森等人，2014)．或者，对于两个参与者的情况，Brams等人(2014)提出一项有趣的议定书，保证嫉妒（和其他物业），但可能不会分配所有商品。

在我看来，我们需要一个可以的公平概念总是对任何数量的玩家来说都是可行的。在你提到的论文中(与王俊兴一起)，我们研究了最大份额(MMS)保证，由埃里克奶油提出。简而言之，假设有N个玩家的给定玩家的MMS保证，是玩家可以的价值保证通过将商品分成n个包，让其他玩家选择包(按照一定顺序)，然后获得剩余的包。这将是伟大的如果能够总是把商品的方式满足玩家的MMS担保,但我们表明情况并非如此,即使估值添加剂为一捆(也就是说,我的价值是值的总和个人物品包)。然而，我们证明了以每个玩家都能得到的方式分配商品是可行的三分之二他的MMS保证。

我们使用这一理论结果去设计在任何数量的玩家中分配不可分割物品的最实用方法。首先，我们让玩家为商品分配点数。其次，为了产生分配，我们考虑三个层次的公平:自由嫉妒性、比例性(n个玩家每个人获得1/n的整个商品价值)和MMS保证;每一层的公平性都比后面一层强。我们返回最大化社会福利的分配，也就是玩家分配给他们所分配的游戏包的点数的总和最强的可行性公平程度。如果最强的公平性能是MMS保障，我们最大限度地提高了零件C，这样我们就可以为所有球员提供的MMS保证的C-Fillaction。我们的理论结果意味着保证的公平性水平的下限 - c至少2/3 - 但在实践中（基于几个组的广泛模拟），似乎C = 1应该始终是对现实实例可行的。

我刚才描述的方法是几个实际的公平划分方法之一偷偷地是一个未营利的公平部门网站，我一直在努力（与Jonathan Goldman）在过去一年中;它将在未来几个月推出。

路加福音从您的角度来看，计算公平分配理论与计算投票理论是如何相互作用的?如果我们不能通过公平分配理论得到某种满意的结果，那么我们是否有时可以通过一个不可操纵的投票方案得到“相当好”的结果，反之亦然?

爱丽儿社会选择和公平划分有一个共同的目标:以一种达到理想结果的方式聚集个人可能相互冲突的偏好。然而，这两种设置有很大的不同，因为公平划分通常涉及到每个人的分配属性，我们前面讨论的公平公理分别适用于每个人;而在经典的社会选择设置中，个人在一个典型的非结构化的社会结果空间中指定他们的偏好。通常，在这两个领域之一开发的方法不应该直接应用于另一个领域。也就是说，一些扩展，比如对组合域进行投票， 和公平分配与外部性-使两个领域更紧密地结合在一起，它们的关系通过Fleburbaey和Maniquet（2011年）。

除了一边（因为你专门询问不可操纵的规则），不可操纵的公平部门计划非常常见（参见，例如，Chen et al.， 2013），但我们不知道如何在计算投票理论中实现非操纵性（A.K.A.战略）。Gibbard-Satterthwaite定理规定了无法操纵的“合理”投票规则的存在。在你的意见采访Toby Walsh是一些投票规则是难以操纵的最糟糕的情况（关于操作问题的一些配方）。然而，我比托比更加悲观，这些结果实际上为操纵障碍提供了障碍，而且事实上，在设计难以操纵的投票规则时几乎是工作的几年。平均到目前为止只产生了消极的结果(见，例如，莫塞尔和拉兹，2012年)．

路加福音：您期望或未期望在未来15年内或未期望的公平部门理论或投票理论的哪些进展？例如。您对寻找不可操纵的“合理”投票规则似乎悲观。你还有什么悲观或乐观？

爱丽儿问题第一部分的简单答案是“应用”。

在（计算）公平部门，我认为我们已经过分了解如何解决现实世界 - 即使是日常公平的分区问题（如租金部门），通过巧妙的方法在几十年中发展起来。但是，曾在实践中实施或使用这些方法中的很少。网站偷偷地我之前提到过，它的目标是向让人们接触到一些最实用的方法(包括我的小组开发的方法)迈出第一步。我相信它也会让我们更清楚地了解哪些问题是人们想要解决的，哪些解决方案是令人满意的(有时世界上所有的数学保证都不足以让人们快乐!)值得一提的是，宾夕法尼亚大学沃顿商学院(Wharton Business School at Penn)最近采纳了一项美丽的公平分裂方法(他们称之为当然比赛)为学生分配工商管理硕士课程。在接下来的15年里，我希望看到更多可用的公平分割系统。亚博体育苹果app官方下载

在(计算)投票理论中，我对众包和人类计算系统的潜在应用持乐观态度，原因有二。亚博体育苹果app官方下载首先，与政治选举不同，众包系统的设计者可以很容易地评估和选择任何投票规则。亚博体育苹果app官方下载第二，一个经充分研究的经典投票模型(可以追溯到孔多塞侯爵)将选民视为根据质量对备选方案进行潜在真实排名的嘈杂估计者;虽然这种模式在政治选举的背景下存在问题(在政治选举中，意见是主观的)，但它非常适合某些众包设置。事实上，现有的系统就像亚博体育苹果app官方下载绮年华已经使用投票才能汇总信息;挑战是了解应该使用哪些投票规则。在我的小组中完成的工作（例如，Caragiannis et al.， 2013)，并由其他人提供了这个问题的一些答案。在未来的15年里，我相信我们将看到众包系统的设计直接由计算投票理论提供信息。亚博体育苹果app官方下载

路加福音：谢谢，阿里尔！