IDEAS home Printed from https://ideas.repec.org/a/eee/spapps/v189y2025ics0304414925001231.html

Majority dynamics on random graphs: The multiple states case

Author

Listed:
  • Chellig, Jordan
  • Fountoulakis, Nikolaos

Abstract

We study the evolution of majority dynamics with more than two states on the binomial random graph G(n,p). In this process, each vertex has a state in {1,…,k}, with k≥3, and at each round every vertex adopts state i if it has more neighbours in state i than in any other state. Ties are resolved randomly. We show that with high probability the process reaches unanimity in at most three rounds, if np≫n2/3.

Suggested Citation

  • Chellig, Jordan & Fountoulakis, Nikolaos, 2025. "Majority dynamics on random graphs: The multiple states case," Stochastic Processes and their Applications, Elsevier, vol. 189(C).
    • Handle: RePEc:eee:spapps:v:189:y:2025:i:c:s0304414925001231
    DOI: 10.1016/j.spa.2025.104682
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304414925001231
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.spa.2025.104682?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

    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. Berkowitz, Ross & Devlin, Pat, 2022. "Central limit theorem for majority dynamics: Bribing three voters suffices," Stochastic Processes and their Applications, Elsevier, vol. 146(C), pages 187-206.
    3. Ellison, Glenn & Fudenberg, Drew, 1993. "Rules of Thumb for Social Learning," Journal of Political Economy, University of Chicago Press, vol. 101(4), pages 612-643, August.
    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. Berkowitz, Ross & Devlin, Pat, 2022. "Central limit theorem for majority dynamics: Bribing three voters suffices," Stochastic Processes and their Applications, Elsevier, vol. 146(C), pages 187-206.
    2. Jonas Hedlund & Carlos Oyarzun, 2018. "Imitation in heterogeneous populations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(4), pages 937-973, June.
    3. Buechel, Berno & Hellmann, Tim & Klößner, Stefan, 2015. "Opinion dynamics and wisdom under conformity," Journal of Economic Dynamics and Control, Elsevier, vol. 52(C), pages 240-257.
    4. Sanjeev Goyal & Fernando Vega-Redondo, 2000. "Learning, Network Formation and Coordination," Econometric Society World Congress 2000 Contributed Papers 0113, Econometric Society.
    5. B Kelsey Jack, "undated". "Market Inefficiencies and the Adoption of Agricultural Technologies in Developing Countries," CID Working Papers 50, Center for International Development at Harvard University.
    6. Tan, Xiujie & Yan, Yaxue & Dong, Yuyang, 2022. "Peer effect in green credit induced green innovation: An empirical study from China's Green Credit Guidelines," Resources Policy, Elsevier, vol. 76(C).
    7. Lahno, Amrei M. & Serra-Garcia, Marta, 2012. "Peer Effects in Risk Taking," Discussion Papers in Economics 14309, University of Munich, Department of Economics.
    8. Horst, Ulrich & Scheinkman, Jose A., 2006. "Equilibria in systems of social interactions," Journal of Economic Theory, Elsevier, vol. 130(1), pages 44-77, September.
    9. Amir, Gideon & Arieli, Itai & Ashkenazi-Golan, Galit & Peretz, Ron, 2025. "Granular DeGroot dynamics – A model for robust naive learning in social networks," Journal of Economic Theory, Elsevier, vol. 223(C).
    10. Davide Crapis & Bar Ifrach & Costis Maglaras & Marco Scarsini, 2017. "Monopoly Pricing in the Presence of Social Learning," Management Science, INFORMS, vol. 63(11), pages 3586-3608, November.
    11. Fang, Ming & Francis, Bill & Hasan, Iftekhar & Wu, Qiang, 2022. "External social networks and earnings management," The British Accounting Review, Elsevier, vol. 54(2).
    12. Sommarat Chantarat & Christopher Barrett, 2012. "Social network capital, economic mobility and poverty traps," The Journal of Economic Inequality, Springer;Society for the Study of Economic Inequality, vol. 10(3), pages 299-342, September.
    13. Osili, Una Okonkwo & Paulson, Anna, 2014. "Crises and confidence: Systemic banking crises and depositor behavior," Journal of Financial Economics, Elsevier, vol. 111(3), pages 646-660.
    14. Li, Mengjia & Ding, Wenjie & Li, Hao & Wang, Qingwei & Xiao, Jason Zezhong, 2025. "Sell-side financial analyst social network and forecast accuracy," International Review of Economics & Finance, Elsevier, vol. 103(C).
    15. Tat Y. Chan & Jia Li & Lamar Pierce, 2014. "Learning from Peers: Knowledge Transfer and Sales Force Productivity Growth," Marketing Science, INFORMS, vol. 33(4), pages 463-484, July.
    16. Bisin, Alberto & Horst, Ulrich & Ozgur, Onur, 2006. "Rational expectations equilibria of economies with local interactions," Journal of Economic Theory, Elsevier, vol. 127(1), pages 74-116, March.
    17. Jim Malley & Apostolis Philippopoulos, 1999. "Economic Growth And Endogenous Fiscal Policy: In Search Of A Data Consistent General Equilibrium Model," Working Papers 1999_18, Business School - Economics, University of Glasgow, revised Jan 1998.
    18. Michael Kearns & Aaron Roth & Emily Ryu, 2025. "Networked Information Aggregation via Machine Learning," Papers 2507.09683, arXiv.org, revised Oct 2025.
    19. Yamauchi, Futoshi, 2007. "Social learning, neighborhood effects, and investment in human capital: Evidence from Green-Revolution India," Journal of Development Economics, Elsevier, vol. 83(1), pages 37-62, May.
    20. Rodepeter, Ralf & Winter, Joachim, 1999. "Rules of thumb in life-cycle savings models," Sonderforschungsbereich 504 Publications 99-81, Sonderforschungsbereich 504, Universität Mannheim;Sonderforschungsbereich 504, University of Mannheim.

    More about this item

    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:eee:spapps:v:189:y:2025:i:c:s0304414925001231. 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/wps/find/journaldescription.cws_home/505572/description#description .

    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.