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

Dargaj, J & Simonsen, JG 2020, A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff. in EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation., 3399520, Association for Computing Machinery, pp. 69-70, 21st ACM Conference on Economics and Computation, EC 2020, Virtual, Online, Hungary, 13/07/2020. https://doi.org/10.1145/3391403.3399520

APA

Dargaj, J., & Simonsen, J. G. (2020). A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 69-70). [3399520] Association for Computing Machinery. https://doi.org/10.1145/3391403.3399520

Vancouver

Dargaj J, Simonsen JG. A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation. Association for Computing Machinery. 2020. p. 69-70. 3399520 https://doi.org/10.1145/3391403.3399520

Author

Dargaj, Jakub ; Simonsen, Jakob Grue. / A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff. EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation. Association for Computing Machinery, 2020. pp. 69-70

Bibtex

@inproceedings{e1725c630efd499798371fa0bff62d09,
title = "A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff",
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",
keywords = "computable strategy, repeated game, subgame-perfect equilibrium",
author = "Jakub Dargaj and Simonsen, {Jakob Grue}",
year = "2020",
doi = "10.1145/3391403.3399520",
language = "English",
pages = "69--70",
booktitle = "EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation",
publisher = "Association for Computing Machinery",
note = "21st ACM Conference on Economics and Computation, EC 2020 ; Conference date: 13-07-2020 Through 17-07-2020",

}

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