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 [2016-2018] - Networked Controlled Systems
Inria Grenoble - Rhône-Alpes, GIPSA-DA - Département Automatique
2 POLARIS [2016-2019] - Performance analysis and optimization of LARge Infrastructures and Systems [2016-2019]
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 metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Federica Garin <>
Submitted on : Thursday, March 8, 2018 - 3:52:42 PM
Last modification on : Wednesday, October 7, 2020 - 11:02:03 AM
Long-term archiving on: : Saturday, June 9, 2018 - 2:59:04 PM


Files produced by the author(s)


  • HAL Id : hal-01726836, version 1


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⟩



Record views


Files downloads