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