[J11] - Inertial game dynamics and applications to constrained optimization

R. Laraki and P. Mertikopoulos. SIAM Journal on Control and Optimization, vol. 53, no. 5, pp. 3141–3170, October 2015.

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 (multi-population) 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.

arXiv link: https://arxiv.org/abs/1305.0967

Nifty tech tag lists from Wouter Beeftink