Dynamics, (min-max) optimization, and games

Résumé

This talk aims to survey the triple-point interface between optimization, game theory, and dynamical systems. We will begin by discussing how the ordinary differential equation (ODE) method of stochastic approximation can be used to analyze the trajectories of a wide array of stochastic first-order algorithms in non-convex minimization problems and games. The key notion here is that of an internally chain transitive (ICT) set: in minimization problems, ICT sets correspond to the problem's critical points, and we discuss a range of conditions guaranteeing convergence to critical points while avoiding unstable saddle points. Similar results can also be derived for min-max problems and games: unstable stationary points are avoided and stable Nash equilibria are attracting with probability $1$ (or with arbitrarily high probability in the local case). However, despite these encouraging results, the overall situation can be considerably more involved: we show that the sequence of play may converge with arbitrarily high probability to lower-dimensional manifolds that are in no way unilaterally stable (or even stationary). "Spurious attractors" of this type can arise even in simple two-player zero-sum games with one-dimensional action sets and polynomial losses of degree 4, a fact which highlights the fundamental gap between minimization problems and games.