research-article

Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria

Authors:

Jakob Grue SimonsenAuthors Info & Claims

ACM Transactions on Economics and Computation, Volume 10, Issue 1

Article No.: 3, Pages 1 - 39

https://doi.org/10.1145/3505585

Published: 08 April 2022 Publication History

Abstract

A classic result in computational game theory states that there are infinitely repeated games where one player has a computable strategy that has a best response, but no computable best response. For games with discounted payoff, the result is known to hold for a specific class of games—essentially generalizations of Prisoner’s Dilemma—but until now, no necessary and sufficient condition is known. To be of any value, the computable strategy having no computable best response must be part of a subgame-perfect equilibrium, as otherwise a rational, self-interested player would not play the strategy.

We give the first necessary and sufficient conditions for a two-player repeated game \(G\) to have such a computable strategy with no computable best response for all discount factors above some threshold. The conditions involve existence of a Nash equilibrium of the repeated game whose discounted payoffs satisfy certain conditions involving the min–max payoffs of the underlying stage game. We show that it is decidable in polynomial time in the size of the payoff matrix of \(G\) whether it satisfies these conditions.

References

[1]

Kenneth Arrow and Gerard Debreu. 1954. Existence of an equilibrium for a competitive economy. Econometrica 22, 3 (1954), 265–290.

[2]

Robert J. Aumann. 1981. Survey of repeated games. Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern (1981), 11–42.

[3]

Elchanan Ben-Porath. 1990. The complexity of computing a best response automaton in repeated games with mixed strategies. Games and Economic Behavior 2, 1 (1990), 1–12.

[4]

Kimmo Berg and Mitri Kitti. 2019. Equilibrium paths in discounted supergames. Discrete Applied Mathematics 260 (2019), 1–27.

Digital Library

[5]

Kimmo Berg and Markus Kärki. 2018. Critical discount factor values in discounted supergames. Games 9, 3 (07 2018), 47.

[6]

David Blackwell. 1965. Discounted dynamic programming. Annals of Mathematical Statistics 36, 1 (02 1965), 226–235.

[7]

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou. 2010. The myth of the folk theorem. Games and Economic Behavior 70, 1 (2010), 34–43.

[8]

Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, and Shiheng Wang. 2017. K-memory strategies in repeated games. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1493–1498.

Digital Library

[9]

Lijie Chen and Pingzhong Tang. 2015. Bounded rationality of restricted turing machines. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (Istanbul, Turkey). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1673–1674.

Digital Library

[10]

Jakub Dargaj and 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. In Proceedings of the 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, Péter Biró, Jason Hartline, Michael Ostrovsky, and Ariel D. Procaccia (Eds.), ACM, 69–70.

Digital Library

[11]

F. Forges, J. F. Mertens, and A. Neyman. 1986. A counterexample to the folk theorem with discounting. Economics Letters 20, 1 (1986), 7.

[12]

Lance Fortnow and Duke Whang. 1994. Optimality and domination in repeated games with bounded players. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing. 741–749.

Digital Library

[13]

Drew Fudenberg and Eric Maskin. 1986. The folk theorem in repeated games with discounting or with incomplete information. Econometrica 54, 3 (1986), 533–554.

[14]

Drew Fudenberg and Jean Tirole. 1991. Game Theory. MIT Press, Cambridge, MA.

[15]

Itzhak Gilboa. 1988. The complexity of computing best-response automata in repeated games. Journal of Economic Theory 45, 2 (1988), 342–352.

[16]

Joseph Y. Halpern, Rafael Pass, and Lior Seeman. 2019. The truth behind the myth of the folk theorem. Games and Economic Behavior 117 (2019), 479–498.

[17]

Vicki Knoblauch. 1994. Computable strategies for repeated prisoner’s dilemma. Games and Economic Behavior 7 (1994), 381–389.

[18]

Kevin Leyton-Brown and Yoav Shoham. 2008. Essentials of Game Theory: A Concise, Multidisciplinary Introduction (1st ed.). Morgan and Claypool Publishers.

[19]

Michael L. Littman and Peter Stone. 2005. A polynomial-time nash equilibrium algorithm for repeated games. Decision Support Systems 39, 1 (2005), 55–66.

[20]

Eric Maskin and D. Fudenberg. 1991. On the dispensability of public randomization in discounted repeated games. Journal of Economic Theory 53, 2 (1991), 428–438.

[21]

Jean-François Mertens, Sylvain Sorin, and Shmuel Zamir. 2015. Repeated Games. Cambridge University Press.

[22]

John H. Nachbar and William R. Zame. 1996. Non-computable strategies and discounted repeated games. Economic Theory 8, 1 (1996), 103–122.

[23]

Abraham Neyman and Daijiro Okada. 2000. Two-person repeated games with finite automata. International Journal of Game Theory 29, 3 (2000), 309–325.

[24]

Martin J. Osborne and Ariel Rubinstein. 1994. A Course in Game Theory. The MIT Press, Cambridge. electronic edition.

[25]

Marcel K. Richter and Kam-Chau Wong. 1999. Non-computability of competitive equilibrium. Economic Theory 14, 1 (1999), 1–27.

[26]

Hartley Rogers. 1967. Theory of Recursive Functions and Effective Computability. McGraw-Hill. Reprint, MIT press 1987.

Digital Library

[27]

Ariel Rubinstein. 1986. Finite automata play the repeated prisoner’s dilemma. Journal of Economic Theory 39, 1 (1986), 83–96.

[28]

Michael Sipser. 2013. Introduction to the Theory of Computation (3rd international ed.). Cengage Learning.

[29]

Raymond M. Smullyan. 1958. Undecidability and recursive inseparability. Mathematical Logic Quarterly 4, 7–11 (1958), 143–147.

[30]

P. M. Vaidya. 1987. An algorithm for linear programming which requires o(((m+n)n2+(m+n)1.5n)l) arithmetic operations. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, New York, NY, 29–38. DOI:

Digital Library

[31]

Klaus Weihrauch. 2013. Computable Analysis: An Introduction. Springer Publishing Company.

[32]

Song Zuo and Pingzhong Tang. 2015. Optimal machine strategies to commit to in two-person repeated games. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, January 25–30, 2015, Austin, Texas. 1071–1078.

Cited By

Dargaj JSimonsen J(2023)A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoffJournal of Economic Theory10.1016/j.jet.2023.105713213(105713)Online publication date: Oct-2023
https://doi.org/10.1016/j.jet.2023.105713

Index Terms

Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Models of computation
    1. Computability

Recommendations

Computing equilibria in discounted dynamic games

Game theory (GT) is an essential formal tool for interacting entities; however computing equilibria in GT is a hard problem. When the same game can be played repeatedly over time, the problem becomes even more complicated. The existence of multiple game ...
Subgame Perfection in Positive Recursive Games with Perfect Information

We consider a class of n-player stochastic games with the following properties: (1) in every state, the transitions are controlled by one player; (2) the payoffs are equal to zero in every nonabsorbing state; (3) the payoffs are nonnegative in every ...
Some Asymptotic Results in Discounted Repeated Games of One-Sided Incomplete Information

The paper analyzes the Nash equilibria of two-person discounted repeated games with one-sided incomplete information and known own payoffs. If the informed player is arbitrarily patient, relative to the uninformed player, then the characterization for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 10, Issue 1

March 2022

149 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3505215

Editors:
David Pennock
Rutgers University, USA
,
Ilya Segal
Stanford University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2022

Accepted: 01 October 2021

Revised: 01 June 2021

Received: 01 October 2020

Published in TEAC Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dargaj JSimonsen J(2023)A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoffJournal of Economic Theory10.1016/j.jet.2023.105713213(105713)Online publication date: Oct-2023
https://doi.org/10.1016/j.jet.2023.105713

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents