Stéphane Durand - Analyse de la dynamique de meilleure réponse dans les jeux de potentiel

09:30
Mardi
11
Déc
2018
  • Soutenance de thèse
Intervenant : 
Stéphane Durand
Équipes : 

 

Thèse co-encadrée par Bruno GAUJAL et Federica GARIN.
Thèse préparée au sein des laboratoires LIG et Gipsa-lab et financée par PERSYVAL-lab.

Lieu de soutenance de la thèse :

Salle Mont Blanc, GIPSA-lab, 11 rue des Mathématiques, St. Martin d'Hères

 

Membres du jury :

  • Giacomo Como, rapporteur,  associate Professor, Politecnico di Torino et Lund University
  • Jean Mairesse, rapporteur, directeur de Recherche CNRS, ESIEE
  • Olivier Brun, examinateur, directeur de recherche, CNRS, LAAS
  • Johanne Cohen, examinatrice, directrice de recherche, CNRS, LRI
  • Denis Trystram, examinateur, Professeur, Université Grenoble Alpes, LIG
  • Federica Garin, co-encadrante de thèse, chargée de recherche, Inria, Gipsa-Lab
  • Bruno Gaujal, co-directeur de thèse, directeur de recherche, Inria, LIG

Dans le contexte de la théorie des jeux, les équilibres de Nash, ie les états dans lesquels aucun joueur ne peut augmenter son utilité en changeant sa stratégie unilatéralement, sont une des formes principales de solutions des jeux. 
Ils sont les états les plus probables rencontrés lors de l’évolution des systèmes, des points de stabilité, et sont l'objet de nombreuse propriétés utiles (le prix de l'anarchie bornant la distance à un optimum du jeu, par exemple). 
La classe des jeux de potentiel est une large sous classe des jeux incluant entre autre tous les jeux de congestions, et permettant de modéliser un grand nombre de problèmes.  
Dans cette classe, il est difficile de trouver un équilibre de Nash: ce problème est PLS -complet, PLS étant une classe de complexité située entre P et NP. 
La dynamique de meilleure réponse, un algorithme glouton assez simple utilisé initialement comme outil de preuve pour montrer l'existence d'équilibre de Nash dans tous jeux, admet une complexité en pire cas exponentielle en e nombre de joueurs. 
En conséquence, cette dynamique n'est pas considérée un outil efficace pour obtenir un équilibre. 
Dans cette thèse, nous allons montrer que cet algorithme est efficace et robuste, selon le critère de l'analyse en moyenne. 
Dans le cas le plus simple, on obtient une borne linéaire sur le temps moyen avant convergence, a l'aide d'une approximation par une chaîne de Markov qui peut être résolue analytiquement. 
Cette approche montre que la dynamique de meilleure réponse reste efficace pour des conditions d'utilisation beaucoup plus générales. 
Cela inclus les systèmes distribués (des joueurs indépendants, chacun ayant peu de connaissances sur les états des autres) avec une borne en O(n log n), ainsi que les systèmes dans lesquels les joueurs ne connaissent pas leurs utilités avec une borne du même ordre. 
Cette approche montre également comment profiter d'une structure de type réseau pour obtenir une complexité fonction du nombre de voisins au lieu du nombre de joueurs.