Calendar

Dans cet exposé, nous calculons la complexité moyenne de l'algorithme de meilleure réponse dans des jeux de potentiel. Contrairement au cas le pire (complexité exponentielle), la complexité moyenne est linéaire en le nombre de joueurs. On montre aussi que l'algorithme de meilleure réponse est optimal parmi tous ceux qui reposent sur une information locale. Nous étudions aussi les versions distribuées de la dynamique de meilleure réponse. Nous montrons d’abord que la sélection du prochain joueur selon une suite IID donne un temps de convergence moyen à une constante multiplicative de celui d’une suite optimale. De plus, une telle suite IID peut être implémentée de manière distribuée nous permettant de proposer un algorithme distribué avec un coût en temps d’exécution global minimal. Ensuite nous montrons comment utiliser la structure des interactions entre joueurs pour, en permettant aux joueurs non associés d’agir simultanément, améliorer le temps d’exécution. Dans un contexte centralisé, les joueurs peuvent être groupés selon une coloration du graphe d’interaction permettant à la complexité d’être proportionnelle au nombre chromatique de ce graphe au lieu du nombre de joueurs. Enfin, cette structure peut aussi être exploitée dans le contexte distribué pour des algorithmes plus efficaces.