A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation. Association for Computing Machinery, 2020. p. 69-70 3399520.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
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
PY - 2020
Y1 - 2020
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. Full version: https://arxiv.org/abs/2005.13921
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. Full version: https://arxiv.org/abs/2005.13921
KW - computable strategy
KW - repeated game
KW - subgame-perfect equilibrium
UR - http://www.scopus.com/inward/record.url?scp=85089280150&partnerID=8YFLogxK
U2 - 10.1145/3391403.3399520
DO - 10.1145/3391403.3399520
M3 - Article in proceedings
AN - SCOPUS:85089280150
SP - 69
EP - 70
BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 21st ACM Conference on Economics and Computation, EC 2020
Y2 - 13 July 2020 through 17 July 2020
ER -
ID: 260413489