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

Philippe Michelon

Description

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

Sujets

• Tomalá
• Gaubert
• Antipolis
• Bernhard
• École polytechnique

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 septembre 2009
• Nombre de lectures: 43
• Poids de l'ouvrage: 3 Mo

Extrait

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 Instantaneo