Skip to Main content Skip to Navigation

Best Response Algorithms for Random Network 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 study distributed algorithms for computing a Nash Equilibrium in potential games. Our algorithms are based on best-response dynamics, with suitable revision sequences (orders of play). First, we show that random iid revision sequences have a convergence time within a constant factor from the optimal revision sequence, on average. Random iid revision sequences can be implemented in a distributed way, allowing us to propose a distributed algorithm, at minimal cost in terms of total execution time. Then we show how to take advantage of the structure of the interactions between players: Convergence time can be improved by letting non-interacting players play simultaneously. In a centralized setup, players can be grouped according to a coloring of the interaction graph so that the complexity scales with the chromatic number instead of the number of players. Finally this technique can also be exploited to design efficient distributed versions of the best response dynamics.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Stephane Durand Connect in order to contact the contributor
Submitted on : Wednesday, May 17, 2017 - 10:00:45 AM
Last modification on : Wednesday, November 3, 2021 - 6:45:35 AM


networkGameRR (1).pdf
Files produced by the author(s)


  • HAL Id : hal-01522919, version 1


Stéphane Durand, Federica Garin, Bruno Gaujal. Best Response Algorithms for Random Network Games. [Research Report] RR-9066, Inria; Université Grenoble - Alpes; Gipsa-lab; Persival. 2017. ⟨hal-01522919⟩



Record views


Files downloads