Document Open Access Logo

Information Cascades on Arbitrary Topologies

Authors Jun Wan, Yu Xia, Liang Li, Thomas Moscibroda

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.64.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Jun Wan
Yu Xia
Liang Li
Thomas Moscibroda

Cite As Get BibTex

Jun Wan, Yu Xia, Liang Li, and Thomas Moscibroda. Information Cascades on Arbitrary Topologies. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.64

Abstract

In this paper, we study information cascades on graphs. In this setting, each node in the graph represents a person. One after another, each person has to take a decision based on a private signal as well as the decisions made by earlier neighboring nodes. Such information cascades commonly occur in practice and have been studied in complete graphs where everyone can overhear the decisions of every other player. It is known that information cascades can be fragile and based on very little information, and that they have a high likelihood of being wrong.

Generalizing the problem to arbitrary graphs reveals interesting insights. In particular, we show that in a random graph G(n,q), for the right value of q, the number of nodes making a wrong decision is logarithmic in n. That is, in the limit for large n, the fraction of players that make a wrong decision tends to zero. This is intriguing because it contrasts to the two natural corner cases: empty graph (everyone decides independently based on his private signal) and complete graph (all decisions are heard by all nodes). In both of these cases a constant fraction of nodes make a wrong decision in expectation. Thus, our result shows that while both too little and too much information sharing causes nodes to take wrong decisions, for exactly the right amount of information sharing, asymptotically everyone can be right. We further show that this result in random graphs is asymptotically optimal for any topology, even if nodes follow a globally optimal algorithmic strategy. Based on the analysis of random graphs, we explore how topology impacts global performance and construct an optimal deterministic topology among layer graphs.

Subject Classification

Keywords
  • Information Cascades
  • Herding Effect
  • Random Graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Daron Acemoglu, Munther A. Dahleh, Ilan Lobel, and Asuman Ozdaglar. Bayesian Learning in Social Networks. Review of Economic Studies, 78(4):1201-1236, 2011. URL: https://ideas.repec.org/a/oup/restud/v78y2011i4p1201-1236.html.
  2. Daron Acemoglu and Asuman Ozdaglar. Opinion dynamics and learning in social networks. Dynamic Games and Applications, 1(1):3-49, 2010. Google Scholar
  3. Lisa R Anderson and Charles A Holt. Classroom games: Information cascades. The Journal of Economic Perspectives, 10(4):187-193, 1996. Google Scholar
  4. Lisa R Anderson and Charles A Holt. Information cascades in the laboratory. The American economic review, pages 847-862, 1997. Google Scholar
  5. Abhijit Banerjee and Drew Fudenberg. Word-of-mouth learning. Games and Economic Behavior, 46(1):1-22, January 2004. Google Scholar
  6. Abhijit V Banerjee. A simple model of herd behavior. The Quarterly Journal of Economics, pages 797-817, 1992. Google Scholar
  7. Sushil Bikhchandani, David Hirshleifer, and Ivo Welch. A theory of fads, fashion, custom, and cultural change as informational cascades. Journal of political Economy, pages 992-1026, 1992. Google Scholar
  8. David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 57-66, 2011. Google Scholar
  9. Boǧaçhan Çelena and Shachar Kariv. Observational learning with imperfect information. Games and Economic Behavior, 47:72-86, 2004. Google Scholar
  10. Flavio Chierichetti, Jon Kleinberg, and Alessandro Panconesi. How to schedule a cascade in an arbitrary graph. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC'12, pages 355-368, New York, NY, USA, 2012. ACM. Google Scholar
  11. Morris H DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69:118-121, 1974. Google Scholar
  12. David Easley and Jon Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010. Google Scholar
  13. Benjamin Golub and Matthew O. Jackson. Naive learning in social networks: convergence, influence, and the wisdom of crowds, 2010. Google Scholar
  14. Mark Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420-1443, May 1978. Google Scholar
  15. MohammadTaghi Hajiaghayi, Hamid Mahini, and David Malec. The polarizing effect of network influences. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC'14, pages 131-148, New York, NY, USA, 2014. ACM. Google Scholar
  16. MohammadTaghi Hajiaghayi, Hamid Mahini, and Anshul Sawant. Scheduling a cascade with opposing influences. In Algorithmic Game Theory: 6th International Symposium, SAGT 2013, Aachen, Germany, October 21-23, 2013. Proceedings, pages 195-206, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  17. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, March 4-6, 1999 Proceedings, pages 404-413, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. Google Scholar
  18. David Krackhardt. A plunge into networks. Science, 326(5949):47-48, 2009. URL: http://dx.doi.org/10.1126/science.1167367.
  19. Lones Smith and Peter Sørensen. Pathological outcomes of observational learning. ECONOMETRICA, 68:371-398, 1999. Google Scholar
  20. Lones Smith and Peter Sørensen. Rational social learning with random sampling, 2008. URL: http://lonessmith.com/sites/default/files/rational.pdf.
  21. Arthur W Brian. Competing technologies, increasing returns, and lock-in by historical events. The Economic Journal, 99(394):116-131, 1989. Google Scholar
  22. Jun Wan, Yu Xia, Liang Li, and Thomas Moscibroda. Information cascades on arbitrary topologies, 2016. URL: http://arxiv.org/abs/1604.07166.
  23. Ivo Welch. Sequential sales, learning, and cascades. The Journal of finance, 47(2):695-732, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact