Skip to Main content Skip to Navigation

Analysis of Best Response Dynamics in Potential Games

Abstract : In game theory, Nash equilibria, the states where no players can gain by unilaterally changing their strategy, are one of the main notions of solution of the games. nash equilibria are the most likely states at equilibrium, they are also stable and in many context they have properties guaranteeing being near the optimums. We focus on potential games, a subclass of the gameswhich include among other all congestion games and routing games. Even restricted on the class of potential games, finding a Nash equilibrium is difficult. This problem is in fact PLS-complete, which is a class between P and NP. Best response dynamics, are a greedy algorithm, which were first devised as a tool for proving existence of a Nash equilibrium. Their worst-case complexity is exponential with respect to the number of players. they were also though to need their players acting strictly one after the others to ensure convergence. as such they do not appears as an efficient algorithm for actually computing an equilibrium. However, in this thesis we will show that the condition to ensure convergence is more permissive than separates players, and that this algorithm is efficient when considered through average complexity: When averaging over the set of all potential games, we can obtain a linear bound on the basic version. In order to obtain this result, we apply a Markovian approximation allowing us to solve the system analytically. This approach also shows that the best response dynamics are robust, they stay efficient under much wider conditions of application. This include distributed system, with independent actors with little knowledge of each other, with a bound in O(n log n). It can also take into account instances where players do not know their utilities, getting a similar bound. This approach also shows how to benefit from a network structure on the game to get a complexity based on the number of neighbors of the players instead of the number of players.
Document type :
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Wednesday, September 30, 2020 - 4:08:08 PM
Last modification on : Wednesday, November 3, 2021 - 5:07:49 AM
Long-term archiving on: : Monday, January 4, 2021 - 8:44:07 AM


Version validated by the jury (STAR)


  • HAL Id : tel-02953991, version 1



Stéphane Durand. Analysis of Best Response Dynamics in Potential Games. Artificial Intelligence [cs.AI]. Université Grenoble Alpes, 2018. English. ⟨NNT : 2018GREAM096⟩. ⟨tel-02953991⟩



Record views


Files downloads