博弈论教程（奥斯本）课后习题答案.pdf

solutionmanualfor acourseingametheory solutionmanualfor acourseingametheory bymartinj osborneandarielrubinstein martinj osborne arielrubinstein withtheassistanceofwulonggu themitpress cambridge massachusetts london england thismanualwastypesetbytheauthors whoaregreatlyindebtedtodonaldknuth the creatoroft e x leslielamport thecreatorofl a t e x andeberhardmattes thecreator ofemt e x forgenerouslyputtingsuperlativesoftwareinthepublicdomain andtoed sznyterforprovidingcriticalhelpwiththemacrosweusetoexecuteournumbering scheme version contents prefacexi nashequilibrium exercise firstpriceauction exercise secondpriceauction exercise warofattrition exercise locationgame exercise necessityofconditionsinkakutani stheorem exercise symmetricgames exercise increasingpayo sinstrictlycompetitivegame exercise boswithimperfectinformation exercise exchangegame exercise moreinformationmayhurt mixed correlated andevolutionaryequilibrium exercise guesstheaverage exercise investmentrace exercise guessingright exercise airstrike exercise technicalresultonconvexsets exercise examplesofharsanyi spuri cation exercise exampleofcorrelatedequilibrium exercise existenceofessin game rationalizabilityanditeratedeliminationofdominated actions exercise exampleofrationalizableactions exercise cournotduopoly vicontents exercise guesstheaverage exercise modi edrationalizabilityinlocationgame exercise iteratedeliminationinlocationgame exercise dominancesolvability exercise announcingnumbers exercise non weaklydominatedactionasbestresponse knowledgeandequilibrium exercise exampleofinformationfunction exercise rememberingnumbers exercise informationfunctionsandknowledgefunctions exercise decisionsandinformation exercise commonknowledgeanddi erentbeliefs exercise commonknowledgeandbeliefsaboutlotteries exercise knowledgeandcorrelatedequilibrium extensivegameswithperfectinformation exercise extensivegameswith strategicforms exercise speofstackelberggame exercise necessityof nitehorizonforonedeviationproperty exercise necessityof nitenessforkuhn stheorem exercise speofgamessatisfyingnoindi erencecondition exercise speandunreachedsubgames exercise speandunchosenactions exercise armies exercise odpandkuhn stheoremwithchancemoves exercise threeplayerssharingpie exercise namingnumbers exercise odpandkuhn stheoremwithsimultaneousmoves exercise equilibriumofcentipedegame exercise variantofthegameburningmoney exercise variantofthegameburningmoney amodelofbargaining exercise onedeviationpropertyforbargaininggame exercise constantcostofbargaining exercise one sidedo ers exercise finitegridofpossibleo ers exercise outsideoptions contentsvii exercise riskofbreakdown exercise three playerbargaining repeatedgames exercise discountfactorsthatdi er exercise strategiesand nitemachines exercise machinethatguaranteesv i exercise machinefornashfolktheorem exercise examplewithdiscounting exercise long andshort livedplayers exercise gamethatisnotfulldimensional exercise onedeviationpropertyfordiscountedrepeatedgame exercise nashfolktheoremfor nitelyrepeatedgames complexityconsiderationsinrepeatedgames exercise unequalnumbersofstatesinmachines exercise equilibriaoftheprisoner sdilemma exercise equilibriawithintroductoryphases exercise caseinwhichconstituentgameisextensivegame implementationtheory exercise dse implementationwithstrictpreferences exercise exampleofnon dseimplementablerule exercise grovesmechanisms exercise implementationwithtwoindividuals extensivegameswithimperfectinformation exercise de nitionofx i h exercise one playergamesandprinciplesofequivalence exercise exampleofmixedandbehavioralstrategies exercise mixedandbehavioralstrategiesandimperfectrecall exercise splittinginformationsets exercise parlorgame sequentialequilibrium exercise exampleofsequentialequilibria exercise onedeviationpropertyforsequentialequilibrium exercise non orderedinformationsets exercise sequentialequilibriumandpbe viiicontents exercise bargainingunderimperfectinformation exercise pbeisseinspence smodel exercise pbeofchain storegame exercise pre trialnegotiation exercise tremblinghandperfectionandcoalescingofmoves exercise exampleoftremblinghandperfection thecore exercise coreofproductioneconomy exercise marketforindivisiblegood exercise convexgames exercise simplegames exercise zerosumgames exercise pollutethelake exercise gamewithemptycore exercise syndicationinamarket exercise existenceofcompetitiveequilibriuminmarket exercise coreconvergenceinproductioneconomy exercise coreandequilibriaofexchangeeconomy stablesets thebargainingset andtheshapleyvalue exercise stablesetsofsimplegames exercise stablesetofmarketforindivisiblegood exercise stablesetsofthree playergames exercise dummy spayo instablesets exercise generalizedstablesets exercise coreandbargainingsetofmarket exercise nucleolusofproductioneconomy exercise nucleolusofweightedmajoritygames exercise necessityofaxiomsforshapleyvalue exercise exampleofcoreandshapleyvalue exercise shapleyvalueofproductioneconomy exercise shapleyvalueofamodelofaparliament exercise shapleyvalueofconvexgame exercise coalitionalbargaining thenashbargainingsolution exercise standardnashaxiomatization exercise e ciencyvs individualrationality contentsix exercise asymmetricnashsolution exercise kalai smorodinskysolution exercise exactimplementationofnashsolution preface thismanualcontainssolutionstotheexercisesinacourseingametheory bymartinj osborneandarielrubinstein thesourcesoftheproblems aregiveninthesectionentitled notes attheendofeachchapterofthe book weareverygratefultowulongguforcorrectingoursolutionsand providingmanyofhisownandtoebbehendonforcorrectingoursolutionto exercise pleasealertustoanyerrorsthatyoudetect errorsinthebook postscriptandpcl lesoferrorsinthebookarekeptat http www socsci mcmaster ca econ faculty osborne cgt martinj osborne osborne mcmaster ca departmentofeconomics mcmasteruniversity hamilton canada l s m arielrubinstein rariel ccsg tau ac il departmentofeconomics telavivuniversity ramataviv israel departmentofeconomics princetonuniversity princeton nj usa nashequilibrium firstpriceauction thesetofactionsofeachplayeriis thesetof possiblebids andthepayo ofplayeriisv i b i ifhisbidb i isequaltothe highestbidandnoplayerwithalowerindexsubmitsthisbid and otherwise thesetofnashequilibriaisthesetofpro lesbofbidswithb v v b j b forallj andb j b forsomej itiseasytoverifythatallthesepro lesarenashequilibria toseethat therearenootherequilibria rstwearguethatthereisnoequilibriumin whichplayer doesnotobtaintheobject supposethatplayeri submits thehighestbidb i andb b i ifb i v thenplayeri spayo isnegative sothathecanincreasehispayo bybidding ifb i v thenplayer can deviatetothebidb i andwin increasinghispayo nowletthewinningbidbeb wehaveb v otherwiseplayer can changehisbidtosomevaluein v b andincreasehispayo alsob v otherwiseplayer canreduceherbidandincreaseherpayo finally b j b forsomej otherwiseplayer canincreaseherpayo bydecreasingher bid commentanassumptionintheexerciseisthatintheeventofatieforthe highestbidthewinneristheplayerwiththelowestindex ifinthiseventthe objectisinsteadallocatedtoeachofthehighestbidderswithequalprobability thenthegamehasnonashequilibrium iftiesarebrokenrandomlyinthisfashionand inaddition wedeviate fromtheassumptionsoftheexercisebyassumingthatthereisa nitenumber ofpossiblebidsthenifthepossiblebidsarecloseenoughtogetherthereisa nashequilibriuminwhichplayer sbidisb v v andoneoftheother players bidsisthelargestpossiblebidthatislessthanb notealsothat incontrasttothesituationinthenextexercise noplayer hasadominantactioninthegamehere chapter nashequilibrium secondpriceauction thesetofactionsofeachplayeriis thesetof possiblebids andthepayo ofplayeriisv i b j ifhisbidb i isequaltothe highestbidandb j isthehighestoftheotherplayers bids possiblyequalto b i andnoplayerwithalowerindexsubmitsthisbid and otherwise foranyplayerithebidb i v i isadominantaction toseethis letx i be anotheractionofplayeri ifmax j i b j v i thenbybiddingx i playerieither doesnotobtaintheobjectorreceivesanonpositivepayo whilebybidding b i heguaranteeshimselfapayo of ifmax j i b j v i thenbybiddingv i playeriobtainsthegoodatthepricemax j i b j whilebybiddingx i eitherhe winsandpaysthesamepriceorloses anequilibriuminwhichplayerjobtainsthegoodisthatinwhichb v j b j v andb i forallplayersi f jg warofattrition thesetofactionsofeachplayeriisa i andhis payo functionis u i t t t i ift i t j v i t i ift i t j v i t j ift i t j wherej f gnfig let t t beapairofactions ift t thenby concedingslightlylaterthant player canobtaintheobjectinitsentirety insteadofgettingjusthalfofit sothisisnotanequilibrium if t t thenplayer canincreaseherpayo tozerobydeviatingtot finally if t t thenplayer canincreaseherpayo bydeviatingtoatime slightlyaftert unlessv t similarlyfor t t toconstitutean equilibriumweneedv t hence t t isanashequilibriumifand onlyifeither t t andt v or t t andt v commentaninterestingfeatureofthisresultisthattheequilibriumout comeisindependentoftheplayers valuationsoftheobject locationgame therearenplayers eachofwhosesetofactionsisfoutg notethatthemodeldi ersfromhotelling sinthatplayerschoose whetherornottobecomecandidates eachplayerprefersanactionpro le inwhichheobtainsmorevotesthananyotherplayertooneinwhichheties forthelargestnumberofvotes heprefersanoutcomeinwhichhetiesfor correctionto rstprintingofbook the rstsentenceonpage ofthebookshouldbe amendedtoread thereisacontinuumofcitizens eachofwhomhasafavoriteposition thedistributionoffavoritepositionsisgivenbyadensityfunctionfon withf x forallx chapter nashequilibrium rstplace regardlessofthenumberofcandidateswithwhomheties toone inwhichhestaysoutofthecompetition andhepreferstostayoutthanto enterandlose letfbethedistributionfunctionofthecitizens favoritepositionsandlet m f beitsmedian whichisunique sincethedensityfiseverywhere positive itiseasytocheckthatforn thegamehasauniquenashequilibrium inwhichbothplayerschoosem theargumentthatforn thegamehasnonashequilibriumisas follows thereisnoequilibriuminwhichsomeplayerbecomesacandidateand loses sincethatplayercouldinsteadstayoutofthecompetition thus inanyequilibriumallcandidatesmusttiefor rstplace thereisnoequilibriuminwhichasingleplayerbecomesacandidate sincebychoosingthesamepositionanyoftheremainingplayerstiesfor rstplace thereisnoequilibriuminwhichtwoplayersbecomecandidates sinceby theargumentforn inanysuchequilibriumtheymustbothchoose themedianpositionm inwhichcasethethirdplayercanentercloseto thatpositionandwinoutright thereisnoequilibriuminwhichallthreeplayersbecomecandidates ifallthreechoosethesamepositionthenanyoneofthemcanchoose apositionslightlydi erentandwinoutrightratherthantyingfor rstplace iftwochoosethesamepositionwhiletheotherchoosesadi erent positionthenthelonecandidatecanmoveclosertotheothertwo andwinoutright ifallthreechoosedi erentpositionsthen giventhattheytiefor rstplace eitheroftheextremecandidatescanmoveclosertohis neighborandwinoutright commentifthedensityfisnoteverywherepositivethenthesetofmedi ansmaybeaninterval say m m inthiscasethegamehasnashequilibria whenn inallequilibriaexactlytwoplayersbecomecandidates one choosingmandtheotherchoosingm chapter nashequilibrium necessityofconditionsinkakutani stheorem i xisthereallineandf x x ii xistheunitcircle andfisrotationby iii x and f x f gifx f gifx f gifx iv x f x ifx andf symmetricgames de nethefunctionf a a byf a b a the bestresponseofplayer toa thefunctionfsatis estheconditionsof lemma andhencehasa xedpoint saya thepairofactions a a isanashequilibriumofthegamesince giventhesymmetry ifa isabest responseofplayer toa thenitisalsoabestresponseofplayer toa asymmetric nitegamethathasnosymmetricequilibriumishawk dove figure commentinthenextchapterofthebookweintroducethenotionofa mixedstrategy fromthe rstpartoftheexerciseitfollowsthata nite symmetricgamehasasymmetricmixedstrategyequilibrium increasingpayo sinstrictlycompetitivegame a letu i beplayeri spayo functioninthegameg letw i behispay o functioning andlet x y beanashequilibriumofg then us ingpart b ofproposition wehavew x y min y max x w x y min y max x u x y whichisthevalueofg b thisfollowsfrompart b ofproposition andthefactthatforany functionfwehavemax x x f x max x y f x ify x c intheuniqueequilibriumofthegame chapter nashequilibrium player receivesapayo of whileintheuniqueequilibriumof shereceivesapayo of ifsheisprohibitedfromusinghersecondactionin thissecondgamethensheobtainsanequilibriumpayo of however boswithimperfectinformation thebayesiangameisasfollows there aretwoplayers sayn f g andfourstates say f b b b s s b s s g wherethestate x y isinterpretedasasituationinwhich player spreferredcomposerisxandplayer sisy theseta i ofactionsof eachplayeriisfb sg thesetofsignalsthatplayerimayreceiveisfb sg andplayeri ssignalfunction i isde nedby i i abeliefofeach playeriisaprobabilitydistributionp i over player spreferencesare thoserepresentedbythepayo functionde nedasfollows if bthen u b b u s s andu b s u s b if sthenu isde nedanalogously player spreferencesarede ned similarly foranybeliefsthegamehasnashequilibria b b b b i e each typeofeachplayerchoosesb and s s s s ifoneplayer sequilibrium actionisindependentofhistypethentheotherplayer sisalso thusin anyotherequilibriumthetwotypesofeachplayerchoosedi erentactions whethersuchapro leisanequilibriumdependsonthebeliefs letq x p x x p b x p s x theprobabilitythatplayer assignstothe eventthatplayer prefersxconditionalonplayer preferringx andlet p x p x x p x b p x s theprobabilitythatplayer assignsto theeventthatplayer prefersxconditionalonplayer preferringx if forexample p x andq x forx b s then b s b s isan equilibrium exchangegame inthebayesiangametherearetwoplayers sayn f g thesetofstatesis s s thesetofactionsofeachplayeris fexchange don texchangeg thesignalfunctionofeachplayeriisde nedby i s s s i andeachplayer sbeliefon isthatgeneratedbytwoinde pendentcopiesoff eachplayer spreferencesarerepresentedbythepayo chapter nashequilibrium functionu i x y j ifx y exchangeandu i x y i otherwise letxbethesmallestpossibleprizeandletm i bethehighesttypeof playerithatchoosesexchange ifm i xthenitisoptimalfortypexof playerjtochooseexchange thusifm i m j andm i xthenitisoptimal fortypem i ofplayeritochoosedon texchange sincetheexpectedvalueof theprizesofthetypesofplayerjthatchooseexchangeislessthanm i thus inanypossiblenashequilibriumm i m j x theonlyprizesthatmaybe exchangedarethesmallest moreinformationmayhurt considerthebayesiangameinwhichn f g f g thesetofactionsofplayer isfu dg thesetofactions ofplayer isfl m rg player ssignalfunctionisde nedby and player ssignalfunctionisde nedby the beliefofeachplayeris andthepreferencesofeachplayerarerepresented bytheexpectedvalueofthepayo functionshowninfigure where lmr u d state lmr u d state figure thepayo sinthebayesiangameforexercise thisgamehasauniquenashequilibrium d d l thatis bothtypes ofplayer choosedandplayer choosesl theexpectedpayo satthe equilibriumare inthegameinwhichplayer aswellasplayer isinformedofthestate theuniquenashequilibriumwhenthestateis is u r theuniquenash equilibriumwhenthestateis is u m inbothcasesthepayo is sothatplayer isworseo thanheiswhenheisill informed mixed correlated andevolutionary equilibrium guesstheaverage letk bethelargestnumbertowhichanyplayer sstrat egyassignspositiveprobabilityinamixedstrategyequilibriumandassume thatplayeri sstrategydoesso wenowargueasfollows inorderforplayeri sstrategytobeoptimalhispayo fromthepure strategyk mustbeequaltohisequilibriumpayo inanyequilibriumplayeri sexpectedpayo ispositive sinceforany strategiesoftheotherplayershehasapurestrategythatforsomere alizationoftheotherplayers strategiesisatleastascloseto ofthe averagenumberasanyotherplayer snumber inanyrealizationofthestrategiesinwhichplayerichoosesk some otherplayeralsochoosesk sincebytheprevioustwopointsplayeri s payo ispositiveinthiscase sothatnootherplayer snumberiscloser to oftheaveragenumberthank notethatalltheothernumbers cannotbelessthan oftheaveragenumber inanyrealizationofthestrategiesinwhichplayerichoosesk he canincreasehispayo bychoosingk sincebymakingthischange hebecomestheoutrightwinnerratherthantyingwithatleastoneother player theremainingpossibilityisthatk everyplayerusesthepurestrategy inwhichheannouncesthenumber chapter mixed correlated andevolutionaryequilibrium investmentrace thesetofactionsofeachplayeriisa i thepayo functionofplayeriis u i a a a i ifa i a j a i ifa i a j a i ifa i a j wherej f gnfig wecanrepresentamixedstrategyofaplayeriinthisgamebyaprobability distributionfunctionf i ontheinterval withtheinterpretationthatf i v istheprobabilitythatplayerichoosesanactionintheinterval v de ne thesupportoff i tobethesetofpointsvforwhichf i v f i v for all andde nevtobeanatomoff i iff i v lim f i v suppose that f f isamixedstrategynashequilibriumofthegameandlets i be thesupportoff i fori step s s proof ifnotthenthereisanopeninterval say v w towhichf i assigns positiveprobabilitywhilef j assignszeroprobability forsomei j butthen icanincreasehispayo bytransferringprobabilitytosmallervalueswithin theinterval sincethisdoesnota ecttheprobabilitythathewinsorloses butincreaseshispayo inbothcases step ifvisanatomoff i thenitisnotanatomoff j andforsome thesets j containsnopointin v v proof ifvisanatomoff i thenforsome noactionin v v is optimalforplayerjsincebymovinganyprobabilitymassinf i thatisinthis intervaltoeitherv forsomesmall ifv or ifv playerj increaseshispayo step ifv thenvisnotanatomoff i fori proof ifv isanatomoff i then usingstep playericanincrease hispayo bytransferringtheprobabilityattachedtotheatomtoasmaller pointintheinterval v v step s i m forsomem fori proof supposethatv s i andletw inffw w s i andw vg v bystep wehavew s j andhence giventhatw isnotanatomoff i by step werequirej spayo atw tobenolessthanhispayo atv hence w v bystep atmostonedistributionhasanatomat som chapter mixed correlated andevolutionaryequilibrium step s i andf i v vforv andi proof bysteps and eachequilibriumdistributionisatomless except possiblyat whereatmostonedistribution sayf i hasanatom the