IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v131y2022icp141-170.html
   My bibliography  Save this article

Best response dynamics on random graphs

Author

Listed:
  • Chellig, Jordan
  • Durbac, Calina
  • Fountoulakis, Nikolaos

Abstract

We consider evolutionary games on a population whose underlying topology of interactions is determined by a binomial random graph G(n,p). Our focus is on 2-player symmetric games with 2 strategies played between the incident members of such a population. Players update their strategies synchronously: each player selects the strategy that is the best response to the current set of strategies its neighbours play. We show that such a system reduces to generalised majority and minority dynamics. We further show rapid convergence to unanimity for p in a range that depends on a certain characteristic of the payoff matrix. In the presence of a bias among the pure Nash equilibria, we determine a sharp threshold on p above which the largest connected component reaches unanimity with high probability. For p below this critical value, we identify those substructures inside the largest component that block unanimity.

Suggested Citation

  • Chellig, Jordan & Durbac, Calina & Fountoulakis, Nikolaos, 2022. "Best response dynamics on random graphs," Games and Economic Behavior, Elsevier, vol. 131(C), pages 141-170.
    • Handle: RePEc:eee:gamebe:v:131:y:2022:i:c:p:141-170
    DOI: 10.1016/j.geb.2021.11.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825621001433
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2021.11.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Benjamini, Itai & Chan, Siu-On & O’Donnell, Ryan & Tamuz, Omer & Tan, Li-Yang, 2016. "Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs," Stochastic Processes and their Applications, Elsevier, vol. 126(9), pages 2719-2733.
    2. Itai Arieli & Yakov Babichenko & Ron Peretz & H. Peyton Young, 2020. "The Speed of Innovation Diffusion in Social Networks," Econometrica, Econometric Society, vol. 88(2), pages 569-594, March.
    3. Gilboa, Itzhak & Matsui, Akihiko, 1991. "Social Stability and Equilibrium," Econometrica, Econometric Society, vol. 59(3), pages 859-867, May.
    4. Chakrabarti, Anindya Sundar & Chakrabarti, Bikas K. & Chatterjee, Arnab & Mitra, Manipushpak, 2009. "The Kolkata Paise Restaurant problem and resource utilization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(12), pages 2420-2426.
    5. Lelarge, Marc, 2012. "Diffusion and cascading behavior in random networks," Games and Economic Behavior, Elsevier, vol. 75(2), pages 752-775.
    6. Arieli, Itai & Babichenko, Yakov & Peretz, Ron & Young, H. Peyton, 2020. "The speed of innovation diffusion in social networks," LSE Research Online Documents on Economics 102538, London School of Economics and Political Science, LSE Library.
    7. Oyama, Daisuke & Takahashi, Satoru, 2015. "Contagion and uninvadability in local interaction games: The bilingual game and general supermodular games," Journal of Economic Theory, Elsevier, vol. 157(C), pages 100-127.
    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. Sawa, Ryoji & Wu, Jiabin, 2023. "Statistical inference in evolutionary dynamics," Games and Economic Behavior, Elsevier, vol. 137(C), pages 294-316.
    2. Ryoji Sawa, 2022. "Statistical Inference in Evolutionary Dynamics," Working Papers e170, Tokyo Center for Economic Research.
    3. Srinivas Arigapudi & Yuval Heller & Amnon Schreiber, 2023. "Heterogeneous Noise and Stable Miscoordination," Papers 2305.10301, arXiv.org.
    4. Rehse, Dominik & Tremöhlen, Felix, 2020. "Fostering participation in digital public health interventions: The case of digital contact tracing," ZEW Discussion Papers 20-076, ZEW - Leibniz Centre for European Economic Research.
    5. Marcel Fafchamps & Måns Söderbom & Monique van den Boogart, 2022. "Adoption with Social Learning and Network Externalities," Oxford Bulletin of Economics and Statistics, Department of Economics, University of Oxford, vol. 84(6), pages 1259-1282, December.
    6. Delia Coculescu & M'ed'eric Motte & Huy^en Pham, 2023. "Opinion dynamics in communities with major influencers and implicit social influence via mean-field approximation," Papers 2306.16553, arXiv.org.
    7. , & , H. & ,, 2015. "Sampling best response dynamics and deterministic equilibrium selection," Theoretical Economics, Econometric Society, vol. 10(1), January.
    8. Trieste, Leopoldo & Geisler, Elie & Turchetti, Giuseppe, 2022. "Columbus' egg and the engineer's effect in forecasting solutions adoption," Technological Forecasting and Social Change, Elsevier, vol. 183(C).
    9. Kobayashi, Teruyoshi & Ogisu, Yoshitaka & Onaga, Tomokatsu, 2023. "Unstable diffusion in social networks," Journal of Economic Dynamics and Control, Elsevier, vol. 146(C).
    10. Julian Hidalgo & Michelle Sovinsky, 2023. "Internet (Power) to the People: How to Bridge the Digital Divide," CRC TR 224 Discussion Paper Series crctr224_2023_461, University of Bonn and University of Mannheim, Germany.
    11. Gong, Qingbin & Diao, Xundi, 2023. "The impacts of investor network and herd behavior on market stability: Social learning, network structure, and heterogeneity," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1388-1398.
    12. Ruoxi Ma & Shangguang Yang, 2023. "The Effect of Social Network on Controlled-Release Fertilizer Use: Evidence from Rice Large-Scale Farmers in Jiangsu Province, China," Sustainability, MDPI, vol. 15(4), pages 1-16, February.
    13. Rehse, Dominik & Tremöhlen, Felix, 2022. "Fostering participation in digital contact tracing," Information Economics and Policy, Elsevier, vol. 58(C).
    14. Teruyoshi Kobayashi & Tomokatsu Onaga, 2023. "Dynamics of diffusion on monoplex and multiplex networks: a message-passing approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(1), pages 251-287, July.
    15. Anindya S. Chakrabarti & Diptesh Ghosh, 2019. "Emergence of anti-coordination through reinforcement learning in generalized minority games," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 14(2), pages 225-245, June.
    16. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    17. , & , & ,, 2008. "Monotone methods for equilibrium selection under perfect foresight dynamics," Theoretical Economics, Econometric Society, vol. 3(2), June.
    18. Tsakas, Elias & Voorneveld, Mark, 2009. "The target projection dynamic," Games and Economic Behavior, Elsevier, vol. 67(2), pages 708-719, November.
    19. Sandholm,W.H., 2003. "Excess payoff dynamics, potential dynamics, and stable games," Working papers 5, Wisconsin Madison - Social Systems.
    20. 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.

    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:eee:gamebe:v:131:y:2022:i:c:p:141-170. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.