资源描述：
《1 The Search for Equilibrium Concepts 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TheSearchforEquilibriumConceptsChristosH.PapadimitriouComputerScienceDivision,UniversityofCaliforniaatBerkeley,Berkeley,USAchristos@cs.berkeley.eduAbstract.GameTheoryisaboutpredictingthebehaviorofgroupsofrationalagentswhosedecisionsaffecteachother’swelfare,andsuchpre-dict
2、ionsaremostoftenintheformofequilibriumconcepts.Thereareseveraldesiderataonemightexpectfromanequilibriumconcept:Firstandforemostitshouldbenaturalandconvincingasapredictionofagentbehavior.Thenitshouldbeuniversal—allgamesshouldhaveit,be-causeotherwiseitisanincompletepredicti
3、on.SincecomputerscientistsbecameinterestedinGameTheoryoverthepastdecade,promptedbytheadventoftheInternetanditscomplexsocioeconomicplatform,an-otherimportantquestionhasbeenaskedofanequilibriumconcept:Canitbecomputedefficiently?Intractabilitymakesanequilibriumconceptproblemat
4、ic.Howdothemajorequilibriumconceptscomparewithrespecttothisbatteryofcriteria(convincing,universal,efficient)?ThepureNashequilibriumiscertainlynaturalandconvincing,andcanbecomputedefficiently,butiscertainlynon-universal(notjustmatchingpennies:arandomn×ngamewillfailtohaveapureN
5、ashequilibriumwithprobabilityasymptoticto1).Incontrast,themixedeNashequilibriumisfamouslyuniversalbyNash’stheorem[13],butwasrecentlyshowntobePPAD-complete,andthuspresumablyintractable[5].(Whetheritisconvincingthatagentswillengageinpreciserandomizationamongequivalentaltern
6、ativesjusttokeepothersontheirtoesisaninterestingquestion.)Thecorrelatedequilibriumisbothefficientanduniversal,butassumestoomuchma-chinerytobetrulyconvincing.Incidentally,theaboveaccountoftheefficiencyofequilibriumconceptsappliestothenormalformrepresentationofgames,andthisform
7、isinadequatefordescribingmultiplayergames.Insuccinctlyrepre-sentablegames,thesituationisquiteabitdifferent:PureNashequilibriacanbeNP-complete(graphicalgames)orPLS-complete(congestiongames[10]),whileformostsuccinctrepresentationsmixedNashequilibriaremainPPAD-complete[4]andc
8、orrelatedequilibriaremaintractable[14]).TherecentproofoftheintractabilityoffindingamixedNashequil
