Distributed gradient methods to reach a Nash equilibrium in potential games
Vineeth S. Varma, Jomphop Veetaseveera, Romain Postoyan, Irinel‐Constantin Morărescu · 2021 60th IEEE Conference on Decision and Control (CDC) · 2021
We study multi-agent optimization problems described by ordinal potential games. The objective is to reach a Nash equilibrium (NE) in a distributed manner. It is well known that an asynchronous best response dynamics (ABRD) will always converge to a pure NE in this case. However, computing the exact best response at every step of the algorithm may be computationally heavy, if not impossible. Therefore, instead of computing the exact best response, we propose an algorithm that performs a "better response", which decreases the local cost rather than minimizing it. The agents perform a distributed asynchronous gradient descent algorithm, in which only a finite number of iterations of the gradient descent are performed by each player. We prove that this algorithm always converges to a NE and demonstrate via simulations that the computational time to reach the NE can be much shorter than with the classical ABRD. Taking into account the time required for each agent to communicate, the proposed algorithm is shown to also outperform a distributed synchronous gradient descent in simulations.