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.
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01726836
Contributor : Federica Garin <>
Submitted on : Thursday, March 8, 2018 - 3:52:42 PM
Last modification on : Tuesday, April 2, 2019 - 2:52:13 AM
Document(s) archivé(s) le : Saturday, June 9, 2018 - 2:59:04 PM

File

ECC18-Durand-Garin-Gaujal.pdf
Files produced by the author(s)

Identifiers

  • 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. pp.1-6. ⟨hal-01726836⟩

Share

Metrics

Record views

325

Files downloads

180