演化博弈理论(进化博弈论)

EvolutionaryGameTheoryAmitBahlCIS620OutlineEGTversusCGTEvolutionaryStableStrategiesConceptsandExamplesReplicatorDynamicsConceptsandExamplesOverviewof2papersSelectionmethods,finitepopulationsEGTv.ConventionalGameTheoryModelsusedtostudyinteractivedecisionmaking.Equilibriumisstillatheartofthemodel.Keydifferenceisinthenotionofrationalityofagents.AgentRationalityInGT,oneassumesthatagentsareperfectlyrational.InEGT,trialanderrorprocessgivesstrategiesthatcanbeselectedforbysomeforce(evolution-biological,cultural,etc…).ThislackofrationalityisthepointofdeparturebetweenEGTandGT.EvolutionWheninbiologicalsense,naturalselectionismodeofevolution.StrategiesthatincreaseDarwinianfitnessarepreferable.Frequencydependentselection.EvolutionaryGameTheory(EGT)HasoriginsinworkofR.A.Fisher[TheGeneticTheoryofNaturalSelection(1930)].•Fisherstudiedwhysexratioisapproximatelyequalinmanyspecies.•MaynardSmithandPriceintroduceconceptofanESS[TheLogicofAnimalConflict(1973)].•Taylor,Zeeman,Jonker(1978-1979)providecontinuousdynamicsforEGT(replicatordynamics).ESSApproachESS=NashEquilibrium+StabilityConditionNotionofstabilityappliesonlytoisolatedburstsofmutations.SelectionwilltendtoleadtoanESS,onceatanESSselectionkeepsusthere.ESS-Definition•Considera2playersymmetricgamewithESSgivenbyIwithpayoffmatrixE.•LetpbeasmallpercentageofpopulationplayingmutantstrategyJI.•FitnessgivenbyW(I)=W0+(1-p)E(I,I)+pE(I,J)W(J)=W0+(1-p)E(J,I)+pE(J,J)•RequirethatW(I)W(J)ESS-DefinitionStandardDefinitionforESS(MaynardSmith).IisanESSifforallJI,E(I,I)E(J,I)andE(I,I)=E(J,I)E(I,J)E(J,J)whereEisthepayofffunction.ESS-DefinitionAssumptions:1)Pairwise,symmetriccontests2)Asexualinheritance3)Infinitepopulation4)CompletemixingESS-ExistenceLetGbeatwo-payersymmetricgamewith2purestrategiessuchthatE(s1,s1)E(s2,s1)ANDE(s1,s2)E(s2,s2)thenGhasanESS.ESSExistenceIfac,thens1isESS.Ifdb,thens2isESS.Otherwise,ESSgivenbyplayings1withprobabilityequalto(b-d)/[(b-d)+(a-c)].s1s2s1abs2cdESS-Example1ConsidertheHawk-DovegamewithpayoffmatrixNashequilibriumgivenby(7/12,5/12).ThisisalsoanESS.HDH-25,-2550,0D0,5015,15ESS-Example1Bishop-CanningsTheorem:IfIisamixedESSwithsupporta,b,c,…,thenE(a,I)=E(b,I)=…=E(I,I).Atastablepolymorphicstate,thefitnessofHawksandDovesmustbethesame.W(H)=W(D)=TheESSgivenisastablepolymorphism.StablePolymorphicStateESS-Example2ConsidertheRock-Scissors-PaperGame.PayoffmatrixisgivenbyRSPR-e1-1S-1-e1P1-1-eThenI=(1/3,1/3,1/3)isanESSbutstablepolymorphicpopulation1/3R,1/3P,1/3Sisnotstable.ESS-Example3Payoffmatrix:ThenI=(1/3,1/3,1/3)istheuniqueNE,butnotanESSsinceE(I,s1)=E(s1,s1)=1.s1s2s3s11,12,-2-2,2s2-2,21,12,-2s32,-2-2,21,1SexRatiosRecallFisher’sanalysisofthesexratio.Whyarethereapproximatelyequalnumbersofmalesandfemalesinapopulation?Greatestproductionofoffspringwouldbeachievedifthereweremanytimesmorefemalesthanmales.SexRatiosLetsexratiobesmalesand(1-s)females.W(s,s’)=fitnessofplayingsinpopulationofs’FitnessisthenumberofgrandchildrenW(s,s’)=N2[(1-s)+s(1-s’)/s’]W(s’,s’)=2N2(1-s’)Needs*s.t.sW(s*,s*)W(s,s*)DynamicsApproachAimstostudyactualevolutionaryprocess.OneApproachisReplicatorDynamics.Replicatordynamicsareasetofdeterministicdifferenceordifferentialequations.RD-Example1Assumptions:Discretetimemodel,non-overlappinggenerations.xi(t)=proportionplayingiattimet(i,x(t))=E(numberofreplacementforagentplayingiattimet)j{xj(t)(j,x(t))}=v(x(t))xi(t+1)=[xi(t)(i,x(t))]/v(x(t))RD-Example1Assumptions:Discretetimemodel,non-overlappinggenerations.xi(t+1)-xi(t)=xi(t)[(i,x(t))-v(x(t))]v(x(t))RD-Example2Assumptions:overlappinggenerations,discretetimemodel.Intimeperiodoflength,letfractiongivebirthtoagentsalsoplayingsamestrategy.jxj(t)[1+(j,x(t))]=v(x(t))xi(t+)=xi(t)[1+(i,x(t))]v(x(t))RD-Example2Assumptions:overlappinggenerations,discretetimemodel.xi(t+)-xi(t)=xi(t)[(i,x(t))-v(x(t))]1+v(x(t))RD-Example3Assumptions:Continuoustimemodel,overlappinggenerations.Let0,thendxi/dt=xi(t)[(i,x(t))-v(x(t))]StabilityLetx(x0,t):SXRSbetheuniquesolutiontothereplicatordynamic.AstatexSisstationaryifdx/dt=0.AstatexisstableifitisstationaryandforeveryneighborhoodVofx,thereexistsaUVs.t.x0U,tx(x0,t)V.PropostionsforRDIf(x,x)isaNE,thenxisastationarystateoftheRD.dxi/dt=xi(t)[(i,x(t))-v(x(t))]Whatabouttheconverse?Considerpopulationofalldoves.PropostionsforRDIfxisastablestateoftheRD,then(x,x)isaNE.Consideranyperturbationthatintroducesabetterreply.Whatabouttheconverse?Consider:s1s2s11,10,0s20,00,0StrongernotionofStabilityAstatexisasymptoticallystableifitisstableandthereexistsaneighborhoodVofxs.t.x0V,limtx(x0,t)=x.ESSandRDIngeneral,everyESSisasymptoticallystable.Whatabouttheconverse?ESSandRDConsiderthefollowinggame:UniqueNEgivenbyx*=(1/3,1/3,1/3).Ifx=(0,1/2,1/2),thenE(x,x*)=E(x*,x*)=2/3butE(x,x)=5/47/6=E(x*,x).s1s2s3s10,01,-21,1s2-2,10,04,1s31,11,40,0ESSandRDs1s2s3s10,01,-21,1s2-2,10,04,1s31,11,40,0x*xx*2/3,2/37/6,2/3x2/3,7/65/4,5/4In2X2games,xisanESSifandonlyifxisasymptoticallystable.AGame-TheoreticInvestigationofSelect