Directory Intranet
Chargement
DURAND Stťphane

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