Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3391403.3399520acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
abstract

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

Published: 13 July 2020 Publication History

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

References

[1]
Vicki Knoblauch. 1994. Computable Strategies for Repeated Prisoner's Dilemma. Games and Economic Behavior 7 (1994), 381--389.
[2]
John H. Nachbar and William R. Zame. 1996. Non-computable strategies and discounted repeated games. Economic Theory 8, 1 (1996), 103--122.

Cited By

View all
  • (2024)What Can We Know About That Which We Cannot Even Imagine?New Frontiers in Science in the Era of AI10.1007/978-3-031-61187-2_15(301-331)Online publication date: 11-Oct-2024
  • (2022)Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect EquilibriaACM Transactions on Economics and Computation10.1145/350558510:1(1-39)Online publication date: 8-Apr-2022

Index Terms

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

        Recommendations

        Comments

        Please enable JavaScript to view thecomments powered by Disqus.

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
        July 2020
        937 pages
        ISBN:9781450379755
        DOI:10.1145/3391403
        Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 13 July 2020

        Check for updates

        Author Tags

        1. computable strategy
        2. repeated game
        3. subgame-perfect equilibrium

        Qualifiers

        • Abstract

        Conference

        EC '20
        Sponsor:
        EC '20: The 21st ACM Conference on Economics and Computation
        July 13 - 17, 2020
        Virtual Event, Hungary

        Acceptance Rates

        Overall Acceptance Rate 664 of 2,389 submissions, 28%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)2
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 09 Nov 2024

        Other Metrics

        Citations

        Cited By

        View all
        • (2024)What Can We Know About That Which We Cannot Even Imagine?New Frontiers in Science in the Era of AI10.1007/978-3-031-61187-2_15(301-331)Online publication date: 11-Oct-2024
        • (2022)Discounted Repeated Games Having Computable Strategies with No Computable Best Response under Subgame-Perfect EquilibriaACM Transactions on Economics and Computation10.1145/350558510:1(1-39)Online publication date: 8-Apr-2022

        View Options

        Get Access

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media