Networks

Lecture Notes

The actual size of these slides is 12.8 cm by 9.6 cm. Use Adobe Reader's print options to scale the slide to fit the page before printing.

SES #

TOPICS

SLIDES

1

Introduction to economic, social, and communication networks

Lecture 1(PDF - 1.0MB)

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

Lecture 2 (PDF)

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

Lecture 3 (PDF)

Lecture 4 (PDF)

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

Lecture 5 (PDF)

Lecture 6 (PDF)

Lecture 7 (PDF)

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

Lecture 8 (PDF)

9-11

Introduction to game theory

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

Lecture 9 (PDF)

Lecture 10 (PDF)

Lecture 11 (PDF)

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

Lecture 12 (PDF)

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

Lectures 13 and 14 (PDF)

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

Lecture 15 (PDF)

Lecture 16 (PDF)

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

Lectures 17 and 18 (PDF)

19-21

Games of incomplete information

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

Lectures 19 to 21 (PDF)

22-23

Social learning in networks

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

Lectures 22 and 23 (PDF)

24

Decisions in groups

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

Lecture 24 (PDF)

Assignments

 

ASSIGNMENTS

TOPICS

FILES

SUPPORTING FILES

Problem set 1

Phase transitions in the Erdös-Renyi model

Clustering in the configuration model

Clustering in the small world model

(PDF)

 

Problem set 2

Degree distribution in networks

Navigation time for an analog of Kleinberg's grid-based navigation model

Comparison of SIR (susceptible, infected, removed) model with the Erdős-Renyi random graph model

Small world network vs. random graph: computational problem

(PDF)

lattice.net (NET)

Pajek tutorial (Tutorial by Lada Adamic) (PDF)

Problem set 3

Iterated elimination of strictly dominated strategies

Iterated elimination of strictly dominated strategies in Cournot competition

Competition with capacity constraints

Bertrand competition with different marginal costs

The rotten kid theorem

(PDF)

 

Problem set 4

Sudoku as a game of cooperation

Network formation game of Lecture 12

The stag hunt game, a game of social cooperation

The chain store paradox

(PDF)

 

Problem set 5

Cooperation over social networks

Network effects

Bertrand competition under imperfect information

Herding with crazy types

(PDF)

 

Additional problems

Multitype Erdös-Renyi random graph model

Navigating a structured network on a hypercube

Sequential duel

Choosing the estate tax rate as an extensive form game

Voter equilibrium

The Colonel Blotto game

(PDF)

 

Exams

The midterm consisted of three problems on these topics:

  • Dying links in preferential attachment
  • Repeated Bertrand competition with different marginal costs of production
  • Public goods game

Midterm (PDF)