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. Contents: 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