ACM通信
研究突出了
技术视角:为什么要研究无政府状态的代价?
2012年5月16日，ACM算法与计算理论特别兴趣小组(SIGACT)和欧洲理论计算机科学协会(EATCS)宣布了2012年Göedel奖的获奖者，获奖论文包括:
- 《最坏情况均衡》，Elias Koutsoupias和Christos H. Papadimitriou，
- Tim Roughgarden和Éva Tardos合著的《自私路由有多糟糕?
- 《算法机制设计》，作者:Noam Nisan和Amir Ronen。
这一喜事将于本月在英国沃里克举行的自动机、语言和编程国际研讨会上举行。因此，蒂姆·拉夫加登的这篇新论文出现在本期的《通信．
1999年，Elias Koutsoupias和Christos Papadimitriou发起了一项关于“自私会让我们的生活变得多么糟糕”的研究。他们比较了最坏情况下的纯纳什均衡和最优解(就某些目标函数而言，通常是社会福利)。这个比率后来被称为无政府状态的价格。的研究混乱的价格催生了一个全新的研究领域。
Roughgarden使用了一种“平滑博弈”的技巧来给出边界，不仅是关于纯纳什均衡的无政府状态的价格，而且是关于更一般(且令人信服)的设定。
自私行为的负面影响被观察到的领域之一是在交通网络分析中的Wardrop均衡(本质上，纳什均衡中有无限多个无穷小的代理)。对于具有线性延迟函数的非原子路由，Roughgarden和Tardos显示了混乱价格的紧密边界。最糟糕的例子是众所周知的Braess悖论(D. Braess, 1968)，但Roughgarden和Tardos表明这是严密的。
关于无政府状态的代价，有两个令人不安的问题:
- 纯纳什均衡并不总是存在。混合策略(随机)纳什均衡保证存在。
- 一般来说，计算纳什均衡是困难的。引用帕帕迪米特里欧的话:“如果你的笔记本电脑找不到它，那么市场也找不到。”那么，为什么要研究一个在实践中可能不存在的概念的混乱代价呢?
在接下来的论文中，Roughgarden研究了“平滑博弈”来给出边界，不仅是关于纯纳什均衡的无政府状态的价格，而且是关于更一般的(有说服力的)情况。他扩展了这种方法有效的博弈类别，扩展了这种方法能给出良好边界的均衡类别。
特别是，这种技术被证明对所谓的“最小化遗憾”动态有效，这是相当自然和可信的，因为它代表了真实发生的事情。由此得到的边界适用于遗憾最小化动态，这意味着它们适用于所谓的粗相关均衡，这意味着它们适用于相关均衡，由此推断它们适用于混合纳什均衡，因此适用于纯纳什均衡，如果它们存在的话。
Roughgarden在下文中的另一个重要贡献是证明了存在一些有趣的博弈族，这些博弈族的平滑分析可以给出无政府状态边界的最佳价格(关于纯纳什均衡，因此也关于所有包含纯纳什均衡的类别:混合、相关、粗相关和无遗憾动态)。对于这类游戏，平滑分析给出了全部答案，不需要其他技巧。
对于这种平滑技术的完全普遍性，需要注意的是其他自然动力学，如最佳响应动力学和所谓的汇平衡，对于这些动力学，平滑分析可能不足以确定无政府状态的代价。
Christodoulou和Koutsoupias使用类似的平滑技术，在混合均衡和相关均衡的背景下，对混乱价格(STOC 2005)和稳定价格(ESA 2005)进行了拥堵对策(特殊情况)的研究。平滑技术在许多早期的论文中被含蓄地用于对无政府状态结果进行定价。阅读下面的文章比阅读原文更容易理解先前的无政府状态的许多代价结果。
©2012 acm 0001-0782/12/0700 $10.00
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2012 ACM, Inc.
没有发现记录