Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2014 | Submitted + Published
Journal Article Open

Majority Dynamics and Aggregation of Information in Social Networks

Abstract

Consider n individuals who, by popular vote, choose among q ≥ 2 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 n individuals would result in the correct outcome, with probability approaching one exponentially quickly as n → ∞. Our interest in this paper 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 n → ∞? 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.

Additional Information

© 2013 The Author(s). Published online: 11 June 2013. We would like to thank Miklos Racz for his careful reading of the manuscript and his suggestions. Elchanan Mossel is supported by a Sloan fellowship in Mathematics, by BSF Grant 2004105, by NSF Career Award (DMS 054829), by ONR Award N00014-07-1-0506 and by ISF Grant 1300/08. Omer Tamuz is supported by ISF Grant 1300/08. Omer Tamuz is a recipient of the Google Europe Fellowship in Social Computing, and this research is supported in part by this Google Fellowship.

Attached Files

Published - art_3A10.1007_2Fs10458-013-9230-4.pdf

Submitted - 1207.0893.pdf

Files

1207.0893.pdf
Files (526.0 kB)
Name Size Download all
md5:acdf1281d1c3b9cdc4e24e531dfac134
246.4 kB Preview Download
md5:cf291967e14dfb49ef9991856e0efec9
279.6 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023