Complexité et optimalité de l’algorithme de meilleure réponse dans les jeux de potentiel randomisés

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 finitepotential games. Our approach is based on a Markov chain model of BRAand a coupling technique that transform the average execution time of thisdiscrete algorithm into the solution of an ordinary differential equation.In a potential game with N players and A strategies per player, we show thatthe worst case complexity of BRA (number of moves) is exactly N A^(N-1), while itsaverage complexity over random potential games is equal to e^gamma N + O(N), wheregamma is the Euler constant.We also show that the effective number of states visited by BRA isequal to \log N + c + O(1/N) (with c < e^\gamma), on average.Finally, weshow that BRA computes a pure Nash Equilibriumfaster (in the strong stochastic order sense) than any local search algorithmover random potential games.Dans cet article, nous calculons le temps d’exécution en moyenne et en pire cas de l’algorithme de meilleure réponse (AMR) pour calculer un équilibre de Nash pur dans les jeux de potentiel finis. Notre approche utilise une chaîne de Markov pour modéliser le comportement de AMR et un couplage qui transforme le temps d’exécution de AMR en la solution d’une équation différentielle. Pour un jeu de potentiel avec N joueurs et A stratégies par joueur, le nombre d’itérations de AMR est exactement N A^(N-1), dans le pire cas et e^gamma N + O(N) dans le cas moyen, où est la constante d’Euler. Nous montrons aussi que le nombre de changements d’état est \log N + c + O(1/N) (with c < e^\gamma), en moyenne. Finalement, nous montrons aussi que AMR calcule un équilibre de Nash plus vite que tout algorithme de recherche local, pour l’ordre stochastique fort