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

EvolutionaryGameTheoryAmitBahlCIS620OutlineEGTversusCGTEvolutionaryStableStrategies ConceptsandExamplesReplicatorDynamics ConceptsandExamplesOverviewof2papers Selectionmethods,finitepopulations EGTv.ConventionalGameTheoryModelsusedtostudyinteractivedecisionmaking.Equilibriumisstillatheartofthemodel.Keydifferenceisinthenotionofrationalityofagents.AgentRationalityInGT,oneassumesthatagentsareperfectlyrational.InEGT,trialanderrorprocessgivesstrategiesthatcanbeselectedforbysomeforce(evolution-biological,cultural,etc…).ThislackofrationalityisthepointofdeparturebetweenEGTandGT.EvolutionWheninbiologicalsense,naturalselectionismodeofevolution.StrategiesthatincreaseDarwinianfitnessarepreferable.Frequencydependentselection.EvolutionaryGameTheory(EGT)HasoriginsinworkofR.A.Fisher[TheGeneticTheoryofNaturalSelection(1930)].Fisherstudiedwhysexratioisapproximatelyequalinmanyspecies.MaynardSmithandPriceintroduceconceptofanESS[TheLogicofAnimalConflict(1973)].Taylor,Zeeman,Jonker(1978-1979)providecontinuousdynamicsforEGT(replicatordynamics).ESSApproachESS=NashEquilibrium+StabilityConditionNotionofstabilityappliesonlytoisolatedburstsofmutations.SelectionwilltendtoleadtoanESS,onceatanESSselectionkeepsusthere.ESS-DefinitionConsidera2playersymmetricgamewithESSgivenbyIwithpayoffmatrixE.LetpbeasmallpercentageofpopulationplayingmutantstrategyJ

I.Fitnessgivenby

W(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-DefinitionStandardDefinitionforESS(MaynardSmith).IisanESSifforallJ

I, E(I,I)

E(J,I)and E(I,I)=E(J,I)

E(I,J)>E(J,J)whereEisthepayofffunction.ESS-DefinitionAssumptions: 1)Pairwise,symmetriccontests 2)Asexualinheritance 3)Infinitepopulation 4)CompletemixingESS-ExistenceLetGbeatwo-payersymmetricgamewith2purestrategiessuchthat

E(s1,s1)

E(s2,s1)AND E(s1,s2)

E(s2,s2) thenGhasanESS.ESSExistenceIfa>c,thens1isESS.Ifd>b,thens2isESS.Otherwise,ESSgivenbyplayings1withprobabilityequalto(b-d)/[(b-d)+(a-c)].ESS-Example1ConsidertheHawk-Dovegamewithpayoffmatrix Nashequilibriumgivenby(7/12,5/12).ThisisalsoanESS.ESS-Example1Bishop-CanningsTheorem:IfIisamixedESSwithsupporta,b,c,…,thenE(a,I)=E(b,I)=…=E(I,I).Atastablepolymorphicstate,thefitnessofHawksandDovesmustbethesame.W(H)=W(D)=>TheESSgivenisastablepolymorphism.

StablePolymorphicStateESS-Example2ConsidertheRock-Scissors-PaperGame.Payoffmatrixisgivenby

RSP R-e

1

-1 S-1-e1 P1-1-e ThenI=(1/3,1/3,1/3)isanESSbutstablepolymorphicpopulation1/3R,1/3P,1/3Sisnotstable.ESS-Example3Payoffmatrix:ThenI=(1/3,1/3,1/3)istheuniqueNE,butnotanESSsinceE(I,s1)=E(s1,s1)=1.SexRatiosRecallFisher’sanalysisofthesexratio.Whyarethereapproximatelyequalnumbersofmalesandfemalesinapopulation?Greatestproductionofoffspringwouldbeachievedifthereweremanytimesmorefemalesthanmales.SexRatiosLetsexratiobesmalesand(1-s)females.W(s,s’)=fitnessofplayingsinpopulation ofs’FitnessisthenumberofgrandchildrenW(s,s’)=N2[(1-s)+s(1-s’)/s’] W(s’,s’)=2N2(1-s’)Needs*s.t.sW(s*,s*)

W(s,s*)DynamicsApproachAimstostudyactualevolutionaryprocess.OneApproachisReplicatorDynamics.Replicatordynamicsareasetofdeterministicdifferenceordifferentialequations.RD-Example1Assumptions:Discretetimemodel,non-overlappinggenerations.xi(t)=proportionplayingiattimet(i,x(t))=E(numberofreplacementfor agentplayingiattimet)

j{xj(t)

(j,x(t))}=v(x(t))xi(t+1)=[xi(t)(i,x(t))]/v(x(t))RD-Example1Assumptions:Discretetimemodel,non-overlappinggenerations.xi(t+1)-xi(t)=xi(t)[(i,x(t))-v(x(t))] v(x(t))

RD-Example2Assumptions:overlappinggenerations,discretetimemodel.Intimeperiodoflength

,letfraction

givebirthtoagentsalsoplayingsamestrategy.

j

xj(t)[1+

(j,x(t))]=v(x(t))xi(t+

)=xi(t)[1+

(i,x(t))]

v(x(t))RD-Example2Assumptions:overlappinggenerations,discretetimemodel.xi(t+

)-xi(t)=xi(t)[

(i,x(t))-

v(x(t))] 1+v(x(t))RD-Example3 Assumptions:Continuoustimemodel,overlappinggenerations.Let0,then

dxi

/dt

=

xi(t)[(i,x(t))-v(x(t))]

StabilityLetx(x0,t):

SXR

Sbetheuniquesolutiontothereplicatordynamic.Astatex

Sisstationaryifdx/dt=0.AstatexisstableifitisstationaryandforeveryneighborhoodVofx,thereexistsaU

Vs.t.

x0

U,

tx(x0,t)

V.PropostionsforRDIf(x,x)isaNE,thenxisastationarystateoftheRD.

dxi/dt

=xi(t)[(i,x(t))-v(x(t))] Whatabouttheconverse?Considerpopulationofalldoves.PropostionsforRDIfxisastablestateoftheRD,then(x,x)isaNE.Consideranyperturbationthatintroducesabetterreply.Whatabouttheconverse?Consider:StrongernotionofStabilityAstatex

isasymptoticallystableifitisstableandthereexistsaneighborhoodVofx

s.t.

x0

V,limt

x(x0,t)=x.ESSandRDIngeneral,everyESSisasymptoticallystable.Whatabouttheconverse?

ESSandRDConsiderthefollowinggame:UniqueNEgivenbyx*=(1/3,1/3,1/3).Ifx=(0,1/2,1/2),then E(x,x*)=E(x*,x*)=2/3but E(x,x)=5/4>7/6=E(x*,x).

ESSandRDIn2X2games,xisanESSifandonlyifxisasymptoticallystable.AGame-TheoreticInvestigationofSelectionMethodsUsedinEvolutionaryAlgorithmsFicici,Melnik,PollackSelectionMethodsHowdocommonselectionmethodsusedinevolutionaryalgorithmsfunctioninEGT?Dynamicsandfixedpointsofthegame.Selectionfunctionxi(t+1)=S(F(xi(t)),xi(t)) whereSistheselectionfunction, Fisthefitnessfunction,and xi(t)istheproportionofpopulation playingiattimet.FitnessDependentSelectionf’=(pXf)/(p•f){x(x0,t):t

R}=orbitpassingthroughx0.

TruncationSelection1)Sortbyfitness2)Replacek%oflowestbyk%ofhighestTruncationSelectionConsidertheHawk-DovegamewithESSgivenby(7/12H,5/12D) If.5<xH(t)<7/12,thenxH(t+1)=1. TruncationSelectionMapDiagram:(,)-ESSelectionGivenapopulationofoffspring,thebestarechosentoparentthenextgeneration.Moreextremethantruncationselection.LinearRankSelectionAgentssortedaccordingtofitness.Assignednewfitnessvaluesaccordingtotheirrank.Causesfitnesstochangelinearlywithrank.Cause