A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff. / Dargaj, Jakub; Simonsen, Jakob Grue.
I: Journal of Economic Theory, Bind 213, 105713, 2023.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff
AU - Dargaj, Jakub
AU - Simonsen, Jakob Grue
N1 - Publisher Copyright: © 2023 Elsevier Inc.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Best response strategies
KW - Computability
KW - Limit-of-means payoff
KW - Repeated games
KW - Subgame-perfect equilibria
U2 - 10.1016/j.jet.2023.105713
DO - 10.1016/j.jet.2023.105713
M3 - Journal article
AN - SCOPUS:85168727575
VL - 213
JO - Journal of Economic Theory
JF - Journal of Economic Theory
SN - 0022-0531
M1 - 105713
ER -
ID: 371569990