I   Games and Graphs

  1   Game Theory

1.1   The Prisoner’s Dilemma Game

1.2   Normal-form Games

1.3   Dominant Strategies

1.4   Iterated Strict Dominance (ISD)

1.5   Nash Equilibria and Best-Response Dynamics

1.6   A Cautionary Game: The Traveler’s Dilemma

1.7   Mixed-strategy Nash Equilibrium

  2   Graphs

2.1   Basic Definitions

2.2   Connectivity and Reachability

2.3   Breadth-first Search and Shortest Paths

  3   Analyzing Best-Response Dynamics

3.1   A Graph Representation of Games

3.2   Characterizing Convergence of BRD

3.3   Better-response Dynamics

3.4   Games without PNE

  4   Coordination in Social Networks

4.1   Plain Networked Coordination Games

4.2   Convergence of BRD

4.3   Incorporating Intrinsic Values

4.4   The Price of Stability

4.5   Incorporating Strength of Friendship

  5   Contagion in Social Networks

5.1   Cascades

5.2   Characterizing Cascades

5.3   Strong Cascades

5.4   Dealing with Subjective Thresholds

II   Markets on Networks

  6   More on Graphs: Flows and Matchings

6.1   The Max-Flow Problem

6.2   The Max-Flow Min-Cut Duality

6.3   Bipartite Graphs and Maximum Matchings

6.4   Perfect Matchings and Constricted Sets

  7   Traffic Network Games

7.1   Definition of a Traffic Network Game

7.2   Braess’s Paradox

7.3   Convergence of BRD

7.4   Price of Stability

  8   Matching Markets

8.1   Definition of a Matching Market

8.2   Acceptability and Preferred Choices

8.3   Social Optimality of Market Equilibria

8.4   Existence of Market Equilibria

8.5   Emergence of Market Equilibria

8.6   Bundles of Identical Goods

  9   Exchange Networks

9.1   Definition of an Exchange Network

9.2   Stable Outcomes

9.3   Existence of Stable Outcomes

9.4   Applications of Stability

9.5   Balanced Outcomes

III   Mechanisms for Networks

10   Mechanism Design and Auctions

10.1   The Mechanism Design Model

10.2   Goals of Mechanism Design

10.3   The VCG Mechanism

10.4   VCG and Matching Markets

10.5   Generalized Second-price (GSP) Auctions

10.6   Applications to Sponsored Search

11   Voting: Basic Notions

11.1   Social-choice Contexts

11.2   Voting Rules and Strategy-proofness

11.3   Condorcet Voting

11.4   The Problem with Nonbinary Elections

12   Voting: Barriers and Ways around Them

12.1   The Gibbard–Satterthwaite Theorem

12.2   Proof of the Gibbard–Satterthwaite Theorem [Advanced]

12.3   Single-peaked Preferences and the Median Voter Theorem

12.4   Voting with Payments

12.5   Summarizing the Voting Landscape

13   One-sided Matchings: House Allocation Problems

13.1   (One-sided) Matching Contexts

13.2   Strategy-proof Matching Rules: Serial Dictatorship

13.3   Uniqueness of Serial Dictatorship [Advanced]

13.4   Proof of the Uniqueness Theorem [Advanced]

14   Two-sided Matchings: Stable Marriages

14.1   Two-sided Matching Problems

14.2   The Stable Marriage Theorem

14.3   Optimality of Stable Outcomes

14.4   Strategy-proofness of Two-sided Matching Rules

14.5   Strategy-proofness vs. Stability

15   Web Search

15.1   Weighted Voting and PageRank

15.2   Scaled PageRank

15.3   Impossibility of Non-manipulable Web Search

IV   The Role of Beliefs

16   The Wisdom and Foolishness of Crowds

16.1   The Wisdom of Crowds

16.2   The Foolishness of Crowds: Herding

17   Knowledge and Common Knowledge

17.1   The Muddy Children Puzzle

17.2   Kripke’s “Possible Worlds” Model

17.3   Common Knowledge

17.4   Can We Agree to Disagree? [Advanced]

17.5   The “No-Trade” Theorem [Advanced]

17.6   Justified True Belief and the Gettier Problems

18   Common Knowledge of Rationality

18.1   Knowledge and Games

18.2   An Epistemic Characterization of ISD

18.3   An Epistemic Characterization of PNE

18.4   Knowledge vs. Belief: Explaining Bubbles in the Market

19   Markets with Network Effects

19.1   Simple Networked Markets

19.2   Markets with Asymmetric Information

V   Appendix

A   A Primer on Probability

A.1   Probability Spaces

A.2   Conditional Probability

A.3   Bayes’ Rule

A.4   Random Variables

A.5   Expectation