Majority dynamics and aggregation of information in social networks
Majority dynamics and aggregation of information in social networks
复制标题
DOI：
10.1007/s10458-013-9230-4
复制
发表时间：
2014-05-01
影响因子：
1.9
通讯作者：
Tamuz, Omer
中科院分区：
文献类型：
--
作者：
Mossel, Elchanan;Neeman, Joe;Tamuz, Omer
以个人为例，他们通过全民投票在备选方案中做出选择，其中一个比其他的“更好”。假设每个人都独立地随机投票，并且投票给更好的选择的概率大于投票给任何其他选择的概率。根据大数定律，多数人投票就会产生正确的结果，其概率以指数速度接近1。我们对本文感兴趣的是上述过程的一种变体，在形成初步意见后，选民根据与社交网络中的邻居的互动更新他们的决定。我们的主要例子是“多数动态”，即每个选民都采纳其朋友中最受欢迎的意见。这种相互作用重复进行几轮，然后进行全民多数投票。我们要解决的问题是“信息的有效聚合”：在哪些情况下，选择概率接近1的更好的替代方案？相反，对于哪些不断增长的图序列，聚合会失败，从而选择错误的替代方案，其概率有界于零？我们构建了一组例子，其中交互阻碍了信息的有效聚合，并给出了一个确保聚合发生的社会网络条件。对于多数动力学的情况，我们也研究了极限一致的问题。特别是，如果选民的社会网络是一个扩展图，我们表明，如果初始人群对特定的选择有足够的偏向，那么该选择最终将成为整个人群的一致偏好。
Consider individuals who, by popular vote, choose among alternatives, one of which is "better" than the others. Assume that each individual votes independently at random, and that the probability of voting for the better alternative is larger than the probability of voting for any other. It follows from the law of large numbers that a plurality vote among the individuals would result in the correct outcome, with probability approaching one exponentially quickly as . Our interest in this article is in a variant of the process above where, after forming their initial opinions, the voters update their decisions based on some interaction with their neighbors in a social network. Our main example is "majority dynamics", in which each voter adopts the most popular opinion among its friends. The interaction repeats for some number of rounds and is then followed by a population-wide plurality vote. The question we tackle is that of "efficient aggregation of information": in which cases is the better alternative chosen with probability approaching one as ? Conversely, for which sequences of growing graphs does aggregation fail, so that the wrong alternative gets chosen with probability bounded away from zero? We construct a family of examples in which interaction prevents efficient aggregation of information, and give a condition on the social network which ensures that aggregation occurs. For the case of majority dynamics we also investigate the question of unanimity in the limit. In particular, if the voters' social network is an expander graph, we show that if the initial population is sufficiently biased towards a particular alternative then that alternative will eventually become the unanimous preference of the entire population.