Vous êtes ici : GIPSA-lab > Formation > Thèses soutenues
DURAND Stphane

Analyse de la dynamique de meilleure réponse dans les jeux de potentiel

 

Directeur de thèse :     Federica GARIN

Co-directeur de thèse :     Federica GARIN

École doctorale : Mathématiques, sciences et technologies de l'information, informatique (MSTII)

Spécialité : Informatique

Structure de rattachement : Université Grenoble Alpes

Établissement d'origine : ENS Lyon

Financement(s) : Contrat doctoral ; contrat à durée déterminée

 

Date d'entrée en thèse : 01/10/2015

Date de soutenance : 11/12/2018

 

Composition 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

 

Résumé : Dans le context de la théorie des jeux, les équilibres de Nash, ie les états dans lesquels aucun joueur ne peut augmenter son utilitée 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'évolutions des systèmes, eds 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 modeliser 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 dinamique 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 consequence, cette dynamique n'est pas considérée un outil efficace pour obtenir un equilibre. Dans cette thèse, nous allons montrer que cet algorithme est efficace et robuste, selon le critere 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épendents, chacun ayant peu de connaissances sur les états des autres) avec une borne en O(n log n), ainsi que les systemes 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.


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31