New complexity results about Nash equilibria
We provide a single reduction that demonstrates that in normal-form games: (1) it is -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 ), and (3) it is -hard to count the Nash equilibria. We also show that determining whether a pure-strategy Bayes-Nash equilibrium exists in a Bayesian game is -complete, and that determining whether a pure-strategy Nash equilibrium exists in a Markov (stochastic) game is -hard even if the game is unobserved (and that this remains -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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- William R. Zame, 1995.
"Non-Computable Strategies and Discounted Repeated Games,"
UCLA Economics Working Papers
735, UCLA Department of Economics.
- Nachbar, John H & Zame, William R, 1996. "Non-computable Strategies and Discounted Repeated Games," Economic Theory, Springer, vol. 8(1), pages 103-22, June.
- William R. Zame & John H. Nachbar, 1996. "Non-computable strategies and discounted repeated games," Economic Theory, Springer, vol. 8(1), pages 103-122.
- Ben-porath, Elchanan, 1990. "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economic Behavior, Elsevier, vol. 2(1), pages 1-12, March.
- Itzhak Gilboa & Eitan Zemel, 1988.
"Nash and Correlated Equilibria: Some Complexity Considerations,"
777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
- von Stengel, Bernhard, 1996. "Efficient Computation of Behavior Strategies," Games and Economic Behavior, Elsevier, vol. 14(2), pages 220-246, June.
- Koller, Daphne & Megiddo, Nimrod & von Stengel, Bernhard, 1996. "Efficient Computation of Equilibria for Extensive Two-Person Games," Games and Economic Behavior, Elsevier, vol. 14(2), pages 247-259, June.
- Knoblauch Vicki, 1994. "Computable Strategies for Repeated Prisoner's Dilemma," Games and Economic Behavior, Elsevier, vol. 7(3), pages 381-389, November.
- McLennan, A., 1999.
"The Expected Number of Nash Equilibria of a Normal Form Game,"
306, Minnesota - Center for Economic Research.
- Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
- Porter, Ryan & Nudelman, Eugene & Shoham, Yoav, 2008. "Simple search methods for finding a Nash equilibrium," Games and Economic Behavior, Elsevier, vol. 63(2), pages 642-662, July.
- Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, 03.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 2002. "Computing normal form perfect equilibria for extensive two-person games," Other publications TiSEM 9f112346-b587-47f3-ad2e-6, Tilburg University, School of Economics and Management.
- Koller, Daphne & Megiddo, Nimrod, 1992. "The complexity of two-person zero-sum games in extensive form," Games and Economic Behavior, Elsevier, vol. 4(4), pages 528-552, October.
- Drew Fudenberg & Jean Tirole, 1991. "Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061414, June.
- McLennan, Andrew & Berg, Johannes, 2005. "Asymptotic expected number of Nash equilibria of two-player normal form games," Games and Economic Behavior, Elsevier, vol. 51(2), pages 264-295, May.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:63:y:2008:i:2:p:621-641. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.