Algorithme de meilleure réponse appliqué au jeux aléatoires sur réseau

In this paper we study distributed algorithms for computing a Nash Equilibrium in potential games.Our algorithms are based on best-response dynamics, with suitable revision sequences (orders of play).First, we show that random iid revision sequences have a convergence time within a constant factor from the optimal revision sequence, on average. Random iid revision sequences can be implemented in a distributed way, allowing us to propose a distributed algorithm, at minimal cost in terms of total execution time.Then we show how to take advantage of the structure of the interactions between players: Convergence time can be improved by letting non-interacting players play simultaneously. In a centralized setup, players can be grouped according to a coloring of the interaction graph so that the complexity scales with the chromatic number instead of the number of players. Finally this technique can also be exploited to design efficient distributed versions of the best response dynamics.Dans ce rapport, nous \'etudions les algorithmes distribu\'es pour calculer un \'equilibre de Nash dans des jeux de potentiel. Nos algorithmes s'appuient sur la dynamique de meilleure r\'eponse, avec des s\'equences de r\'evison (ordre de jeu) ad\'equates. Nous montrons d'abord que des s\'equences IID ont un temps de convergence moyen \`a une constante multiplicative de celui d'une s\'equence optimale. De plus, une s\'equence al\'eatoire peut \^etre impl\'ement\'ee de mani\`ere distribu\'ee nous permettant de proposer un algorithme distribu\'e avec un co\^ut en temps d'ex\'ecution global minimal. Ensuite nous montrons comment utiliser la structure des interactions entre joueurs pour, en permettant aux joueurs non associ\'es d'agir simultan\'ement, am\'eliorer le temps d'ex\'ecution. Dans un contexte centralis\'e, les joueurs peuvent \^etre group\'es selon une coloration du graphe d'interaction permettant \`a la complexit\'e d'\^etre proportionnelle au nombre chromatique de ce graphe au lieu du nombre de joueurs. Enfin, cette structure peut aussi \^etre exploit\'ee dans le contexte distribu\'e pour des algorithmes plus efficaces.