License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.192
URN: urn:nbn:de:0030-drops-46976
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4697/
Go to the corresponding LIPIcs Volume Portal

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

Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks

pdf-format:
14.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{feldman_et_al:LIPIcs:2014:4697,
  author =	{Michal Feldman and Nicole Immorlica and Brendan Lucier and S. Matthew Weinberg},
  title =	{{Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{192--208},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4697},
  URN =		{urn:nbn:de:0030-drops-46976},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.192},
  annote =	{Keywords: Information Cascades, Social Networks, non-Bayesian Asynchronous Learning, Expander Graphs, Stochastic Processes}
}

Keywords: Information Cascades, Social Networks, non-Bayesian Asynchronous Learning, Expander Graphs, Stochastic Processes
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI