关闭

关闭

关闭

封号提示

内容

首页 Potential Games.pdf

Potential Games.pdf

Potential Games.pdf

上传者: 不动如由 2013-10-23 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《Potential Gamespdf》,可适用于高等教育领域,主题内容包含GAMESANDECONOMICBEHAVIOR,–()ARTICLENOPotentialGamesDovMonderer⁄FacultyofIn符等。

GAMESANDECONOMICBEHAVIOR,–()ARTICLENOPotentialGamesDovMonderer⁄FacultyofIndustrialEngineeringandManagement,TheTechnion,Haifa,IsraelandLloydSShapleyDepartmentofEconomicsandDepartmentofMathematics,UniversityofCalifornia,LosAngeles,CaliforniaReceivedJanuary,WedefineanddiscussseveralnotionsofpotentialfunctionsforgamesinstrategicformWecharacterizegamesthathaveapotentialfunction,andwepresentavarietyofapplicationsJournalofEconomicLiteratureClassificationNumbers:C,CAcademicPress,IncINTRODUCTIONConsiderasymmetricoligopolyCournotcompetitionwithlinearcostfunctionsciqiDcqi,•i•nTheinversedemandfunction,FQ,Q>,isapositivefunction(nomonotonicity,continuity,ordifferentiabilityassumptionsonFareneeded)TheprofitfunctionofFirmiisdefinedonRnCCasiqq:::qnDFQqicqiwhereQDPnjDqjDefineafunctionP:RnCC!R:Pqq:::qnDqqqnFQc:ForeveryFirmi,andforeveryqiRnCC,iqiqiixiqi>iffPqiqiPxiqi>qixiRCC:()⁄Firstversion:DecemberFinancialsupportfromtheFundforthePromotionofResearchattheTechnionisgratefullyacknowledgedbythefirstauthorEmail:dovtechunixtechnionacil$CopyrightbyAcademicPress,IncAllrightsofreproductioninanyformreservedPOTENTIALGAMESAfunctionPsatisfying()iscalledanordinalpotential,andagamethatpossessesanordinalpotentialiscalledanordinalpotentialgameClearly,thepurestrategyequilibriumsetoftheCournotgamecoincideswiththepurestrategyequilibriumsetofthegameinwhicheveryfirm’sprofitisgivenbyPAconditionstrongerthan()isrequiredifweareinterestedinmixedstrategiesConsideraquasiCournotcompetitionwithalinearinversedemandfunctionFQDabQ,ab>,andarbitrarydifferentiablecostfunctionsciqi,•i•nDefineafunctionP⁄qq:::qnasP⁄qq:::qnDanXjDqjbnXjDqjbX•i<j•nqiqjnXjDcjqj:()ItcanbeverifiedthatForeveryFirmi,andforeveryqiRnC,iqiqiixiqiDP⁄qiqiP⁄xiqiqixiRC::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(),KrishnaandSjostrom(),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,whereYDYYYnisthesetofstrategyprofiles,andRdenotesthesetofrealnumbersWhennoconfusionmayarisewedenoteuu:::unbyForSµN,SdenotesthecomplementarysetofS,andYSdenotestheCartesianproductiSYiForsingletonsetsfig,YfigisdenotedbyYiAfunctionP:Y!Risanordinalpotentialfor,ifforeveryiNandforeveryyiYiuiyixuiyiz>iffPyixPyiz>foreveryxzYi()iscalledanordinalpotentialgameifitadmitsanordinalpotentialLetwDwiiNbeavectorofpositivenumberswhichwillbecalledweightsAfunctionP:Y!RisawpotentialforifforeveryiNandforeveryyiYiuiyixuiyizDwiPyixPyizforeveryxzYi()iscalledawpotentialgameifitadmitsawpotentialCrawford()gaveanevolutionaryinterpretationoftheseexperiments’resultsThisargmaxsetisassumedtobeasingletonAnotherapplicationtocooperativegamesisdiscussedbyQin()MONDERERANDSHAPLEYWhenwearenotinterestedinparticularweightsw,wesimplysaythatPisaweightedpotentialandthatisaweightedpotentialgameAfunctionP:Y!Risanexactpotential(or,inshort,apotential)forifitisawpotentialforwithwiDforeveryiNiscalledanexactpotentialgame(or,inshort,apotentialgame)ifitadmitsapotentialForexample,thematrixPisapotentialforthePrisoner’sDilemmagameGdescribedbelow:GDµPDµ:ThenextlemmacharacterizestheequilibriumsetofordinalpotentialgamesItsobviousproofwillbeomittedLEMMALetPbeanordinalpotentialfunctionforuu:::unThentheequilibriumsetofuu:::uncoincideswiththeequilibriumsetofPP:::PThatis,yYisanequilibriumpointforifandonlyifforeveryiNPy‚PyixforeveryxYiConsequently,IfPadmitsamaximalvalueinY,thenpossessesa(purestrategy)equilibriumCOROLLARYEveryfiniteordinalpotentialgamepossessesapurestrategyequilibriumApathinYisasequenceDyy:::suchthatforeveryk‚thereexistsauniqueplayer,sayPlayeri,suchthatykDyikxforsomexDyikinYiyiscalledtheinitialpointof,andifisfinite,thenitslastelementiscalledtheterminalpointofDyy:::isanimprovementpathwithrespecttoifforallk‚uiyk>uiyk,whereiistheuniquedeviatoratstepkHence,animprovementpathisapathgeneratedbymyopicplayershasthefiniteimprovementproperty(FIP)ifeveryimprovementpathisfiniteLEMMAEveryfiniteordinalpotentialgamehastheFIPProofForeveryimprovementpathDyyy:::wehaveby()Py<Py<Py<:AsYisafiniteset,thesequencemustbefiniteUsingBlume’s()terminologywecangiveanequivalentdefinition:isaweightedpotentialgameifandonlyifthereexistsapayofffunctionwhichisstronglybestresponseequivalenttoeachoftheplayers’payofffunctionsSela()provedthatifthetwopersongameABdoesnothaveweaklydominatedstrategies,thenithasaweightedpotentialifandonlyifitisbetterresponseequivalentinmixedstrategies(seeMondererandShapley()fortheprecisedefinition)toagameoftheformPPThisresultcanbeeasilygeneralizedtonpersongamesSeefootnotePOTENTIALGAMESItisobviousthatforfinitegameswiththeFIP,andinparticularforfiniteordinalpotentialgames,everymaximalimprovementpathmustterminateinanequilibriumpointThatis,themyopiclearningprocessbasedontheonesidedbetterreplydynamicconvergestotheequilibriumsetHoweverwehaveobtainedastrongerlearningresult:THEOREM(MondererandShapley,)EveryfiniteweightedpotentialgamehastheFictitiousPlaypropertyItisinterestingtonotethathavingtheFIPisnotequivalenttohavinganordinalpotentialAcounterexampleisthegameGdescribedbelowTherowsinGarelabeledbyaandb,andthecolumnsarelabeledbycanddGDµ:ThegameGhastheFIP,butanyordinalpotentialPforGmustsatisfythefollowingimpossiblesequenceofrelations:Pac<Pbc<Pbd<PadDPac:AfunctionP:Y!RisageneralizedordinalpotentialforifforeveryiNandforeveryyiYi,andforeveryxzYi,uiyixuiyiz>impliesthatPyixPyiz>::LEMMALetbeafinitegameThen,hastheFIPifandonlyifhasageneralizedordinalpotentialProofLetbeagamewiththeFIPDefineabinaryrelation“>”onYasfollows:x>yiffxDyandthereexistsafiniteimprovementpathwithaninitialpointyandaterminalpointxThefiniteimprovementpropertyimpliesthat“>”isatransitiverelationLetZµYWesaythatZisrepresentedifthereexistsQ:Z!RsuchthatforeveryxyZ,x>yimpliesthatQx>QyLetZbeamaximalrepresentedsubsetofYWeproceedtoprovethatZDYSupposexZIfx>zforeveryzZ,weextendQtoZfxgbydefiningQxDCmaxzZQz,thuscontradictingthemaximalityofZIfz>xforeveryzZ,weextendQtoZfxgbydefiningQxDminzZQz,contradictingagainthemaximalityofZOtherwiseweextendQandcontradictthemaximalityofZbydefiningQxDaCb,SeveralnotionsofacyclicityarediscussedintherecentlearningliteratureMostofthem(unliketheFIP)arerelatedtothebestresponsedynamicSee,eg,Young()OtherresultsrelatingthefictitiousplaypropertywithvarioustypesofimprovementpathscanbefoundinMondererandSela()MONDERERANDSHAPLEYwhereaDmaxfQz:zZx>zg,andbDminfQz:zZz>xgHenceYisrepresentedCOROLLARYLetbeafinitegamewiththeFIPSupposeinadditionthatforeveryiNandforeveryyiYiuiyixDuiyizforeveryxDzYiThenhasanordinalpotentialProofObservethattheconditiononimpliesthateverygeneralizedordinalpotentialforisanordinalpotentialforHence,theprooffollowsfromLemmaOrdinalpotentialgameshavemanyordinalpotentialsForexactpotentialgameswehave:LEMMALetPandPbepotentialsforthegameThenthereexistsaconstantcsuchthatPyPyDcforeveryyY:ProofFixzYForallyYdefineHyDnXiDuiaiuiai⁄whereaDyandforevery•i•n,aiDaiiziIfPstandsforeitherPorP,thenby(),HyDPyPzforeveryyYThereforePyPyDcforeveryyY:ThenextresultscharacterizeexactpotentialgamesinawaythatresemblesthestandardapproachtopotentialfunctionsinphysicsForafinitepathDyy:::yNandforavectorvDvv:::vnoffunctionsvi:Y!R,wedefineIvDnXkDvikykvikyk⁄whereikistheuniquedeviatoratstepk(ie,yikkDyikk)AconstructiveandmoreelegantproofofthisresultisgiveninMilchtaich()heshowedthatthefunctionPthatassignstoeachyYthenumberofstrategyprofilesthatareconnectedtoybyanimprovementpaththatterminatesinyisageneralizedordinalpotentialforPOTENTIALGAMESThepathDyy:::yNisclosedifyDyNItisasimpleclosedpathifinadditionylDykforevery•lDk•NThelengthofasimpleclosedpathisdefinedtobethenumberofdistinctverticesinitThatis,thelengthofDyy:::yNisNTHEOREMLetbeagameinstrategicform,asdescribedatthebeginningofthissectionThenthefollowingclaimsareequivalent:()isapotentialgame()IuDforeveryfiniteclosedpaths()IuDforeveryfinitesimpleclosedpaths()IuDforeveryfinitesimpleclosedpathsoflengthTheproofofTheoremisgiveninAppendixAAtypicalsimpleclosedpath,,oflengthisdescribedbelowInthispath,iandjaretheactiveplayers,aYfijgisafixedstrategyprofileoftheotherplayers,xiyiYi,andxjyjYj,DAˆDyxB!CwhereADxixja,BDyixja,CDyiyja,andDDxiyjaCOROLLARYisapotentialgameifandonlyifforeveryijN,foreveryaYfijg,andforeveryxiyiYiandxjyjYj,uiBuiACujCujBCuiDuiCCujAujDDwherethepointsABC,andDaredescribedaboveWeendthissectionwithanimportantremarkconcerningthemixedextensionoffinitegamesLEMMALetbeafinitegameThenisawpotentialgameifandonlyifthemixedextensionofisawpotentialgameProofForiNletibethesetofmixedstrategiesofPlayeriandletUibethepayofffunctionofplayeriinthemixedextensionofThatis,UifDUiff:::fnDXyYuiyy:::ynfyfy:::fnynf,whereDiNiObviously,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)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/20
1下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部