Transcription
ii“Alles” — 2014/5/8 — 11:19 — page i — #1iiGame TheoryThrough Examplesiiii
ii“Alles” — 2014/5/8 — 11:36 — page ii — #2iic 2014 by the Mathematical Association of America, Inc.Electronic edition ISBN 978-1-61444-115-1iiii
ii“Alles” — 2014/5/8 — 11:19 — page iii — #3iiGame TheoryThrough ExamplesErich PrisnerFranklin University SwitzerlandPublished and Distributed byThe Mathematical Association of Americaiiii
ii“Alles” — 2014/5/8 — 11:19 — page iv — #4iiCouncil on Publications and CommunicationsFrank Farris, ChairCommittee on BooksFernando Gouvêa, ChairClassroom Resource Materials Editorial BoardSusan G Staples, EditorMichael BardzellJennifer BergnerCaren L DiefenderferChristopher HallstromCynthia J HuffmanPaul R KlingsbergBrian LinsMary MorleyPhilip P MummertBarbara E ReynoldsDarryl Yongiiii
ii“Alles” — 2014/5/8 — 11:19 — page v — #5iiCLASSROOM RESOURCE MATERIALSClassroom Resource Materials is intended to provide supplementary classroom material for students—laboratory exercises, projects, historical information, textbooks with unusual approaches for presenting mathematical ideas, career information, etc.101 Careers in Mathematics, 3rd edition edited by Andrew SterrettArchimedes: What Did He Do Besides Cry Eureka?, Sherman SteinCalculus: An Active Approach with Projects, Stephen Hilbert, Diane Driscoll Schwartz, Stan Seltzer, JohnMaceli, and Eric RobinsonCalculus Mysteries and Thrillers, R. Grant WoodsConjecture and Proof, Miklós LaczkovichCounterexamples in Calculus, Sergiy KlymchukCreative Mathematics, H. S. WallEnvironmental Mathematics in the Classroom, edited by B. A. Fusaro and P. C. KenschaftExcursions in Classical Analysis: Pathways to Advanced Problem Solving and Undergraduate Research, byHongwei ChenExplorations in Complex Analysis, Michael A. Brilleslyper, Michael J. Dorff, Jane M. McDougall, James S.Rolf, Lisbeth E. Schaubroeck, Richard L. Stankewitz, and Kenneth StephensonExploratory Examples for Real Analysis, Joanne E. Snow and Kirk E. WellerExploring Advanced Euclidean Geometry with GeoGebra, Gerard A. VenemaGame Theory Through Examples, Erich PrisnerGeometry From Africa: Mathematical and Educational Explorations, Paulus GerdesHistorical Modules for the Teaching and Learning of Mathematics (CD), edited by Victor Katz and KarenDee MichalowiczIdentification Numbers and Check Digit Schemes, Joseph KirtlandInterdisciplinary Lively Application Projects, edited by Chris ArneyInverse Problems: Activities for Undergraduates, Charles W. GroetschKeeping it R.E.A.L.: Research Experiences for All Learners, Carla D. Martin and Anthony TongenLaboratory Experiences in Group Theory, Ellen Maycock ParkerLearn from the Masters, Frank Swetz, John Fauvel, Otto Bekken, Bengt Johansson, and Victor KatzMath Made Visual: Creating Images for Understanding Mathematics, Claudi Alsina and Roger B. NelsenMathematics Galore!: The First Five Years of the St. Marks Institute of Mathematics, James TantonMethods for Euclidean Geometry, Owen Byer, Felix Lazebnik, and Deirdre L. SmeltzerOrdinary Differential Equations: A Brief Eclectic Tour, David A. SánchezOval Track and Other Permutation Puzzles, John O. KiltinenParadoxes and Sophisms in Calculus, Sergiy Klymchuk and Susan StaplesA Primer of Abstract Mathematics, Robert B. AshProofs Without Words, Roger B. NelsenProofs Without Words II, Roger B. NelsenRediscovering Mathematics: You Do the Math, Shai Simonsoniiii
ii“Alles” — 2014/5/8 — 11:19 — page vi — #6iiShe Does Math!, edited by Marla ParkerSolve This: Math Activities for Students and Clubs, James S. TantonStudent Manual for Mathematics for Business Decisions Part 1: Probability and Simulation, DavidWilliamson, Marilou Mendel, Julie Tarr, and Deborah YoklicStudent Manual for Mathematics for Business Decisions Part 2: Calculus and Optimization,Williamson, Marilou Mendel, Julie Tarr, and Deborah YoklicDavidTeaching Statistics Using Baseball, Jim AlbertVisual Group Theory, Nathan C. CarterWhich Numbers are Real?, Michael HenleWriting Projects for Mathematics Courses: Crushed Clowns, Cars, and Coffee to Go, Annalisa Crannell,Gavin LaRose, Thomas Ratliff, and Elyn RykkenMAA Service CenterP.O. Box 91112Washington, DC 20090-11121-800-331-1MAAFAX: 1-301-206-9789iiii
ii“Alles” — 2014/5/8 — 11:19 — page vii — #7iiContentsPrefacexvi1 Theory 1: Introduction1.1 What’s a Game? . . . . . . . . . . . .1.2 Game, Play, Move: Some Definitions1.3 Classification of Games . . . . . . . .Exercises . . . . . . . . . . . . . . . . . .111232 Theory 2: Simultaneous Games2.1 Normal Form—Bimatrix Description . . . . .2.1.1 Two Players . . . . . . . . . . . . . .2.1.2 Two Players, Zero-sum . . . . . . . .2.1.3 Three or More Players . . . . . . . .2.1.4 Symmetric Games . . . . . . . . . .2.2 Which Option to Choose . . . . . . . . . . .2.2.1 Maximin Move and Security Level . .2.2.2 Dominated Moves . . . . . . . . . .2.2.3 Best Response . . . . . . . . . . . .2.2.4 Nash Equilibria . . . . . . . . . . . .2.3 Additional Topics . . . . . . . . . . . . . . .2.3.1 Best Response Digraphs . . . . . . .2.3.2 2-Player Zero-sum Symmetric GamesExercises . . . . . . . . . . . . . . . . . . . . . .Project 1: Reacting fast or slow . . . . . . . . . . .444556667891313141518.19191921212223232324243 Example: Selecting a Class3.1 Three Players, Two Classes3.1.1 “I like you both” .3.1.2 Disliking the Rival3.1.3 Outsider . . . . . .3.2 Larger Cases . . . . . . .3.3 Assumptions . . . . . . .Exercises . . . . . . . . . . . .Project 2 . . . . . . . . . . . . .Project 3 . . . . . . . . . . . . .Project 4 . . . . . . . . . . . . .viiiiii
ii“Alles” — 2014/5/8 — 11:19 — page viii — #8iiviiiContents4 Example: Doctor Location Games4.1 Doctor Location . . . . . . . . . . . . . . . . . . . . . . .4.1.1 An Example Graph . . . . . . . . . . . . . . . . .4.1.2 No (Pure) Nash Equilibrium? . . . . . . . . . . .4.1.3 How Good are the Nash Equilibria for the Public?4.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3 More than one Office (optional) . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 5: Doctor location on MOPs . . . . . . . . . . . . . . .Project 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25252627282831313333335 Example: Restaurant Location Games5.1 A First Graph . . . . . . . . . . . .5.2 A Second Graph . . . . . . . . . . .5.3 Existence of Pure Nash Equilibria .5.4 More than one Restaurant (optional)Exercises . . . . . . . . . . . . . . . . .3435363738396 Using Excel6.1 Spreadsheet Programs like Excel .6.2 Two-Person Simultaneous Games6.3 Three-Person Simultaneous GamesExercises . . . . . . . . . . . . . . . .Project 8: Simultaneous Quatro-Uno . .Project 9: Restaurant Location Games .Project 10: 5 Knights . . . . . . . . . .Project 11: 5 Cardinals . . . . . . . . .4242434343444445457 Example: Election I7.1 First Example . . . . . . . . . .7.2 Second Example . . . . . . . .7.3 The General Model . . . . . . .7.4 Third Example . . . . . . . . .7.5 The Eight Cases . . . . . . . . .7.6 Voting Power Indices (optional)Exercises . . . . . . . . . . . . . . .47474850505151528 Theory 3: Sequential Games I: Perfect Information and no Randomness8.1 Extensive Form: Game Tree and Game Digraph . . . . . . . . . . . . .8.2 Analyzing the Game: Backward Induction . . . . . . . . . . . . . . . .8.2.1 Finite Games . . . . . . . . . . . . . . . . . . . . . . . . . . .8.2.2 The Procedure . . . . . . . . . . . . . . . . . . . . . . . . . .8.2.3 Zermelo’s Theorem . . . . . . . . . . . . . . . . . . . . . . . .8.3 Additional Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8.3.1 Reality Check . . . . . . . . . . . . . . . . . . . . . . . . . . .8.3.2 Playing it Safe—Guaranteed Payoffs . . . . . . . . . . . . . .8.3.3 Two-person Zero-sum Games . . . . . . . . . . . . . . . . . .53535656575959596163.iiii
ii“Alles” — 2014/5/8 — 11:19 — page ix — #9iiixContents8.3.48.3.58.3.6ExercisesProject 12:Project 13:Project 14:Project 15:Project 16:Breaking Ties . .Existing Games .Greedy Strategies. . . . . . . . . . .TAKE SOME . . .WHO’s NEXT(n) .LISA’s GAME . .2-AUCTION . . .3-AUCTION . . .6464656569696969699 Example: Dividing A Few Items I9.1 Greedy Strategy . . . . . . . . . . . . . . . . .9.2 Backward Induction . . . . . . . . . . . . . . .9.2.1 Game Tree . . . . . . . . . . . . . . .9.2.2 Game Digraph . . . . . . . . . . . . .9.2.3 Example: Game Digraph for ABBAB .9.3 An Abbreviated Analysis . . . . . . . . . . . .9.3.1 Why it Matters: Complexity (optional)9.4 Bottom-Up Analysis . . . . . . . . . . . . . .9.5 Interdependencies between the Items (optional)Exercises . . . . . . . . . . . . . . . . . . . . . . .707071717172727475767610 Example: Shubik Auction I77Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79Project 17: SHUBIK AUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7911 Example: Sequential Doctor and Restaurant Location11.1 General Observations for Symmetric Games . . . . . . . . . . . .11.2 Doctor Location . . . . . . . . . . . . . . . . . . . . . . . . . . .11.3 Constant-Sum Games . . . . . . . . . . . . . . . . . . . . . . . .11.4 Restaurant Location . . . . . . . . . . . . . . . . . . . . . . . . .11.5 Nash Equilibria and First Mover Advantage for Symmetric GamesExercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 19: Hostile versus Friendly Play . . . . . . . . . . . . . . . . .80808182838484858512 Theory 4: Probability12.1 Terminology . . . . . . . . . . . . . . . .12.2 Computing Probabilities . . . . . . . . .12.2.1 Equally Likely Simple Events . .12.2.2 Simple Events not Equally Likely12.3 Expected Value . . . . . . . . . . . . . .12.4 Multistep Experiments . . . . . . . . . .12.4.1 Probability Trees . . . . . . . . .12.4.2 Conditional Probabilities . . . . .12.4.3 Probability Digraphs . . . . . . .12.5 Randomness in Simultaneous Games . . .12.6 Counting without Counting . . . . . . . .868688888889919191939495.iiii
ii“Alles” — 2014/5/8 — 11:19 — page x — #10iixContentsExercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95Project 20: Tennis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97Project 21: Final Exam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9813 France 165499Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10114 Example: DMA Soccer I14.1 1-Round 2-Step Experiment for Given Player Distributions14.2 Expected Goal Difference for the One-Round Game . . . .14.3 3-Rounds Experiment for Given Player Distributions . . .14.4 Static Three-round Game . . . . . . . . . . . . . . . . . .14.5 Static Nine-round DMA Soccer . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 22: DMA6* Soccer . . . . . . . . . . . . . . . . . . . .Project 23: DMA7* Soccer . . . . . . . . . . . . . . . . . . . .10210310410510710810810910915 Example: Dividing A Few Items II15.1 Goals of Fairness and Efficiency . . . . . . . . . . . . . . . . . . . .15.1.1 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.1.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.1.3 Three Additional Features . . . . . . . . . . . . . . . . . . .15.1.4 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . .15.2 Some Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.2.1 Selecting one by one Games . . . . . . . . . . . . . . . . . .15.2.2 Cut and Choose . . . . . . . . . . . . . . . . . . . . . . . . .15.2.3 Random and Exchange . . . . . . . . . . . . . . . . . . . . .15.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15.4 Comparison of the Games for Seven Items and Complete Information15.4.1 Opposing or Similar Preferences . . . . . . . . . . . . . . . .15.5 Incomplete Information . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 24: Dividing five items A . . . . . . . . . . . . . . . . . . . . . . .Project 25: Dividing five items B . . . . . . . . . . . . . . . . . . . . . . 2016 Theory 5: Sequential Games with Randomness16.1 Extensive Form Extended . . . . . . . . . . . . . . . . . . . . . . . . .16.2 Analyzing the Game: Backward Induction again . . . . . . . . . . . . .16.3 Decision Theory: Alone against Nature . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 26: Job Interviews . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 27: 5 Envelopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 28: Oh-No or Oh-No6 . . . . . . . . . . . . . . . . . . . . . . . . .Project 29: 3 4 version of Polyomino REC THE SQUARE with randomness.121121121122125127127128128.17 Example: Sequential Quiz Show I12917.1 Candidates with Little Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12917.1.1 More May be Less . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130iiii
ii“Alles” — 2014/5/8 — 11:19 — page xi — #11iixiContents17.2 One Candidate Knows More . . . . . . . . . .17.2.1 Cindy Knows one Answer to be False .Exercises . . . . . . . . . . . . . . . . . . . . . . .Project 30: SEQUENTIAL QUIZ SHOW, clever AnnProject 31: SEQUENTIAL QUIZ SHOW, clever Beth.13113313313413418 Las Vegas 1962135Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13819 Example: Mini Blackjack and Card Counting19.1 The Basic Game . . . . . . . . . . . . . . . .19.2 Playing against the House . . . . . . . . . . .19.2.1 How Likely are the Distributions? . .19.2.2 Betting High and Low . . . . . . . .19.2.3 Reshuffling . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . .Project 32: 8 ROUNDS BLACK OR WHITE . . .Project 33: x ROUNDS RED, GREEN, OR BLUEProject 34: MINI BLACKJACK . . . . . . . . . .13913914214314514614714714814820 Example: Duel20.1 One Bullet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20.1.1 Analysis of One-bullet Variants with Increasing Probabilities without Computer Help20.1.2 Analysis of DUEL(1; 1jm; 2m; 3m; : : :) . . . . . . . . . . . . . . . . . . . . . . . .20.2 Two or more Bullets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20.2.1 A few Cases of DUEL(2; 2jm; 2m; 3m; : : :) . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 35: Drunk Adam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 36: How more dangerous weapons affect the state budget and the health of citizens . . . .Project 37: Selecting m between 0.04 and 0.13 . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 38: What duels are best for society? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149149150151152153154154154154155.21 Santa Monica in the 50s15622 Theory 6: Extensive Form of General Games22.1 Extensive Form and Information Sets . . . . . . . .22.2 No Backward Induction for Imperfect Information .22.3 Subgames . . . . . . . . . . . . . . . . . . . . . .22.4 Multi-round Games . . . . . . . . . . . . . . . . .22.5 Why Trees for Imperfect Information? . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . .15915916316416516516623 Example: Shubik Auction II23.1 Possible Sudden End . . . . . . . . . . . .23.2 Imperfect and Incomplete Information . . .23.3 The Auctioneer Enters the Game (optional)Exercises . . . . . . . . . . . . . . . . . . . . .Project 39 . . . . . . . . . . . . . . . . . . . . .169169172172174174.iiii
ii“Alles” — 2014/5/8 — 11:19 — page xii — #12iixiiContentsProject 40 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174Project 41: SHUBIK AUCTION(45; 35; 6; p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175Project 42: SHUBIK AUCTION(A; B; C; n; p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17524 Theory 7: Normal Form and Strategies24.1 Pure Strategies . . . . . . . . . . . . . . . . . . . . . . . .24.1.1 Reduced Pure Strategies . . . . . . . . . . . . . . .24.2 Normal Form . . . . . . . . . . . . . . . . . . . . . . . . .24.3 Using Tools from Simultaneous Games for the Normal Form24.4 Subgame Perfectness . . . . . . . . . . . . . . . . . . . . .24.5 Special Case of Sequential Games with Perfect Information .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17617617717718018018218225 Example: VNM POKER and KUHN POKER25.1 Description . . . . . . . . . . . . . . . . .25.2 VNM POKER . . . . . . . . . . . . . . . .25.3 KUHN POKER . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . .18518518719019126 Example: Waiting for Mr. Perfect26.1 The Last Round . . . . . . . . . . . . . . . . .26.2 The Eight Pure Strategies . . . . . . . . . . . .26.3 Computing the Payoffs . . . . . . . . . . . . .26.4 Domination . . . . . . . . . . . . . . . . . . .26.5 The Reduced Normal Forms in the Three Cases26.5.1 The Case p2 C 2p3 1 . . . . . . . .26.5.2 The Case p2 C 2p3 1 . . . . . . . .26.5.3 The Case p2 C 2p3 D 1 . . . . . . . .Project 43 . . . . . . . . . . . . . . . . . . . . . . .Project 44 . . . . . . . . . . . . . . . . . . . . . . .Project 45 . . . . . . . . . . . . . . . . . . . . . . .Project 46 . . . . . . . . . . . . . . . . . . . . . . .Project 47 . . . . . . . . . . . . . . . . . . . . . . .Project 48 . . . . . . . . . . . . . . . . . . . . . . 199200200202203203203204205207209210.27 Theory 8: Mixed Strategies27.1 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.1.1 Best Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.1.2 Brown’s Fictitious Play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.1.3 Mixed Maximin Strategy, Mixed Security Level, and Linear Programs . . . . . .27.2 Mixed Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.2.1 Two-player Zero-sum Games . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.2.2 Non-Zero-sum Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.3 Computing Mixed Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27.3.1 Small Two-player Zero-sum Games (optional) . . . . . . . . . . . . . . . . . .27.3.2 Solving Small non Zero-sum Two-player Games by Solving Equations (optional)Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Project 49: Balanced 3-spinner duel with five options . . . . . . . . . . . . . . . . . . . . . .iiii
ii“Alles” — 2014/5/8 — 11:19 — page xiii — #13iixiiiContentsProject 50:Project 51:Project 52:Project 53:Project 54Project 55:Balanced 3-spinner duel . . . .COLONEL BLOTTO(4, 9, 9) .Iterated COLONEL BLOTTO .Simultaneous Quatro-Uno . . . . . . . . . . . . . . . . . . . .4-round Waiting for Mr. Perfect.21021021121121121128 Princeton in 195021229 Example: Airport Shuttle29.1 The Simple Model . . .29.1.1 To the Airport . .29.1.2 From the Airport29.1.3 Combining Both29.2 Impatient Customers . .Exercises . . . . . . . . . . .21521521521821821921930 Example: Election II30.1 Left Over from Election I . . . . . . . . . . .30.2 More Effort into Large Districts . . . . . . .30.3 Defend Where Ahead or Attack Where Weak?30.4 Is Larger Better? . . . . . . . . . . . . . . .30.5 ELECTION(7; 8; 13j 1; 1; 2jx; x/ . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . .22022022122222322322431 Example: VNM POKER(2; r; m; n)n31.1 The Case m 2 r1 . . . . . . . .31.2 Best Responses . . . . . . . . . . .31.3 Reading the Opponent (optional) . .n31.4 Mixed Nash Equilibrium for m 231.5 Small Changes in the Parameters . .Exercises . . . . . . . . . . . . . . . . .225226227227228229230. . . . . . . . . .1. .r. . . . . . .32 Theory 9: Behavioral Strategies32.1 Behavioral versus Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.1.1 Calculating Mixed Strategies from Behavioral Strategies . . . . . . . . . . . . . . .32.1.2 Calculating Behavioral Strategies from Mixed Strategies for a Game Tree with PerfectRecall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32.1.3 Kuhn’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 Example: Multiple-Round Chicken33.1 Ordinary Chicken . . . . . . . . . . . . . . . . . . . . . . . . . . .33.2 Two-round Chicken . . . . . . . . . . . . . . . . . . . . . . . . . .33.2.1 Generalized Backward Induction, using the Extensive Form33.2.2 Working with the Normal Form . . . . . . . . . . . . . . .33.2.3 Connections between the two Approaches . . . . . . . . . .33.3 Three-round Chicken . . . . . . . . . . . . . . . . . . . . . . . . .231. 232. 233. 233. 235. 235.237237238238240240241iiii
ii“Alles” — 2014/5/8 — 11:19 — page xiv — #14iixivContentsExercisesProject 56Project 57Project 58.24324324324334 Example: DMA Soccer II34.1 Multi-round Simultaneous Games . . . . . . .34.2 Information Sets and Moves . . . . . . . . . .34.3 The Optimal Third Move in Selected Cases . .34.3.1 A Detailed Example: (2, 2) versus (3, 1)34.3.2 A Second Example: (1, 3) versus (2, 2)34.4 The Optimal Second Move for Seven Positions34.5 Couldn’t We Analyze the Whole Game? . . . .34.6 How Good a Model is it? . . . . . . . . . . . .24424424524624624924925125135 Example: Sequential Quiz Show II35.1 Fixed Coalitions . . . . . . . . . . . . . .35.1.1 Ann and Cindy Form a Coalition .35.1.2 Ann and Beth Form a Coalition .35.1.3 Beth and Cindy Form a Coalition35.2 Which Coalition Will Form? . . . . . . .35.2.1 Fixed 50:50 Split . . . . . . . . .35.3 Another Variant: Split can be Negotiated .35.4 The Grand Coalition . . . . . . . . . . .35.4.1 The Core . . . . . . . . . . . . .35.4.2 The Shapley Value . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . .Project 59 . . . . . . . . . . . . . . . . . . . .252252252254254254254255256256256257258.36 Example: VNM POKER(4, 4, 3, 5)25936.1 Mixed Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25936.2 Performance of Pure Strategies against the Mixed Nash Equilibria . . . . . . . . . . . . . . . 26137 Example: KUHN POKER(3, 4, 2, 3)26437.1 From Behavioral Strategies to Mixed Strategies to Expectations . . . . . . . . . . . . . . . . 26537.2 From Mixed Strategies to Behavioral Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 266Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26638 Example: End-of-Semester Poker Tournament38.1 Expectations . . . . . . . . . . . . . . . . .38.2 Odds . . . . . . . . . . . . . . . . . . . . .38.2.1 Many Rounds . . . . . . . . . . . .38.3 The Favorite in Knockout Tournaments . .38.4 Similarity of the DNA (optional) . . . . . .38.5 How to Create your own Tournament . . . .Exercises . . . . . . . . . . . . . . . . . . . . .Project 60 . . . . . . . . . . . . . . . . . . . . .Project 61 . . . . . . . . . . . . . . . . . . . . .
"Alles" — 2014/5/8 — 11:36 — page ii — #2 c 2014by the Mathematical Associationof America,Inc. Electronic edition ISBN 978-1-61444-115-1
