Asynchronous Majority Dynamics in Preferential Attachment Trees

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+\delta$. 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 \cite{BarabasiA99}, 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$.

arXiv commentICALP 2020

References in corpus (7)

• Emergence of scaling in random networks
• Diameters in preferential attachment models
• Asymptotic Learning on Bayesian Social Networks
• Modeling the structure and evolution of discussion cascades
• Learning in Hierarchical Social Networks
• Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks
• Local majority dynamics on preferential attachment graphs