Asynchronous Majority Dynamics in Preferential Attachment Trees
Asynchronous Majority Dynamics in Preferential Attachment Trees
复制标题
DOI：
10.4230/lipics.icalp.2020.8
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Maryam Bahrani;Nicole Immorlica;Divyarthi Mohan;S. Weinberg
中科院分区：
文献类型：
--
作者：
Maryam Bahrani;Nicole Immorlica;Divyarthi Mohan;S. Weinberg
我们研究网络中的信息聚合，代理人作出二元决策（标记为不正确或正确）。代理最初形成独立的私人信念的更好的决定，这是正确的概率为1/2+\delta$。我们考虑的动态是异步的（每一轮，单个代理更新其宣布的决定）和非贝叶斯的（代理简单地复制其邻居之间的大多数公告，打破平局有利于他们的私人信号）。我们的主要结果证明，当网络是一棵树形成的优先连接模型~\cite{BarabasiA 99}，以高概率，该过程稳定在一个正确的多数。我们将我们的结果扩展到其他树结构，包括平衡的$M$-ary树的任何$M$。
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. We extend our results to other tree structures, including balanced $M$-ary trees for any $M$.