IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2005.13921.html
   My bibliography  Save this paper

A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff

Author

Listed:
  • Jakub Dargaj
  • Jakob Grue Simonsen

Abstract

It is well-known that for infinitely repeated games, there are computable strategies that have best responses, but no computable best responses. These results were originally proved for either specific games (e.g., Prisoner's dilemma), or for classes of games satisfying certain conditions not known to be both necessary and sufficient. We derive a complete characterization in the form of simple necessary and sufficient conditions for the existence of a computable strategy without a computable best response under limit-of-means payoff. We further refine the characterization by requiring the strategy profiles to be Nash equilibria or subgame-perfect equilibria, and we show how the characterizations entail that it is efficiently decidable whether an infinitely repeated game has a computable strategy without a computable best response.

Suggested Citation

  • Jakub Dargaj & Jakob Grue Simonsen, 2020. "A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff," Papers 2005.13921, arXiv.org, revised Jun 2020.
    • Handle: RePEc:arx:papers:2005.13921
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2005.13921
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Halpern, Joseph Y. & Pass, Rafael & Seeman, Lior, 2019. "The truth behind the myth of the Folk theorem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 479-498.
    4. Nachbar, John H & Zame, William R, 1996. "Non-computable Strategies and Discounted Repeated Games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(1), pages 103-122, June.
    5. Kam-Chau Wong & Marcel K. Richter, 1999. "Non-computability of competitive equilibrium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 14(1), pages 1-27.
    6. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, December.
    7. Gilboa, Itzhak, 1988. "The complexity of computing best-response automata in repeated games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 342-352, August.
    8. Knoblauch Vicki, 1994. "Computable Strategies for Repeated Prisoner's Dilemma," Games and Economic Behavior, Elsevier, vol. 7(3), pages 381-389, November.
    9. Rubinstein, Ariel, 1986. "Finite automata play the repeated prisoner's dilemma," Journal of Economic Theory, Elsevier, vol. 39(1), pages 83-96, June.
    Full references (including those not matched with items on IDEAS)

    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. Hubie Chen, 2013. "Bounded rationality, strategy simplification, and equilibrium," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 593-611, August.
    2. João E. Gata, 2019. "Controlling Algorithmic Collusion: short review of the literature, undecidability, and alternative approaches," Working Papers REM 2019/77, ISEG - Lisbon School of Economics and Management, REM, Universidade de Lisboa.
    3. Compte, Olivier & Postlewaite, Andrew, 2015. "Plausible cooperation," Games and Economic Behavior, Elsevier, vol. 91(C), pages 45-59.
    4. Nachbar, John H & Zame, William R, 1996. "Non-computable Strategies and Discounted Repeated Games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(1), pages 103-122, June.
    5. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    6. Oliveira, Fernando S., 2010. "Limitations of learning in automata-based systems," European Journal of Operational Research, Elsevier, vol. 203(3), pages 684-691, June.
    7. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    8. Gilboa Itzhak & Schmeidler David, 1994. "Infinite Histories and Steady Orbits in Repeated Games," Games and Economic Behavior, Elsevier, vol. 6(3), pages 370-399, May.
    9. Joshua M. Epstein, 2007. "Agent-Based Computational Models and Generative Social Science," Introductory Chapters, in: Generative Social Science Studies in Agent-Based Computational Modeling, Princeton University Press.
    10. 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.
    11. Olivier Compte & Andrew Postlewaite, 2007. "Effecting Cooperation," PIER Working Paper Archive 09-019, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 29 May 2009.
    12. Hamid Sabourian & Jihong Lee, 2004. "Complexity and Efficiency in Repeated Games with Negotiation," Econometric Society 2004 Far Eastern Meetings 401, Econometric Society.
    13. Daijiro Okada & Abraham Neyman, 2004. "Growing Strategy Sets in Repeated Games," Econometric Society 2004 North American Summer Meetings 625, Econometric Society.
    14. Ho, Teck-Hua, 1996. "Finite automata play repeated prisoner's dilemma with information processing costs," Journal of Economic Dynamics and Control, Elsevier, vol. 20(1-3), pages 173-207.
    15. Horaguchi, Haruo, 1996. "The role of information processing cost as the foundation of bounded rationality in game theory," Economics Letters, Elsevier, vol. 51(3), pages 287-294, June.
    16. D. Sgroi & D. J. Zizzo, 2002. "Strategy Learning in 3x3 Games by Neural Networks," Cambridge Working Papers in Economics 0207, Faculty of Economics, University of Cambridge.
    17. Yuval Salant & Jörg L. Spenkuch, 2021. "Complexity and Choice," CESifo Working Paper Series 9239, CESifo.
    18. Spiegler, Ran, 2005. "Testing threats in repeated games," Journal of Economic Theory, Elsevier, vol. 121(2), pages 214-235, April.
    19. repec:dau:papers:123456789/6127 is not listed on IDEAS
    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.
    21. Lu Hong & Scott E. Page, 1998. "Diversity and Optimality," Research in Economics 98-08-077e, Santa Fe Institute.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:arx:papers:2005.13921. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.