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+δ. 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.