Article ID Journal Published Year Pages File Type
5072794 Games and Economic Behavior 2008 21 Pages PDF
Abstract

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-93]), (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 NP-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.

Keywords
Related Topics
Social Sciences and Humanities Economics, Econometrics and Finance Economics and Econometrics
Authors
, ,