these-boulogne
185 Pages
English

these-boulogne

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

µ ¶THESE DE DOCTORAT DE L’UNIVERSITE PARIS 6¶ ¶Sp¶ecialit¶e : MATHEMATIQUES APPLIQUEESpr¶esent¶ee parThomas BOULOGNEpour obtenir le grade de¶Docteur de l’UNIVERSITE PARIS 6Jeux strat¶egiques non-atomiquesetapplications aux r¶eseauxSoutenue le 15 d¶ecembre 2004 devant le jury compos¶e de :MM. Eitan Altman DirecteurGuillaume Carlier ExaminateurJean FonluptSt¶ephane GaubertSylvain Sorin DirecteurNicolas Vieille RapporteurBernhard Von Stengel RappTable des matiµeres / ContentsIntroduction 7Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14I Nonatomic strategic games 15Notations 171 Two models of nonatomic games 191.1 The assumption of nonatomicity . . . . . . . . . . . . . . . . . . . . . 191.2 S-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.2.1 Payofi functions deflned on S£F . . . . . . . . . . . . . . . 20S1.2.2 Payofi on S£co(S) . . . . . . . . . . . . . . 241.3 M-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.4 Relations betweenS-games andM-games . . . . . . . . . . . . . . . 291.4.1 FromS-games toM-games . . . . . . . . . . . . . . . . . . . 301.4.2 FromM toS . . . . . . . . . . . . . . . . . . . 322 Approximation of large games by nonatomic games 372.1 S-games and ‚-convergence . . . . . . . . . . . . . . . . . . . . . . . 382.2 S and conv in distribution . . . . . . . . . . . . . . . . 452.3 M-games and weak convergence . . . . . . . . . . . ...

Subjects

Informations

Published by
Reads 22
Language English

µ ¶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 le paiement des autres. Nous appelons ces jeux grands
jeux.
Nous montrons que les jeux non-atomiques sont de bons modµeles pour analyser
les grands jeux. Ceci est ¶etabli en consid¶erant des suites de jeux avec un nombre
flni de joueurs, ouµ l’in uence d’un joueur s’evanouit lorsque le nombre de joueurs
augmente(dor¶enavant hypothµese d’¶evanescence). Puis, nous¶etudionsdiversesappli-
cations des jeux non-atomiques. Enfln, nous proposons un ra–nement de l’¶equilibre
que nous appelons stabilit¶e. Ceci constitue la premiµere partie de cet ouvrage.
78 INTRODUCTION
L’autre volet de ce manuscrit considµere des problµemes dans les domaines des
t¶el¶ecommunications et de l’Internet, autrement dit des r¶eseaux, dans une optique de
th¶eorie des jeux. Sont consid¶er¶es des modµeles ouµ un grand nombre de paquets (dans
le cadre du traflc routier, ceux-ci correspondent µa des v¶ehicules), mod¶elis¶e par un
continuum, doivent aller d’un point du r¶eseau aµ un autre. Pour ce faire les paquets
peuvent^etred¶elivr¶esviadifi¶erentschemins(routes)possibles. Toutcheminpr¶esente
un cout^ d¶ependant de sa fr¶equentation ou plus g¶en¶eralement de la r¶epartition des
paquets au travers des difi¶erents chemins. Les d¶ecisions de routage, c’est- a-dire le
choix des routes pour les paquets, peuvent se faire de trois maniµeres difi¶erentes :
(1) la d¶ecision centralis¶ee : une entit¶e organise la circulation des paquets afln de
minimiser le cout^ total de transport,
(2) la d¶ecision group¶ee : les paquets sont group¶es, chaque groupe ayant un d¶ecideur
qui essaie de minimiser le cout^ de \son" groupe,
(3) la d¶ecision individuelle : chaque paquet possµede son propre d¶ecideur qui choisit
son chemin afln de minimiser son cout.^
Le premier cas est un problµeme d’optimisation qui n’entre pas dans le cadre de la
th¶eorie des jeux et n’est donc pas consid¶er¶e ici. Les deux derniers cas sont des jeux
ouµ les joueurs sont les d¶ecideurs et les fonctions de paiement sont les oppos¶ees des
fonctions de cout.^ Le cas (2) correspond µa un jeu avec un petit nombre de joueurs
et le (3) µa un jeu non-atomique.
Nousproposonset¶etudionstoutd’abordunconceptd’¶equilibrepourdesmodµeles
danslesquelsd¶ecisiongroup¶eeetd¶ecisionindividuellecoexistent: certainspaquetsse
routentseul,d’autress’enremettentµauneentit¶esup¶erieure. Puisnous¶etablissonsla
convergencedesystµemesdynamiquesversdes¶equilibresdansdesjeuxµadeuxjoueurs
pr¶esentant une architecture de r¶eseaux sp¶eciflque. Finalement, nous mod¶elisons une
situation propre aux r¶eseaux de communications ouµ les paquets doivent aller d’une
origine aµ plusieurs destinations.
¶PARTIE 1 : JEUX STRATEGIQUES NON-ATOMIQUES
Le premier objectif de cette partie est de montrer que les modµeles de jeux non-
atomiques propos¶es par Schmeidler (1973) et Mas-Colell (1984) constituent de bons
outils pour analyser des situations de jeux avec un grand nombre de joueurs satis-
faisant l’hypothµese d’evanescence (grands jeux).
Un autre but est de pr¶esenter un cadre englobant diverses applications des jeux
non-atomiques, tels les jeux de routage, les jeux de foule et les jeux ¶evolutionnaires
et d’y ¶etendre un concept propre aµ ces derniers : la strat¶egieement
stable.
Chapitre 1 : Deux modµeles de jeux non-atomiques
Aprµes avoir d¶eflni la non-atomicit¶e, nous d¶ecrivons les jeux non-atomiques in-
troduits par Schmeidler (1973) (S-jeux) et ceux introduits par Mas-Colell (1984)
(M-jeux). Pour ces deux types de jeux, tous les joueurs ont le m^eme ensemble de
strat¶egies S, espace m¶etrique compact.
Un S-jeu est caract¶eris¶e par une fonction u qui associe aµ chaque joueur t 20
T = [0;1] (muni de la mesure de Lebesgue, ‚), une fonction de paiement u . Lat0INTRODUCTION 9
fonction u d¶epend de la strat¶egie de t et d’une fonction mesurable f associant µat 00
chaque joueur t2 T une strat¶egie s 2 S. Une f d¶ecrit une interaction ett
se nomme profll de strat¶egies.
Dans un M-jeu, les fonctions de paiement d¶ependent de la strat¶egie du joueur
concern¶eetdelar¶epartitiondesstrat¶egiesauseindelapopulation. Pluspr¶ecis¶ement,
unM-jeuestd¶ecritparuneprobabilit¶esurl’ensembledesfonctionsr¶eellescontinues
sur S£M(S), not¶e C(S£M(S)) (ouµM(X) est l’ensemble des probabilit¶es sur X,
muni de la topologie faible) et les interactions sont mod¶elis¶ees par des probabilit¶es
sur l’ensemble produit C(S£M(S))£S.
Losque les S-jeux et les M-jeux sont d¶eflnis sous les m^emes hypothµeses, nous
¶etablissons les liens les unissant. Une des hypothµeses pour les S-jeux est que la
fonction de paiement de tout joueur d¶epend d’un profll de strat¶egies f uniquement
¡1aµ travers sa distribution -ou mesure image- f[‚] =‚–f 2M(S) (le jeu est alors
dit anonyme). Nous montrons que
(i) la measure image u[‚] d’unS-jeu anonyme u est unM-jeu,
(ii) la (u;f)[‚] de u et d’un de ses ¶equilibres f est un ¶equilibre pour
leM-jeu u[‚].
R¶eciproquementnous¶etablissonslarepr¶esentationdesM-jeux(etdeleurs¶equili-
bres) par desS-jeux anonymes. Ce dernier r¶esultat est une application du th¶eorµeme
de repr¶esentation de Skorohod.
Chapitre 2 : Approximation des grands jeux par les jeux non-atomiques
Nous appelons suite ¶evanescente de jeux, une suite de jeux avec un nombre flni
dejoueurs(dor¶enavantjeuxflnis),tellequel’in uencedetoutjoueursurlepaiement
desautress’¶evanouitlorsquelenombredejoueursaugmente. Nousconsid¶eronstou-
jours des jeux flnis ouµ tous les joueurs ont le m^eme ensemble de strat¶egies S.
Il est montr¶e ici que les jeux non-atomiques constituent un cadre ad¶equat pour
analyser les grands jeux.
Pourcefaire, nouspr¶esentonstroisr¶esultatsd’approximationcorrespondantaux
trois formulations de jeux flnis suivantes.
1Forme adapt¶ee : ouµ l’ensemble des joueurs est plong¶e dans l’intervalle [0;1] = T.
nLes proflls de strat¶egies y sont des fonctions f adapt¶ees µa une certaine partitionT
nde T. Le jeu est alors repr¶esent¶e par une fonction u adapt¶ee µaT .
nForme quasi-normale : P = f1;:::;ng est l’ensemble des joueurs, un profll de
nstrat¶egies est une fonction de P dans S. Le jeu est d¶ecrit par une fonction qui
nassocie aµ chaque joueur i sa fonction de paiement u :S !R.i
Forme probabiliste : les fonctions de paiement sont d¶eflnies sur S£M(S), et le jeu
est donn¶e par une probabilit¶e atomique „ sur l’ensemble de ces fonctions.
Alaformeadapt¶ee,nousassocionsuneconvergence\uniforme",µalaformequasi-
normale,laconvergenceendistributionutilis¶eeparHildenbrand(1974)etµalaforme
probabiliste, la convergence faible des mesures. Les deux premiµeres approximations
concernent les S-jeux, la derniµere les M-jeux. Les r¶esultats obtenus sont du type
suivant.
1Etantdonn¶eeunepartitionmesurableT deT,unefonction’ayantpourdomaineded¶eflnition
T et constante sur chaque ¶el¶ement deT est appel¶ee adapt¶ee µa la partitionT.10 INTRODUCTION
nSoient une suite ¶evanescente de jeux G qui converge vers un jeu non-atomique
n nG et une suite d’interactions ’ de G qui converge vers une interaction ’ de G.
Alors
n n n(1) si’ estun¶equilibredeG ,pourunnombreinflniden,alors’ estun¶equilibre
de G et inversement,
n(2) si ’ est un ¶equilibre de G alors pour n assez grand ’ est \approximativement"
nun ¶equilibre de G .
Chapitre 3 : Extensions et variations
Cechapitrepr¶esentetoutd’aborddesr¶esultatssurl’extensiondesS-jeuxanony-
mes ¶etablis par Rath (1992) et Khan-Sun (2002), puis ¶etend lesM-jeux µa des situ-
ations ouµ
(i) l’ensemble des joueurs est partionn¶e en un nombre flni de populations, chaque
population ayant son propre ensemble de strat¶egies,
(ii) les fonctions de paiement d¶ependent des r¶epartitions des strat¶egies au sein de
chaque population.
Les jeux ainsi d¶eflnis sont appel¶es C-jeux. Nous montrons l’existence d’¶equilibre
pour les C-jeux de deux maniµeres difi¶erentes. La premiµere consiste en l’application
classique d’un th¶eorµeme de point-flxe µa une correspondance de meilleures r¶eponses
(ses points flxes sont des ¶equilibres). La seconde considµere une fonction allant de
l’ensembledesC-jeuxdansceluidesM-jeuxetmontrequ’ aun¶equilibred’un M-jeu
„ correspond un ¶equilibre du C-jeu dont „ est l’image par la fonction mentionn¶ee
ci-dessus.
Nous nous restreignons ensuite aµ une classe de C-jeux ouµ tous les joueurs d’une
m^eme population ont la m^eme fonction de paiement. Dans ces jeux, appel¶es jeux de
population, l’existence d’¶equilibre peut s’obtenir µa l’aide d’in¶egalit¶es variationnelles.
Comme il est montr¶e dans le chapitre 4, ces jeux englobent diverses applications des
jeux non-atomiques.
Finalement, nous pr¶esentons une sous-classe des jeux de population, les jeux de
potentiel introduits par Sandholm (2001). Ces jeux ont la propri¶et¶e de poss¶eder une
fonction, appel¶ee fonction de potentiel, dont les maxima sont des ¶equilibres du jeu
consid¶er¶e. Sandholm (2001) ¶etablit un r¶esultat d’approximation des jeux de poten-
tiel avec un nombre flni de joueurs par les jeux de potentiel avec un continuum de
joueurs. Nous montrons que ce r¶esultat est plus restrictif que les approximations
obtenues au chapitre 2.
Chapitre 4 : Applications des jeux non-atomiques
Ce chapitre est consacr¶e µa l’¶etude de trois types de jeux de population.
Les jeux de routage sont tout d’abord consid¶er¶es. Le contexte est celui d’un
traflc routier et un jeu mod¶elise des situations ouµ un grand nombre de v¶ehicules
doivent aller d’une origine µa une destination. Pour ce faire ils ont plusieurs routes
possibles et chacun d¶esire minimiser son temps de trajet, temps qui d¶epend de la
route choisie et de sa fr¶equentation. Nous sommes donc dans le cas de d¶ecision
individuelle d¶eflnie au d¶ebut de l’introduction. La solution d’¶equilibre dans ces jeux
remontent µa Wardrop (1952). Nous pr¶esentons un r¶esultat d’approximation des
¶equilibres des jeux de routage flnis (d¶ecision group¶ee) par l’¶equilibre de Wardrop du^