Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria. / Dargaj, Jakub; Simonsen, Jakob Grue.
I: ACM Transactions on Economics and Computation, Bind 10, Nr. 1, 3, 2022, s. 1-39.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria
AU - Dargaj, Jakub
AU - Simonsen, Jakob Grue
N1 - Publisher Copyright: © 2022 Association for Computing Machinery.
PY - 2022
Y1 - 2022
N2 - 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 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 whether it satisfies these conditions.
AB - 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 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 whether it satisfies these conditions.
KW - best response strategies
KW - discounted payoff
KW - Nash equilibria
KW - Repeated games
KW - subgame-perfect equilibria
U2 - 10.1145/3505585
DO - 10.1145/3505585
M3 - Journal article
AN - SCOPUS:85130965183
VL - 10
SP - 1
EP - 39
JO - ACM Transactions on Economics and Computation
JF - ACM Transactions on Economics and Computation
SN - 2167-8375
IS - 1
M1 - 3
ER -
ID: 309122306