Dynamique du jeu actif randomisée sur les jeux à somme nulle 

Télécharger le fichier pdf d’un mémoire de fin d’études

Dynamique du jeu ctif randomisee sur les jeux a somme nulle

Ce chapitre presente la dynamique du jeu ctif randomise qui converge rapidement pour les jeux matriciels a somme nulle a deux joueurs. La preuve de convergence rapide partage l’utilisation de l’approximation et l’utilisation d’un potentiel comme similarite avec celles expos dans les chapitres suivants. Elle a cependant des di erence notables : la solution recherchee dans les chapitres suivant est un equilibre pur, ce qui n’est pas le cas dans ce chapitre, car les jeux a somme nulle ne presentent pas toujours de solution en strategie pur. De plus, ce n’est pas le pro l des strategies jouees par les joueurs qui converge vers un equilibre mais la moyenne statistiques des strategies jouees.
La dynamique presentee converge en temps logarithmique dans le nombre de strategies et est une amelioration de la dynamique de jeu ctif. Cette amelioration est une application de la methode par mise a jour multiplicative des poids (MPM). Cette methode utilise la randomisation de maniere tres e cace. Il y a d’ailleurs une borne inferieure qui stipule qu’un algorithme deterministe ne peut pas ^etre aussi rapide.
La preuve de convergence rapide est tiree de [53].

Jeux matriciels a deux joueurs a somme nulle

Dans un jeu a deux joueurs a somme nulle, les joueurs sont des adversaires ; cela signi e que ce que gagne un joueur, l’autre le perd.
Ces jeux sont representables sous forme matricielle avec une seule matrice A = (ai;j)i n;j m avec n le nombre de strategies de I et m le nombre de strategies de II. Les fonctions d’utilite des joueurs sont de nies comme suit : pour tout i n et j m, uI (i; j) = ai;j et uII (i; j) = uI (i; j). On note u la fonction uI . On rappelle qu’une strategie mixte est un vecteur de probabilite sur un ensemble de strategies pures. Une strategie pure est une strategie mixte dont les coe cients sont des 0 et un 1. Si I utilise une strategie mixte I , et II utilise une strategie mixte II , alors u( I ; II ) = It A II .
On note M RI ( ) (resp. M RII ), une meilleure reponse du joueur I (resp. du joueur II) si le joueur I (resp. II) joue ; c’est-a-dire une strategie pure s qui maximise (resp. minimise) u(s; ) (resp. u( ; s)).

Solution des jeux a somme nulle

Von Neumann a demontr l’existence d’un pro l de strategies optimales (cette notion est equivalente aux equilibres de Nash pour les jeux a deux joueurs a somme nulle). Un pro l ( I ; II ) est constitue de strategies optimales si u(M RI ( II ); II ) u( I ; II ) u( I ; M RII ( I )).
La valeur du jeu est de nie comme l’utilite du joueur I sur un pro l de strategies optimales.

Dynamique du jeu ctif randomisee : une application de la methode de mise a jour multiplicative des poids

On presente dans cette section une version randomisee de la dynamique du jeu ctif due a Grigoriadis et Khachian [16] qui trouve un equilibre approche en O(log(n:m)) tours, avec n et m le nombre de strategies des deux joueurs. La complexit totale de l’algorithme est O((n + m):log(n:m)). Grigoriadis et Khachian ont d’ailleurs remarqu qu’il s’agissait la d’un cas ou l’utilisation de bits aleatoires est necessaire ; aucun algorithme deterministe ne peut trouver un equilibre approche en temps inferieur a (m:n).
L’idee est la suivante : plut^ot que jouer la meilleure reponse face a l’estimation, les joueurs jouent une meilleure reponse bruitee ; c’est-a-dire qu’ils tirent leur strategie en suivant une distribution qui met beaucoup de poids sur les bonnes strategies.
pi(t) . i0 pi0(t)
Cette meilleure reponse bruitee correspond a une application de la methode par mise a jour multiplicative de poids (Multiplicative Weight Update Method), que l’on notera MPM [17].

Probleme des experts et MPM

Considerons comme une illustration du probleme des experts le cas d’un parieur sur des courses de chevaux compulsif et ignare. Le parieur doit (il est compulsif) a chaque course decider sur quel cheval parier. Il n’a aucune connaissance des courses de chevaux. Cependant le parieur a acces a un ensemble d’experts qui avant chaque course lui proposent une decision. Le parieur decide a chaque course de suivre la decision proposee par un des experts. Apres chaque course, le parieur constate le vainqueur. Il peut constater combien il aurait gagne s’il avait suivi la decision proposee par un autre expert.
Le probleme des experts est representable par un couple < N; (ut)t=1:::T > avec :
{ N est un ensemble d’experts ;
{ ut : N ! [ 1; 1], est une fonction telle que ut(i) est l’utilite obtenue en suivant l’expert i
au temps t ;
Le probleme est en ligne, c’est-a-dire qu’a chaque tour t, le parieur doit choisir un expert a suivre sans conna^tre ut. Cependant, le parieur conna^t l’historique, c’est-a-dire la sequence des ut0 pour t0 < t.
La MPM determine de facon randomisee a chaque tour un expert a suivre. Avec cette methode, en un temps relativement court, le parieur gagnera autant que le meilleur expert.
L’algorithme fonctionne en attribuant a chaque tour t et a chaque expert i un poids note pi(t). A chaque tour, l’expert suivi est tire aleatoirement selon une distribution proportionnelle aux
poids des experts ; c’est a dire que i est choisi avec probabilite P
Apres chaque tour, l’algorithme met a jour les poids multiplicativement en fonction des performances des experts.
La mise a jour des poids La mise a jour depend d’un parametre reel > 0. Les experts commencent avec un poids initial egal a 1. Le poids est mise a jour selon la regle suivante : pi(t + 1) = pi(t):e ut(i).
Complexit des equilibres sur les jeux de congestion
Ce chapitre presente des resultats qui stipulent que les equilibres de Nash purs sur les jeux de congestion sont di ciles a calculer. Cette di culte s’exprime en etablissant que calculer un equilibre de Nash dans un jeu de congestion est un probleme complet pour la classe de complexit PLS. S’il n’existe pas d’algorithme qui calcule e cacement un equilibre de Nash, il n’y a pas non plus de dynamique raisonnable qui converge rapidement.
La section 3.1 revient sur le resultat de Fabrikant et all [18] qui relie le probleme du calcul d’un NEP dans un jeu de congestion et la classe PLS. La section 3.2 presente les deux approches utilisees dans la litterature pour decortiquer les parametres qui rendent le probleme di cile : determiner des sous-problemes resolubles en temps polynomial, et rechercher une solution approchee. Les resultats evoques dans ces sections portent sur les jeux de congestion positifs. La section 3.3 presente nos resultats qui etendent les precedents aux les jeux sans contrainte de signe [54].

PLS et NEP

La classe PLS : Polynomial Local Search

La di culte du probleme SAT (NP-complet) vient-elle uniquement du fait que l’on cherche un optimum global ? Un optimum local serait-il plus simple a trouver ? C’est en tentant de repondre a cette question que Johnson, Papadimitriou et Yannakakis [55] ont de ni la classe PLS. Un optimum local est une solution qui est optimale dans son voisinage.
La classe de complexit PLS contient les problemes de recherche d’optimum local pour lesquels le voisinage d’une solution peut ^etre explor e cacement. Il s’agit d’une sous-classe de TFNP, la famille des problemes de recherche dans NP pour lesquels il est garanti qu’il existe une solution. Bien que PLS soit incluse dans NP \coNP, il est globalement admis que cette classe n’est pas resoluble en temps polynomial.
Un probleme de recherche d’optimum local est de ni par un quadruplet
< I; F; (cI )I2I; (NI )I2I > avec :
{ I est un ensemble d’instances du probleme ;
{ F (I) pour I 2 I est l’ensemble des solutions faisables pour l’instance I ;
{ cI : F (I) ! Z est une fonction de co^ut calculable en temps polynomiale de nie sur F (I) ;
{ NI : F (I) ! 2F (I) est une fonction qui de nit le voisinage d’une solution dans F (I).
Soit : < I; F; (cI )I2I; (NI )I2I >, une solution s 2 F (I) est un minimum local de si pour toute solution s0 2 NI (s), cI (s) cI (s0).

La di culte d’un NEP dans un jeu de congestion

On expose la preuve de PLS-completude du calcul d’un NEP dans un jeu de congestion comme un exemple de PLS-reduction.
Theoreme 3.1 ([18]). Trouver un NEP dans un jeu de congestion est PLS-Complet
Demonstration. La preuve est obtenue par une reduction depuis le probleme 3NAE-SAT pondere(Not-All-Equal) dont la PLS-completude est prouvee par Scha er et Yannakakis [57].
3NAE-SAT ponder FLIP
{ Entree :
{ un ensemble de variables X ;
{ un ensemble C de 3NAE-clauses sur X. Une 3NAE-clause est determinee par un triplet de litteraux (x1; x2; x3). Elle est veri ee des lors qu’il existe un litteral parmi les trois qui n’a pas la m^eme valuation que les deux autres (c’est-a-dire, 2 litteraux a VRAI et 1 a FAUX,ou 2 a FAUX et un a VRAI) ;
{ pour chaque clause c dans C, un poids entier wc ;
{ Sortie : une valuation sur les variables telle que dans le voisinage par FLIP de cette valuation, la somme des poids des clauses non satisfaites ne diminue pas.
Chapitre 3. Complexit des equilibres dans les jeux de congestion 31
Veri cation que le calcul d’un NEP est dans PLS L’ensemble des solutions faisables est l’ensemble des pro ls. Le voisinage d’un pro l contient tous les pro ls 0 sur lesquels la strategie d’un seul joueur di ere par rapport a . En sortie, on recherche un pro l qui est un minimum local du potentiel de Rosenthal, ce qui est equivalent a un NEP. La procedure IN IT IALISE peut ^etre implementee en prenant pour chaque joueur la premiere strategie de son espace de strategies. La procedure AM ELIORE, peut ^etre implementee des lors que le nombre de strategies est borne polynomialement dans la taille de la description du jeu, en veri ant exhaustivement pour chaque joueur et chaque strategie si elle ameliore son co^ut.
La reduction La PLS-reduction construit a partir d’un ensemble de clauses un jeu de congestion pour lequel, si l’on dispose d’un NEP, on peut trouver une valuation qui est un minimum local.

Table des matières

1 Preliminaires : allocation de ressources et jeux 
1.1 Généralités sur les Jeux
1.1.1 Jeux sous forme stratégique
1.1.2 La représentation matricielle
1.1.3 Dynamiques
1.1.4 Dynamiques pour des jeux à information partielle
1.1.5 Efficacité des solutions
1.2 Jeux de congestion
1.2.1 Des jeux à n joueurs avec une représentation succincte
1.2.2 Existence d’un NEP et fonction de potentiel
1.3 Jeux d’appariement
1.3.1 Jeux d’appariement à liens asymétriques : jeux de suiveurs
1.3.2 Jeux à liens symétriques : les jeux de couplage
2 Dynamique du jeu actif randomisée sur les jeux à somme nulle 
2.1 Jeux matriciels à deux joueurs à somme nulle
2.1.1 Solution des jeux à somme nulle
2.1.2 La dynamique du jeu actif
2.2 Dynamique du jeu actif randomisée : une application de la méthode de mise
a jour multiplicative des poids
2.2.1 Problème des experts et MPM
2.2.2 Jeu actif randomisé : l’application aux jeux à somme nulle
Application du lemme
Conclusion
3 Complexité des équilibres sur les jeux de congestion
3.1 PLS et NEP
3.1.1 La classe PLS : Polynomial Local Search
3.1.2 La difficulté d’un NEP dans un jeu de congestion
3.2 Approfondir l’étude de la complexité du calcul d’un NEP dans un jeu de congestion
3.2.1 Restreindre la structure
3.2.2 Approcher la solution
3.3 Résultats sur les jeux sans contraintes de signes
4 Dynamiques sur les jeux de congestion 
4.1 Sur les jeux positifs
4.1.1 Dynamiques de Nash
4.1.2 Convergence rapide de la dynamique é-Nash
4.2 Convergence rapide sur les jeux négatifs
4.2.1 Avec des co^uts croissants
4.2.2 Sur les jeux à co^uts monotones
4.2.3 Résumé des résultats sur la complexité des NEP approchés
4.2.4 Question : jeux à co^uts sans contrainte de signe indépendants ?
5 Dynamiques sur les jeux d’appariement 
5.1 Dynamiques sur les jeux de suiveurs
5.1.1 Dynamique de Nash concurrente
5.1.2 Dynamiques avec diffusion
5.2 Dynamiques sur les jeux de couplage
5.2.1 Dynamiques sur les jeux de couplage à information compléte
5.2.2 Comment la vision limitée ralentit la convergence
5.2.3 Dynamiques avec exploration
Conclusion 
Bibliographie 

Télécharger le rapport complet