关闭

关闭

关闭

封号提示

内容

首页 Potential Games

Potential Games.pdf

Potential Games

不动如由
2013-10-23 0人阅读 0 0 0 暂无简介 举报

简介:本文档为《Potential Gamespdf》,可适用于高等教育领域

GAMESANDECONOMICBEHAVIOR,–()ARTICLENOPotentialGamesDovMonderer⁄FacultyofIndustrialEngineeringandManagement,TheTechnion,Haifa,IsraelandLloydSShapleyDepartmentofEconomicsandDepartmentofMathematics,UniversityofCalifornia,LosAngeles,CaliforniaReceivedJanuary,WedefineanddiscussseveralnotionsofpotentialfunctionsforgamesinstrategicformWecharacterizegamesthathaveapotentialfunction,andwepresentavarietyofapplicationsJournalofEconomicLiteratureClassificationNumbers:C,C©AcademicPress,IncINTRODUCTIONConsiderasymmetricoligopolyCournotcompetitionwithlinearcostfunctionsciqiDcqi,•i•nTheinversedemandfunction,FQ,Q>,isapositivefunction(nomonotonicity,continuity,ordifferentiabilityassumptionsonFareneeded)TheprofitfunctionofFirmiisdefinedonRnCCasiqq:::qnDFQqi¡cqiwhereQDPnjDqjDefineafunctionP:RnCC¡!R:Pqq:::qnDqq¢¢¢qnFQ¡c:ForeveryFirmi,andforeveryq¡iRn¡CC,iqiq¡i¡ixiq¡i>iffPqiq¡i¡Pxiq¡i>qixiRCC:()⁄Firstversion:DecemberFinancialsupportfromtheFundforthePromotionofResearchattheTechnionisgratefullyacknowledgedbythefirstauthorEmail:dovtechunixtechnionacil$Copyright©byAcademicPress,IncAllrightsofreproductioninanyformreservedPOTENTIALGAMESAfunctionPsatisfying()iscalledanordinalpotential,andagamethatpossessesanordinalpotentialiscalledanordinalpotentialgameClearly,thepurestrategyequilibriumsetoftheCournotgamecoincideswiththepurestrategyequilibriumsetofthegameinwhicheveryfirm’sprofitisgivenbyPAconditionstrongerthan()isrequiredifweareinterestedinmixedstrategiesConsideraquasiCournotcompetitionwithalinearinversedemandfunctionFQDa¡bQ,ab>,andarbitrarydifferentiablecostfunctionsciqi,•i•nDefineafunctionP⁄qq:::qnasP⁄qq:::qnDanXjDqj¡bnXjDqj¡bX•i<j•nqiqj¡nXjDcjqj:()ItcanbeverifiedthatForeveryFirmi,andforeveryq¡iRn¡C,iqiq¡i¡ixiq¡iDP⁄qiq¡i¡P⁄xiq¡iqixiRC::AfunctionP⁄satisfying()willbecalledapotentialfunctionTheequalities()implythatthemixedstrategyequilibriumsetofthequasiCournotgamecoincideswiththemixedstrategyequilibriumsetofthegameobtainedbyreplacingeverypayofffunctionbyP⁄Inparticular,firmsthatarejointlytryingtomaximizethepotentialfunctionP⁄(ortheordinalpotentialP)endupinanequilibriumWewillprovethatthereexistsatmostonepotentialfunction(uptoanadditiveconstant)Thisraisesthenaturalquestionabouttheeconomiccontent(orinterpretation)ofP⁄:WhatdothefirmstrytojointlymaximizeNegativepricesarepossibleinthisgame,thoughthepricesinanynondegenerateequilibriumwillbepositiveInphysics,P⁄isapotentialfunctionfor:::nifiqiDP⁄qiforevery•i•nIftheprofitsfunctionsarecontinuouslydifferentiablethenthisconditionisequivalentto()Slade()provedtheexistenceofafunctionP⁄satisfying()forthequasiCournotgameShecalledthisfunctionafictitiousobjectivefunctionEveryq⁄thatmaximizesP⁄isapurestrategyequilibrium,buttheremaybepurestrategyequilibriumprofilesthatarejust“local”maximumpoints,andtheremaybemixedstrategyequilibriumprofilesaswellTherefore,theargmaxsetofthepotentialcanbeusedasarefinementtoolforpotentialgames(thisissueisdiscussedinSection)Neyman()showedthatifthepotentialfunctionisconcaveandcontinuouslydifferentiable,theneverymixedstrategyequilibriumprofileispureandmustmaximizethepotentialfunctionNeyman’sresultisrelatedbyShinandWilliamson()totheconceptof“simpleequilibriumoutcome”inBayesiangamesMONDERERANDSHAPLEYWedonothaveananswertothisquestionHowever,itisclearthatthemereexistenceofapotentialfunctionhelpsus(andtheplayers)tobetteranalyzethegameInthispaperwewillprovevariouspropertiesofpotentialgames,andwewillprovidesimplemethodsfordetectingthemandforcomputingtheirpotentialfunctionsToourknowledge,thefirsttousepotentialfunctionsforgamesinstrategicformwasRosenthal()Rosenthaldefinedtheclassofcongestiongamesandproved,byexplicitlyconstructingapotentialfunction,thateverygameinthisclasspossessesapurestrategyequilibriumTheclassofcongestiongamesis,ontheonehand,narrow,butontheotherhand,veryimportantforeconomicsAnygamewhereacollectionofhomogeneousagentshavetochoosefromafinitesetofalternatives,andwherethepayoffofaplayerdependsonthenumberofplayerschoosingeachalternative,isacongestiongameWewillshowthattheclassofcongestiongamescoincides(uptoanisomorphism)withtheclassoffinitepotentialgamesRecently,muchattentionhasbeendevotedtoseveralnotionsof“myopic”learningprocessesWeshowthatforgenericfinitegames,theexistenceofanordinalpotentialisequivalenttotheconvergencetoequilibriumofthelearningprocessdefinedbytheonesidedbetterreplydynamicThenewlearningliteratureraisedanewinterestintheFictitiousPlayprocessingamesinstrategicformdefinedbyBrown()ItwasstudiedforzerosumgamesbyRobinson()andfornonzerosumgamesbyMiyasawa(),Shapley(),Deschamps(),andlatelybyKrishna(),MilgromandRoberts(),Sela(),FudenbergandKreps(),Jordan(),Hofbauer(),KrishnaandSjo¨stro¨m(),FudenbergandLevine(),Mondereretal(),andothersInMondererandShapley()weprovethattheFictitiousPlayprocessconvergestotheequilibriumsetinaclassofgamesthatcontainsthefinite(weighted)potentialgamesMilchtaich()analyzedclassesofgamesrelatedtocongestiongamesHiswork,aswellasthatofBlume(),indicatesthatordinalpotentialgamesarenaturallyrelatedtotheevolutionarylearningaswell(seeeg,Crawford,KandoriandRob,Young,RothandErev,andthereferenceslistedtherein)Asthepotentialfunctionisuniquelydefineduptoanadditiveconstant,theargmaxsetofthepotentialfunctiondoesnotdependonaparticularpotentialfunctionThus,forpotentialgamesthisargmaxsetrefinestheequilibriumset,atleasttechnicallyWeshowthatthisrefinementconceptaccuratelypredictstheexperimentalresultsobtainedbyVanHuycketal()Wedonotattempttoprovideanyexplanationtothispredictionpowerobtained(perhapsasacoinciAsimilarproblemisdiscussedbyBergstromandVarian()POTENTIALGAMESdence)inthiscaseApossiblewayofexplainingthiscanbefoundinBlume()BlumediscussesvariousstochasticstrategyrevisionprocessesforplayerswhohavedirectinteractiononlywithsmallpartofthepopulationHeprovesfortheloglinearstrategyrevisionprocessthatthestrategiesoftheplayersinasymmetricpotentialgameconvergetotheargmaxsetofthepotentialHartandMasColell()haveappliedpotentialtheorytocooperativegamesExceptforthefactthatweareallusingpotentialtheoryourworksarenotconnectedNevertheless,wewillshowinthelastsectionthatcombiningourworkwithHartandMasColell’syieldsasurprisingapplicationtovaluetheoryThepaperisorganizedasfollows:InSectionwegivethebasicdefinitionsandprovideseveralusefulcharacterizationsoffinitepotentialandfiniteordinalpotentialgamesAnequivalencetheorembetweenpotentialgamesandcongestiongamesisgiveninSectionInSectionwediscussandcharacterizeinfinitepotentialgamesSectionisdevotedtoadiscussionoftheexperimentalresultsofVanHuycketalInSectionweshowanapplicationofourtheorytothestrategicapproachtocooperativegamesPOTENTIALGAMESLetuu:::unbeagameinstrategicformwithafinitenumberofplayersThesetofplayersisNDf:::ng,thesetofstrategiesofPlayeriisYi,andthepayofffunctionofPlayeriisui:Y!R,whereYDY£Y£¢¢¢£Ynisthesetofstrategyprofiles,andRdenotesthesetofrealnumbersWhennoconfusionmayarisewedenoteuu:::unbyForSµN,¡SdenotesthecomplementarysetofS,andYSdenotestheCartesianproduct£iSYiForsingletonsetsfig,Y¡figisdenotedbyY¡iAfunctionP:Y!Risanordinalpotentialfor,ifforeveryiNandforeveryy¡iY¡iuiy¡ix¡uiy¡iz>iffPy¡ix¡Py¡iz>foreveryxzYi()iscalledanordinalpotentialgameifitadmitsanordinalpotentialLetwDwiiNbeavectorofpositivenumberswhichwillbecalledweightsAfunctionP:Y!RisawpotentialforifforeveryiNandforeveryy¡iY¡iuiy¡ix¡uiy¡izDwi¡Py¡ix¡Py¡iz¢foreveryxzYi()iscalledawpotentialgameifitadmitsawpotentialCrawford()gaveanevolutionaryinterpretationoftheseexperiments’resultsThisargmaxsetisassumedtobeasingletonAnotherapplicationtocooperativegamesisdiscussedbyQin()MONDERERANDSHAPLEYWhenwearenotinterestedinparticularweightsw,wesimplysaythatPisaweightedpotentialandthatisaweightedpotentialgameAfunctionP:Y!Risanexactpotential(or,inshort,apotential)forifitisawpotentialforwithwiDforeveryiNiscalledanexactpotentialgame(or,inshort,apotentialgame)ifitadmitsapotentialForexample,thematrixPisapotentialforthePrisoner’sDilemmagameGdescribedbelow:GDµ¶PDµ¶:ThenextlemmacharacterizestheequilibriumsetofordinalpotentialgamesItsobviousproofwillbeomittedLEMMALetPbeanordinalpotentialfunctionforuu:::unThentheequilibriumsetofuu:::uncoincideswiththeequilibriumsetofPP:::PThatis,yYisanequilibriumpointforifandonlyifforeveryiNPy‚Py¡ixforeveryxYiConsequently,IfPadmitsamaximalvalueinY,thenpossessesa(purestrategy)equilibriumCOROLLARYEveryfiniteordinalpotentialgamepossessesapurestrategyequilibriumApathinYisasequence°Dyy:::suchthatforeveryk‚thereexistsauniqueplayer,sayPlayeri,suchthatykDy¡ik¡xforsomexDyik¡inYiyiscalledtheinitialpointof°,andif°isfinite,thenitslastelementiscalledtheterminalpointof°°Dyy:::isanimprovementpathwithrespecttoifforallk‚uiyk>uiyk¡,whereiistheuniquedeviatoratstepkHence,animprovementpathisapathgeneratedbymyopicplayershasthefiniteimprovementproperty(FIP)ifeveryimprovementpathisfiniteLEMMAEveryfiniteordinalpotentialgamehastheFIPProofForeveryimprovementpath°Dyyy:::wehaveby()Py<Py<Py<¢¢¢:AsYisafiniteset,thesequence°mustbefiniteUsingBlume’s()terminologywecangiveanequivalentdefinition:isaweightedpotentialgameifandonlyifthereexistsapayofffunctionwhichisstronglybestresponseequivalenttoeachoftheplayers’payofffunctionsSela()provedthatifthetwopersongameABdoesnothaveweaklydominatedstrategies,thenithasaweightedpotentialifandonlyifitisbetterresponseequivalentinmixedstrategies(seeMondererandShapley()fortheprecisedefinition)toagameoftheformPPThisresultcanbeeasilygeneralizedtonpersongamesSeefootnotePOTENTIALGAMESItisobviousthatforfinitegameswiththeFIP,andinparticularforfiniteordinalpotentialgames,everymaximalimprovementpathmustterminateinanequilibriumpointThatis,themyopiclearningprocessbasedontheonesidedbetterreplydynamicconvergestotheequilibriumsetHoweverwehaveobtainedastrongerlearningresult:THEOREM(MondererandShapley,)EveryfiniteweightedpotentialgamehastheFictitiousPlaypropertyItisinterestingtonotethathavingtheFIPisnotequivalenttohavinganordinalpotentialAcounterexampleisthegameGdescribedbelowTherowsinGarelabeledbyaandb,andthecolumnsarelabeledbycanddGDµ¶:ThegameGhastheFIP,butanyordinalpotentialPforGmustsatisfythefollowingimpossiblesequenceofrelations:Pac<Pbc<Pbd<PadDPac:AfunctionP:Y!RisageneralizedordinalpotentialforifforeveryiNandforeveryy¡iY¡i,andforeveryxzYi,uiy¡ix¡uiy¡iz>impliesthatPy¡ix¡Py¡iz>::LEMMALetbeafinitegameThen,hastheFIPifandonlyifhasageneralizedordinalpotentialProofLetbeagamewiththeFIPDefineabinaryrelation“>”onYasfollows:x>yiffxDyandthereexistsafiniteimprovementpath°withaninitialpointyandaterminalpointxThefiniteimprovementpropertyimpliesthat“>”isatransitiverelationLetZµYWesaythatZisrepresentedifthereexistsQ:Z!RsuchthatforeveryxyZ,x>yimpliesthatQx>QyLetZbeamaximalrepresentedsubsetofYWeproceedtoprovethatZDYSupposexZIfx>zforeveryzZ,weextendQtoZfxgbydefiningQxDCmaxzZQz,thuscontradictingthemaximalityofZIfz>xforeveryzZ,weextendQtoZfxgbydefiningQxDminzZQz¡,contradictingagainthemaximalityofZOtherwiseweextendQandcontradictthemaximalityofZbydefiningQxDaCb,SeveralnotionsofacyclicityarediscussedintherecentlearningliteratureMostofthem(unliketheFIP)arerelatedtothebestresponsedynamicSee,eg,Young()OtherresultsrelatingthefictitiousplaypropertywithvarioustypesofimprovementpathscanbefoundinMondererandSela()MONDERERANDSHAPLEYwhereaDmaxfQz:zZx>zg,andbDminfQz:zZz>xgHenceYisrepresentedCOROLLARYLetbeafinitegamewiththeFIPSupposeinadditionthatforeveryiNandforeveryy¡iY¡iuiy¡ixDuiy¡izforeveryxDzYiThenhasanordinalpotentialProofObservethattheconditiononimpliesthateverygeneralizedordinalpotentialforisanordinalpotentialforHence,theprooffollowsfromLemmaOrdinalpotentialgameshavemanyordinalpotentialsForexactpotentialgameswehave:LEMMALetPandPbepotentialsforthegameThenthereexistsaconstantcsuchthatPy¡PyDcforeveryyY:ProofFixzYForallyYdefineHyDnXiD£uiai¡¡uiai⁄whereaDyandforevery•i•n,aiDa¡ii¡ziIfPstandsforeitherPorP,thenby(),HyDPy¡PzforeveryyYThereforePy¡PyDcforeveryyY:ThenextresultscharacterizeexactpotentialgamesinawaythatresemblesthestandardapproachtopotentialfunctionsinphysicsForafinitepath°Dyy:::yNandforavectorvDvv:::vnoffunctionsvi:Y!R,wedefineI°vDnXkD£vikyk¡vikyk¡⁄whereikistheuniquedeviatoratstepk(ie,yikkDyikk¡)AconstructiveandmoreelegantproofofthisresultisgiveninMilchtaich()heshowedthatthefunctionPthatassignstoeachyYthenumberofstrategyprofilesthatareconnectedtoybyanimprovementpaththatterminatesinyisageneralizedordinalpotentialforPOTENTIALGAMESThepath°Dyy:::yNisclosedifyDyNItisasimpleclosedpathifinadditionylDykforevery•lDk•N¡ThelengthofasimpleclosedpathisdefinedtobethenumberofdistinctverticesinitThatis,thelengthof°Dyy:::yNisNTHEOREMLetbeagameinstrategicform,asdescribedatthebeginningofthissectionThenthefollowingclaimsareequivalent:()isapotentialgame()I°uDforeveryfiniteclosedpaths°()I°uDforeveryfinitesimpleclosedpaths°()I°uDforeveryfinitesimpleclosedpaths°oflengthTheproofofTheoremisgiveninAppendixAAtypicalsimpleclosedpath,°,oflengthisdescribedbelowInthispath,iandjaretheactiveplayers,aY¡fijgisafixedstrategyprofileoftheotherplayers,xiyiYi,andxjyjYj,°DA¡ˆ¡¡¡DyxB¡¡¡¡!CwhereADxixja,BDyixja,CDyiyja,andDDxiyjaCOROLLARYisapotentialgameifandonlyifforeveryijN,foreveryaY¡fijg,andforeveryxiyiYiandxjyjYj,uiB¡uiACujC¡ujBCuiD¡uiCCujA¡ujDDwherethepointsABC,andDaredescribedaboveWeendthissectionwithanimportantremarkconcerningthemixedextensionoffinitegamesLEMMALetbeafinitegameThenisawpotentialgameifandonlyifthemixedextensionofisawpotentialgameProofForiNletibethesetofmixedstrategiesofPlayeriandletUibethepayofffunctionofplayeriinthemixedextensionofThatis,UifDUiff:::fnDXyYuiyy:::ynfyfy:::fnynf,whereD£iNiObviously,ifNP:!Risawpotentialfunctionforthemixedextensionof,thenitsrestrictiontoYyieldsawpotentialforAsforMONDERERANDSHAPLEYtheconverse,supposePisawpotentialfor,thenitcanbeeasilyverifiedthatNPisapotentialforthemixedextensionof,whereNPff:::fnDXyYPyy:::ynfyfy:::fnyn::AnexampletoanordinalpotentialgamewhosemixedextensionisnotanordinalpotentialgameisgiveninSela()CONGESTIONGAMESCongestiongamesweredefinedbyRosenthal()Theyarederivedfromcongestionmodelsthathavebeenextensivelydiscussedintheliterature(seeeg,GarciaandZangwill,)Consideranillustrativeexample:Acc¡¡¡¡¡!BccyyccD¡¡¡¡¡!ccCInthecongestionmodeldescribedabove,DriverahastogofrompointAtopointCandDriverbhastogofrompointBtopointDABiscalledroadsegment,BCiscalledroadsegment:::etccjdenotesthepayoff(eg,thenegativeofthecost)forasingleuserofroadsegmentjcjdenotesthepayoffforeachuserofroadsegmentjifbothdriversuseroadsegmentjThedriversarethereforeengagedinagame(theassociatedcongestiongame,CG)whosestrategicformisgivenbelow(Therowsarelabeledbyfgandfg,andthecolumnsarelabeledbyfgandfg:CGDµcCccCccCccCccCccCccCccCc¶:ByCorollarythecongestiongameCGadmitsapotentialInparticular(andwithnorestrictionsonthepayoffcji)ithasa(purestrategy)equilibriumForcompletenessweattachbelowapotent

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/20

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料