Game Theory Wiley Seriesin OPERATIONS RESEARCH AND MANAGEMENT SCIENCE OperationsResearchandManagementScience(ORMS)isabroad,interdisciplinarybranch ofappliedmathematicsconcernedwithimprovingthequalityofdecisionsandprocesses andisamajorcomponentoftheglobalmodernmovementtowardstheuseofadvanced analyticsinindustryandscientificresearch.TheWileySeriesinOperationsResearchand ManagementSciencefeaturesabroadcollectionofbooksthatmeetthevariedneedsof researchers,practitioners,policymakers,andstudentswhouseorneedtoimprovetheiruse ofanalytics.ReflectingthewiderangeofcurrentresearchwithintheORMScommunity, theSeriesencompassesapplication,methodology,andtheoryandprovidescoverageofboth classicalandcuttingedgeORMSconceptsanddevelopments.Writtenbyrecognized internationalexpertsinthefield,thiscollectionisappropriateforstudentsaswellas professionalsfromprivateandpublicsectorsincludingindustry,government,andnonprofit organizationwhoareinterestedinORMSatatechnicallevel.TheSeriesiscomprisedof threesections:DecisionandRiskAnalysis;OptimizationModels;andStochasticModels. (cid:2) AdvisoryEditors DecisionandRiskAnalysis GilbertoMontibeller,LondonSchoolofEconomics GregoryS.Parnell,UnitedStatesMilitaryAcademyatWestPoint FoundingSeriesEditor JamesJ.Cochran,LouisianaTechUniversity DecisionandRiskAnalysis (cid:2) Barron GameTheory:AnIntroduction,SecondEdition ForthcomingTitles (cid:2) NussbaumandMislick CostEstimation:MethodsandToolsOptimizationModels OptimizationModels (cid:2) Ghiani,Laporte,andMusmanno IntroductiontoLogisticsSystemsManagement, SecondEdition StochasticModels Game Theory An Introduction SECOND EDITION E.N. Barron LoyolaUniversity Chicago Chicago,Illinois Copyright(cid:2)C 2013byJohnWiley&Sons,Inc.Allrightsreserved. PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey. PublishedsimultaneouslyinCanada. Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorbyanymeans, electronic,mechanical,photocopying,recording,scanning,orotherwise,exceptaspermittedunderSection107or108 ofthe1976UnitedStatesCopyrightAct,withouteitherthepriorwrittenpermissionofthePublisher,orauthorization throughpaymentoftheappropriateper-copyfeetotheCopyrightClearanceCenter,Inc.,222RosewoodDrive, Danvers,MA01923,(978)750-8400,fax(978)646-8600,oronthewebatwww.copyright.com.Requeststothe PublisherforpermissionshouldbeaddressedtothePermissionsDepartment,JohnWiley&Sons,Inc.,111RiverStreet, Hoboken,NJ07030,(201)748-6011,fax(201)748-6008. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbesteffortsinpreparingthis book,theymakenorepresentationsorwarrantieswithrespecttotheaccuracyorcompletenessofthecontentsofthis bookandspecificallydisclaimanyimpliedwarrantiesofmerchantabilityorfitnessforaparticularpurpose.Nowarranty maybecreatedorextendedbysalesrepresentativesorwrittensalesmaterials.Theadviceandstrategiescontainedherein maynotbesuitableforyoursituation.Youshouldconsultwithaprofessionalwhereappropriate.Neitherthepublisher norauthorshallbeliableforanylossofprofitoranyothercommercialdamages,includingbutnotlimitedtospecial, incidental,consequential,orotherdamages. ForgeneralinformationonourotherproductsandservicespleasecontactourCustomerCareDepartmentwithinthe U.S.at877-762-2974,outsidetheU.S.at317-572-3993orfax317-572-4002. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprint,however,maynotbe availableinelectronicformat. LibraryofCongressCataloging-in-PublicationData: Barron,E.N.(EmmanualN.),1949– Gametheory:anintroduction/EmmanuelN.Barron.–Secondedition. pagescm Includesbibliographicalreferencesandindex. ISBN978-1-118-21693-4(cloth) 1.Gametheory. I.Title. QA269.B272013 519.3–dc23 2013008270 PrintedintheUnitedStatesofAmerica. ISBN:9781118216934 10 9 8 7 6 5 4 3 2 1 To Christina, Michael, and Anastasia; and Fotini and Michael Contents Preface for the Second Edition xi Preface for the First Edition xv Acknowledgments xvii Introduction 1 1 Matrix Two-Person Games 5 1.1 TheBasics, 5 Problems, 16 1.2 ThevonNeumannMinimaxTheorem, 18 1.2.1 ProofofvonNeumann’sMinimaxTheorem (Optional), 21 Problems, 24 1.3 MixedStrategies, 25 1.3.1 PropertiesofOptimalStrategies, 35 1.3.2 DominatedStrategies, 38 1.4 Solving2×2GamesGraphically, 41 Problems, 43 1.5 GraphicalSolutionof2×mandn×2Games, 44 Problems, 50 1.6 BestResponseStrategies, 53 Problems, 57 (cid:2) 1.6.1 MapleTM/MathematicaR, 58 BibliographicNotes, 59 2 Solution Methods for Matrix Games 60 2.1 SolutionofSomeSpecialGames, 60 2.1.1 2×2GamesRevisited, 60 Problems, 64 2.2 InvertibleMatrixGames, 65 2.2.1 CompletelyMixedGames, 68 Problems, 74 vii viii Contents 2.3 SymmetricGames, 76 Problems, 81 2.4 MatrixGamesandLinearProgramming, 82 2.4.1 SettingUptheLinearProgram:Method1, 83 2.4.2 ADirectFormulationWithoutTransforming: Method2, 89 Problems, 94 2.5 Appendix:LinearProgrammingandtheSimplexMethod, 98 2.5.1 TheSimplexMethodStepbyStep, 101 Problems, 108 2.6 ReviewProblems, 108 2.7 Maple/Mathematica, 109 2.7.1 InvertibleMatrices, 109 2.7.2 LinearProgramming:Method1, 110 2.7.3 LinearProgramming:Method2, 111 BibliographicNotes, 113 3 Two-Person Nonzero Sum Games 115 3.1 TheBasics, 115 Problems, 123 3.2 2×2BimatrixGames,BestResponse,Equality ofPayoffs, 125 3.2.1 CalculationoftheRationalReactionSetsfor 2×2Games, 125 Problems, 132 3.3 InteriorMixedNashPointsbyCalculus, 135 3.3.1 CalculusMethodforInteriorNash, 135 Problems, 143 3.3.2 ProofthatThereisaNashEquilibriumforBimatrixGames (Optional), 146 3.4 NonlinearProgrammingMethodforNonzeroSumTwo-Person Games, 148 3.4.1 SummaryofMethodsforFindingMixedNash Equilibria, 156 Problems, 158 3.5 CorrelatedEquilibria, 159 3.5.1 LPProblemforaCorrelatedEquilibrium, 165 Problems, 166 3.6 ChoosingAmongSeveralNashEquilibria(Optional), 167 Problems, 172 3.6.1 Maple/Mathematica, 173 3.6.2 MathematicaforLemke–HowsonAlgorithm, 173 BibliographicNotes, 175