This book presents a rigorous introduction to the mathematics of game theory without losing sight of the joy of the subject. This is done by focusing on theoretical highlights (e.g., at least six Nobel Prize winning results are developed from scratch) and by presenting exciting connections of game theory to other fields, such as computer science, economics, social choice, biology, and learning theory. Both classical topics, such as zero-sum games, and modern topics, such as sponsored search auctions, are covered. Along the way, beautiful mathematical tools used in game theory are introduced, including convexity, fixed-point theorems, and probabilistic arguments.

The book is appropriate for a first course in game theory, either at the undergraduate or graduate level, whether in mathematics, economics, computer science, or statistics.

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