New complexity results about Nash equilibria

Published

Journal Article

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. © 2008 Elsevier Inc. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Conitzer, V; Sandholm, T

Published Date

  • July 1, 2008

Published In

Volume / Issue

  • 63 / 2

Start / End Page

  • 621 - 641

Electronic International Standard Serial Number (EISSN)

  • 1090-2473

International Standard Serial Number (ISSN)

  • 0899-8256

Digital Object Identifier (DOI)

  • 10.1016/j.geb.2008.02.015

Citation Source

  • Scopus