Skip to main content

Asynchronous Majority Dynamics in Preferential Attachment Trees

Author(s): Bahrani, Maryam; Immorlica, Nicole; Mohan, Divyarthi; Weinberg, S Matthew

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1026z
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.
Publication Date: 2020
Citation: Bahrani, Maryam, 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): 8:1-8:14. doi:10.4230/LIPIcs.ICALP.2020.8
DOI: 10.4230/LIPIcs.ICALP.2020.8
ISSN: 1868-8969
Pages: 8:1 - 8:14
Type of Material: Conference Article
Journal/Proceeding Title: 47th International Colloquium on Automata, Languages, and Programming (ICALP)
Version: Final published version. This is an open access article.



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.