
Inertial Game Dynamics and Applications to Constrained Optimization
Laraki, Rida; Mertikopoulos, Panayotis (2015), Inertial Game Dynamics and Applications to Constrained Optimization, SIAM Journal on Control and Optimization, 53, 5, p. 3141-3170. 10.1137/130920253
View/ Open
Type
Article accepté pour publication ou publiéDate
2015Journal name
SIAM Journal on Control and OptimizationVolume
53Number
5Pages
3141-3170
Publication identifier
Metadata
Show full item recordAuthor(s)
Laraki, Rida
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mertikopoulos, Panayotis

Laboratoire d'Informatique de Grenoble [LIG]
Abstract (EN)
Aiming to provide a new class of game dynamics with good long-term convergence properties, we derive a second-order inertial system that builds on the widely studied “heavy ball with friction” optimization method. By exploiting a well-known link between the replicator dynamics and the Shahshahani geometry on the space of mixed strategies, the dynamics are stated in a Riemannian geometric framework where trajectories are accelerated by the players' unilateral payoff gradients and they slow down near Nash equilibria. Surprisingly (and in stark contrast to another second-order variant of the replicator dynamics), the inertial replicator dynamics are not well-posed; on the other hand, it is possible to obtain a well-posed system by endowing the mixed strategy space with a different Hessian--Riemannian (HR) metric structure, and we characterize those HR geometries that do so. In the single-agent version of the dynamics (corresponding to constrained optimization over simplex-like objects), we show that regular maximum points of smooth functions attract all nearby solution orbits with low initial speed. More generally, we establish an inertial variant of the so-called folk theorem of evolutionary game theory, and we show that strict equilibria are attracting in asymmetric (multipopulation) games, provided, of course, that the dynamics are well-posed. A similar asymptotic stability result is obtained for evolutionarily stable states in symmetric (single-population) games.Subjects / Keywords
Game dynamics; folk theorem; Hessian–Riemannian metrics; learning; replicator dynamics; second-order dynamics; stability of equilibria; well-posednessJEL
C79 - OtherRelated items
Showing items related by title and author.
-
Laraki, Rida; Mertikopoulos, Panayotis (2012) Article accepté pour publication ou publié
-
Hadikhanloo, Saeed; Laraki, Rida; Mertikopoulos, Panayotis; Sorin, Sylvain (2021) Document de travail / Working paper
-
Baudin, Lucas; Laraki, Rida (2022) Communication / Conférence
-
Laraki, Rida; Sorin, Sylvain (2015) Chapitre d'ouvrage
-
Benhamou, Eric; Atif, Jamal; Laraki, Rida (2018) Document de travail / Working paper