Document Open Access Logo

Asynchronous Majority Dynamics in Preferential Attachment Trees

Authors Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.8.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Maryam Bahrani
  • Princeton University, NJ, USA
Nicole Immorlica
  • Microsoft Research, Cambridge, MA, USA
Divyarthi Mohan
  • Princeton University, NJ, USA
S. Matthew Weinberg
  • Princeton University, NJ, USA

Funding

  • Weinberg, S. Matthew: Supported by NSF CCF-1717899.

Cite AsGet BibTex

Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, and S. Matthew Weinberg. Asynchronous Majority Dynamics in Preferential Attachment Trees. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.8

Abstract

We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability 1/2+δ. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model [Barabási and Albert, 1999], with high probability, the process stabilizes in a correct majority within O(n log n/log log n) rounds. We extend our results to other tree structures, including balanced M-ary trees for any M.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
  • Networks → Network dynamics
Keywords
  • Opinion Dynamics
  • Information Cascades
  • Preferential Attachment
  • Majority Dynamics
  • non-Bayesian Asynchronous Learning
  • Stochastic Processes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mohammed Amin Abdullah, Michel Bode, and Nikolaos Fountoulakis. Local majority dynamics on preferential attachment graphs. In Proceedings of the 12th International Workshop on Algorithms and Models for the Web Graph - Volume 9479, WAW 2015, pages 95-106, Berlin, Heidelberg, 2015. Springer-Verlag. URL: https://doi.org/10.1007/978-3-319-26784-5_8.
  2. Daron Acemoglu, Munther A. Dahleh, Ilan Lobel, and Asuman Ozdaglar. Bayesian learning in social networks. Review of Economic Studies, 78(4):1201-1236, 2011. Google Scholar
  3. Abhijit Banerjee and Drew Fudenberg. Word-of-mouth learning. Games and Economic Behavior, 46(1):1-22, January 2004. URL: http://ideas.repec.org/a/eee/gamebe/v46y2004i1p1-22.html.
  4. Abhijit V. Banerjee. A simple model of herd behavior. The Quarterly Journal of Economics, 107(3):797-817, 1992. Google Scholar
  5. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. URL: https://doi.org/10.1126/science.286.5439.509.
  6. Luca Bechetti, Andrea E.F. Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In ACM Symposium on Discrete Algorithms (SODA), 2016. Google Scholar
  7. Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. A theory of fads, fashion, custom, and cultural change in informational cascades. Journal of Political Economy, 100(5):992-1026, October 1992. Google Scholar
  8. Béla Bollobás and Oliver Riordan. The diameter of a scale-free random graph. Combinatorica, 24(1):5-34, 2004. URL: https://doi.org/10.1007/s00493-004-0002-2.
  9. Béla Bollobás, Oliver Riordan, Joel Spencer, and Gábor E. Tusnády. The degree sequence of a scale-free random graph process. Random Struct. Algorithms, 18(3):279-290, 2001. URL: https://doi.org/10.1002/rsa.1009.
  10. Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika, 60(3):581-588, 1973. URL: http://www.jstor.org/stable/2335008.
  11. Morris H. DeGroot. Reaching a consensus. Review of Economic Studies, 69(345):118-121, 1974. Google Scholar
  12. Michal Feldman, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. Reaching consensus via non-bayesian asynchronous learning in social networks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.192.
  13. Douglas Gale and Shachar Kariv. Bayesian learning in social networks. Games and Economic Behavior, 45(2):329-346, 2003. Special Issue in Honor of Robert W. Rosenthal. URL: https://doi.org/10.1016/S0899-8256(03)00144-1.
  14. Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In ACM Symposium on Principles of Distributed Computing (PODC), 2018. Google Scholar
  15. Mohsen Ghaffari and Merav Parter. A polylogarithmic gossip algorithm for plurality consensus. In ACM Symposium on Principles of Distributed Computing (PODC), 2016. Google Scholar
  16. Benjamin Golub and Matthew O. Jackson. Naïve learning in social networks and the wisdom of crowds. American Economic Journal: Microeconomics, 2(1):112-149, 2010. Google Scholar
  17. Vicenç Gómez, Hilbert J Kappen, and Andreas Kaltenbrunner. Modeling the structure and evolution of discussion cascades. In Proceedings of the 22nd ACM conference on Hypertext and hypermedia, pages 181-190. ACM, 2011. Google Scholar
  18. Richard A. Holley and Thomas M. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The Annals of Probability, 3(4):643-663, 1975. URL: http://www.jstor.org/stable/2959329.
  19. C Douglas Howard. Zero-temperature ising spin dynamics on the homogeneous tree of degree three. Journal of applied probability, 37(3):736-747, 2000. Google Scholar
  20. Y. Kanoria and O. Tamuz. Tractable bayesian social learning on trees. IEEE Journal on Selected Areas in Communications, 31(4):756-765, 2013. Google Scholar
  21. Yashodhan Kanoria and Andrea Montanari. Subexponential convergence for information aggregation on regular trees. In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 5317-5322. IEEE, 2011. Google Scholar
  22. Yashodhan Kanoria, Andrea Montanari, et al. Majority dynamics on trees and the dynamic cavity method. The Annals of Applied Probability, 21(5):1694-1748, 2011. Google Scholar
  23. E. Mossel, N. Olsman, and O. Tamuz. Efficient bayesian learning in social networks with gaussian estimators. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016. Google Scholar
  24. Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of information in social networks. In Autonomous Agents and Multi-Agent Systems (AAMAS), 2013. Google Scholar
  25. Elchanan Mossel, Allan Sly, and Omer Tamuz. Asymptotic learning on bayesian social networks. Probability Theory and Related Fields, 2014. Google Scholar
  26. Manuel Mueller-Frank. A general framework for rational learning in social networks. Theoretical Economics, 8(1):1-40, 2013. Google Scholar
  27. Dinah Rosenberg, Eilon Solan, and Nicolas Vieille. Informational externalities and emergence of consensus. Games and Economic Behavior, 66(2):979-994, 2009. Google Scholar
  28. Lones Smith and Peter Sorensen. Pathological outcomes of observational learning. Econometrica, 68(2):371-398, March 2000. URL: http://ideas.repec.org/a/ecm/emetrp/v68y2000i2p371-398.html.
  29. Omer Tamuz and Ran Tessler. Majority dynamics and the retention of information. In Working paper, 2013. Google Scholar
  30. Y. P. Tian, X. J. Sun, and O. Tian. Detection performance of the majority dominance rule in m-ary relay trees with node and link failures. IEEE Transactions on Signal Processing, 66(6):1469-1482, March 2018. URL: https://doi.org/10.1109/TSP.2017.2788418.
  31. Zhenliang Zhang, Edwin KP Chong, Ali Pezeshki, William Moran, and Stephen D Howard. Learning in hierarchical social networks. IEEE Journal of Selected Topics in Signal Processing, 7(2):305-317, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact