2026-07-24T06:35:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12415 2024-03-06T10:50:04Z ddc:004 open_access

Asynchronous Majority Dynamics in Preferential Attachment Trees Bahrani, Maryam Immorlica, Nicole Mohan, Divyarthi Weinberg, S. Matthew Opinion Dynamics Information Cascades Preferential Attachment Majority Dynamics non-Bayesian Asynchronous Learning Stochastic Processes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maryam Bahrani and Nicole Immorlica and Divyarthi Mohan and S. Matthew Weinberg 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.8 urn:nbn:de:0030-drops-124156 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode