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

Stéphane Durand (1, 2) , Bruno Gaujal (2)

1 NECS - Networked Controlled Systems
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems

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 γ N + O(N), where γ 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 γ), 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.

Domaines: Informatique et théorie des jeux [cs.GT]

Stéphane Durand, Bruno Gaujal. Complexity and Optimality of the Best Response Algorithm in Random Potential Games. SAGT 2016 - Symposium on Algorithmic Game Theory (SAGT) 2016, Sep 2016, Liverpool, United Kingdom. pp.40-51, ⟨10.1007/978-3-662-53354-3_4⟩. ⟨hal-01404643⟩