A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff

Jakub Dargaj, Jakob Grue Simonsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 Citation (Scopus)
35 Downloads (Pure)

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 languageEnglish
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
Number of pages2
PublisherAssociation for Computing Machinery
Publication date2020
Pages69-70
Article number3399520
ISBN (Electronic)9781450379755
DOIs
Publication statusPublished - 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: 13 Jul 202017 Jul 2020

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
Country/TerritoryHungary
CityVirtual, Online
Period13/07/202017/07/2020
SponsorACM SIGecom

Keywords

  • computable strategy
  • repeated game
  • subgame-perfect equilibrium

Cite this