Best Response Algorithms for Random Network Games

Stéphane Durand 1, 2 Federica Garin 1 Bruno Gaujal 2
1 NECS - Networked Controlled Systems
Inria Grenoble - Rhône-Alpes, GIPSA-DA - Département Automatique
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Résumé : 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.}
Type de document :
Rapport
[Research Report] RR-9066, Inria; Université Grenoble - Alpes; Gipsa-lab; Persival. 2017
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01522919
Contributeur : Stephane Durand <>
Soumis le : mercredi 17 mai 2017 - 10:00:45
Dernière modification le : mercredi 11 avril 2018 - 01:59:17

Fichier

networkGameRR (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01522919, version 1

Citation

Stéphane Durand, Federica Garin, Bruno Gaujal. Best Response Algorithms for Random Network Games. [Research Report] RR-9066, Inria; Université Grenoble - Alpes; Gipsa-lab; Persival. 2017. 〈hal-01522919〉

Partager

Métriques

Consultations de la notice

385

Téléchargements de fichiers

124