ACADÉMIE D'AIX MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
ACADÉMIE D'AIX-MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE THÈSE présentée à l'Université d'Avignon et des Pays de Vaucluse pour obtenir le diplôme de DOCTORAT SPÉCIALITÉ : Informatique École Doctorale 380 «Sciences et Agronomie» Laboratoire d'Informatique (EA 931) Population games with networking applications par Hamidou TEMBINE Soutenue publiquement le 18 Septembre 2009 devant un jury composé de : M. Philippe MICHELON Professeur, Université d'Avignon Président M. Tamer BAS¸AR Professeur, University of Illinois at Urbana-Champaign Rapporteur M. Nahum SHIMKIN Professeur, Technion Rapporteur M. Pierre BERNHARD Professeur Emérite, INRIA Examinateur M. Konstantin AVRACHENKOV Chargé de recherche, INRIA Examinateur M. Eitan ALTMAN Directeur de Recherche, INRIA, Sophia Antipolis Directeur M. Rachid EL-AZOUZI Maître de Conférences, Université d'Avignon Co-Directeur Laboratoire d'Informatique d'Avignon

  • stochastic mean

  • games

  • battery-state dependent

  • population games

  • power levels

  • solar-powered system

  • global optimization


Publié le : mardi 1 septembre 2009
Lecture(s) : 43
Source : univ-avignon.fr
Nombre de pages : 222
Voir plus Voir moins

ACADÉMIED’AIX-MARSEILLE
UNIVERSITÉD’AVIGNONETDESPAYSDEVAUCLUSE
THÈSE
présentéeàl’Universitéd’AvignonetdesPaysdeVaucluse
pourobtenirlediplômedeDOCTORAT
SPÉCIALITÉ: Informatique
ÉcoleDoctorale 380«SciencesetAgronomie»
Laboratoire d’Informatique(EA931)
Populationgameswithnetworkingapplications
par
HamidouTEMBINE
Soutenuepubliquementle18Septembre2009devantunjurycomposéde:
M. Philippe MICHELON Professeur,Universitéd’Avignon Président
M. TamerBAS¸AR Professeur,UniversityofIllinois atUrbana-Champaign Rapporteur
M. NahumSHIMKIN Professeur,Technion Rapporteur
M. PierreBERNHARD ProfesseurEmérite,INRIA Examinateur
M. Konstantin AVRACHENKOV Chargéderecherche,INRIA Examinateur
M. EitanALTMAN DirecteurdeRecherche,INRIA,SophiaAntipolis Directeur
M. RachidEL-AZOUZI MaîtredeConférences,Universitéd’Avignon Co-Directeur
Laboratoired’Informatiqued’AvignonContents
1 Introduction 3
I DelayedEvolutionaryGameDynamicswithMigration 14
2 Delayedevolutionarygamedynamics 15
2.1 Settingandnotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 DelaysandFitnesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2 Delayedevolutionarygamedynamics . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Stabilityanalysisofthedelayedreplicatordynamics . . . . . . . . . . . . 20
2.2 MultipleAccessGamewithRegretCost . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 NashEquilibria,ESSandParetooptimality . . . . . . . . . . . . . . . . . . 24
2.2.2 StabilityboundforESSunderreplicatordynamics . . . . . . . . . . . . . . 25
2.2.3 Imitatethebetterdynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.4 Numericalillustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 EvolutionofTransportProtocolsinWirelessandWiredNetworks . . . . . . . . 31
2.3.1 CompetitionBetweenCongestionControlProtocols . . . . . . . . . . . . . 33
2.3.2 CompetitioninWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.3 CompetitioninWirelineNetworks . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.4 Architectingevolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.5 Numericalillustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 Multi-classdelayedevolutionary gamedynamics . . . . . . . . . . . . . . . . . . 41
3 Evolutionarygameswithrandomnumberofinteractingplayers 43
3.1 Reciprocalandnon-reciprocalinteractions . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.1 Non-reciprocalpairwiseinteraction . . . . . . . . . . . . . . . . . . . . . . 44
3.1.2 Non-reciprocalinteractions betweengroupsthreeplayers . . . . . . . . . 45
3.1.3 Interactionsbetweenrandomnumberofplayers . . . . . . . . . . . . . . . 46
3.1.4 Spatialnon-reciprocalrandomaccessgames . . . . . . . . . . . . . . . . . 47
3.2 Why randomnumberofplayers? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Modelandnotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 SlottedAloha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.4 ESSandnodesdistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.9 Coordinationmechanisms toreducecollisions . . . . . . . . . . . . . . . . 63
3.5 W-CDMAWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5.1 NumericalexamplesinW-CDMAWirelessNetworks: . . . . . . . . . . . 69
3.6 OFDMA-basedIEEE802.16Network . . . . . . . . . . . . . . . . . . . . . . . . . . 71
ii3.6.1 NumericalinvestigationinOFDMA-basedIEEE802.16networks . . . . . 74
3.7 CorrelatedEvolutionarilyStableStrategiesinRandomMediumAccess . . . . . . 75
3.7.1 Accesscontrolwithseveralpowerlevels . . . . . . . . . . . . . . . . . . . 77
3.7.5 Generaldistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.7.7 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.7.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4 Evolutionarygamedynamicswithmigration 96
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.2 TheHybridModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.1 GlobalNashEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.2 Globalevolutionarily stablestate(ESS) . . . . . . . . . . . . . . . . . . . . 99
4.2.3 ChoiceConstrainedEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2.4 GeneralGameDynamics withMigration . . . . . . . . . . . . . . . . . . 99
4.3 Equilibriumandrestpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.4 ClassofGameswithMulticomponents Strategies . . . . . . . . . . . . . . . . . . 104
4.4.1 StablePopulationGames . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.2 Potential PopulationGames . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.4.3 Migrationwithconstraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.4.4 Inverseproblem: reachableregionsofapowerlevel . . . . . . . . . . . . . 107
4.5 GlobalOptimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.6 HybridpowercontrolinOFDMA-basedIEEE802.16network . . . . . . . . . . . 108
4.7 AhybridevolutionarygameinmulticellCDMAsystem . . . . . . . . . . . . . . 109
4.8 Numericalinvestigation: Convergencetotheequilibrium . . . . . . . . . . . . . . 111
II StochasticPopulationGames 115
5 StochasticPopulationGames 116
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.2 IllustratingExamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.2.1 Batterystate-deependentpowermanagement . . . . . . . . . . . . . . . . 117
5.2.2 EnergymanagementinhybridAloha-likenetworks . . . . . . . . . . . . . 117
5.2.3 Markovdecisionprocess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.3 Singlepopulationstochasticevolutionary games . . . . . . . . . . . . . . . . . . . 119
5.4 Stochasticpopulationgames: multiclass case . . . . . . . . . . . . . . . . . . . . . 124
5.4.1 Histories andStrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.4.2 Cesaro-limitFitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.5 Constrainedstochasticpopulationgames . . . . . . . . . . . . . . . . . . . . . . . 126
5.6 EnergyControlinWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.6.1 Time averagefitnesscriterion . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.7 Energycontrol: absorbing state . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.7.1 Individualsequentialdecision . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.7.2 BinaryReward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.7.3 Computing Fitness using DynamicProgramming . . . . . . . . . . . . . . 133
5.7.4 SojournTimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.7.5 Reducedgame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.7.6 Deterministic strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.7.7 Purestationarystrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.7.8 State-independentstrategies . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.7.9 State-dependentactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.7.11 Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
iiiContents
5.7.12 NumericalIllustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.7.13 State-Independentaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.7.14 Dependentstateaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.7.15 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5.8 AccessControlinSolar-PoweredBroadbandNetworks . . . . . . . . . . . . . . . 149
5.8.1 Stochasticmodeling oftheenergylevelsofSolar-poweredbattery . . . . 152
5.8.2 Battery-statedependentaccesscontrolinsolar-poweredsystem . . . . . . 153
5.8.3 Computing EquilibriaandESS . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.8.4 Powercontrol incloudedweather . . . . . . . . . . . . . . . . . . . . . . . 156
5.8.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.9 Wardropequilibriainnonatomic stochasticpowercontrolgames . . . . . . . . . 157
5.10 Differenttypesofrenewableenergy . . . . . . . . . . . . . . . . . . . . . . . . . . 159
III MeanFieldLimits 164
6 Meanfieldasymptoticsofpopulationgames 165
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.2 Thesetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
6.2.1 Revisionofstrategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.2.2 Instantaneous payoffs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.3 Convergencetodifferentialequation . . . . . . . . . . . . . . . . . . . . . . . . . . 168
6.4 Frommeanfieldinteractionstoevolutionary games . . . . . . . . . . . . . . . . . 170
6.4.1 Equilibriumstateanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.4.2 Dynamics ofevolvinggames . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.4.3 Singleplayerselectedpertimeslot . . . . . . . . . . . . . . . . . . . . . . . 172
6.4.4 Dynamics forpairwiselocalinteraction . . . . . . . . . . . . . . . . . . . . 173
6.4.5 Equilibriumandrestpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.5 ASpatialNon-ReciprocalRandomAccessModel . . . . . . . . . . . . . . . . . . . 176
7 Stochasticmeanfieldgames 179
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
7.2 Modeldescription . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.2.1 MarkovDecisionEvolutionaryProcessWith N Players . . . . . . . . . . . 180
7.2.2 Payoffs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
7.2.3 Focus onOneSinglePlayer . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.3 MainResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
7.3.1 ScalingAssumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
7.3.3 Convergenceresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.3.7 CasewithGlobalAttractor . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.3.8 Singleplayerpertypeselectedpertime slot . . . . . . . . . . . . . . . . . 190
7.3.9 Equilibriumandoptimality . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.3.12 Robust equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
7.4 Linkwithdifferentialpopulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.5 Illustratingexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.5.1 ODEandStationarystrategies . . . . . . . . . . . . . . . . . . . . . . . . . 195
7.5.2 Computationof R(u ,u ;s,m~). . . . . . . . . . . . . . . . . . . . . . . . . . 1951 2
7.5.3 Thecaseoftwoenergylevels . . . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Listofpublications 202
1Contents
Acknowledgments
I would like to thank my advisors, Eitan Altman and Rachid El Azouzi for their continuous
guidance and support throughout my PhD studies. I amgrateful to them for having given me
the opportunity to begin this work, the freedom to carry it out, and the support and
encouragement to bring it to a conclusion. I am grateful to LIA members, MarcEl Beze, the scientific
leader of LIA, for having hosted me during this thesis. A large part of this thesis owes its
existence to the work done in collaboration with Jean Yves Le Boudec, Yezekael Hayel, and
William H. Sandholm. My sincere gratitude for all the delightful discussions. I wish to thank
Tamer Bas¸ar for hosting me as PhD Internship at University of Illinois at Urbana Champaign
in Fall 2008. It gave me the opportunity to learn new tools and methods, and to extend my
work to "evolutionary games with continuous action space" and application to access control,
rate control and network security. Many thanks to Jean Yves Le Boudec who greatly helped
me in understanding of mean field interactions during my internship at Ecole Polytechnique
Federalede Lausanne (EPFL)in Summer 2008and in Winter 2009. His patience and generous
feedback on many problems we worked on helped me greatly in writing the chapters 6 and 7
and the new class of games : differential population games that is derived from. Many thanks to
WilliamH.Sandholmforhelpfulcomments on"differentialpopulationgames"duringmystay
atUniversityofWisconsin inAugust2009.
It is a great privilege for me to have Konstantin Avrachenkov, Tamer Bas¸ar, Pierre
Bernhard, Philippe Michelon and Nahum Shimkin as members of my PhD thesis committee. I
wish to thank them for having accepted this task. I would like to thank Tamer Bas¸ar and
NahumShimkinforagreeingtoserveasreviewers,forhaving carefullyreadthe manuscript. I
am thankful to Fréderic Bonnans, Pierre Cardaliaguet, Patrick Combettes, Michael Eisermann,
Stéphane Gaubert, Jean Charles Gilbert, Lucien Guillou, Barthel Gottfried, Anatoli Iouditski,
SiegmundKosarew,JeanPierrePonssard,DinahRosenberg,EilonSolan,SylvainSorin,Tristan
Tomala, Yannick Viossat, Patrick Witomski etc for constructive comments during my graduate
and undergraduate studies that lead me to think about several problems in economics,
biology, optimization, control, stochastic processes and game theory. I am in particular indebted
to my colleagues and coauthors, with whom I spent many years, to Ephie Deriche, Jocelyne
Gourret, Patricia Hjelt, Rebecca Lonberger, Simone Mouzac for their administrative assistance
during the last two years. I am deeply grateful to French Ministry of Research, INRIA, EPFL,
EuropeanProjectBIONETS,ProjectWiNEM,ProjectPOPEYEforhavingprovidedthefinancial
supportwhichmadethisworkpossible. Lastbuttheleast,gratitudetoall,whohelpeddirectly
orindirectly.
2Chapter1
Introduction
Recently, there has been a surge in research activities that employ game theory to model
and
analyzetheperformanceofvariousnetworks,suchascommunicationnetworks,computernetworks, social networks, biologically inspirednetworks etc.
Therealreadyexistseveralsuccessfulexampleswheregametheoryprovidesdeeperunderstandingofcomplexnetworkdynamics
and leads to better design of efficient, scalable, and robust networks. Still, there remain many
interesting open research problems yet to be identified and explored, and many issues to be
addressed. Important analysis and applications have been done in the context of static games.
Motivatedbythedynamicbehaviorofmostofthelong-termsystemsandtheunderstandingof
prediction, learning and evolution, dynamic game theory has found several applications.
Those
includecooperativeandnon-cooperativemodelsofrepeatedgames,sequentialgames,stochasticgames,differentialgames,evolutionary
gamesetc.
Evolutionarygamesinlargepopulationprovidesasimpleframeworkfordescribingstrategicinteractionsamonglargenumbersofplayers. Traditionally,predictionsofbehavioringame
theory are based on some solution concept, typically Cournot equilibrium (64), Bertrand
equilibrium (47) or some extension/refinement thereof. These notions require the assumption of
equilibrium knowledge, which posits that each user correctly anticipates how other players
will act or react. The equilibrium knowledge assumption is too strong and is difficult to
justify inparticularincontexts withlargenumberof players. Asanalternativetothe
equilibrium
approach,anexplicitlydynamicupdatingchoiceisproposed,amodelinwhichplayersmyopically update their behavior in response to their current strategic environment. This dynamic
procedure does not assume the automatic coordination of player’s actions and beliefs, and it
can derive many specifications of players’ choice procedures. These procedures are specified
formally by defining a revision of pure strategies called a revision protocol. A revision protocol
takes current payoffs (also called fitness in behavioral ecology) and aggregate behavior as
inputs; its outputs are conditional switch rates which describe how frequently players in some
class playing strategy a who are considering switching strategies move to another strategy b,
given that the current payoff vector and subpopulation state. Revision protocols are
flexible
enoughtoincorporateawidevarietyofparadigms,includingonesbasedonimitation,adaptation, learning, optimization, etc. The revisionprotocols describethe proceduresplayers follow
inadaptingtheirbehaviorinthedynamicevolvingenvironment suchasevolving networks.
3Chapter1. Introduction
BirthofEvolutionaryGameTheoryinEngineering
The evolutionary games formalism is a central mathematical tool developed by biologists for
predicting population dynamics in the context of interactions between populations. This
formalism identifies and studies two concepts: the Evolutionary Stability, and the Evolutionary Game
Dynamics. The unbeatable strategy has been defined by Hamilton (95; 96) which is the
analogousofstrongequilibrium(resilientagainstmultilateraldeviations)inlargesystems. Aweaker
ofnotionoflocallyunbeatablestrategy,theEvolutionarilyStableStateorStrategy(ESS),hasbeen
defined by the biologists MaynardSmith & Price (186). The ESSis characterizedby a property
of robustness against invaders (mutations). More specifically, (i) if an ESS is reached, then the
proportions of eachpopulation do not change in time. (ii) at ESS, the populations are immune
frombeing invadedbyother small populations. This notion is strongerthanNashequilibrium
in which it is only requested that a single user would not benefit by a change (mutation) of
its behavior. The ESS concept helps to understand mixed strategies in games with symmetric
payoffs. A mixed strategy can be interpreted as a composition of the population. An ESS
can
bealsointerpretedasaNashequilibriumoftheone-shotgamebuta(symmetric)Nashequilibriumcannot beanESS.Asisshown in(223),ESShasstrongrefinementpropertiesofequilibria
suchasproperequilibrium,perfectequilibriumetc.
BeforetheESSconcept,HamiltonhasintroducedtheconceptofUnbeatableStrategy(95;96),whichisstrongerthanESS.AlthoughESSand
unbeatablestrategyhavebeendefinedinthecontext ofbiological systems, itis highly relevant
to engineering as well (230). In the biological context, the replicator dynamics is a model for
thechangeofthesizeofthepopulation(s)asbiologistobserve,whereasinengineering,wecan
go beyond characterizing and modeling existing evolution. The evolution of protocols can be
engineeredbyproviding guidelines orregulations forthe waytoupgradeexisting ones andin
determiningparametersrelatedtodeploymentofnewprotocolsandservices.
There have been a lot of work on non-cooperative modeling of power control using game
theory (76; 166). There are two advantages in doing so within the framework of evolutionary
games:

itprovidesthestrongerconceptofequilibria,theESS,whichallowsustoidentifyrobustnessagainstdeviationsofafractionofplayers,and
• itallowsustoapplythegenericconvergencetheoryofevolutionarygamedynamics,and
stabilityresultsthatweintroduceinnextchapters.
Homogenouspopulation
Weconsiderthestandardsettingofevolutionarygames: thereisalargepopulationsofplayers;
eachmemberofthepopulationhasthesamepureactionsetA (afiniteset).
Mixedstrategiesandpopulationprofile
|A|Denote by Δ(A) the (|A|−1)−dimensional simplex of R . Let x(t) be the |A|−
dimensional vectorwhose element x (t)is thepopulationshareofstrategy a attime t.Thuswe,havea
x (t) = 1 and x (t) ≥ 0. We frequently use an equivalent interpretation where x(t) is aa a∑
a∈A
mixed strategyused by all players at time t; by a mixed strategy we mean that a player chooses
attime t anaction a withprobability x (t). Witheitherinterpretations,ateachlocalinteractiona
occurring at time t a given player can expect that the other player would play strategy a with
4probability x (t). Thevector x(t)will alsobecalledthestateofthe populationattime t.Definea
theexpectedpayoffofaplayerwiththeaction a whenthepopulationprofile x(t)by f (x(t)).a
EquilibriumandEvolutionaryStability
The evolutionarily stable state or strategy (ESS)concept have the property that if it is reached,
thentheproportions ofeachpopulationdonot changeintime.
Supposethat,initially,thepopulation state has been x ∈ Δ(A) during a long time. The average payoff in the population is
x f (x).Nowsupposethatasmallgroupofmutantsentersthispopulationplayingaccord-a a∑
a∈A
ing to a different profile mut (and persists using it during a time longer than the delays). If
we call ǫ ∈ (0,1) the size of the subpopulation of mutants after normalization, then the
population profile after mutation will be ǫ mut+(1−ǫ)x. After mutation, the average payoff of
non-mutants who are randomly matched to mutants is given by x f (mut), and the aver-∑ a a
a∈A
agepayoffofnon-mutantswill begivenby
ǫ x f (mut)+(1−ǫ) x f (x).a a a a∑ ∑
a∈A a∈A
Analogously,wecanconstructtheaveragepayoffofmutant
ǫ mut f (mut)+(1−ǫ) mut f (x).a a a a∑ ∑
a∈A a∈A
Apopulation x∈Δ(A) is anESSifforall mut = x,thereexistssome ǫ ∈ (0,1),whichmaymut
dependon mut,suchthatforallǫ∈ (0,ǫ )mut
ǫ mut f (mut)+(1−ǫ) mut f (x) (1.1)∑ a a ∑ a a
a∈A a∈A
< ǫ x f (mut)+(1−ǫ) x f (x)∑ a a ∑ a a
a∈A a∈A
That is, x is ESS if, after mutation, non-mutants are more successful than mutants, in which
casemutantscannotinvadeandwilleventuallygetextinct. Thenumberǫ iscalledinvasionmut
barrier See Weibull (1995). It is the maximum rate of mutants against which s is resistant. If
x is an ESS then x is a Nash equilibrium. Equivalently x is an ESS if and only if it meets best
responseconditions:
mut f (x)≤ x f (x), ∀ mut, (1.2)∑ a a ∑ a a
a∈A a∈A
∀ mut = x, mut f (x) = x f (x)⇒ (1.3)∑ a a ∑ a a
a∈A a∈A
mut f (mut)< x f (mut) (1.4)a a a a∑ ∑
a∈A a∈A
Forpopulationgameswithnon-linearpayoffs(i.ewhen x−→ f (x)isnon-linearfunction),a
define the solution and evolutionary stability concepts as follows: A population profile x is an
equilibriumstateif
x f (x)≥ mut f (x), ∀ muta a a a∑ ∑
a∈A a∈A
5
667Chapter1. Introduction
Thisvariationalinequalityisequivalentto:
(∗)∀a∈A, x > 0 =⇒ f (x) = max f (x)a a b
b∈A
This last condition is sometimes referred to "Wardrop first principle" (233) of optimality and
canbeeasilyobtainedusingtheindifferenceconditionatmixedequilibria. Thecondition (∗)is
sometimes writtenintheform: supp(x)⊆ argmax f (x).a
a
We say that a population profile x = (x ) is evolutionarily stable if for each deviationa a∈A
strategy called "mutant strategy" mut = (mut ) = x, there exists some ǫ > 0 such thata a∈A mut
∀ǫ∈ (0,ǫ ),mut
(x −mut )f (ǫ mut+(1−ǫ)x)> 0. (1.5)∑ a a a
a∈A
The strategy x is a neutrally evolutionary stable state (NESS) if the above inequality is
nonstrict. If the inequality is non-strict and ǫ = 0 then the resulting inequality says that x is an
equilibriumstate. Thus,theESSnotion isstrongerthanNashequilibrium.
Apopulationprofile x∈Δ(A) isanunbeatablestateifforany mut = x,
(x −mut )f (ǫmut+(1−ǫ)x)> 0, ∀ǫ∈ (0,1) (1.6)∑ a a a
a∈A
Thatis, x is anunbeatablestate if,aftermutationofany size(itcanbeall thepopulation),
nonmutants are more successful than mutants. In other words, any mutants of any size cannot
invade the population. Note that an unbeatable state is an evolutionarily stable state, which
impliesneutrallystablestate,whichisanequilibriumoftheone-shotgamei.eifthepopulation
profile is at this state and no player has incentive to unilaterally change his/her action. The
following inclusion holds:
Δ ⊂Δ ⊂Δ ⊂Δ (1.7)Unbeatable state ESS Neutally stable Equilibrium state
Note that evolutionarily stable state and unbeatable state may not exists (see for example
the class of Rock-Paper-Scissor games (99; 90; 65; 234)). The following theorem gives another
necessary and sufficient condition to be an ESS for evolutionary games with bilinear payoff
functions. Aproofcanbefoundin(94).
tTheorem 1.0.0.1. Let q be a symmetric (Nash) equilibrium for the matrix game with payoffs (F,F )
twhere F isthetranspositionmatrixof F = (F(i,j) ) and BRP(q)bethepurebestresponseto qi.ei,j
( )
BRP(q) = j| F(j,k)q = max F(l,k)q .∑ k ∑ k
lk k
Defineq¯as
q if j∈ BRP(q)jq¯ =j
0 otherwise
˜Let F thesubmatrixobtainedfrom F bytakingonlytheindexi,j∈ BRP(q).Thenqisanevolutionarily
stablestrategyifandonlyif
˜(p −q¯ ) F (p −q¯ )< 0∑ k k ∑ k,j j j
k∈BRP(q) j∈BRP(q)
forall p = q.
6
666Notethatthelastconditionisequivalentto
˜∀y∈ Y, y y F < 0∑ k j k,j
k,j∈BRP(q)
where  
 
|BRP(q)|Y := z∈R \{0}, z = 0, andq¯ = 0 =⇒ z ≥ 0∑ j j j
 
j∈BRP(q)
and|BRP(q)|isthecardinalofthefiniteset BRP(q).
ESSisanimportantrefinementofNashequilibriaasshowninthefollowing example.
Example
Consider the following matrix game with two players. Each has one block of strategies 1 nd
one pure strategy 2. The block contains at least two strategies. The corresponding payoffs are
giveninthetabularwheretheplayerIchooses arowr1(theblock )or r2andplayerIIchooses
acolumn c1(block)or c2.
PlayerII
c1 c2
r1 min(α,β),min(α,β) min(α,β),min(α,β)
r2 min(α,β),min(α,β) max(α,β),max(α,β)
where α,β ∈ R. The game has an infinity of Nash equilibria: (i) one of the player chooses
thefirststrategy(intheblock)andthesecondanarbitrarystrategy,(ii)Bothplayerschoosethe
secondstrategy. ButthegamehasonlyoneESS(thesecondstrategy). Anallocationofpayoffsis
saidParetooptimaliftheoutcomecannotbeimproveduponwithouthurtingatleastoneplayer.
In this case the ESS is also Pareto optimal because the payoff obtained at ESS is the maximum
payoffthateachplayercanhave.
Whentheblockhasonlytwopureactions,thegamebecomesthefollowing: Eachplayerhas
threestrategies 1,2or 3. The corresponding payoffsaregiveninthe tabularwherethe player I
chooses arowr1,r2orr3andplayerIIchoosesacolumnc1,c2or c3.
c1 c2 c3
r1 min(α,β),min(α,β) min(α,β),min(α,β) min(α,β),min(α,β)
r2 min(α,β),min(α,β) min(α,β),min(α,β) min(α,β),min(α,β)
r3 min(α,β),min(α,β) min(α,β),min(α,β) max(α,β),max(α,β)
ESSisnotunbeatable
We ask the following question: What happens when the size of mutants is greater than the
invasion barrier of an ESS? To answer to question, we use the unbeatable strategy, a concept
definedbyHamilton(1967),asapopulationprofilewhichisresilienttoanydeviantstrategyof
anysize. AnunbeatablestrategyisalwaysanESS,thoughanESSisnotnecessarilyunbeatable,
as it may be beaten by large migrations into the population. The following example illustrates
asituationwhereESSisnotunbeatable
7
PlayerI

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.