Settling the Complexity of Computing Two-Player Nash Equilibria
Settling the Complexity of Computing Two-Player Nash Equilibria
复制标题
DOI：
10.1145/1516512.1516516
复制
发表时间：
2009-05-01
影响因子：
2.5
通讯作者：
Teng, Shang-Hua
中科院分区：
文献类型：
--
作者：
Chen, Xi;Deng, Xiaotie;Teng, Shang-Hua
我们证明，Bimatrix是在两人游戏中找到NASH均衡的问题，是Papadimitriou在1991年引入的复杂性类PPAD（多项式平价论证，指示版本）的完整的。 al。 [2006a]关于四人纳什均衡的复杂性，在算法游戏理论中解决了一个长期的开放问题。它也是有关两名玩家NASH均衡的复杂性的一系列结果的起点。特别是，我们证明了以下定理： - bimatrix没有完全多项式时间近似方案，除非PPAD中的每个问题都可以在多项式时间内解决。 bimatrix的算法不是多项式的，除非PPAD中的每个问题在随机多项式时间内都可以解决。您的结果在数学经济学中也具有复杂的意义：-Arrow-Debreu市场平衡是PPAD-HARD可以计算。
We prove that BIMATRIX, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems:- BIMATRIX does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.- The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for BIMATRIX is not polynomial unless every problem in PPAD is solvable in randomized polynomial time.Our results also have a complexity implication in mathematical economics:- Arrow-Debreu market equilibria are PPAD-hard to compute.