Complexity and Optimality of the Best Response Algorithm in Random Potential Games

Stéphane Durand 1, 2 Bruno Gaujal 2, 3
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 compute the worst-case and average execution time of the Best Response Algorithm (BRA) to compute a pure Nash equilibrium in finite potential games. Our approach is based on a Markov chain model of BRA and a coupling technique that transform the average execution time of this discrete algorithm into the solution of an ordinary differential equation. In a potential game with N players and A strategies per player, we show that the worst case complexity of BRA (number of moves) is exactly N A^(N-1), while its average complexity over random potential games is equal to e^gamma N + O(N), where gamma is the Euler constant. We also show that the effective number of states visited by BRA is equal to \log N + c + O(1/N) (with c < e^\gamma), on average. Finally, we show that BRA computes a pure Nash Equilibrium faster (in the strong stochastic order sense) than any local search algorithm over random potential games.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/hal-01330805
Contributor : Stephane Durand <>
Submitted on : Tuesday, July 12, 2016 - 1:52:30 PM
Last modification on : Tuesday, February 26, 2019 - 1:20:27 AM

File

RR-8925v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01330805, version 2

Citation

Stéphane Durand, Bruno Gaujal. Complexity and Optimality of the Best Response Algorithm in Random Potential Games. [Research Report] RR-8925, Inria - Research Centre Grenoble – Rhône-Alpes; Grenoble 1 UGA - Université Grenoble Alpe. 2016, pp.30. ⟨hal-01330805v2⟩

Share

Metrics

Record views

829

Files downloads

239