Contributors (Author(s), Editor(s), Translator(s), Illustrator(s) etc.)

Anna R. Karlin, University of Washington, Seattle, WA,
Yuval Peres, Microsoft Research, Redmond, WA

Table of Content

Preface xvii
An overview of the book xvii
Part I: Analyzing games: Strategies and equilibria xvii
Part II: Designing games and mechanisms xxi
For the reader and instructor xxiv
Prerequisites xxiv
Courses xxiv
Notes xxv

Part I: Analyzing games: Strategies and equilibria 1
Chapter 1. Combinatorial games 2
1.1. Impartial games 3
1.1.1. Nim 6
1.1.2. Bouton’s solution of Nim 7
1.1.3. Other impartial games 8
1.2. Partisan games 10
1.2.1. The game of Hex 12
1.2.2. Topology and Hex: A path of arrows* 12
1.2.3. Hex and Y 14
1.2.4. More general boards* 16
1.2.5. Other partisan games played on graphs 17
Notes 21 Exercises 22

Chapter 2. Two-person zero-sum games 24
2.1. Examples 24
2.2. Definitions 26
2.3. The Minimax Theorem and its meaning 27
2.4. Simplifying and solving zero-sum games 28
2.4.1. Pure optimal strategies: Saddle points 28
2.4.2. Equalizing payoffs 29
2.4.3. The technique of domination 29
2.4.4. Using symmetry 31
2.5. Nash equilibria, equalizing payoffs, and optimal strategies 33
2.5.1. A first glimpse of incomplete information 34
2.6. Proof of von Neumann’s Minimax Theorem* 35
2.7. Zero-sum games with infinite action spaces* 38
Notes 38
Exercises 40

Chapter 3. Zero-sum games on graphs 45
3.1. Games in series and in parallel 45
3.1.1. Resistor networks and troll games 46
3.2. Hide and Seek games 48
3.2.1. Maximum matching and minimum covers 49
3.3. A pursuit-evasion game: Hunter and Rabbit* 52
3.3.1. Towards optimal strategies 53
3.3.2. The hunter’s strategy 54
3.3.3. The rabbit’s strategy 55
3.4. The Bomber and Battleship game 59
Notes 59
Exercises 60

Chapter 4. General-sum games 64
4.1. Some examples 64
4.2. Nash equilibria 67
4.3. General-sum games with more than two players 71
4.3.1. Symmetric games 75
4.4. Potential games 75
4.4.1. The general notion 77
4.4.2. Additional examples 78
4.5. Games with infinite strategy spaces 80
4.6. The market for lemons 82
Notes 83
Exercises 84

Chapter 5. Existence of Nash equilibria and fixed points 89
5.1. The proof of Nash’s Theorem 89
5.2. Fixed-point theorems* 90
5.2.1. Easier fixed-point theorems 91
5.2.2. Sperner’s Lemma 92
5.2.3. Brouwer’s Fixed-Point Theorem 93
5.3. Brouwer’s Fixed-Point Theorem via Hex* 96
5.4. Sperner’s Lemma in higher dimensions* 98
Notes 102
Exercises 102

Chapter 6. Games in extensive form 104
6.1. Introduction 104
6.2. Games of imperfect information 109
6.2.1. Behavioral strategies 110
6.3. Games of incomplete information 112
6.3.1. Bayesian games 113
6.3.2. Signaling 116
6.3.3. Zero-sum games of incomplete information 117
6.3.4. Summary: Comparing imperfect and incomplete information 118
6.4. Repeated games 119
6.4.1. Repetition with discounting 120
6.4.2. The Folk Theorem for average payoffs 121
6.4.3. Proof of Theorem 6.4.10* 123
Notes 124
Exercises 125

Chapter 7. Evolutionary and correlated equilibria 127
7.1. Evolutionary game theory 127
7.1.1. Hawks and Doves 127
7.1.2. Evolutionarily stable strategies 128
7.2. Correlated equilibria 132
Notes 135
Exercises 136

Chapter 8. The price of anarchy 138
8.1. Selfish routing 138
8.1.1. Bounding the price of anarchy 141
8.1.2. Affine latency functions 143
8.1.3. Existence of equilibrium flows 143
8.1.4. Beyond affine latency functions 144
8.1.5. A traffic-anarchy tradeoff 146
8.2. Network formation games 146
8.3. A market sharing game 148
8.4. Atomic selfish routing 150
8.4.1. Extension theorems 152
8.4.2. Application to atomic selfish routing 154
Notes 154
Exercises 155

Chapter 9. Random-turn games 161
9.1. Examples 161
9.2. Optimal strategy for random-turn selection games 162
9.3. Win-or-lose selection games 164
9.3.1. Length of play for random-turn Recursive Majority 165
Notes 166
Exercises 167

Part II: Designing games and mechanisms 169
Chapter 10. Stable matching and allocation 170
10.1. Introduction 170
10.2. Algorithms for finding stable matchings 171
10.3. Properties of stable matchings 172
10.3.1. Preferences by compatibility 174
10.3.2. Truthfulness 175
10.4. Trading agents 176
Notes 176
Exercises 178

Chapter 11. Fair division 183
11.1. Cake cutting 183
11.1.1. Cake cutting via Sperner’s Lemma 185
11.2. Bankruptcy 188
Notes 192
Exercises 193

Chapter 12. Cooperative games 194
12.1. Transferable utility games 194
12.2. The core 195
12.3. The Shapley value 196
12.3.1. Shapley’s axioms 196
12.3.2. Shapley’s Theorem 198
12.3.3. Additional examples 199
12.4. Nash bargaining 200
Notes 203
Exercises 205

Chapter 13. Social choice and voting 206
13.1. Voting and ranking mechanisms 206
13.2. Definitions 208
13.3. Arrow’s Impossibility Theorem 209
13.4. The Gibbard-Satterthwaite Theorem 210
13.5. Desirable properties for voting and ranking 210
13.6. Analysis of specific voting rules 211
13.7. Proof of Arrow’s Impossibility Theorem* 214
13.8. Proof of the Gibbard-Satterthwaite Theorem* 216
Notes 218
Exercises 221

Chapter 14. Auctions 223
14.1. Single item auctions 223
14.1.1. Bidder model 224
14.2. Independent private values 226
14.3. Revenue in single-item auctions 227
14.4. Toward revenue equivalence 228
14.4.1. I.I.D. bidders 229
14.4.2. Payment and revenue equivalence 230
14.4.3. Applications 231
14.5. Auctions with a reserve price 232
14.5.1. Revenue equivalence with reserve prices 233
14.5.2. Entry fee versus reserve price 233
14.5.3. Evaluation fee 234
14.5.4. Ex-ante versus ex-interim versus ex-post 235
14.6. Characterization of Bayes-Nash equilibrium 236
14.7. Price of anarchy in auctions 239
14.8. The Revelation Principle 240
14.9. Myerson’s optimal auction 242
14.9.1. The optimal auction for a single bidder 242
14.9.2. A two-bidder special case 243
14.9.3. A formula for the expected payment 245
14.9.4. The multibidder case 245
14.10. Approximately optimal auctions 248
14.10.1. The advantage of just one more bidder 248
14.10.2. When only the highest bidder can win 248
14.10.3. The Lookahead auction is approximately optimal 249
14.11. The plot thickens... 250
Notes 252
Exercises 253

Chapter 15. Truthful auctions in win/lose settings 257
15.1. The second-price auction and beyond 257
15.2. Win/lose allocation settings 258
15.3. Social surplus and the VCG mechanism 259
15.4. Applications 260 15.4.1. Shared communication channel, revisited 260
15.4.2. Spanning tree auctions 260
15.4.3. Public project 261
15.5. Sponsored search auctions, GSP, and VCG 264
15.5.1. Another view of the VCG auction for sponsored search 265
15.5.2. Generalized second-price mechanism 267
15.6. Back to revenue maximization 270
15.6.1. Revenue maximization without priors 270
15.6.2. Revenue extraction 271
15.6.3. An approximately optimal auction 272
Notes 273
Exercises 274

Chapter 16. VCG and scoring rules 278
16.1. Examples 278
16.2. Social surplus maximization and the general VCG mechanism 279
16.3. Scoring rules 283
16.3.1. Keeping the meteorologist honest 283
16.3.2. A solution 283
16.3.3. A characterization of scoring rules* 284
Notes 286
Exercises 287

Chapter 17. Matching markets 289
17.1. Maximum weighted matching 289
17.2. Envy-free prices 291
17.2.1. Highest and lowest envy-free prices 291
17.2.2. Seller valuations and unbalanced markets 294
17.3. Envy-free division of rent 294
17.4. Finding maximum matchings via ascending auctions 295
17.5. Matching buyers and sellers 296
17.5.1. Positive seller values 297
17.6. Application to weighted hide-and-seek games 298
Notes 299
Exercises 301

Chapter 18. Adaptive decision making 302
18.1. Binary prediction with expert advice and a perfect expert 302
18.2. Nobody is perfect 305
18.2.1. Weighted majority 305
18.3. Multiple choices and varying costs 307
18.3.1. Discussion 308
18.3.2. The Multiplicative Weights Algorithm 308
18.3.3. Gains 311
18.4. Using adaptive decision making to play zero-sum games 311
18.5. Adaptive decision making as a zero-sum game* 313
18.5.1. Minimax regret is attained in {0,1} losses 313
18.5.2. Optimal adversary strategy 314
18.5.3. The case of two actions 315
18.5.4. Adaptive versus oblivious adversaries 317
Notes 319
Exercises 320

Appendix A. Linear programming 323
A.1. The Minimax Theorem and linear programming 323
A.2. Linear programming basics 324
A.2.1. Linear programming duality 325
A.2.2. Duality, more formally 325
A.2.3. An interpretation of a primal/dual pair 326
A.2.4. The proof of the Duality Theorem* 328
A.3. Notes 331
Exercises 331

Appendix B. Some useful probability tools 332
B.1. The second moment method 332
B.2. The Hoeffding-Azuma Inequality 332
Appendix C. Convex functions 334
Appendix D. Solution sketches for selected exercises 338
Bibliography 349
Index 365