Average complexity of the Best Response Algorithm in Potential Games

Session : PJC-1 / Prix Jeune Chercheur
Mercredi 10 février 11:00 - 12:40 Salle : Amphi-CI
Bruno Gaujal et Stephane Durand

In a potential game with $N$ players and action space per player of size $A$, we show that the worst case complexity (number of moves) is $N A^{N-1}$, while the average complexity does not depend on $A$ and equals $log(N) + e^gamma + O(1/N)$. We also show that the average number of comparisons performed by the algorithm is $ e^gamma (A-1)(N-1) + O(A)$, We believe that this result qualifies the Best Response Algorithm as a very efficient distributed algorithm to compute Nash Equilibria.

Mots clés : Potential Games, Best Response, Average Complexity