{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T21:09:54Z","timestamp":1758402594783,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>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\u2014essentially generalizations of Prisoner\u2019s Dilemma\u2014but 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.<\/jats:p>\n          <jats:p>\n            We give the first necessary and sufficient conditions for a two-player repeated game\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to have such a\u00a0computable 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\u2013max payoffs of the underlying stage game. We show that it is decidable in polynomial time in the size of the payoff matrix of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            whether it satisfies these conditions.\n          <\/jats:p>","DOI":"10.1145\/3505585","type":"journal-article","created":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T09:06:33Z","timestamp":1649408793000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect Equilibria"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3658-3642","authenticated-orcid":false,"given":"Jakub","family":"Dargaj","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Universitetsparken, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3488-9392","authenticated-orcid":false,"given":"Jakob Grue","family":"Simonsen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, Universitetsparken, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2022,4,8]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_3_4_3_2","first-page":"11","article-title":"Survey of repeated games","author":"Aumann Robert J.","year":"1981","unstructured":"Robert J. Aumann. 1981. Survey of repeated games. Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern (1981), 11\u201342.","journal-title":"Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(90)90010-R"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.026"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.3390\/g9030047"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700285"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.04.016"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/3091125.3091340"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/2772879.2773379"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399520"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1765(86)90069-8"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195448"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/1911307"},{"key":"e_1_3_4_15_2","volume-title":"Game Theory","author":"Fudenberg Drew","year":"1991","unstructured":"Drew Fudenberg and Jean Tirole. 1991. Game Theory. MIT Press, Cambridge, MA."},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(88)90274-8"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2019.04.008"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1994.1057"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01545-8"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.007"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(91)90163-X"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139343275"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212014"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001820000040"},{"key":"e_1_3_4_25_2","volume-title":"A Course in Game Theory","author":"Osborne Martin J.","year":"1994","unstructured":"Martin J. Osborne and Ariel Rubinstein. 1994. A Course in Game Theory. The MIT Press, Cambridge. electronic edition."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001990050281"},{"key":"e_1_3_4_27_2","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers Hartley","year":"1967","unstructured":"Hartley Rogers. 1967. Theory of Recursive Functions and Effective Computability. McGraw-Hill. Reprint, MIT press 1987."},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(86)90021-9"},{"key":"e_1_3_4_29_2","volume-title":"Introduction to the Theory of Computation (3rd international ed.)","author":"Sipser Michael","year":"2013","unstructured":"Michael Sipser. 2013. Introduction to the Theory of Computation (3rd international ed.). Cengage Learning."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19580040705"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28399"},{"key":"e_1_3_4_32_2","volume-title":"Computable Analysis: An Introduction","author":"Weihrauch Klaus","year":"2013","unstructured":"Klaus Weihrauch. 2013. Computable Analysis: An Introduction. Springer Publishing Company."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9295"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505585","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3505585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:24Z","timestamp":1750182564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3505585"],"URL":"https:\/\/doi.org\/10.1145\/3505585","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}