IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v68y2010i2p683-688.html
   My bibliography  Save this article

Simple complexity from imitation games

Author

Listed:
  • McLennan, Andrew
  • Tourky, Rabee

Abstract

We give simple proofs of refinements of the complexity results of Gilboa and Zemel (1989), and we derive additional results of this sort. Our constructions employ imitation games, which are two person games in which both players have the same sets of pure strategies and the second player wishes to play the same pure strategy as the first player.

Suggested Citation

  • McLennan, Andrew & Tourky, Rabee, 2010. "Simple complexity from imitation games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 683-688, March.
    • Handle: RePEc:eee:gamebe:v:68:y:2010:i:2:p:683-688
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899-8256(09)00197-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
    2. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    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


    Cited by:

    1. McLennan, Andrew & Tourky, Rabee, 2010. "Imitation games and computation," Games and Economic Behavior, Elsevier, vol. 70(1), pages 4-11, September.
    2. Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Thomas Demuynck, 2014. "The computational complexity of rationalizing Pareto optimal choice behavior," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 529-549, March.
    2. Rahul Savani & Bernhard Stengel, 2015. "Game Theory Explorer: software for the applied game theorist," Computational Management Science, Springer, vol. 12(1), pages 5-33, January.
    3. Guzmán, Cristóbal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2022. "A sequential Stackelberg game for dynamic inspection problems," European Journal of Operational Research, Elsevier, vol. 302(2), pages 727-739.
    4. Hau Chan & Michael Ceyko & Luis Ortiz, 2017. "Interdependent Defense Games with Applications to Internet Security at the Level of Autonomous Systems," Games, MDPI, vol. 8(1), pages 1-60, February.
    5. Demuynck, Thomas, 2011. "The computational complexity of rationalizing boundedly rational choice behavior," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 425-433.
    6. Vincent Conitzer, 2019. "The Exact Computational Complexity of Evolutionarily Stable Strategies," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 783-792, August.
    7. Guzman, Cristobal & Riffo, Javiera & Telha, Claudio & Van Vyve, Mathieu, 2021. "A Sequential Stackelberg Game for Dynamic Inspection Problems," LIDAM Discussion Papers CORE 2021036, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Jugal Garg & Ruta Mehta & Vijay V. Vaziranic, 2018. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 996-1024, August.
    9. Amir Ali Ahmadi & Jeffrey Zhang, 2021. "Semidefinite Programming and Nash Equilibria in Bimatrix Games," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 607-628, May.
    10. Fabrice Talla Nobibon & Laurens Cherchye & Yves Crama & Thomas Demuynck & Bram De Rock & Frits C. R. Spieksma, 2016. "Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms," Operations Research, INFORMS, vol. 64(6), pages 1197-1216, December.
    11. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    12. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
    13. 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.
    14. Borgs, Christian & Chayes, Jennifer & Immorlica, Nicole & Kalai, Adam Tauman & Mirrokni, Vahab & Papadimitriou, Christos, 2010. "The myth of the Folk Theorem," Games and Economic Behavior, Elsevier, vol. 70(1), pages 34-43, September.
    15. DeCanio, Stephen J. & Fremstad, Anders, 2013. "Game theory and climate diplomacy," Ecological Economics, Elsevier, vol. 85(C), pages 177-187.
    16. Steffen Eibelshäuser & Victor Klockmann & David Poensgen & Alicia von Schenk, 2023. "The Logarithmic Stochastic Tracing Procedure: A Homotopy Method to Compute Stationary Equilibria of Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1511-1526, November.
    17. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    18. Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.
    19. Martin Shubik, 2011. "The Present and Future of Game Theory," Levine's Working Paper Archive 786969000000000173, David K. Levine.
    20. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1989. "The Complexity of Eliminating Dominated Strategies," Discussion Papers 853, Northwestern University, Center for Mathematical Studies in Economics and Management Science.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:68:y:2010:i:2:p:683-688. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.