IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Login to save this article or follow this journal

New complexity results about Nash equilibria

  • Conitzer, Vincent
  • Sandholm, Tuomas
Registered author(s):

    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.

    File URL: http://www.sciencedirect.com/science/article/B6WFW-4SDGR4B-1/1/3813b40c996625b87d57393533b3bab1
    Download Restriction: Full text for ScienceDirect subscribers only

    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.

    Article provided by Elsevier in its journal Games and Economic Behavior.

    Volume (Year): 63 (2008)
    Issue (Month): 2 (July)
    Pages: 621-641

    as
    in new window

    Handle: RePEc:eee:gamebe:v:63:y:2008:i:2:p:621-641
    Contact details of provider: Web page: http://www.elsevier.com/locate/inca/622836

    References listed on IDEAS
    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.:

    as in new window
    1. William R. Zame & John H. Nachbar, 1996. "Non-computable strategies and discounted repeated games," Economic Theory, Springer, vol. 8(1), pages 103-122.
    2. repec:ner:tilbur:urn:nbn:nl:ui:12-88290 is not listed on IDEAS
    3. McLennan, A., 1999. "The Expected Number of Nash Equilibria of a Normal Form Game," Papers 306, Minnesota - Center for Economic Research.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, 03.
    9. 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.
    10. Knoblauch Vicki, 1994. "Computable Strategies for Repeated Prisoner's Dilemma," Games and Economic Behavior, Elsevier, vol. 7(3), pages 381-389, November.
    11. Drew Fudenberg & Jean Tirole, 1991. "Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061414, June.
    12. 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.
    13. Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    14. von Stengel, Bernhard, 1996. "Efficient Computation of Behavior Strategies," Games and Economic Behavior, Elsevier, vol. 14(2), pages 220-246, June.
    Full references (including those not matched with items on IDEAS)

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    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 you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.