Evolutionary and asymptotic stability in symmetric

arXiv:q-bio/0409028v1[q-bio.PE]24Sep2004Evolutionaryandasymptoticstabilityinsymmetricmulti-playergamesMaciejBukowskiInstituteofEconomicsWarsawSchoolofEconomicsAlejeNiepodleglo´sci16202-554Warsaw,Polande-mail:[e-mail]¸ekiszInstituteofAppliedMathematicsandMechanicsWarsawUniversityul.Banacha202-097Warsaw,Polande-mail:[e-mail]9,2008Abstract.Weprovideaclassificationofsymmetricthree-playergameswithtwostrategiesandinvestigateevolutionaryandasymptoticstability(inthereplicatordynamics)oftheirNashequilibria.Wediscusssimilaritiesanddifferencesbetweentwo-playerandmulti-playergames.Inparticular,weconstructexampleswhichexhibitanovelbehaviornotfoundintwo-playergames.KeyWords:Multi-playergames,evolutionarilystablestrategies,asymptoticstability,repli-catordynamics,risk-dominance.11IntroductionEquilibriumbehaviorofsystemsofmanyinteractingentitiescanbedescribedintheframeworkofgame-theoreticmodels.Althoughtherearemanyplayersinthesemodels,theirstrategicinteractionsareusuallydecomposedintoasumoftwo-playergames[1,2,3,4,5].Onlyrecently,therehaveappearedsomesystematicstudiesoftrulymulti-playergames[6,7,8].Wewillprovidehereaclassificationofsymmetricthree-playergameswithtwostrategiesanddescribetheirsymmetricNashequilibriaandevolutionarilystablestrategies.Asintwo-playergames,foracertainrangeofpayoffparameters,thereexistmultipleNashequilibria.Inthefirstclassofourgames,therearetwopureNashequilibriaandamixedone.Suchgamesarethree-playeranalogsoftwo-playercoordinationgames.Inthesecondclass,therearetwomixedNashequilibriaandapureone.OnemayalsohavegameswithonepureandonemixedNashequilibrium.Wearefacedthereforewithastandardproblemofequilibriumselection.Wediscussinthiscontextevolutionarilystablestrategies.WedevelopasimplecriteriontocheckwhetheragivenNashequilibriumisevolutionarilystableinagamewithtwostrategiesandapplyittothree-playergames.ThenweinvestigatetheasymptoticstabilityofNashequilibriainthereplicatordynamics.Herewealsoencountersomenovelbehavior.Itconcernssupersymmetricgames,i.e.,thosewhereforanygivenprofileofstrategies,payoffsofallplayersarethesame.Anysymmetricn-playergamewithtwostrategiescanbetransformedbythestandardpayofftransformationintoasupersymmetricgamewhichhasthesamesetofNashequilibriaandevolutionarilystablestrategies[9,10,11].Inotherwords,anyn-playergamewithtwostrategiesisasocalledpotentialgame[12].Itisknownthatintwo-playergames,interiorevolutionarilystablestrategiesaregloballyasymptoticallystable.Three-playergameswithtwostrategiesbelongingtothesecondcategoryofourclassificationhavetwoevolutionarilystablestrategies,apureandaninteriorone.Duetoageneraltheorem,theyarebothasymptoticallystableandthereforetheinterioroneisnotgloballystable.Wealsoconstructanexampleof2afour-playersupersymmetricgamewithtwointeriorevolutionarilystablestrategies,henceneitherofthemisgloballystable.Itisalsoknownthatinsupersymmetrictwo-playergames,astrategyisevolutionarilystableifandonlyifitisasymptoticallystableinthereplicatordynamics.Weshowthatthisisalsotrueinsupersymmetricn-playergames.Finally,wediscusstheconceptofrisk-dominance[13]anditsrelationtothesizeofthebasinofattractioninthereplicatordynamicsofaNashequilibrium.Weshow,thatunlikeintwo-playergameswithtwostrategies,risk-dominantstrategiesmayhavesmallerbasinsofattractionthandominatedones.InSection2,wedefinemulti-playergames.InSection3,weprovideaclassificationofsymmetricthree-playergameswithtwostrategiesanddescribetheirsymmetricNashequilibria.InSection4,wediscussevolutionarilystablestrategiesofourgames.InSection5,westudyasymptoticstabilityofNashequilibriainthereplicatordynamics.InSection6,relationsbetweentherisk-dominanceandthesizeofthebasinofattractionareanalyzed.DiscussionfollowsinSection7.2Multi-PlayerGamesDefinition1AgameinthenormalformisatripleG=(I,S,π),whereI={1,2,...,n}isthesetofplayers,S=×ni=1Si,whereSi={1,2,...,ki},isthefinitesetofstrategiesavailableforeachplayer,π:S→Rnisapayofffunctionassigningtoeveryprofileofpurestrategies,s=(s1,s2,...,sn)∈S,avectorofpayoffs,π(s)=(π1(s),π2(s),...πn(s)),whereπi(s)isthepayoffofthei-thplayerintheprofiles.Wewillconsiderhereonlysymmetricgames.Insuchgames,allplayersassumethesameroleinthegameandmoreoverthepayoffofanyplayerdependsonlyonhisstrategyandnumbersofplayersplayingdifferenttypesofstrategies.Moreformally,Definition2Giscalledsymmetric,ifforeverypermutationofthesetofplayers,σ:I→I,3wehaveπi(s1,s2,...,sn)=πσ−1(i)sσ(1),sσ(2),...,sσ(n).Aspecialsubclassofsymmetricgamesconsistofsupersymmetricgames,whereallplayersgetthesamepayoffdependentonlyontheprofileofstrategies.Definition3G=(I,S,π)iscalledsupersymmetricifforeverypermutationofthesetofplayers,σ:I→I,andeveryi,πi(s1,s2,...,sn)=π1sσ(1),sσ(2),...,sσ(n).Payoffsinsymmetricgamesareuniquelydeterminedbythepayofffunctionof,say,thefirstplayer:u1:S→R.Wesetas1s2...sn=π1(s1,s2,...,sn).Thepayofffunctionofatwo-playergamewithkstrategiescanbethenrepresentedbyak×kmatrix,A=(aij),whereaijisthepayoffofthefirst(row)playerwhenheplaysthestrategyi,whilethesecond(column)playerisplayingthestrategyj.Payoffsofathree-playergamewithkstrat