Constantinos Daskalakis2014-03-14 11:32 AM

计算一个纳什均衡的复杂性 The Complexity of Computing a Nash Equilibrium

论文摘要: 

1951年,约翰·F·纳什证明了任何博弈都存在纳什均衡。但是他的证明是非构造性质的,依赖于布劳威尔的不动点定理,于是也引发了以下的问题:是不是存在一种多项式时间算法来计算纳什均衡呢?以及这是不是取决于布劳威尔其不动点定理的内在规律?基于此点出发,之后提出了很多算法试图寻找纳什均衡点,但是没有一个是可以符合多项式时间运算的。1991年,布劳威尔问题的计算是属于PPAD(有向图的多项式校验参数)-complete的,而这种计算复杂类别被引进于解决纳什均衡问题,这主要是为了解决纳什均衡的分类问题。至于纳什问题对于这个类别是否具有完备性还有待商榷。在这篇论文中我们将解决以下这些问题:我们会证明在三人博弈中,纳什均衡的计算是属于PPAD-complete的。而且我们是通过对布劳威尔问题进行归约完成的,于是证实了这两个问题在计算上是等质的。我们通过一个图型博弈来模拟一个布劳威尔方程(程序化的)进行归约,借助一些“装备”,使得图型博弈进行了各种算术以及逻辑上的运算。接着我们又展示了如何通过三人博弈来模拟图型博弈,而在这场博弈中每一位玩家在底色图上本质为一种色类。通过完善我们的构造,接下来我们把结果加强到二人博弈的纳什均衡计算也是属于PPAP-complete的。下文我们将证明通过我们的论据何以如此轻而易举的得到这一结果。


Abstract
In 1951, John F. Nash proved that every game has a Nash equilibrium [43]. His proof is non-constructive, relying on Brouwer’s fixed point theorem, thus leaving open the questions: Is there a polynomial-time algorithm for computing Nash equilibria? And is this reliance on Brouwer inherent? Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the complexity class PPAD, for which Brouwer’s problem is complete, was introduced [48], motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper we resolve these questions: We show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and we do so by a reduction from Brouwer’s problem, thus establishing that the two problems are computationally equivalent. Our reduction simulates a (stylized) Brouwer function by a graphical game [33], relying on “gadgets,” graphical games performing various arithmetic and logical operations. We then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. Subsequent work [8] established, by improving our construction, that even two player games are PPAD-complete; here we show that this result follows easily from our proof.

KEYWORDS

SHARE & LIKE

COMMENTS

ABOUT THE AUTHOR

Constantinos Daskalakis

Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with LIDS and ORC.

0 Following 2 Fans 0 Projects 10 Articles

SIMILAR ARTICLES

论文摘要 最近在[12]中表明, 在所有具有任意(可能的组合)可行性约束和受任意(可能组合)需求约束的独立添加的投标人的多维贝叶斯拍卖问题中,收入最优化可以从计算上有效减持至福利最优化。这种减持在所有拍卖假设中给可以得到有效解决的最优化机制设计问题提供了一种多项式时间解决方案,但它的这种逼近很脆弱且不

Read More

论文摘要 线性编程低密度奇偶校验码(和例如压缩感知的相关领域)的解码由于其近似于迭代解码算法的实际性能和它对有限块长度分析的可处理性在近几年已获得越来越多的关注。一些和Feldman等人所著同期的著作展示了如何使用膨胀曲线特性分析LP解码。这一分析线性具有低误差率,比经验观察性能更低上几个数量级。如同

Read More

Abstract:We propose a new no-regret learning algorithm. When used against an adversary, our algorithm achieves average regret that scales as O (1/√T) w

Read More

论文摘要: 1951年,约翰·F·纳什证明了任何博弈都存在纳什均衡。但是他的证明是非构造性质的,依赖于布劳威尔的不动点定理,于是也引发了以下的问题:是不是存在一种多项式时间算法来计算纳什均衡呢?以及这是不是取决于布劳威尔其不动点定理的内在规律?基于此点出发,之后提出了很多算法试图寻找纳什均衡点,但是没

Read More

论文摘要: 基于允许插入与缺失(即简称为indels)条件的层序演化模型我们引进了一级多项式时间系统发育重建算法。基于合适的假设,我们的算法要求序列长度随叶形分类群数呈现多项式形式的增长。我们的方法是是基于距离测量而且在很大程度上绕开了多重调节的问题。Abstract:We introduce the

Read More

论文摘要: 对于多维度单位需求定价问题即当消费者的心理价值相互独立时(但是未必是恒等分布的),我们提供了一个多项式时间近似算法。对于任意epsilon>0的情况,我们得到(1+epsilon)这个因子来近似最优收益。有以下三种情况:当这些价值数据是从符合单调风险率分布中取样得到时,近似值符合时间多项式

Read More

论文摘要 我们引入了一种新系统发育重建算法,不同于以往大多数严谨的推理技术,该算法不依赖于有关分支长度或树深度的假设。该算法返回了保证含有以下所有边界的森林: 1)足够长 2)足够接近叶。 真正树中有多少能够得到恢复依赖于所提供序列的长度。该算法基于距离且在多项式时间中运行。 Abstract:We

Read More

论文摘要 排序和搜索的经典问题假设了被比较对象的一个基本线性排序。在本文中我们基于偏序背景研究了这些问题,其中对象的某些对不可类比。从组合角度来看,这种概括很有趣,且它可在例如会议提交的非基于线性排序排名场景中有直接应用。它也可应用于例如包括生物网络的某些类型网络的重构中。与二十年前由Faigle和T

Read More

Abstract:A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Mar

Read More

Abstract:We introduce CLS, for continuous local search, a class of polynomial-time checkable total functions that lies at the intersection of PPAD and

Read More