Advanced Search
MyIDEAS: Login

New complexity results about Nash equilibria

Contents:

Author Info

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

    Abstract

    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.

    Download Info

    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.

    Bibliographic Info

    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

    Related research

    Keywords:

    References

    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. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
    2. Stengel, B. von & Elzen, A.H. van den & Talman, A.J.J., 2002. "Computing normal form perfect equilibria for extensive two-person games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-88290, Tilburg University.
    3. Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
    4. William R. Zame, 1995. "Non-Computable Strategies and Discounted Repeated Games," UCLA Economics Working Papers 735, UCLA Department of Economics.
    5. 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.
    6. 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.
    7. Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, 03.
    8. 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.
    9. 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.
    10. 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.
    11. von Stengel, Bernhard, 1996. "Efficient Computation of Behavior Strategies," Games and Economic Behavior, Elsevier, vol. 14(2), pages 220-246, June.
    12. Drew Fudenberg & Jean Tirole, 1991. "Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061414, December.
    13. Knoblauch Vicki, 1994. "Computable Strategies for Repeated Prisoner's Dilemma," Games and Economic Behavior, Elsevier, vol. 7(3), pages 381-389, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    2. Jiang, Albert Xin & Leyton-Brown, Kevin & Bhat, Navin A.R., 2011. "Action-Graph Games," Games and Economic Behavior, Elsevier, vol. 71(1), pages 141-173, January.
    3. McLennan, Andrew & Tourky, Rabee, 2010. "Simple complexity from imitation games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 683-688, March.
    4. Rota Bulò, Samuel & Bomze, Immanuel M., 2011. "Infection and immunization: A new class of evolutionary game dynamics," Games and Economic Behavior, Elsevier, vol. 71(1), pages 193-211, January.

    Lists

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

    Statistics

    Access and download statistics

    Corrections

    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.