Learning Equilibria in Games by Stochastic Distributed Algorithms.

Abstract We consider a family of stochastic distributed dynamics to learn equilibria in games, that we prove to correspond to an Ordinary Differential Equation (ODE). We focus then on a class of stochastic dynamics where this ODE turns out to be related to multipopulation replicator dynamics. Using facts known about conver-gence of this ODE, we discuss the convergence of the initial stochastic dynamics. For general games, there might be non-convergence, but when the convergence of the ODE holds, considered stochastic algorithms converge towards Nash equilibria. For games admitting a multiaffine Lyapunov function, we prove that this Lyapunov function is a super-martingale over the stochastic dynamics and that the stochastic dynamics converge. This leads a way to provide bounds on their time of convergence by martingale arguments. This applies in particular for many classes of games con-sidered in literature, including several load balancing games and congestion games.