Lecture notes for COMS 6998 - Social Network Economics
Fall 2013, Columbia University
by A. Chaintreau


Part A.1 - Consensus and the Wisdom of the Crowd

General review of results on consensus with landmarks papers

Original paper proposing iterated consensus

M. H. Degroot, “Reaching a Consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, Mar. 1974.

Summary of contributions:

Further analysis of iterated consensus as an (imperfect) opinion formation problem

P. M. DeMarzo, D. Vayanos, and J. Zwiebel, “Persuasion Bias, Social Influence, and Unidimensional Opinions,” The Quarterly Journal of Economics, vol. 118, no. 3, pp. 909–968, Aug. 2003.

Summary of contributions:

Model and Assumptions:

Main results:

Asymptotic correctness: the Wisdom of the crowd

Motivation and origin

In many settings such as the one considered above, the entire population as a whole has access to a very large set of information that, if they were centrally known by a single person, would be sufficient to obtain an extremely good estimator of the true state of the world.

Two celebrated papers argue early on mathematically and empirically for this argument in favor of democratic decision, coining the terms "The wisdom of the crowds" in which an estimator that combines many imperfect signals end up being better than any single individual expert, however skilled this expert might be.

M. J. Condorcet, “Essai sur l‘application de l’analyse à la probabilité des décisions rendus à la pluralité des voix,” Imprimerie Royale, 1785.

Essentially formulates a weak law of large numbers in favor of using a democratic process in court.

F. Galton, “Vox Populi,” Nature, vol. 75, no. 1949, pp. 450–451, Mar. 1907.

Empirically compares the average of all proposed answers to an "ox weight guessing competition" organized in a stock and poultry exhibition. Shows that the median is surprisingly close to the truth and the deviation of the answer is comparable to a normal distribution

However, many social systems do not allow information owned by all individuals to be known in a public manner. Instead, information is implicitly aggregated in an interaction process. Whether or not this aggregation is successful depends on various factors: the limitation of one individual's access to others, and the possibility that information is given too much weight if the social interaction process is unbalanced.

Wisdom of the crowd in iterated consensus

B. Golub and M. O. Jackson, “Naïve Learning in Social Networks and the Wisdom of Crowds,” American Economic Journal: Microeconomics, vol. 2, no. 1, pp. 112–149, Feb. 2010.

Can be seen as following up DeMarzo et al. 2003 paper as a starting point and answering the following question: Since the estimator is not necessarily optimal, under which conditions this estimator becomes asymptotically exacts as the population of nodes grow.

Summary of contributions:

Model and Assumptions:

Proof of counterexample (PROP3):
We assume Bn is finite (i.e. supn|Bn|<) and uniformly prominent:

α>0such thatn,tnsuch that(T(n)tn)i,Bnαfor any iB.
(This is equivalent to say that Bn is always α-prominent for some iterate of T(n), with α>0 independent of n.)
We wish to prove it implies that the wisdom of the crowd can fail in that case.

Proof of sufficient conditions for wisdom of the crowd (THM1):
We wish to prove that a crowd is wise if we have
(i) min dispersion: There exists q,r>0 such that (T(n))Bn,Cnr whenever |Bn|q and |Cn|nn1.
(ii) balance: jn as n such that Bnjn implies A>0 such that TBn¯,Bn(n)<A×TBn,Bn¯(n).

Going further : More on Social Learning

Herding

A classic setting for social learning is the following: each agent receives a private signal and is able to observe some actions made by others (such as in a sequential irreversible public choices). In this setting, even when agents are perfectly rational (i.e. they stricly apply Bayesian rule), the system may enter states in which information is not aggregated. Although collectively the population possess sufficient information to make the best guess with high probability, the process can enter after a few steps a state in which all agents choose the same action although it is suboptimal. This phenomenon is sometimes referred to as herding or information(al) cascade; the former terminology is by far more descriptive and should be preferred.

This first appeared in

A. Banerjee, “A Simple Model of Herd Behavior,” The Quarterly Journal of Economics, vol. 107, no. 3, pp. 797–817, Aug. 1992.

S. Bikhchandani, D. Hirshleifer, and I. Welch, “A theory of fads, fashion, custom, and cultural change as informational cascades,” Journal of political Economy, vol. 100, no. 5, pp. 992–1026, 1992.

And it was recently exposed in textbook:

D. Easley and J. M. Kleinberg, Networks, Crowds, and Markets. Cambridge University Press, 2010. (Chap. 16)

Revisiting herding on social networks

Most works on herding assume that agents see actions of all others in the past, while in many situations each agent may only see a subset (i.e., her friend).

D. Acemoglu, M. A. Dahleh, I. Lobel, and A. Ozdaglar, “Bayesian learning in social networks,” The Review of Economic Studies, vol. 78, no. 4, pp. 1201–1236, 2011.

I. Lobel and E. Sadler, “Social learning and network uncertainty,” Available at SSRN 2102401, 2012.

I. Lobel and E. Sadler, “Preferences, Homophily, and Social Learning,” 2013.

D. Gale and S. Kariv, “Bayesian learning in social networks,” Games and Economic Behavior, vol. 45, no. 2, pp. 329–346, Nov. 2003.

A recent

E. Mossel, A. Sly, and O. Tamuz, “Asymptotic learning on Bayesian social networks,” Probability theory and related fields, pp. 1–31, 2012.

Variants of naive learning

G. Ellison and D. Fudenberg, “Rules of Thumb for Social Learning,” Journal of political Economy, vol. 101, no. 4, pp. 612–643, Aug. 1993.

G. Ellison and D. Fudenberg, “Word-of-Mouth Communication and Social Learning,” The Quarterly Journal of Economics, 1995.

V. Bala and S. Goyal, “Learning from Neighbours,” Rev Econ Studies, vol. 65, no. 3, pp. 595–621, Jul. 1998.

A. Banerjee and D. Fudenberg, “Word-of-mouth learning,” Games and Economic Behavior, vol. 46, no. 1, pp. 1–22, Jan. 2004.

A. Jadbabaie, P. Molavi, A. Sandroni, and A. Tahbaz-Salehi, “Non-Bayesian social learning,” Games and Economic Behavior, vol. 76, no. 1, pp. 210–225, Sep. 2012.

The robustness and simplicity of iterated averaging lead to a broad interest in designing similar algorithm for various communication computation tasks. They are sometimes refered to as gossip algorithms, rumor mongering, epidemic algorithm, or distributed averaging. It would be impossible to describe all the works done in this area since more than two decades, I'm focusing on very classical results and topics that have seen recent advances.

Gossip algorithms for efficient communication

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, Dec. 1987.

is generally considered the first examples of application of this principle to the design of distributed system (in this case large databases).

Various works have considered how the topology of the graph constraining the epidemics affects the speed and output of an epidemics process, such as the propagation of a computer virus. Among them:

A. Ganesh, L. Massoulié, and D. Towsley, “The effect of network topology on the spread of epidemics,” INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol. 2, pp. 1455–1466, 2005.

Present several bounds based on the spectral property of the graph to predict when is an epidemic long-lived and it disappears quickly.

More on distributed consensus

A. Tahbaz-Salehi and A. Jadbabaie, “A Necessary and Sufficient Condition for Consensus Over Random Networks,” IEEE Transactions on Automatic Control, vol. 53, no. 3, pp. 791–795, 2008.

provides a refined conditions based on coefficient of ergodicity of the sequences of matrices that leads to a consensus.

A. Olshevsky and J. N. Tsitsiklis, “Convergence Speed in Distributed Consensus and Averaging,” SIAM J. Control Optim., vol. 48, no. 1, pp. 33–55, Jan. 2009.

Establish general bounds on the convergence time of distributed averaging.

D. Shah, “Gossip Algorithms,” Foundations and Trends® in Networking, vol. 3, no. 1, 2009.

A survey of results in the area with applications to communications, averaging, dealing especially with the case when the gossip algorithms is restricted to a given graph.

Algorithmic complexity of rumor spreading:

R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, “Randomized rumor spreading,” presented at the Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, 2000, pp. 565–574.

Provides tight bounds on the speed and cost (in number of messages) of broadcast in a complete network using gossip algorithms. Introduces a push/pull stages that correspond to the beginning and end of a broadcast. This leaves open the complexity of similar algorithms on arbitrary graphs.

A long standing problem that only got cracked recently is to derive the exact conditions on a graph that allows for a rumor spreading algorithm to achieve a logarithmic time and cost.

F. Chierichetti, S. Lattanzi, and A. Panconesi, “Rumor spreading in social networks,” Proceedings of ICALP, pp. 375–386, 2009. F. Chierichetti, S. Lattanzi, and A. Panconesi, “Almost tight bounds for rumour spreading with conductance,” Proceedings of the 42nd ACM symposium on Theory of computing, pp. 399–408, 2010. G. Giakkoupis, “Tight Bounds for Rumor Spreading with Vertex Expansion,” SODA '14: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014.

A recent work analyzed gossip on a variant of the preferential attachment model (that reproduced power law degree distribution as well as some other social properties). It proved the striking result that rumor spreads faster than logarithmically, by exploiting nodes with very large degree or hubs.

B. Doer, M. Fouz, and T. Friedrich, “Why rumors spread so quickly in social networks,” Communications of the ACM, vol. 55, no. 6, p. 70, Jun. 2012.

Written with StackEdit.