Complexity and Optimality of the Best Response Algorithm in Random Potential Games
Complexité et optimalité de l’algorithme de meilleure réponse dans les jeux de potentiel randomisés
Résumé
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.
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.
Origine : Fichiers produits par l'(les) auteur(s)