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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01522919
Contributor : Stephane Durand <>
Submitted on : Wednesday, May 17, 2017 - 10:00:45 AM
Last modification on : Friday, August 23, 2019 - 1:16:41 AM

File

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

Identifiers

  • HAL Id : hal-01522919, version 1

Citation

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⟩

Share

Metrics

Record views

485

Files downloads

5945