Abstract
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
Original language | English |
---|---|
Title of host publication | EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation |
Number of pages | 2 |
Publisher | Association for Computing Machinery |
Publication date | 2020 |
Pages | 69-70 |
Article number | 3399520 |
ISBN (Electronic) | 9781450379755 |
DOIs | |
Publication status | Published - 2020 |
Event | 21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary Duration: 13 Jul 2020 → 17 Jul 2020 |
Conference
Conference | 21st ACM Conference on Economics and Computation, EC 2020 |
---|---|
Country/Territory | Hungary |
City | Virtual, Online |
Period | 13/07/2020 → 17/07/2020 |
Sponsor | ACM SIGecom |
Keywords
- computable strategy
- repeated game
- subgame-perfect equilibrium