these-boulogne

Informations

• Publié par: Ensoo
• Nombre de lectures: 22
• Langue: English

Extrait

µ ¶THESE DE DOCTORAT DE L’UNIVERSITE PARIS 6
¶ ¶Sp¶ecialit¶e : MATHEMATIQUES APPLIQUEES
pr¶esent¶ee par
Thomas BOULOGNE
pour obtenir le grade de
¶Docteur de l’UNIVERSITE PARIS 6
Jeux strat¶egiques non-atomiques
et
applications aux r¶eseaux
Soutenue le 15 d¶ecembre 2004 devant le jury compos¶e de :
MM. Eitan Altman Directeur
Guillaume Carlier Examinateur
Jean Fonlupt
St¶ephane Gaubert
Sylvain Sorin Directeur
Nicolas Vieille Rapporteur
Bernhard Von Stengel RappTable des matiµeres / Contents
Introduction 7
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
I Nonatomic strategic games 15
Notations 17
1 Two models of nonatomic games 19
1.1 The assumption of nonatomicity . . . . . . . . . . . . . . . . . . . . . 19
1.2 S-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.1 Payofi functions deflned on S£F . . . . . . . . . . . . . . . 20S
1.2.2 Payofi on S£co(S) . . . . . . . . . . . . . . 24
1.3 M-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4 Relations betweenS-games andM-games . . . . . . . . . . . . . . . 29
1.4.1 FromS-games toM-games . . . . . . . . . . . . . . . . . . . 30
1.4.2 FromM toS . . . . . . . . . . . . . . . . . . . 32
2 Approximation of large games by nonatomic games 37
2.1 S-games and ‚-convergence . . . . . . . . . . . . . . . . . . . . . . . 38
2.2 S and conv in distribution . . . . . . . . . . . . . . . . 45
2.3 M-games and weak convergence . . . . . . . . . . . . . . . . . . . . . 47
3 Extensions and variations 53
3.1 ofS-games . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Extension ofM . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3 Population games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4 Potential games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 Inflnite potential games . . . . . . . . . . . . . . . . . . . . . 61
3.4.2 Potential games as limits of flnite player games . . . . . . . . 62
4 Applications 69
4.1 Routing games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1.1 Nonatomic routing games . . . . . . . . . . . . . . . . . . . . 69
4.1.2 Approximation of Wardrop equilibria by Nash equilibria . . . 72
4.2 Crowding games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Large crowding games . . . . . . . . . . . . . . . . . . . . . . 75
iiiµiv TABLE DES MATIERES / CONTENTS
4.2.2 Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3 Evolutionary games . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.1 From Nash to Maynard Smith: difierent interpretations of
Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.2 Games with a single population . . . . . . . . . . . . . . . . . 79
4.3.3 Stability in games with n-populations . . . . . . . . . . . . . . 84
5 Equilibrium’s reflnement: stability 87
5.1 S-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Potential games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3 Stability based on a recursive process . . . . . . . . . . . . . . . . . . 94
Appendix 97
A Referenced theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
B Measurability conditions . . . . . . . . . . . . . . . . . . . . . . . . . 100
C Proof of Proposition 2.24 . . . . . . . . . . . . . . . . . . . . . . . . . 101
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Glossary of Symbols 107
List of deflnitions 109
II Network applications 113
6 Mixed equilibrium for multiclass routing games 115
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Mixed equilibrium (M.E.): model and assumptions . . . . . . . . . . 117
6.3 Existence of M.E. through variational inequalities . . . . . . . . . . . 119
6.4 of M.E.: a flxed point approach . . . . . . . . . . . . . . . 121
6.5 Uniqueness of M.E.: Rosen’s type condition . . . . . . . . . . . . . . 122
6.5.1 Su–cient condition for DSI . . . . . . . . . . . . . . . . . . . 126
6.6 Uniqueness of M.E.: linear costs . . . . . . . . . . . . . . . . . . . . . 127
6.7 of M.E.: positive ows. . . . . . . . . . . . . . . . . . . . 128
6.8 Uniqueness of M.E. for speciflc topologies . . . . . . . . . . . . . . . . 132
6.8.1 Parallel links . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.8.2 Load balancing with unidirectional links . . . . . . . . . . . . 135
6.8.3 Load with a communication bus . . . . . . . . . . . 135
6.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
A Constraints in general networks . . . . . . . . . . . . . . . . . 137
B Relation between a bidirectional link and a network of unidi-
rectional ones . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
C Proof of Lemma 6.8.2 . . . . . . . . . . . . . . . . . . . . . . . 138
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1417 OntheconvergencetoNashequilibriuminproblemsofdistributed
computing 145
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.2.1 Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.2.2 The Elementary Stepwise System . . . . . . . . . . . . . . . . 148
7.3 A network with two processors . . . . . . . . . . . . . . . . . . . . . . 148
7.4 Network with N users . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.4.1 Uniqueness of Nash equilibrium . . . . . . . . . . . . . . . . . 152
7.4.2 A network with N processors: uniqueness . . . . . . . . . . . 153
7.4.3 Convergence of ESS . . . . . . . . . . . . . . . . . . . . . . . . 153
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8 Competitive routing in multicast communications 159
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.3 Uniqueness of equilibrium: speciflc topologies . . . . . . . . . . . . . 166
8.3.1 A three nodes network . . . . . . . . . . . . . . . . . . . . . . 166
8.3.2 A four nodes network . . . . . . . . . . . . . . . . . . . . . . . 171
8.4 Uniqueness of equilibrium: general topology . . . . . . . . . . . . . . 174
8.4.1 Extended Wardrop equilibrium . . . . . . . . . . . . . . . . . 174
8.4.2 Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.5 Numerical example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.6 Multicast networks with duplication at the source . . . . . . . . . . . 178
8.7 Conclusion, discussion and further extensions . . . . . . . . . . . . . 182
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1826Introduction
La th¶eorie des jeux est l’¶etude de situations ouµ plusieurs individus interagissent.
Une interaction sp¶ecifle le comportement de chaque individu et donne aµ tous une
utilit¶e. Cette derniµere se mesure par une fonction r¶eelle, appel¶ee fonction d’utilit¶e
ou fonction de paiement, que tout individu est suppos¶e maximiser. Un individu est
appel¶e joueur et un comportement strat¶egie. Formellement : I est l’ensemble des
joueurs, S l’ensemble de strat¶egies du joueur i2 I et u : S = ƒ S !R est sai i i2I i
fonction de paiement. Le triplet (I;(S ) ;(u ) ) constitue un jeu (strat¶egique),i i2I i i2I
une interaction est d¶ecrite par un profll de strat¶egies s=(s ) 2S.i i2I
Un concept fondamental dans les jeux strat¶egiques est l’¶equilibre de Nash ; il
s’agit d’un profll de strat¶egies tel qu’aucune d¶eviation unilat¶erale ne soit profltable
au joueur d¶eviant. Explicitement, s = (s ;s ) est un ¶equilibre de Nash du jeuj ¡j
(I;(S ) ;(u ) ) si et seulement sii i2I i i2I
¡ ¢
0 0u (s))‚u s ;s ; 8j2I;s 2S :j j ¡j jj j
Lorque le mot ¶equilibre est employ¶e ci-aprµes, il doit s’interpr¶eter comme une varia-
tion de l’¶equilibre de Nash.
L’objet de cette thµese est double. D’une part il consiste en l’analyse de jeux
avec un continuum de joueurs ouµ la strat¶egie d’un de ceux-ci, quel qu’il soit, a une
in uence nulle sur la fonction de paiement de n’importe quel autre joueur. Ces jeux
sont appel¶es jeux non-atomiques.
L’usagedesjeuxpermetd’obtenirdesr¶esultatscommel’existence
d’¶equilibre lorsque les ensembles de strat¶egies sont flnis (autrement dit ¶equilibre en
strat¶egie pure, ce qui n’est g¶en¶eralement pas le cas pour les jeux avec un nombre
flni de joueurs) et d’utiliser des outils d’analyse fonctionnelle.
Cependant, une inflnit¶e de joueurs (a fortiori un continuum) ne se rencontre
pas \dans la r¶ealit¶e". Les jeux non-atomiques sont donc utilis¶es pour d¶ecrire des
interactionsavecungrandnombred’individusetouµlecomportementdequiconquea
une in uence n¶egligeable sur l