Distributed Best Response Algorithms for Potential 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
Abstract : In this paper we design and analyze distributed algorithms to compute a Nash equilibrium in potential games. Our algorithms are based on best-response dynamics, with suitable revision sequences (orders of play). We compute the average complexity over all potential games of best response dynamics under a random i.i.d. revision sequence, since it can be implemented in a distributed way using Poisson clocks. We obtain a distributed algorithm whose execution time is within a constant factor of the optimal centralized one. We then show how to take advantage of the structure of the interactions between players in a network game: non-interacting players can play simultaneously. This improves best response algorithm, both in the centralized and in the distributed case.
Type de document :
Communication dans un congrès
16th European Control Conference (ECC 2018), Jun 2018, Limassol, Cyprus. 2018
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-01726836
Contributeur : Federica Garin <>
Soumis le : jeudi 8 mars 2018 - 15:52:42
Dernière modification le : lundi 11 juin 2018 - 15:33:48
Document(s) archivé(s) le : samedi 9 juin 2018 - 14:59:04

Fichier

ECC18-Durand-Garin-Gaujal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01726836, version 1

Citation

Stéphane Durand, Federica Garin, Bruno Gaujal. Distributed Best Response Algorithms for Potential Games. 16th European Control Conference (ECC 2018), Jun 2018, Limassol, Cyprus. 2018. 〈hal-01726836〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

64