Inertial Game Dynamics and Applications to Constrained Optimization

Laraki, Rida ORCID: 0000-0002-4898-2424 and Mertikopoulos, Panayotis (2015) Inertial Game Dynamics and Applications to Constrained Optimization. SIAM Journal on Control and Optimization, 53 (5). pp. 3141-3170.

Text LarakiPanayotisSIAM2015.pdf - Published version Download (1MB)

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	game dynamics, folk theorem, Hessian-Riemannian metrics, learning, replicator dynamics, second-order dynamics, stability of equilibria, well-posedness
Depositing User:	Symplectic Admin
Date Deposited:	25 Jan 2018 07:50
Last Modified:	19 Jan 2023 06:42
DOI:	10.1137/130920253
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3016770