Convergence of Mirror Descent Dynamics in the Routing Game

We consider a routing game played on a graph, in which different populations of drivers (or packet routers) iteratively make routing decisions and seek to minimize their delays. The Nash equilibria of the game are known to be the minimizers of a convex potential function, over the product of simplexes which represent the strategy spaces of the populations. We consider a class of population dynamics which only uses local loss information, and which can be interpreted as a mirror descent on the convex potential. We show that for vanishing, non-summable learning rates, mirror descent dynamics are guaranteed to converge to the set of Nash equilibria, and derive convergence rates as a function of the learning rate sequences of each population, and illustrate these results on numerical examples.