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

Finding pure Nash equilibria in large random games

Author

Listed:
  • Andrea Collevecchio
  • Tuan-Minh Nguyen
  • Ziwen Zhong

Abstract

Best Response Dynamics (BRD) is a class of strategy updating rules to find Pure Nash Equilibria (PNE) in a game. At each step, a player is randomly picked, and the player switches to a "best response" strategy based on the strategies chosen by others, so that the new strategy profile maximises their payoff. If no such strategy exists, a different player will be chosen randomly. When no player wants to change their strategy anymore, the process reaches a PNE and will not deviate from it. On the other hand, either PNE may not exist, or BRD could be "trapped" within a subgame that has no PNE. We consider a random game with $N$ players, each with two actions available, and i.i.d. payoffs, in which the payoff distribution may have an atom, i.e. ties are allowed. We study a class of random walks in a random medium on the $N$-dimensional hypercube induced by the random game. The medium contains two types of obstacles corresponding to PNE and traps. The class of processes we analyze includes BRD, simple random walks on the hypercube, and many other nearest neighbour processes. We prove that, with high probability, these processes reach a PNE before hitting any trap.

Suggested Citation

  • Andrea Collevecchio & Tuan-Minh Nguyen & Ziwen Zhong, 2024. "Finding pure Nash equilibria in large random games," Papers 2406.09732, arXiv.org, revised Aug 2024.
    • Handle: RePEc:arx:papers:2406.09732
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Rinott, Yosef & Scarsini, Marco, 2000. "On the Number of Pure Strategy Nash Equilibria in Random Games," Games and Economic Behavior, Elsevier, vol. 33(2), pages 274-293, November.
    2. Noga Alon & Kirill Rudov & Leeat Yariv, 2021. "Dominance Solvability in Random Games," Working Papers 2021-84, Princeton University. Economics Department..
    3. Gilboa, Itzhak & Matsui, Akihiko, 1991. "Social Stability and Equilibrium," Econometrica, Econometric Society, vol. 59(3), pages 859-867, May.
    4. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, January.
    5. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, December.
    6. Mimun, Hlafo Alfie & Quattropani, Matteo & Scarsini, Marco, 2024. "Best-response dynamics in two-person random games with correlated payoffs," Games and Economic Behavior, Elsevier, vol. 145(C), pages 239-262.
    7. Powers, Imelda Yeung, 1990. "Limiting Distributions of the Number of Pure Strategy Nash Equilibria in N-Person Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(3), pages 277-286.
    8. Noga Alon & Kirill Rudov & Leeat Yariv, 2021. "Dominance Solvability in Random Games," Papers 2105.10743, arXiv.org.
    9. Matsui, Akihiko, 1992. "Best response dynamics and socially stable strategies," Journal of Economic Theory, Elsevier, vol. 57(2), pages 343-362, August.
    10. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2023. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 703-735, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Andrea Collevecchio & Hlafo Alfie Mimun & Matteo Quattropani & Marco Scarsini, 2024. "Basins of Attraction in Two-Player Random Ordinal Potential Games," Papers 2407.05460, arXiv.org.

    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. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Nov 2023.
    2. Andrea Collevecchio & Hlafo Alfie Mimun & Matteo Quattropani & Marco Scarsini, 2024. "Basins of Attraction in Two-Player Random Ordinal Potential Games," Papers 2407.05460, arXiv.org.
    3. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2023. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 703-735, September.
    4. Mimun, Hlafo Alfie & Quattropani, Matteo & Scarsini, Marco, 2024. "Best-response dynamics in two-person random games with correlated payoffs," Games and Economic Behavior, Elsevier, vol. 145(C), pages 239-262.
    5. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2021. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," Papers 2101.04222, arXiv.org, revised Nov 2022.
    6. Ben Amiet & Andrea Collevecchio & Marco Scarsini & Ziwen Zhong, 2021. "Pure Nash Equilibria and Best-Response Dynamics in Random Games," Mathematics of Operations Research, INFORMS, vol. 46(4), pages 1552-1572, November.
    7. Pangallo, Marco & Heinrich, Torsten & Jang, Yoojin & Scott, Alex & Tarbush, Bassel & Wiese, Samuel & Mungo, Luca, 2021. "Best-Response Dynamics, Playing Sequences, And Convergence To Equilibrium In Random Games," INET Oxford Working Papers 2021-23, Institute for New Economic Thinking at the Oxford Martin School, University of Oxford.
    8. Arieli, Itai & Babichenko, Yakov, 2016. "Random extensive form games," Journal of Economic Theory, Elsevier, vol. 166(C), pages 517-535.
    9. Takahashi, Satoru, 2008. "The number of pure Nash equilibria in a random game with nondecreasing best responses," Games and Economic Behavior, Elsevier, vol. 63(1), pages 328-340, May.
    10. Szabó, György & Borsos, István & Szombati, Edit, 2019. "Games, graphs and Kirchhoff laws," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 416-423.
    11. Pei, Ting & Takahashi, Satoru, 2019. "Rationalizable strategies in random games," Games and Economic Behavior, Elsevier, vol. 118(C), pages 110-125.
    12. Sandholm,W.H., 2003. "Excess payoff dynamics, potential dynamics, and stable games," Working papers 5, Wisconsin Madison - Social Systems.
    13. Viossat, Yannick, 2008. "Evolutionary dynamics may eliminate all strategies used in correlated equilibrium," Mathematical Social Sciences, Elsevier, vol. 56(1), pages 27-43, July.
    14. Antonio Cabrales & Giovanni Ponti, 2000. "Implementation, Elimination of Weakly Dominated Strategies and Evolutionary Dynamics," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 3(2), pages 247-282, April.
    15. Thijssen, J.J.J., 2003. "Investment under uncertainty, market evolution and coalition spillovers in a game theoretic perspective," Other publications TiSEM 672073a6-492e-4621-8d4a-0, Tilburg University, School of Economics and Management.
    16. Christoph Kuzmics & Daniel Rodenburger, 2018. "A case of evolutionary stable attainable equilibrium in the lab," Graz Economics Papers 2018-05, University of Graz, Department of Economics.
    17. Hofbauer, Josef & Hopkins, Ed, 2005. "Learning in perturbed asymmetric games," Games and Economic Behavior, Elsevier, vol. 52(1), pages 133-152, July.
    18. Christoph Kuzmics & Daniel Rodenburger, 2020. "A case of evolutionarily stable attainable equilibrium in the laboratory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 685-721, October.
    19. Ewerhart, Christian & Valkanova, Kremena, 2020. "Fictitious play in networks," Games and Economic Behavior, Elsevier, vol. 123(C), pages 182-206.
    20. Andreas Blume, 1995. "Information Transmission and Preference Similarity," Game Theory and Information 9504002, University Library of Munich, Germany, revised 29 May 1996.

    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:2406.09732. 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.