Game Theory, Alive

1 game theory , AliveAnna R. Karlin and Yuval PeresDecember 13, 2016 Please send comments and corrections to AMS. License or copyright restrictions may apply to redistribution; see to AMS. License or copyright restrictions may apply to redistribution; see overview of the book1 Part I: Analyzing games : Strategies and equilibria1 Part II: Designing games and mechanisms5 For the reader and instructor8 Prerequisites8 Courses8 Notes9 Part I: Analyzing games : Strategies and equilibria11 chapter 1. Combinatorial Impartial Bouton s solution of Other impartial Partisan The game of Topology and Hex: A path of arrows* Hex and More general boards* Other partisan games played on graphs27 Notes31 Exercises32 chapter 2. Two-person zero-sum The Minimax Theorem and its Simplifying and solving zero-sum Pure optimal strategies: Saddle Equalizing The technique of Using Nash equilibria, equalizing payoffs, and optimal A first glimpse of incomplete Proof of von Neumann s Minimax Theorem Zero-sum games with infinite action spaces 48iiiLicensed to AMS.

2 License or copyright restrictions may apply to redistribution; see 3. Zero-sum games on games in series and in Resistor networks and troll Hide and Seek Maximum matching and minimum A pursuit-evasion game: Hunter and Rabbit Towards optimal hunter s rabbit s The Bomber and Battleship game69 Notes69 Exercises70 chapter 4. General-sum Some Nash General-sum games with more than two Symmetric Potential The general Additional games with infinite strategy The market for lemons92 Notes93 Exercises94 chapter 5. Existence of Nash equilibria and fixed The proof of Nash s Fixed-point theorems Easier fixed-point Sperner s Brouwer s Fixed-Point Brouwer s Fixed-Point Theorem via Hex* Sperner s Lemma in higher dimensions 108 Notes112 Exercises112 chapter 6. games in extensive games of imperfect Behavioral games of incomplete Bayesian Zero-sum games of incomplete Summary: comparing imperfect and incomplete Repeated games129 Licensed to AMS.

3 License or copyright restrictions may apply to redistribution; see Repetition with The Folk Theorem for average Proof of Theorem 133 Notes134 Exercises135 chapter 7. Evolutionary and correlated Evolutionary game Hawks and Evolutionarily stable Correlated equilibria142 Notes145 Exercises146 chapter 8. The price of Selfish Bounding the price of Affine latency Existence of equilibrium Beyond affine latency A traffic-anarchy Network formation A market sharing Atomic selfish Extension Application to atomic selfish routing164 Notes164 Exercises165 chapter 9. Random-turn Optimal strategy for random-turn selection Win-or-lose selection Length of play for random-turn Recursive Majority175 Notes176 Exercises176 Part II: Designing games and mechanisms179 chapter 10. Stable matching and Algorithms for finding stable Properties of stable Preferences by Trading agents186 Notes186 Exercises188 chapter 11.

4 Fair division193 Licensed to AMS. License or copyright restrictions may apply to redistribution; see Cake Cake cutting via Sperner s Bankruptcy198 Notes202 Exercises203 chapter 12. Cooperative Transferable utility The The Shapley Shapley s Shapley s Additional Nash bargaining210 Notes213 Exercises215 chapter 13. Social choice and Voting and ranking Arrow s Impossibility The Gibbard-Satterthwaite Desirable properties for voting and Analysis of specific voting Proof of Arrow s Impossibility Theorem Proof of the Gibbard-Satterthwaite Theorem 226 Notes228 Exercises231 chapter 14. Single item Bidder Independent private Revenue in single-item Toward revenue Payment and revenue Auctions with a reserve Revenue equivalence with reserve Entry fee versus reserve Evaluation Ex-ante versus ex-interim versus Characterization of Bayes-Nash Price of anarchy in The Revelation Myerson s optimal The optimal auction for a single A two-bidder special case253 Licensed to AMS.

5 License or copyright restrictions may apply to redistribution; see A formula for the expected The multibidder Approximately optimal The advantage of just one more When only the highest bidder can The Lookahead auction is approximately The plot 15. Truthful auctions in win/lose The second-price auction and Win/lose allocation Social surplus and the VCG Shared communication channel, Spanning tree Public Sponsored search auctions, GSP, and Another view of the VCG auction for sponsored Generalized second-price Back to revenue Revenue maximization without Revenue An approximately optimal auction282 Notes283 Exercises284 chapter 16. VCG and scoring Social surplus maximization and the general VCG Scoring Keeping the meteorologist A A characterization of scoring rules 294 Notes296 Exercises297 chapter 17.

6 matching Maximum weighted Envy-free Highest and lowest envy-free Seller valuations and unbalanced Envy-free division of Finding maximum matchings via ascending matching buyers and Positive seller Application to weighted hide-and-seek games307 Notes309 Licensed to AMS. License or copyright restrictions may apply to redistribution; see 18. Adaptive decision Binary prediction with expert advice and a perfect Nobody is Weighted Multiple choices and varying The Multiplicative Weights Using adaptive decision making to play zero-sum Adaptive decision making as a zero-sum game Minimax regret is attained in{0,1} Optimal adversary The case of two Adaptive versus oblivious adversaries327 Notes329 Exercises330 Appendix A. Linear The Minimax Theorem and linear Linear programming Linear programming Duality, more An interpretation of a primal/dual The proof of the Duality Theorem Notes341 Exercises341 Appendix B.

7 Some useful probability The second moment The Hoeffding-Azuma Inequality342 Appendix C. Convex functions344 Appendix D. Solution sketches for selected exercises348 Bibliography359 Index376 Licensed to AMS. License or copyright restrictions may apply to redistribution; see are grateful to Alan Hammond, Yun Long, G abor Pete, and Peter Ralphfor scribing early drafts of some of the chapters in this book from lectures by YuvalPeres. These drafts were edited by Liat Kessler, Asaf Nachmias, Sara Robinson,Yelena Shvets, and David Wilson. We are especially indebted to Yelena Shvetsfor her contributions to the chapters on combinatorial games and voting, and toDavid Wilson for numerous insightful edits. Their efforts greatly improved thebook. David was also a major force in writing the paper [PSSW07], which islargely reproduced in chapter 9. The expository style of that paper also inspiredour treatment of other topics in the thank TJ Gilbrough, Christine Hill, Isaac Kuek, Davis Shepherd, and Ye-lena Shvets for creating figures for the book.

8 We also thank Ranjit Samra for thelemon figure and Barry Sinervo for the picture in Figure The artistic drawingsin the book were created by Gabrielle Cohn, Nate Jensen, and Yelena Shvets. Weare extremely grateful to all three of Bartlett, Allan Borodin, Sourav Chatterjee, Amos Fiat, Elchanan Mossel,Asaf Nachmias, Allan Sly, Shobhana Stoyanov, and Markus Vasquez taught fromdrafts of the book and provided valuable suggestions and feedback. Thanks also toOmer Adelman, John Buscher, Gabriel Carroll, Jiechen Chen, Wenbo Cui, VarshaDani, Kira Goldner, Nick Gravin, Brian Gu, Kieran Kishore, Elias Koutsoupias,Itamar Landau, Shawn Lee, Eric Lei, Bryan Lu, Andrea McCool, Mallory Monas-terio, Andrew Morgan, Katia Nepom, Uuganbaatar Ninjbat, Miki Racz, ColleenRoss, Zhuohong Shen, Davis Shepherd, Stephanie Somersille, Kuai Yu, SithparranVanniasegaram, and Olga Zamaraeva for their helpful comments and support of the NSF VIGRE grant to the Department of Statistics at theUniversity of California, Berkeley, and NSF grants DMS-0244479, DMS-0104073,CCF-1016509, and CCF-1420381 is gratefully to AMS.

9 License or copyright restrictions may apply to redistribution; see to AMS. License or copyright restrictions may apply to redistribution; see live in a highly connected world, with multiple self-interested agents inter-acting, leading to myriad opportunities for conflict and cooperation. Understandingthese is the goal of game theory . It finds application in fields such as economics,business, political science, biology, psychology, sociology, computer science, and en-gineering. Conversely, ideas from the social sciences ( , fairness), from biology(evolutionary stability), from statistics (adaptive learning), and from computer sci-ence (complexity of finding equilibria) have greatly enriched game theory . In thisbook, we present an introduction to this field. We will see applications from a vari-ety of disciplines and delve into some of the fascinating mathematics that underliesgame overview of the bookPart I: Analyzing games : Strategies and begin inChap-ter 1withcombinatorial games , in which two players take turns making movesuntil a winning position for one of them is people playing classic example of a combinatorial game isNim.

10 In this game, there areseveral piles of chips, and players take turns removing one or more chips from asingle pile. The player who takes the last chip wins. We will describe a winningstrategy for Nim and show that a large class of combinatorial games can be reducedto well-known combinatorial games are Chess, Go, and Hex. The youngestof these isHex, which was invented by Piet Hein in 1942 and independently by JohnNash in 1947. Hex is played on a rhombus-shaped board tiled with small hexagons(see Figure 2). Two players, Blue and Yellow, alternate coloring in hexagons in theirassigned color, blue or yellow, one hexagon per turn. Blue wins if she produces1 Licensed to AMS. License or copyright restrictions may apply to redistribution; see board for the game of blue chain crossing between her two sides of the board and Yellow wins if heproduces a yellow chain connecting the other two will show that the player who moves first has a winning strategy; findingthis strategy remains an unsolved problem, except when the board is 3029323134333635 3837403942414443464548475060495251545356 55585759626164636665686769 Figure board position near the end of the match between Queenbeeand Hexy at the 5th Computer Olympiad.