Martin J. Osborne_An introduction to game theory_1

AnIntroductiontoGameTheoryPleasesendcommentstoMartinJ.OsborneDepartmentofEconomics150St.GeorgeStreetUniversityofTorontoToronto,CanadaM5S3G7email:[e-mail]:2002/7/25Note:Thecategorizationofexercisesaccordingtotheavailabilityoftheirsolutionsistentative.Nosolutionsarecurrentlypubliclyavailable.Note:TheIndexcurrentlycoversonlyChapters1and2(andafewotherbitsandpieces).Note:Badlinebreaksandpagebreakshavenotyetbeencorrected.AnIntroductiontoGameTheoryMartinJ.OsborneNewYorkOxfordOXFORDUNIVERSITYPRESS2002OXFORDUNIVERSITYPRESSOxfordNewYorkAthensAucklandBangkokBombayCalcuttaCapeTownDaresSalaamDeliFlorenceHongKongIstanbulKarachiKualaLumpurMadrasMadridMelbourneMexicoCityNairobiParisSingaporeTaipeiTokyoTorontoandassociatedcompaniesinBerlinIbadanCopyright©1995–2002byMartinJ.OsbornePublishedbyOxfordUniversityPress,Inc.,198MadisonAvenue,NewYork,NewYork10016OxfordisaregisteredtrademarkofOxfordUniversityPressAllrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmitted,byanyformorbyanymeans,electronic,mechanical,photocopying,recording,orotherwise,withoutthepriorpermissionofOxfordUniversityPress.Thisbookwastypesetbytheauthor,whoisgreatlyindebtedtoDonaldKnuth(TEX),LeslieLamport(LATEX),DiegoPuga(mathpazo),ChristianSchenk(MiKTEX),EdSznyter(ppctr),TimothyvanZandt(PSTricks),andothers,forgenerouslymakingsuperlativesoftwarefreelyavailable.Themainfontis10ptPalatino.LibraryofCongressCataloging-in-PublicationDataOsborne,MartinJohn.AnIntroductiontoGameTheory/MartinJ.Osbornep.cm.Includesbibliographicalreferencesandindex.ISBN?????1.GameTheory.2.Economics,Mathematical.I.II.Title.HB144.O????2002ContentsPrefacexi1Introduction11.1Whatisgametheory?1Anoutlineofthehistoryofgametheory3JohnvonNeumann31.2Thetheoryofrationalchoice41.3Comingattractions7Notes8IGameswithPerfectInformation92NashEquilibrium:Theory112.1Strategicgames112.2Example:thePrisoner'sDilemma122.3Example:BachorStravinsky?162.4Example:MatchingPennies172.5Example:theStagHunt182.6Nashequilibrium19JohnF.Nash,Jr.21StudyingNashequilibriumexperimentally222.7ExamplesofNashequilibrium24ExperimentalevidenceonthePrisoner'sDilemma26Focalpoints302.8Bestresponsefunctions332.9Dominatedactions432.10Equilibriuminasinglepopulation:symmetricgamesandsymmetricequilibria49Notes51vviContents3NashEquilibrium:Illustrations533.1Cournot'smodelofoligopoly533.2Bertrand'smodelofoligopoly61Cournot,Bertrand,andNash:somehistoricalnotes673.3Electoralcompetition683.4TheWarofAttrition753.5Auctions78AuctionsfromBabyloniatoeBay793.6Accidentlaw89Notes944MixedStrategyEquilibrium974.1Introduction97Someevidenceonexpectedpayofffunctions1024.2Strategicgamesinwhichplayersmayrandomize1034.3MixedstrategyNashequilibrium1054.4Dominatedactions1174.5Pureequilibriawhenrandomizationisallowed1204.6Illustration:expertdiagnosis1214.7Equilibriuminasinglepopulation1264.8Illustration:reportingacrime128Reportingacrime:socialpsychologyandgametheory1314.9Theformationofplayers'beliefs1324.10Extension:FindingallmixedstrategyNashequilibria1354.11Extension:MixedstrategyNashequilibriaofgamesinwhicheachplayerhasacontinuumofactions1404.12Appendix:Representingpreferencesoverlotteriesbytheexpectedvalueofapayofffunction144Notes1485ExtensiveGameswithPerfectInformation:Theory1515.1Extensivegameswithperfectinformation1515.2Strategiesandoutcomes1575.3Nashequilibrium1595.4Subgameperfectequilibrium1625.5Findingsubgameperfectequilibriaofnitehorizongames:backwardinduction168Ticktacktoe,chess,andrelatedgames176Notes177Contentsvii6ExtensiveGameswithPerfectInformation:Illustrations1796.1Theultimatumgame,theholdupgame,andagendacontrol179Experimentsontheultimatumgame1816.2Stackelberg'smodelofduopoly1856.3Buyingvotes1906.4Arace195Notes2017ExtensiveGameswithPerfectInformation:ExtensionsandDiscussion2037.1Allowingforsimultaneousmoves203Moreexperimentalevidenceonsubgameperfectequilibrium2097.2Illustration:entryintoamonopolizedindustry2117.3Illustration:electoralcompetitionwithstrategicvoters2137.4Illustration:committeedecision­making2157.5Illustration:exitfromadecliningindustry2197.6Allowingforexogenousuncertainty2247.7Discussion:subgameperfectequilibriumandbackwardinduction228Experimentalevidenceonthecentipedegame232Notes2348CoalitionalGamesandtheCore2378.1Coalitionalgames2378.2Thecore2418.3Illustration:ownershipandthedistributionofwealth2458.4Illustration:exchanginghomogeneoushorses2498.5Illustration:exchangingheterogeneoushouses2548.6Illustration:voting2588.7Illustration:matching261Matchingdoctorswithhospitals2668.8Discussion:othersolutionconcepts267Notes268viiiContentsIIGameswithImperfectInformation2719BayesianGames2739.1Motivationalexamples2739.2Generaldenitions2789.3Twoexamplesconcerninginformation2839.4Illustration:Cournot'sduopolygamewithimperfectinformation2859.5Illustration:providingapublicgood2899.6Illustration:auctions292Auctionsoftheradiospectrum3009.7Illustration:juries3019.8Appendix:Analysisofauctionsforanarbitrarydistributionofvaluations308Notes31110ExtensiveGameswithImperfectInformation31310.