Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Accepteret manuskript, 855 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Artikelnummer | 3 |
Tidsskrift | ACM Transactions on Economics and Computation |
Vol/bind | 10 |
Udgave nummer | 1 |
Sider (fra-til) | 1-39 |
ISSN | 2167-8375 |
DOI | |
Status | Udgivet - 2022 |
Bibliografisk note
Publisher Copyright:
© 2022 Association for Computing Machinery.
ID: 309122306