New complexity results about Nash equilibria

• 成果类型: Article; Proceedings Paper
• 署名作者: Conitzer, Vincent; Sandholm, Tuomas
• 署名单位: Duke University; Duke University; Carnegie Mellon University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.02.015
• 发表日期: 2008
• 页码: 621-641

摘要

We provide a single reduction that demonstrates that in normal-form games: (1) it is NP-complete to determine whether Nash equilibria with certain natural properties exist (these results are similar to those obtained by Gilboa and Zemel [Gilboa, I., Zemel, E., 1989. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav. 1, 80-931), (2) more significantly, the problems of maximizing certain properties of a Nash equilibrium are inapproximable (unless P = NP), and (3) it is #P-hard to count the Nash equilibria. We also show that determining whether a pure-strategy Bayes-Nash equilibrium exists in a Bayesian game is NP-complete, and that determining whether a pure-strategy Nash equilibrium exists in a Markov (stochastic) game is PSPACE-hard even if the game is unobserved (and that this remains A(P-hard if the game has finite length). All of our hardness results hold even if there are only two players and the game is symmetric. (C) 2008 Elsevier Inc. All rights reserved.