IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2408.11146.html
   My bibliography  Save this paper

Swim till You Sink: Computing the Limit of a Game

Author

Listed:
  • Rashida Hakim
  • Jason Milionis
  • Christos Papadimitriou
  • Georgios Piliouras

Abstract

During 2023, two interesting results were proven about the limit behavior of game dynamics: First, it was shown that there is a game for which no dynamics converges to the Nash equilibria. Second, it was shown that the sink equilibria of a game adequately capture the limit behavior of natural game dynamics. These two results have created a need and opportunity to articulate a principled computational theory of the meaning of the game that is based on game dynamics. Given any game in normal form, and any prior distribution of play, we study the problem of computing the asymptotic behavior of a class of natural dynamics called the noisy replicator dynamics as a limit distribution over the sink equilibria of the game. When the prior distribution has pure strategy support, we prove this distribution can be computed efficiently, in near-linear time to the size of the best-response graph. When the distribution can be sampled -- for example, if it is the uniform distribution over all mixed strategy profiles -- we show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.

Suggested Citation

  • Rashida Hakim & Jason Milionis & Christos Papadimitriou & Georgios Piliouras, 2024. "Swim till You Sink: Computing the Limit of a Game," Papers 2408.11146, arXiv.org.
    • Handle: RePEc:arx:papers:2408.11146
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2408.11146
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shayegan Omidshafiei & Karl Tuyls & Wojciech M. Czarnecki & Francisco C. Santos & Mark Rowland & Jerome Connor & Daniel Hennes & Paul Muller & Julien Pérolat & Bart De Vylder & Audrunas Gruslys & Rémi, 2020. "Navigating the landscape of multiplayer games," Nature Communications, Nature, vol. 11(1), pages 1-17, December.
    2. H. Peyton Young, 2007. "The Possible and the Impossible in Multi-Agent Learning," Economics Series Working Papers 304, University of Oxford, Department of Economics.
    3. Pangallo, Marco & Farmer, J. Doyne & Sanders, James & Galla, Tobias, 2017. "A taxonomy of learning dynamics in 2 × 2 games," INET Oxford Working Papers 2017-06, Institute for New Economic Thinking at the Oxford Martin School, University of Oxford.
    4. Young, H Peyton, 1993. "The Evolution of Conventions," Econometrica, Econometric Society, vol. 61(1), pages 57-84, January.
    5. Sergiu Hart & Andreu Mas-Colell, 2013. "Uncoupled Dynamics Do Not Lead To Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 7, pages 153-163, World Scientific Publishing Co. Pte. Ltd..
    6. Babichenko, Yakov, 2012. "Completely uncoupled dynamics and Nash equilibria," Games and Economic Behavior, Elsevier, vol. 76(1), pages 1-14.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jonathan Newton, 2018. "Evolutionary Game Theory: A Renaissance," Games, MDPI, vol. 9(2), pages 1-67, May.
    2. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Oct 2024.
    3. Nax, Heinrich H., 2015. "Equity dynamics in bargaining without information exchange," LSE Research Online Documents on Economics 65426, London School of Economics and Political Science, LSE Library.
    4. Heinrich Nax, 2015. "Equity dynamics in bargaining without information exchange," Journal of Evolutionary Economics, Springer, vol. 25(5), pages 1011-1026, November.
    5. Arnaud Z. Dragicevic, 2019. "Market Coordination Under Non-Equilibrium Dynamics," Networks and Spatial Economics, Springer, vol. 19(3), pages 697-715, September.
    6. Jean-François Laslier & Bernard Walliser, 2015. "Stubborn learning," Theory and Decision, Springer, vol. 79(1), pages 51-93, July.
    7. Yakov Babichenko, 2010. "Completely Uncoupled Dynamics and Nash Equilibria," Discussion Paper Series dp529, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    8. Saran, R.R.S. & Serrano, R., 2010. "Ex-Post regret learning in games with fixed and random matching: the case of private values," Research Memorandum 032, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    9. Young, H. Peyton, 2009. "Learning by trial and error," Games and Economic Behavior, Elsevier, vol. 65(2), pages 626-643, March.
    10. Johannes Zschache, 2017. "The Explanation of Social Conventions by Melioration Learning," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 20(3), pages 1-1.
    11. Anke Gerber & Thorsten Hens & Bodo Vogt, "undated". "Coordination in a Repeated Stochastic Game with Imperfect Monitoring," IEW - Working Papers 126, Institute for Empirical Research in Economics - University of Zurich.
    12. Marden, Jason R. & Shamma, Jeff S., 2015. "Game Theory and Distributed Control****Supported AFOSR/MURI projects #FA9550-09-1-0538 and #FA9530-12-1-0359 and ONR projects #N00014-09-1-0751 and #N0014-12-1-0643," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. Lahkar, Ratul, 2017. "Equilibrium selection in the stag hunt game under generalized reinforcement learning," Journal of Economic Behavior & Organization, Elsevier, vol. 138(C), pages 63-68.
    14. Lim, Wooyoung & Neary, Philip R., 2016. "An experimental investigation of stochastic adjustment dynamics," Games and Economic Behavior, Elsevier, vol. 100(C), pages 208-219.
    15. Cartwright, Edward, 2003. "Imitation and the Emergence of Nash Equilibrium Play in Games with Many Players," The Warwick Economics Research Paper Series (TWERPS) 684, University of Warwick, Department of Economics.
    16. Balkenborg, Dieter & Hofbauer, Josef & Kuzmics, Christoph, 2016. "Refined best reply correspondence and dynamics," Center for Mathematical Economics Working Papers 451, Center for Mathematical Economics, Bielefeld University.
    17. Babichenko, Yakov & Rubinstein, Aviad, 2022. "Communication complexity of approximate Nash equilibria," Games and Economic Behavior, Elsevier, vol. 134(C), pages 376-398.
    18. Jindani, Sam, 2022. "Learning efficient equilibria in repeated games," Journal of Economic Theory, Elsevier, vol. 205(C).
    19. Saran, Rene & Serrano, Roberto, 2014. "Ex-post regret heuristics under private values (I): Fixed and random matching," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 97-111.
    20. Pradelski, Bary S.R. & Young, H. Peyton, 2012. "Learning efficient Nash equilibria in distributed systems," Games and Economic Behavior, Elsevier, vol. 75(2), pages 882-897.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2408.11146. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.