Jeux de population et applications dans les réseaux, Population games with networking applications

Hamidou Tembine

Description

Sous la direction de Eitan Altman, Rachid El-Azouzi
Thèse soutenue le 18 septembre 2009: Avignon
Ce manuscrit présente les fondements dynamiques des jeux de population avec un nombre variable de joueurs ainsi que leurs concepts de solutions et de stabilités. Nous introduisons d'abord les dynamiques de jeux avec retard et étudions leurs stabilités. Nous les appliquons aux réseaux filaires et aux réseaux sans fils. Ensuite nous nous intéressons aux aspects de mobilité et aux distributions spatiales des joueurs sur le réseau. Cela nous conduit à une nouvelle classe de dynamique de jeux à stratégies vectorielles avec des contraintes de migrations, appelée dynamique de jeux d'évolution avec migration. Nous dérivons de telles dynamiques pour les réseaux hybrides et appliquons aux problèmes de contrôle de puissance dans les réseaux hétérogènes, choix entre plusieurs technologies et migration entre plusieurs classes d'utilisateurs. Ensuite nous nous focalisons aux jeux stochastiques de population avec plusieurs classes de joueurs dans lesquels chaque joueur possède son propre état et fait face un vecteur qui évolue dans le temps. Des applications à la gestion d'énergie dans les réseaux sont présentées. Finalement, nous étudions une classe de jeux à champ moyen. Lorsque la taille de la population devient très grande, les asymptotiques du système conduisent à des dynamiques appelées dynamiques de jeux à champ moyen. Cette classe de dynamiques contient les dynamiques standard basées sur des révisions de stratégies. Nous utilisons ce modèle pour analyser les problèmes accès aléatoires à des ressources dans un environnement où les utilisateurs et les ressources sont spatialement distribuées. Nous établissons un lien entre les jeux à champ moyen et les jeux différentiels de population dans lesquels chaque joueur a son état individuel et optimise son paiement à long terme pendant son temps de séjour dans le système sous contraintes que le profil de population évolue selon une dynamique de jeux à champ moyen
-Jeux d'évolution
-Jeux de population
-Jeux stochastiques
-Jeux différentiels
-Champs moyens
-Jeux avec contraintes
-Réseaux sans fils
-Gestion d'énergie
-Allocation de ressources
his manuscript presents dynamic foundations of population games with variable number of players and their solutions and stability concepts. We first introduce delayed evolutionary game dynamics and study their stability. Applications to both wired and wireless networks are presented. We then introduce mobility and spatial aspects of players distribution into the network dynamics. This leads to a new class of game dynamics with multicomponent strategies and migration constraints called evolutionary game dynamics with migration. We derived such dynamics for hybrid systems such as power control in heterogenous networks, switching between technologies and migration between different classes of users. After that we focus on stochastic population games with multiple classes of players in which each player has its own state and facing to an evolving vector which represents the population profile. We use this model to analyze resource and energy constrained interactions in wireless networks. Finally, we present a class of mean field games. When taking the asymptotics of finite systems, we derive a new class of game dynamics called mean field game dynamics. This class contains the standard evolutionary game dynamics based on revision of pure actions. We apply this model to analyze spatial random access game and dynamic resource competition game with individual states. We establish a link betweenmean field games and differential population games inwhich each player optimizes its long-term objective during its sojourn time in the system subject to the constraint that the population profile evolves according to some mean field game dynamics
-Evolutionary games
-Population games
-Stochastic games
-Differential games
-Mean field games
-Constrained games
-Wireless networks
-Energy management
-Resource allocation
Source: http://www.theses.fr/2009AVIG0168/document

Sujets

• Réseau sans fil
• Allocation de ressources

Informations

• Publié par: Thesee
• Nombre de lectures: 23
• Langue: English
• 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’Avignon
tel-00451970, version 1 - 1 Feb 2010Contents
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
ii
tel-00451970, version 1 - 1 Feb 20103.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
iii
tel-00451970, version 1 - 1 Feb 2010Contents
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .