## A Course in Networks and Markets

by Pass

### Instructor Requests

A graduate-level, mathematically rigorous introduction to strategic behavior in a networked world.

This introductory graduate-level text uses tools from game theory and graph theory to examine the role of network structures and network effects in economic and information markets. The goal is for students to develop an intuitive and mathematically rigorous understanding of how strategic agents interact in a connected world. The text synthesizes some of the central results in the field while also simplifying their treatment to make them more accessible to nonexperts. Thus, students at the introductory level will gain an understanding of key ideas in the field that are usually only taught at the advanced graduate level.

The book introduces basic concepts from game theory and graph theory as well as some fundamental algorithms for exploring graphs. These tools are then applied to analyze strategic interactions over social networks, to explore different types of markets and mechanisms for networks, and to study the role of beliefs and higher-level beliefs (beliefs about beliefs). Specific topics discussed include coordination and contagion on social networks, traffic networks, matchings and matching markets, exchange networks, auctions, voting, web search, models of belief and knowledge, and how beliefs affect auctions and markets. An appendix offers a “Primer on Probability.”  Mathematically rigorous, the text assumes a level of mathematical maturity (comfort with definitions and proofs) in the reader.

Expand/Collapse All
Contents (pg. vii)
Introduction (pg. xi)
I. Games and Graphs (pg. 1)
1. Game Theory (pg. 3)
1.1 The Prisoner's Dilemma Game (pg. 3)
1.2 Normal-form Games (pg. 4)
1.3 Dominant Strategies (pg. 6)
1.4 Iterated Strict Dominance (ISD) (pg. 7)
1.5 Nash Equilibria and Best-Response Dynamics (pg. 9)
1.6 A Cautionary Game: The Traveler's Dilemma (pg. 13)
1.7 Mixed-strategy Nash Equilibrium (pg. 14)
2. Graphs (pg. 17)
2.1 Basic Definitions (pg. 18)
2.2 Connectivity and Reachability (pg. 19)
2.3 Breadth-first Search and Shortest Paths (pg. 20)
3. Analyzing Best-Response Dynamics (pg. 25)
3.1 A Graph Representation of Games (pg. 25)
3.2 Characterizing Convergence of BRD (pg. 26)
3.3 Better-response Dynamics (pg. 29)
3.4 Games without PNE (pg. 31)
4. Coordination in Social Networks (pg. 33)
4.1 Plain Networked Coordination Games (pg. 33)
4.2 Convergence of BRD (pg. 35)
4.3 Incorporating Intrinsic Values (pg. 37)
4.4 The Price of Stability (pg. 40)
4.5 Incorporating Strength of Friendship (pg. 42)
5. Contagion in Social Networks (pg. 45)
5.4 Dealing with Subjective Thresholds (pg. 49)
II. Markets on Networks (pg. 51)
6. More on Graphs: Flows and Matchings (pg. 53)
6.1 The Max-Flow Problem (pg. 53)
6.2 The Max-Flow Min-Cut Duality (pg. 56)
6.3 Bipartite Graphs and Maximum Matchings (pg. 58)
6.4 Perfect Matchings and Constricted Sets (pg. 60)
7. Traffic Network Games (pg. 65)
7.1 Definition of a Traffic Network Game (pg. 65)
7.3 Convergence of BRD (pg. 68)
7.4 Price of Stability (pg. 69)
8. Matching Markets (pg. 73)
8.1 Definition of a Matching Market (pg. 74)
8.2 Acceptability and Preferred Choices (pg. 75)
8.3 Social Optimality of Market Equilibria (pg. 76)
8.4 Existence of Market Equilibria (pg. 79)
8.5 Emergence of Market Equilibria (pg. 81)
8.6 Bundles of Identical Goods (pg. 82)
9. Exchange Networks (pg. 85)
9.1 Definition of an Exchange Network (pg. 85)
9.2 Stable Outcomes (pg. 86)
9.3 Existence of Stable Outcomes (pg. 89)
9.4 Applications of Stability (pg. 90)
9.5 Balanced Outcomes (pg. 92)
III. Mechanisms for Networks (pg. 97)
10. Mechanism Design and Auctions (pg. 99)
10.1 The Mechanism Design Model (pg. 100)
10.2 Goals of Mechanism Design (pg. 102)
10.3 The VCG Mechanism (pg. 106)
10.4 VCG and Matching Markets (pg. 109)
10.5 Generalized Second-price (GSP) Auctions (pg. 112)
10.6 Applications to Sponsored Search (pg. 114)
11. Voting: Basic Notions (pg. 119)
11.1 Social-choice Contexts (pg. 119)
11.2 Voting Rules and Strategy-proofness (pg. 120)
11.3 Condorcet Voting (pg. 121)
11.4 The Problem with Nonbinary Elections (pg. 122)
12. Voting: Barriers and Ways around Them (pg. 125)
12.1 The Gibbard‒Satterthwaite Theorem (pg. 125)
12.2 Proof of the Gibbard‒Satterthwaite Theorem [Advanced] (pg. 126)
12.3 Single-peaked Preferences and the Median Voter Theorem (pg. 132)
12.4 Voting with Payments (pg. 135)
12.5 Summarizing the Voting Landscape (pg. 137)
13. One-sided Matchings: House Allocation Problems (pg. 139)
13.1 (One-sided) Matching Contexts (pg. 139)
13.2 Strategy-proof Matching Rules: Serial Dictatorship (pg. 140)
13.3 Uniqueness of Serial Dictatorship [Advanced] (pg. 142)
13.4 Proof of the Uniqueness Theorem [Advanced] (pg. 143)
14. Two-sided Matchings: Stable Marriages (pg. 147)
14.1 Two-sided Matching Problems (pg. 147)
14.2 The Stable Marriage Theorem (pg. 148)
14.3 Optimality of Stable Outcomes (pg. 151)
14.4 Strategy-proofness of Two-sided Matching Rules (pg. 153)
14.5 Strategy-proofness vs. Stability (pg. 157)
15. Web Search (pg. 161)
15.1 Weighted Voting and PageRank (pg. 162)
15.2 Scaled PageRank (pg. 166)
15.3 Impossibility of Non-manipulable Web Search (pg. 171)
IV. The Role of Beliefs (pg. 175)
16. The Wisdom and Foolishness of Crowds (pg. 177)
16.1 The Wisdom of Crowds (pg. 177)
16.2 The Foolishness of Crowds: Herding (pg. 181)
17. Knowledge and Common Knowledge (pg. 185)
17.1 The Muddy Children Puzzle (pg. 185)
17.2 Kripke's "Possible Worlds" Model (pg. 186)
17.3 Common Knowledge (pg. 191)
17.4 Can We Agree to Disagree? [Advanced] (pg. 193)
17.6 Justified True Belief and the Gettier Problems (pg. 197)
18. Common Knowledge of Rationality (pg. 201)
18.1 Knowledge and Games (pg. 201)
18.2 An Epistemic Characterization of ISD (pg. 203)
18.3 An Epistemic Characterization of PNE (pg. 205)
18.4 Knowledge vs. Belief: Explaining Bubbles in the Market (pg. 206)
19. Markets with Network Effects (pg. 211)
19.1 Simple Networked Markets (pg. 211)
19.2 Markets with Asymmetric Information (pg. 215)
V. Appendix (pg. 219)
A. A Primer on Probability (pg. 221)
A.1 Probability Spaces (pg. 221)
A.2 Conditional Probability (pg. 223)
A.3 Bayes' Rule (pg. 224)
A.4 Random Variables (pg. 228)
A.5 Expectation (pg. 229)
Bibliography (pg. 235)
Index (pg. 243)

#### Rafael Pass

Rafael Pass is Professor of Computer Science at Cornell Tech and Cornell University.

Instructors
You must have an instructor account and submit a request to access instructor materials for this book.
eTextbook