Group Dominant Strategies (Extended Abstract)

GroupDominantStrategies(ExtendedAbstract)[e-mail][e-mail]–IsraelInstituteofTechnology,Haifa32000,IsraelAbstract.Weintroduceanewsolutionconceptforcompleteinformationgames,whichwecallequilibriumingroupdominantstrategies.Thisconceptisthestrongestofallknownsolutionconceptssofar,sinceitencompassesboththeideasbe-hindtheconceptsofdominantstrategiesandstrongequilibrium.Becauseofitsstrength,asolutioningroupdominantstrategiesdoesnotexistinanyinterest-inggame;however,asweshow,suchsolutionscanbeachievedinvariousrichsettingswiththeuseofmediators.1IntroductionAfinitegameinstrategicformisatuple=hN;fAigi2N;fuigi2Niwhere:–N=f1;:::;ngisafinitesetofplayers.–Foreachplayeri2N,Aiisafinitenon-emptysetofactions(orstrategies,weusethetermsinterchangeably)availabletoplayeri.–ForSN,ASdenotesQi2SAi,andASdenotesQi2NnSAi.ANisdenotedbyA.–Foreachplayeri2N,ui:A!isautilityfunction,whichrepresentsthe“contentment”oftheplayerwitheachspecificstrategyprofile.–Leta2A.Wewillsometimeswriteaas(ai;ai)fori2Nandas(aS;aS)forSN.Oneofthemostbasicquestionsofgametheoryis:givenagameinstrategicform,whatisthesolutionofthegame?Basically,bya“solution”wemeanastablestrategyprofilewhichcanbeproposedtoallagents,inasensethatnorationalagentwouldwanttodeviatefromit.Manysolutionconceptsforgameshavebeenstudied,differingmainlybytheassumptionsthatarationalagentwouldhavetomakeabouttherationalityofotheragents.Forexample,probablythemostwellknownsolutionconceptforgamesistheNashequilibrium:Aprofileofactionsa2AisaNashequilibrium(NE)if8i2Nai2bri(ai)Here,bri(ai)fori2N,ai2Aidenotesargmaxai2Aifui(ai;ai)g(thesetofbestresponsesofitoai).TherearetwobasicproblemswiththeNashequilibriumasasolutioncon-ceptforgames:Problem1:ANEguaranteesabsenceofprofitabledeviationstoaplayeronlyinthecasethatalltheotherplayersplayaccordingtothesuggestedprofile;inthecasewhereevenoneoftheotherplayersdeviates,wehavenosuchguaran-tees.So,theassumptionthatthisconceptrequiresabouttherationalityofotherplayersis:alltheotherplayerswillsticktotheirprescribedstrategies.Butwhyshouldarationalplayermakethatassumption?Thefollowingstabilityconcepttakesthisproblemintoaccount:Aprofileofactionsa2Aisanequilibriuminweaklydominantstrategiesif8i2N;bi2Aiai2bri(bi)TheabovedefinitionstrengthenstheconceptofNEbytakingcareoftheaforementionedproblem:nounilateraldeviationcaneverbebeneficial,nomat-terwhatotherplayersdo;inotherwords,itrequiresnoassumptionsontherationalityofotherplayers.Problem2:ANEdoesnottakeintoaccountjointdeviationsbycoalitionsofplayers.Weusuallyassumethatanindividualwilldeviatefromaprofileifshehasanavailablestrategythatstrictlyincreasesherincome.Insomesettingsitwouldbenaturaltoassumealsothatagroupofindividualswilldeviateiftheyhaveanavailablejointstrategythatstrictlyincreasestheincomeofeachgroupmember.Forexample,considerthefamousPrisoner’sDilemmagame:CDC4,40,6D6,01,1Thestrategyprofile(D;D)isaNEandevenanequilibriuminweaklydom-inantstrategies;however,itisnotstableinthesensethatifbothplayersdeviateto(C;C),theincomeofeachoneofthemwillincrease.Thefollowingstabilityconceptby(Aumann,1959)dealswiththisproblem:Aprofileofactionsa2Aisastrongequilibrium(SE)if8SNaS2brS(aS)Here,theconceptofbestresponsestrategyisextendedtomultipleplayersasfollows:forSNandaS2AS,brS(aS)denotesthesetofbestresponsesofStoaS:brS(aS)=faS2ASj8bS2AS9i2Sui(bS;aS)ui(aS;aS)gTheconceptofstrongequilibriumindeedtakescareofProblem2;how-ever,itagaindoesnottakeProblem1intoaccount.Whatwewouldideallyliketohaveisasolutionconceptthathasneitheroftheseproblems:wewouldliketoassumethatplayersareabletocooperateformutualbenefit,andontheotherhandwewouldalsoliketoassumenothingabouttheactionsoftheotherplayers.Theserequirementsmayseemconflicting.Notethatsimplysayingthatweareinterestedinaprofilea2AthatisbothaSEandanequilibriuminweaklydominantstrategiesisnotenough:forgameswithmorethan2players,wewouldhavenoguaranteesabouttheabsenceofjointdeviationsforplayers1and2,inthecasethatplayer3deviated.Thisbringsustothestabilityconceptthatwewishtopresent:aprofileofactionsa2Aisanequilibriumingroup(weakly)dominantstrategies(GDS)if8SN;bS2ASaS2brS(bS)ExistenceofaGDSimplies,foreachplayer,thatnomatterwhattheotherplayerschoose,andnomatterwithwhomcansheuniteinmakingherdecision,theywillnotfindajointstrategythatwillbebettertoallofthemthantheproposedone.Andthus,ifaGDSexistsinagivengame,wecansafelydeclareittobethesolutionofthegame.However,aGDSdoesnotexistinanygamethathaseverbeenasubjectofinterest.Thisisnotsurprising,sincetheconceptissostrongthatitsmereexistencerendersanygamenotinteresting.Forthisreason,theconceptwasneverasubjectofexplorationincompleteinformationgames.Inincompleteinformationgamestheconceptisknownunderthenameofgroupstrategyproofnessandiswidelystudied,becauseinsomecasessuchsolutionscanbeindeedimplementedbymechanismdesign.However,thewholeapproachofmechanismdesignisnotapplicabletocompleteinformationgames–althoughwewouldindeedwanttoassumetheexistenceofaninterestedparty,wedon’twanttogiveitthepowertodesignthegame.Aninter