General Revision Protocols in Best Response Algorithms for Potential Games

Pierre Coucheney 1 Stéphane Durand 2 Bruno Gaujal 3, 4 Corinne Touati 5, 4
1 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation
2 ENS Lyon - École normale supérieure - Lyon
3 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 Laboratoire d'Informatique de Grenoble
5 Inria Grenoble - Rhône-Alpes
Abstract : In this paper, we characterize the revision sets in different variants of the best response algorithm that guarantee convergence to pure Nash Equilibria in potential games. We prove that if the revision protocol is separable (to be defined in the paper), then the greedy version as well as smoothed versions of the algorithm converge to pure Nash equilibria. If the revision protocol is not separable, then convergence to Nash Equilibria may fail in both cases. For smoothed best response, we further show convergence to Nash Equilibria with optimal potential when players can only play one by one. Again this may fail as soon as simultaneous play is allowed, unless the number of players is two. We also provide several examples/counter-examples testing the domain of validity of these results.
Keywords : Potential Games Best Response Logit Dynamics
Type de document :
Communication dans un congrès
IEEE Explore. Netwok Games, Control and OPtimization (NetGCoop), Oct 2014, Trento, Italy. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01085077
Contributeur : Bruno Gaujal <>
Soumis le : jeudi 20 novembre 2014 - 16:58:43
Dernière modification le : jeudi 9 février 2017 - 15:41:50
Document(s) archivé(s) le : vendredi 14 avril 2017 - 19:56:58

Fichier

netGcoopCameraReady.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01085077, version 1

Collections

ENS-LYON | INRIA | LIG | PRISM | UVSQ | UGA | LIG_SRCPR

Citation

Pierre Coucheney, Stéphane Durand, Bruno Gaujal, Corinne Touati. General Revision Protocols in Best Response Algorithms for Potential Games. IEEE Explore. Netwok Games, Control and OPtimization (NetGCoop), Oct 2014, Trento, Italy. 2014. <hal-01085077>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

345

Téléchargements du document

202

Contact | Consulter le Guide UGA


Logo de l'INPG Logo de l'INPG Logo de l'INRIA Logo de l'USMB Logo du CEA Logo de l'IEPG Logo de l'ENSAG