Transcription
Gamethrough EXAMPLESERICHPRISNERCLASSROOM RESOURCE MATERIALS
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,Williamson, Marilou Mendel, Julie Tarr, and Deborah YoklicDavidStudent 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 . . . . . . . . . . . . . . . . . . .
Committeeon Books Fernando Gouveˆa, Chair Classroom Resource Materials Editorial Board Susan G Staples, Editor Michael Bardzell Jennifer Bergner Caren L Diefenderfer ChristopherHallstrom CynthiaJ Huffman Paul R Klingsberg BrianLins Mary Morley PhilipP Mummert Barbara E Reynolds Darryl Yong “Alles” — 2014/5/8 — 11:19 — page v — #5 CLASSROOM RESOURCE MATERIALS Classroom
