Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01726836
Contributor : Federica Garin Connect in order to contact the contributor
Submitted on : Thursday, March 8, 2018 - 3:52:42 PM
Last modification on : Thursday, October 21, 2021 - 3:52:44 AM
Long-term archiving on: : 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. ECC 2018 - 16th European Control Conference, Jun 2018, Limassol, Cyprus. pp.1-6. ⟨hal-01726836⟩

Share

Metrics

Record views

491

Files downloads

678