TY - GEN
T1 - Asynchronous majority dynamics in preferential attachment trees
AU - Bahrani, Maryam
AU - Immorlica, Nicole
AU - Mohan, Divyarthi
AU - Matthew Weinberg, S.
N1 - Publisher Copyright:
© Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, and S. Matthew Weinberg; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
PY - 2020/6/1
Y1 - 2020/6/1
N2 - 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 [5], with high probability, the process stabilizes in a correct majority within O(nlog n/log log n) rounds. We extend our results to other tree structures, including balanced M-ary trees for any M.
AB - 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 [5], with high probability, the process stabilizes in a correct majority within O(nlog n/log log n) rounds. We extend our results to other tree structures, including balanced M-ary trees for any M.
KW - Information Cascades
KW - Majority Dynamics
KW - Non-Bayesian Asynchronous Learning
KW - Opinion Dynamics
KW - Preferential Attachment
KW - Stochastic Processes
UR - http://www.scopus.com/inward/record.url?scp=85089350128&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089350128&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2020.8
DO - 10.4230/LIPIcs.ICALP.2020.8
M3 - Conference contribution
AN - SCOPUS:85089350128
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
A2 - Czumaj, Artur
A2 - Dawar, Anuj
A2 - Merelli, Emanuela
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
Y2 - 8 July 2020 through 11 July 2020
ER -