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 -