Reaching consensus via non-bayesian asynchronous learning in social networks

Michal Feldman, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We study the outcomes of information aggregation in online social networks. Our main result is that networks with certain realistic structural properties avoid information cascades and enable a population to effectively aggregate information. In our model, each individual in a network holds a private, independent opinion about a product or idea, biased toward a ground truth. Individuals declare their opinions asynchronously, can observe the stated opinions of their neighbors, and are free to update their declarations over time. Supposing that individuals conform with the majority report of their neighbors, we ask whether the population will eventually arrive at consensus on the ground truth. We show that the answer depends on the network structure: there exist networks for which consensus is unlikely, or for which declarations converge on the incorrect opinion with positive probability. On the other hand, we prove that for networks that are sparse and expansive, the population will converge to the correct opinion with high probability.

Original languageEnglish (US)
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages192-208
Number of pages17
ISBN (Electronic)9783939897743
DOIs
StatePublished - Sep 1 2014
Externally publishedYes
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: Sep 4 2014Sep 6 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Other

Other17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
CountrySpain
CityBarcelona
Period9/4/149/6/14

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Expander Graphs
  • Information Cascades
  • Non-Bayesian Asynchronous Learning
  • Social Networks
  • Stochastic Processes

Fingerprint Dive into the research topics of 'Reaching consensus via non-bayesian asynchronous learning in social networks'. Together they form a unique fingerprint.

  • Cite this

    Feldman, M., Immorlica, N., Lucier, B., & Weinberg, S. M. (2014). Reaching consensus via non-bayesian asynchronous learning in social networks. In K. Jansen, C. Moore, N. R. Devanur, & J. D. P. Rolim (Eds.), Leibniz International Proceedings in Informatics, LIPIcs (pp. 192-208). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 28). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.192