Game Theory, Alive - University of Washington

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.

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

3 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.

4 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.

5 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. 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.

6 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.

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

8 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. 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.

9 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.

10 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.