二人严格博弈的两个等价结果

Twoequivalenceresultsfortwo-personstrictgamesPingzhongTang,FangzhenLinAbstractAgameisstrictifforbothplayers,differentprofileshavedifferentpayoffs.Twogamesarebestresponseequivalentiftheirbestresponsefunctionsarethesame.Weprovethatatwo-personstrictgamehasatmostonepureNashequilibriumifandonlyifitisbestresponseequivalenttoastrictlycompetitivegame,andthatitisbestresponseequivalenttoanordinalpotentialgameifandonlyifitisbestresponseequivalenttoaquasi-supermodulargame.Keywords:Strictlycompetitivegames；Ordinalpotentialgames；Quasi-supermodulargames；Bestresponseequivalence；Strictgames1.IntroductionInthispaperweprovetworesultsaboutpureNashequilibria(PNEs)for2-personstrictgames,whicharethosewherepayofffunctionsareone-to-one.Thefirstresultsaysthata2-personstrictgamehasatmostonePNEifitisbest-responseequivalent(Rosenthal,1974)toastrictlycompetitivegame(Moulin,1976;Friedman,1983).Thesecondresultsaysthata2-personstrictgameisbest-responseequivalenttoanordinalpotentialgame(MondererandShapley,1996)ifitisbest-responseequivalenttoaquasi-supermodulargame(Topkis,1998).Theseresultscameoutofourprojectonusingcomputerstodiscovertheoremsingametheory(see,e.g.TangandLin,2009).WewerelookingforconditionsthatimplytheuniquenessandexistenceofthePNEs,andwereusingcomputerstorunthroughalargesetofconjectures.Giventhenumberofallpossiblegames,itmadesensetotesttheseconditionsfirstonsomespecialclassesofgames,andtheclassofstrictgamesisanaturalchoiceasinthesegames,thepayofffunctionsareone-to-one,thuseasiertogenerate.Asitturnedout,someinterestingconditionsholdonlyforthisclassofgames.WehavedescribedsomeoftheminTangandLin(2009).Thetworesultsthatwereportherearespecialinthattheirproofsarenon-trivialandhadtobedonemanually.2.BasicdefinitionsA2-persongameisatuple(A,B,u1,u2),whereAandBaresetsofpurestrategiesofplayers1and2,respectively,andu1andu2arefunctionsfromA×Btorealscalledthepayofffunctionsforplayers1and2,respectively.InthispaperweassumebothAandBarefinite.Agameissaidtobestrictifbothplayers’payofffunctionsareone-to-one:forany(a1,b1)and(a2,b2)inA×B,if(a1,b1)≠(a2,b2)thenui(a1,b1)≠ui(a2,b2),i=1,2.Arelatednotionintheliteratureisnon-degenerategames(see,e.g.Berger,2007):agameisnon-degenerateifforanya1,a2∈Aandb1,b2∈B,u1(a1,b1)≠u1(a2,b1)whenevera1≠a2,andu2(a1,b1)≠u2(a1,b2)wheneverb1≠b2.Clearly,astrictgameisalsonon-degenerate,buttheconverseisnottrueingeneral.Foreachb∈B,letB1(b)bethesetofbestresponsesbyplayeronetotheactionbbyplayertwo:B1(b)=﹛a∣a∈A,andforalla′∈A,u1(a′,b)≤u1(a,b)﹜.Similarly,foreacha∈A,letB2(a)=﹛b∣b∈B,andforallb′∈N,u2(a,b′)≤u2(a,b)﹜.Aprofile(a,b)∈A×BisapureNashequilibrium(PNE)ifa∈B1(b)andb∈B2(a).InthispaperweconsideronlyPNEs.OurinitialmotivationforthisworkwastocapturetheclassofgameswithatmostonePNE.Westartedwithstrictlycompetitivegames(seebelow).WhileeverystrictlycompetitivegamecanhaveatmostonePNE,theconverseisnottrueingeneral.ThisledustoconsidernotionsofequivalencebetweengamesthatwillpreservePNEs.Theonethatsuitsourpurposehereisthatofbest-responseequivalence(Rosenthal,1974):two2-persongamesG1=(A,B,u1,u2)andG2=(A,B,u1′,u2′)aresaidtobebest-responseequivalentifforeacha∈A,B2(a)inG1andG2arethesame,andforeachb∈B,B1(b)inG1andG2arethesame.Itiseasytoseethatbest-responseequivalentgameshavethesamesetsofPNEs.3.StrictlycompetitivegamesandatmostonePNETheorem1.Astrict2-persongamehasatmostonePNEifandonlyifitisbest-responseequivalenttoastrictlycompetitivegame.4.Ordinalpotentialandquasi-supermodulargamesTheorem2.A2-personstrictgameisbest-responseequivalenttoaquasi-supermodulargameifandonlyofithasnobest-responsecycle.DiscussionsTheorem2stillholdsfornon-degenerategames,sincetheonlyassumptionwemadeisthatthebest-responsefunctionsaresinglevalued.Forgeneraltwopersongames,therearethreewaystodefineabestresponsecycle:1.Normalcycle.Inthisdefinition,aslongasanybest-responsefunctionismulti-valued,thereisalwaysatrivialcycleinwhichoneplayerdeviatesamongmultiplebest-responses.2.Voorneveld’scycle.Thisdefinitionisessentiallythesametoaboveexceptthatitrequiresatleastoneedgeinthecyclethatstrictlyincreasesthepayoffforthedeviatingplayer.Inthisway,itrulesoutthetrivialcycleinouroriginaldefinition.3.Strictcycle.Inthisdefinition,everyedgeinthecyclemuststrictlyincreasesthepayoffforthedeviatingplayer.Threedefinitionsareequivalentwhenconsiderstrictgamesonly.WenowdiscusstheextensionofTheorem2togeneral2-persongameswithrespecttothreetypesofcycles.The“onlyif”partofTheorem2doesnotholdforgeneral2-persongamesfornormalcycleandVoorneveld’scyclebutstillholdsforstrictcycle.Forinstance,thefollowinggeneralgame:1,12,12,21,2isaquasi-supermodulargameundertheorderingthatordersplayer1’s(rowplayer)strategiesfromtoptodownandplayer2’sactionfromlefttoright.However,goingcounterclockwisestartinginanycellwillformbothanormalcycleaswellasVoorneveld’scycle.Thusthisgameisnotbest-responseequivalenttoanyordinalpotentialgame.However,accordingtoTheorem3inKukushkinetal.(2005),thereisnostrictcycleifagameisquasi-supermodular(thereforenostrictcycleforagamethatisbest-responseequivalenttoit).The“if”partoftheorem2doesnotholdforgeneral2-pers