Readings

A list of readings by session is available below.

Textbooks

The lecture slides we will provide contain all of the information and material you need for the course.

In addition, two textbooks are useful supplements, and you will benefit from studying one or both of those, particularly to obtain additional details or different derivations and discussions. The first is David Easley's and Jon Kleinberg's forthcoming book Networks, Crowds, and Markets: Reasoning about a Highly Connected World, which covers most of the topics at a level somewhat lower than this class.

[EK] = Buy at Amazon Easley, David, and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. New York, NY: Cambridge University Press, 2010. ISBN: 9780521195331.

At a level that is slightly more advanced than our course is Matthew Jackon's Social and Economic Networks, which is a useful reference both for substantive and technical material.

[Jackson] = Buy at Amazon Jackson, Matthew O. Social and Economic Networks. Princeton, NJ: Princeton University Press, 2008. ISBN: 9780691134406.

The analysis of economic and social networks relies heavily on game theory. Of course, the course does not presume any game theoretic background, though some students will have taken 14.12 Economic Applications of Game Theory or may be concurrently registered with this course. We will cover all of the game theory that you need as we go along. Two books that are excellent references are:

[Osborne] = Buy at Amazon Osborne, Martin J. Introduction to Game Theory. New York, NY: Oxford University Press, 2003. ISBN: 9780195128956.

[Gibbons] = Buy at Amazon Gibbons, Robert. Game Theory for Applied Economists. Princeton, NJ: Princeton University Press, 1992. ISBN: 9780691003955.

We will also refer to a variety of other books that are non-technical. These will be particularly useful in providing you with context and possible real-world applications. Some of the material in these books is overblown, so be warned. These books are:

[Gladwell] = Buy at Amazon Gladwell, Malcom. The Tipping Point: How Little Things Can Make a Big Difference. Boston, MA: Little, Brown and Co, 2002. ISBN: 9780316346627.

[Surowiecki] = Buy at Amazon Surowiecki, James. The Wisdom of Crowds: Why the Many Are Smarter Than the Few and How Collective Wisdom Sharpens Business, Economies, Societies, and Nations. New York, NY: Doubleday Publishing, 2004. ISBN: 9780385503860. Reprinted with a new Afterword as: Buy at Amazon The Wisdom of Crowds. Anchor Books ed. New York, NY: Anchor Books, 2005. ISBN: 9780385721707.

[Barabasi] = Buy at Amazon Barabasi, Albert-Laszlo. Linked: How Everything Is Connected to Everything Else and What It Means for Business, Science, and Everyday Life. New York, NY: Penguin, 2003. ISBN: 9780452284395.

[Schelling] = Buy at Amazon Schelling, Thomas C. Micromotives and Macrobehavior. Revised ed. New York, NY: W.W. Norton and Co., 2006. ISBN: 9780393329469. This old classic is still relevant.

Finally, we will also refer to the following book for Markov chains:

Buy at Amazon Bertsekas, Dimitri, and John Tsitsiklis. Introduction to Probability. 2nd ed. Belmont, MA: Athena Scientific, 2008. ISBN: 9781886529236.

Readings by Session

SES # TOPICS READINGS
1

Introduction to economic, social, and communication networks

[EK] chapter 1 (skim chapters 3-5).

[Jackson] chapter 1.

Optional

[Gladwell] chapters 1 and 2.

[Barabasi] chapters 1 to 4.

2

Graph theory and social networks

Directed and undirected graphs, paths, cycles, diameter, clustering, bipartite graphs. Applications: the web as a directed graph, graphical representation of homophily.

[EK] chapters 2 and 13.

[Jackson] chapters 2 and 3.

3-4

Branching processes and random graph models

Review of branching processes, Erdös-Renyi graphs, degree distributions, phase transitions, connectedness, and giant component. Applications: tipping, six degrees of separation, and disease transmissions.

Ses #3

[Jackson] sections 4.1.1, and 4.2.1 to 4.2.3.

Ses #4

[Jackson] sections 4.2.2 to 4.2.5, and 4.3.

Optional

[Gladwell] chapter 3.

[Barabasi] chapter 3 (read this chapter again after lecture) and chapter 10.

5-7

Rich get richer phenomena, power laws, and small worlds

Preferential attachment, degree distributions, generalized random graphs, and clustering. Applications: firm size distributions, link analysis and web search, PageRank, decentralized search, and navigation.

Ses #5

[Jackson] sections 4.1.2, 4.1.4 to 4.1.6, 4.2.1, 4.2.6, and 4.2.7.

[EK] chapter 20.

Ses #6

[EK] chapter 18.

[Jackson] chapter 5, sections 5.1 to 5.2.

Ses #7

[EK] sections 20.3 to 20.6 (navigation).

[EK] chapter 14 (web search).

Optional

[Barabasi] chapters 5 to 7.

[Gladwell] chapter 6.

Buy at Amazon Kleinberg, Jon. "The Small-World Phenomenon: An Algorithmic Perspective." In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Portland, Oregon, May 21-23, 2000. New York, NY: ACM (Association for Computing Machinery) Press, 2000, pp. 163-170.

8

Epidemics and diffusion through networks

SIR (susceptible, infected, removed) and SIS (susceptible, infected susceptible) models of diffusion. Applications: spread of information and disease, and genetic inheritance.

[EK] chapter 21.

[Jackson] chapter 7, sections 7.1 and 7.2.

Optional

[Barabasi] chapters 5 to 7.

[Gladwell] chapter 6.

9-11

Introduction to game theory

Games, strategies, payoffs, extensive and normal forms, and Nash equilibrium. Applications: tragedy of the commons and coordination games.

Ses #9

[Osborne] chapters 1 and 2.

[EK] chapter 6.

Ses #10

[Osborne] chapters 3 to 5.

Ses #11

Osborne, chapters 5 to 6.

Optional

Gibbons, chapter 1.

12

Applications of game theory to networks

Modeling network traffic, strategic network formation, negative externalities, Braess' paradox, and potential games. Application: congestion tax in London.

[EK] chapter 8.

[Jackson] chapter 6.

Optional

[Schelling] chapter 1.

[Surowiecki] chapter 7.

13-14

Evolution, learning, and myopia vs. rationality

Evolutionary stable strategies, fictitious play, emergence of Nash equilibrium from rules of thumb, limits of myopic behavior. Application: rules of thumb in traffic.

[EK] chapter 7.

[Osborne] chapter 13.

15-16

Dynamic and repeated games, and cooperation and trust in networks

Subgame perfect Nash equilibrium, repeated games, prisoners' dilemma, repeated games over networks. Application: emergence of cooperation in social networks.

Ses #15

[Osborne] chapters 14 and 15.

Ses #16

[Osborne] chapters 14 and 15.

Optional

[Osborne] chapters 5 and 6.

[EK] chapter 6.

[Gibbons] chapter 2.

[Surowiecki] chapter 6.

17-18

Network effects, innovation, tipping and contagion

Positive externalities, strategic complements, path dependence, diffusion of innovation, and tipping in technology, financial, and product markets. Application: the rise of Microsoft and contagion phenomena.

[EK] chapter 17.

[Jackson] section 9.6.

Optional

[EK] chapter 19.

[Jackson] section 9.7.

[Gladwell] chapters 3 and 6.

[Barabasi] chapter 10.

19-21

Games of incomplete information

Bayes's rule, Bayesian Nash equilibria, first and second price auctions, and introduction to social learning. Applications: spectrum auctions, market for lemons, and keyword-based advertising.

[Osborne] chapter 9.

[EK] chapter 16.

Optional

[EK] chapters 9, 15, and 22.

[Gibbons] chapter 3.

22-23

Social learning in networks

Bayesian learning, benefits of copying, herd behavior, informational cascades. Applications: consumer behavior and financial markets.

[Jackson] chapter 8.

[EK] chapter 16.

Optional

[Surowiecki] chapters 1 to 4.

[Gladwell] chapter 2.

[Barabasi] chapter 10.

24

Decisions in groups

Decision making in organizations and societies, social choice, Condorcet jury theorem, and political economy. Application: committee decisions.

[EK] chapter 23.

[Osborne] section 9.7.

Optional

[EK] chapter 24.

[Surowiecki] chapters 9-11.

 

Additional Study

TOPICS READINGS

Wisdom of crowds, information aggregation over networks

Review of Markov Chains, law of large numbers, imitation and social influence, and consensus and gossip algorithms. Application: prediction markets.

[Jackson] section 8.3.

Markets and networks

Competitive equilibrium, equilibrium as matching, markets as networks, bargaining and trading on networks. Application: matching

[EK] chapters 10 to 12.

Optional

[Jackson] chapter 10.

[Schelling] chapter 3.