Generalized mirror descents with non-convex potential functions in atomic congestion games: Continuous time and discrete time

Abstract

When playing certain specific classes of no-regret algorithms such as multiplicative updates and replicator dynamics in atomic congestion games, some previous convergence analyses were done with the standard Rosenthal potential function in terms of mixed strategy profiles (i.e., probability distributions on atomic flows), which could be non-convex. In several other works, the convergence, when playing the mirror-descent algorithm (a more general family of no-regret algorithms including multiplicative updates, gradient descents, etc.), was guaranteed with a convex potential function in terms of nonatomic flows as an approximation of the Rosenthal one. The convexity of the potential function provides convenience for analysis. One may wonder if the convergence of mirror descents can still be guaranteed directly with the non-convex Rosenthal potential function. In this paper, we answer the question affirmatively for discrete-time generalized mirror descents with the smoothness property (similarly adopted in many previous works for congestion games and markets) and for continuous-time generalized mirror descents with the separability of regularization functions. (C) 2017 Elsevier B.V. All rights reserved.