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. 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).
    5. 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.
    6. 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).
    7. Michael Kearns & Aaron Roth & Emily Ryu, 2025. "Networked Information Aggregation via Machine Learning," Papers 2507.09683, arXiv.org, revised Oct 2025.
    8. Gilles Duranton, 1997. "La nouvelle économie géographique : agglomération et dispersion," Économie et Prévision, Programme National Persée, vol. 131(5), pages 1-24.
    9. Xiong, Hang & Payne, Diane & Kinsella, Stephen, 2016. "Peer effects in the diffusion of innovations: Theory and simulation," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 63(C), pages 1-13.
    10. Abhimanyu Khan, 2014. "Coordination under global random interaction and local imitation," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 721-745, November.
    11. Jadbabaie, Ali & Molavi, Pooya & Sandroni, Alvaro & Tahbaz-Salehi, Alireza, 2012. "Non-Bayesian social learning," Games and Economic Behavior, Elsevier, vol. 76(1), pages 210-225.
    12. Atmaca, Sümeyra & Schoors, Koen & Verschelde, Marijn, 2020. "Bank loyalty, social networks and crisis," Journal of Banking & Finance, Elsevier, vol. 112(C).
    13. Cabrales, Antonio & Charness, Gary, 2011. "Optimal contracts with team production and hidden information: An experiment," Journal of Economic Behavior & Organization, Elsevier, vol. 77(2), pages 163-176, February.
    14. Alessandro Stanziani, 2004. "Wine Reputation and Quality Controls: The Origin of the AOCs in 19th Century France," European Journal of Law and Economics, Springer, vol. 18(2), pages 149-167, September.
    15. Larson, Nathan, 2004. "Match choice and Ghettoization in evolutionary games," Journal of Economic Theory, Elsevier, vol. 117(1), pages 1-28, July.
    16. Sobel, Joel, 2000. "Economists' Models of Learning," Journal of Economic Theory, Elsevier, vol. 94(2), pages 241-261, October.
    17. Charness, Gary & Corominas-Bosch, Margarida & Frechette, Guillaume R., 2007. "Bargaining and network structure: An experiment," Journal of Economic Theory, Elsevier, vol. 136(1), pages 28-65, September.
    18. Marra, Michele & Pannell, David J. & Abadi Ghadim, Amir, 2003. "The economics of risk, uncertainty and learning in the adoption of new agricultural technologies: where are we on the learning curve?," Agricultural Systems, Elsevier, vol. 75(2-3), pages 215-234.
    19. Zhengzheng Pan, 2012. "Opinions and Networks: How Do They Effect Each Other," Computational Economics, Springer;Society for Computational Economics, vol. 39(2), pages 157-171, February.
    20. Antoine Feylessoufi & Stylianos Kavadias & Daniel Ralph, 2024. "Behavioral Microfoundations of New Practice Adoption: The Effects of Rewards, Training and Population Dynamics," Management Science, INFORMS, vol. 70(10), pages 6685-6703, October.

    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.