Game Theory, Alive Anna R. Karlin and Yuval Peres December 13, 2016 Please send comments and corrections to: [email protected] and [email protected] Contents Preface 1 An overview of the book 1 Part I: Analyzing games: Strategies and equilibria 1 Part II: Designing games and mechanisms 5 For the reader and instructor 8 Prerequisites 8 Courses 8 Notes 9 Part I: Analyzing games: Strategies and equilibria 11 Chapter 1. Combinatorial games 12 1.1. Impartial games 13 1.1.1. Nim 16 1.1.2. Bouton’s solution of Nim 17 1.1.3. Other impartial games 18 1.2. Partisan games 20 1.2.1. The game of Hex 22 1.2.2. Topology and Hex: A path of arrows* 22 1.2.3. Hex and Y 24 1.2.4. More general boards* 26 1.2.5. Other partisan games played on graphs 27 Notes 31 Exercises 32 Chapter 2. Two-person zero-sum games 34 2.1. Examples 34 2.2. Definitions 36 2.3. The Minimax Theorem and its meaning 37 2.4. Simplifying and solving zero-sum games 38 2.4.1. Pure optimal strategies: Saddle points 38 2.4.2. Equalizing payoffs 39 2.4.3. The technique of domination 39 2.4.4. Using symmetry 41 2.5. Nash equilibria, equalizing payoffs, and optimal strategies 43 2.5.1. A first glimpse of incomplete information 44 2.6. Proof of von Neumann’s Minimax Theorem∗ 45 2.7. Zero-sum games with infinite action spaces∗ 48 Notes 48 Exercises 50 Chapter 3. Zero-sum games on graphs 55 3.1. Games in series and in parallel 55 3.1.1. Resistor networks and troll games 56 3.2. Hide and Seek games 58 3.2.1. Maximum matching and minimum covers 59 3.3. A pursuit-evasion game: Hunter and Rabbit∗ 62 3.3.1. Towards optimal strategies 63 3.3.2. The hunter’s strategy 64 3.3.3. The rabbit’s strategy 65 3.4. The Bomber and Battleship game 69 Notes 69 Exercises 70 Chapter 4. General-sum games 74 4.1. Some examples 74 4.2. Nash equilibria 77 4.3. General-sum games with more than two players 81 4.3.1. Symmetric games 85 4.4. Potential games 85 4.4.1. The general notion 87 4.4.2. Additional examples 88 4.5. Games with infinite strategy spaces 90 4.6. The market for lemons 92 Notes 93 Exercises 94 Chapter 5. Existence of Nash equilibria and fixed points 99 5.1. The proof of Nash’s Theorem 99 5.2. Fixed-point theorems∗ 100 5.2.1. Easier fixed-point theorems 101 5.2.2. Sperner’s Lemma 102 5.2.3. Brouwer’s Fixed-Point Theorem 103 5.3. Brouwer’s Fixed-Point Theorem via Hex* 106 5.4. Sperner’s Lemma in higher dimensions∗ 108 Notes 112 Exercises 112 Chapter 6. Games in extensive form 114 6.1. Introduction 114 6.2. Games of imperfect information 119 6.2.1. Behavioral strategies 120 6.3. Games of incomplete information 122 6.3.1. Bayesian games 123 6.3.2. Signaling 126 6.3.3. Zero-sum games of incomplete information 127 6.3.4. Summary: comparing imperfect and incomplete information 128 6.4. Repeated games 129 6.4.1. Repetition with discounting 130 6.4.2. The Folk Theorem for average payoffs 131 6.4.3. Proof of Theorem 6.4.10∗ 133 Notes 134 Exercises 135 Chapter 7. Evolutionary and correlated equilibria 137 7.1. Evolutionary game theory 137 7.1.1. Hawks and Doves 137 7.1.2. Evolutionarily stable strategies 138 7.2. Correlated equilibria 142 Notes 145 Exercises 146 Chapter 8. The price of anarchy 148 8.1. Selfish routing 148 8.1.1. Bounding the price of anarchy 151 8.1.2. Affine latency functions 153 8.1.3. Existence of equilibrium flows 153 8.1.4. Beyond affine latency functions 154 8.1.5. A traffic-anarchy tradeoff 156 8.2. Network formation games 156 8.3. A market sharing game 158 8.4. Atomic selfish routing 160 8.4.1. Extension theorems 162 8.4.2. Application to atomic selfish routing 164 Notes 164 Exercises 165 Chapter 9. Random-turn games 171 9.1. Examples 171 9.2. Optimal strategy for random-turn selection games 172 9.3. Win-or-lose selection games 174 9.3.1. Length of play for random-turn Recursive Majority 175 Notes 176 Exercises 176 Part II: Designing games and mechanisms 179 Chapter 10. Stable matching and allocation 180 10.1. Introduction 180 10.2. Algorithms for finding stable matchings 181 10.3. Properties of stable matchings 182 10.3.1. Preferences by compatibility 184 10.3.2. Truthfulness 185 10.4. Trading agents 186 Notes 186 Exercises 188 Chapter 11. Fair division 193 11.1. Cake cutting 193 11.1.1. Cake cutting via Sperner’s Lemma 195 11.2. Bankruptcy 198 Notes 202 Exercises 203 Chapter 12. Cooperative games 204 12.1. Transferable utility games 204 12.2. The core 205 12.3. The Shapley value 206 12.3.1. Shapley’s axioms 206 12.3.2. Shapley’s Theorem 208 12.3.3. Additional examples 209 12.4. Nash bargaining 210 Notes 213 Exercises 215 Chapter 13. Social choice and voting 216 13.1. Voting and ranking mechanisms 216 13.2. Definitions 218 13.3. Arrow’s Impossibility Theorem 219 13.4. The Gibbard-Satterthwaite Theorem 220 13.5. Desirable properties for voting and ranking 220 13.6. Analysis of specific voting rules 221 13.7. Proof of Arrow’s Impossibility Theorem∗ 224 13.8. Proof of the Gibbard-Satterthwaite Theorem∗ 226 Notes 228 Exercises 231 Chapter 14. Auctions 233 14.1. Single item auctions 233 14.1.1. Bidder model 234 14.2. Independent private values 236 14.3. Revenue in single-item auctions 237 14.4. Toward revenue equivalence 238 14.4.1. I.I.D. bidders 239 14.4.2. Payment and revenue equivalence 240 14.4.3. Applications 241 14.5. Auctions with a reserve price 242 14.5.1. Revenue equivalence with reserve prices 243 14.5.2. Entry fee versus reserve price 243 14.5.3. Evaluation fee 244 14.5.4. Ex-ante versus ex-interim versus ex-post 245 14.6. Characterization of Bayes-Nash equilibrium 246 14.7. Price of anarchy in auctions 249 14.8. The Revelation Principle 250 14.9. Myerson’s optimal auction 252 14.9.1. The optimal auction for a single bidder 252 14.9.2. A two-bidder special case 253 14.9.3. A formula for the expected payment 255 14.9.4. The multibidder case 255 14.10. Approximately optimal auctions 258 14.10.1. The advantage of just one more bidder 258 14.10.2. When only the highest bidder can win 258 14.10.3. The Lookahead auction is approximately optimal 259 14.11. The plot thickens... 260 Notes 262 Exercises 264 Chapter 15. Truthful auctions in win/lose settings 267 15.1. The second-price auction and beyond 267 15.2. Win/lose allocation settings 268 15.3. Social surplus and the VCG mechanism 269 15.4. Applications 270 15.4.1. Shared communication channel, revisited 270 15.4.2. Spanning tree auctions 270 15.4.3. Public project 271 15.5. Sponsored search auctions, GSP, and VCG 274 15.5.1. Another view of the VCG auction for sponsored search 275 15.5.2. Generalized second-price mechanism 277 15.6. Back to revenue maximization 280 15.6.1. Revenue maximization without priors 280 15.6.2. Revenue extraction 281 15.6.3. An approximately optimal auction 282 Notes 283 Exercises 284 Chapter 16. VCG and scoring rules 288 16.1. Examples 288 16.2. Social surplus maximization and the general VCG mechanism 289 16.3. Scoring rules 293 16.3.1. Keeping the meteorologist honest 293 16.3.2. A solution 293 16.3.3. A characterization of scoring rules∗ 294 Notes 296 Exercises 297 Chapter 17. Matching markets 299 17.1. Maximum weighted matching 299 17.2. Envy-free prices 301 17.2.1. Highest and lowest envy-free prices 301 17.2.2. Seller valuations and unbalanced markets 304 17.3. Envy-free division of rent 304 17.4. Finding maximum matchings via ascending auctions 305 17.5. Matching buyers and sellers 306 17.5.1. Positive seller values 307 17.6. Application to weighted hide-and-seek games 307 Notes 309 Exercises 310 Chapter 18. Adaptive decision making 312 18.1. Binary prediction with expert advice and a perfect expert 312 18.2. Nobody is perfect 315 18.2.1. Weighted majority 315 18.3. Multiple choices and varying costs 317 18.3.1. Discussion 318 18.3.2. The Multiplicative Weights Algorithm 318 18.3.3. Gains 321 18.4. Using adaptive decision making to play zero-sum games 321 18.5. Adaptive decision making as a zero-sum game∗ 323 18.5.1. Minimax regret is attained in {0,1} losses 323 18.5.2. Optimal adversary strategy 324 18.5.3. The case of two actions 325 18.5.4. Adaptive versus oblivious adversaries 327 Notes 329 Exercises 330 Appendix A. Linear programming 333 A.1. The Minimax Theorem and linear programming 333 A.2. Linear programming basics 334 A.2.1. Linear programming duality 335 A.2.2. Duality, more formally 335 A.2.3. An interpretation of a primal/dual pair 336 A.2.4. The proof of the Duality Theorem∗ 338 A.3. Notes 341 Exercises 341 Appendix B. Some useful probability tools 342 B.1. The second moment method 342 B.2. The Hoeffding-Azuma Inequality 342 Appendix C. Convex functions 344 Appendix D. Solution sketches for selected exercises 348 Bibliography 359 Index 376 Preface We live in a highly connected world, with multiple self-interested agents inter- acting,leadingtomyriadopportunitiesforconflictandcooperation. Understanding these is the goal of game theory. It finds application in fields such as economics, business,politicalscience,biology,psychology,sociology,computerscience,anden- gineering. Conversely, ideas from the social sciences (e.g., fairness), from biology (evolutionarystability),fromstatistics(adaptivelearning),andfromcomputersci- ence (complexity of finding equilibria) have greatly enriched game theory. In this book, wepresentanintroductiontothisfield. Wewillseeapplicationsfromavari- etyofdisciplinesanddelveintosomeofthefascinatingmathematicsthatunderlies game theory. An overview of the book Part I: Analyzing games: Strategies and equilibria. WebegininChap- ter 1 with combinatorial games, in which two players take turns making moves until a winning position for one of them is reached. Figure 1. Two people playing Nim. A classic example of a combinatorial game is Nim. In this game, there are several piles of chips, and players take turns removing one or more chips from a single pile. The player who takes the last chip wins. We will describe a winning strategyforNimandshowthatalargeclassofcombinatorialgamescanbereduced to it. Other well-known combinatorial games are Chess, Go, and Hex. The youngest oftheseisHex,whichwasinventedbyPietHeinin1942andindependentlybyJohn Nash in 1947. Hex is played on a rhombus-shaped board tiled with small hexagons (seeFigure2). Twoplayers,BlueandYellow,alternatecoloringinhexagonsintheir assigned color, blue or yellow, one hexagon per turn. Blue wins if she produces 2 PREFACE Figure 2. The board for the game of Hex. a blue chain crossing between her two sides of the board and Yellow wins if he produces a yellow chain connecting the other two sides. We will show that the player who moves first has a winning strategy; finding this strategy remains an unsolved problem, except when the board is small. 28 27 30 33 29 34 41 32 31 36 43 40 26 35 38 45 42 23 37 46 53 44 25 22 39 52 24 48 55 19 51 50 47 54 56 21 4 62 1 57 20 2 5 49 66 58 61 13 3 64 67 60 14 18 8 68 63 59 15 11 65 16 12 7 9 69 17 10 6 Figure 3. The board position near the end of the match between Queenbee and Hexy at the 5th Computer Olympiad. Each hexagon is labeled by the timeatwhichitwasplacedontheboard. Bluemovesnext,butYellowhasa winning strategy. Can you see why? In an interesting variant of the game, the players, instead of alternating turns, toss a coin to determine who moves next. In this case, we can describe optimal strategies for the players. Such random-turn combinatorial games are the subject of Chapter 9. In Chapters 2–5, we consider games in which the players simultaneously select from a set of possible actions. Their selections are then revealed, resulting in a payoff to each player. For two players, these payoffs are represented using the matrices A = (a ) and B = (b ). When player I selects action i and player II ij ij selects action j, the payoffs to these players are a and b , respectively. Two- ij ij persongameswhereoneplayer’sgainistheotherplayer’sloss,thatis,a +b =0 ij ij for all i,j, are called zero-sum games. Such games are the topic of Chapter 2. AN OVERVIEW OF THE BOOK 3 We show that every zero-sum game has a value V such that player I can ensure her expected payoff is at least V (no matter how II plays) and player II can ensure he pays I at most V (in expectation) no matter how I plays. For example, in Penalty Kicks, a zero-sum game inspired by soccer, one player, the kicker, chooses to kick the ball either to the left or to the right of the otherplayer,thegoalie. Atthesameinstantasthekick,thegoalieguesseswhether to dive left or right. Figure 4. The game of Penalty Kicks. Thegoaliehasachanceofsavingthegoalifhedivesinthesamedirectionasthe kick. The kicker, who we assume is right-footed, has a greater likelihood of success if she kicks right. The probabilities that the penalty kick scores are displayed in the table below: goalie L R L 0.5 1 r e k R 1 0.8 c ki Forthissetofscoringprobabilities,theoptimalstrategyforthekickeristokickleft withprobability2/7andkickrightwithprobability5/7—thenregardlessofwhat thegoaliedoes,theprobabilityofscoringis6/7. Similarly,theoptimalstrategyfor the goalie is to dive left with probability 2/7 and dive right with probability 5/7. Chapter 3 goes on to analyze a number of interesting zero-sum games on graphs. For example, we consider a game between a Troll and a Traveler. Each ofthemchoosesaroute(asequenceofroads)fromSyracusetoTroy,andthenthey simultaneously disclose their routes. Each road has an associated toll. For each roadchosenbybothplayers,thetravelerpaysthetolltothetroll. Wefindoptimal strategies by developing a connection with electrical networks. In Chapter 4 we turn to general-sum games. In these games, players no longer have optimal strategies. Instead, we focus on situations where each player’s strategy is a best response to the strategies of the opponents: a Nash equilibrium is an assignment of (possibly randomized) strategies to the players, with the property that no player can gain by unilaterally changing his strategy.