Skip to yearly menu bar Skip to main content


Poster

A Geometric Decomposition of Games: Convergence vs. Recurrence under No-Regret Learning

Davide Legacci · Panayotis Mertikopoulos · Bary Pradelski


Abstract:

In view of the complexity of the dynamics of no-regret learning in games, we seek to decompose a game into simpler components where the day-to-day behavior of the dynamics - and, in particular, the dynamics of exponential / multiplicative weights schemes - is well understood. Our starting point for this is Helmholtz's theorem, which resolves a vector field into a potential and an incompressible component. However, the geometry of the dynamics is not well-aligned with the Euclidean underpinnings of Helmholtz's theorem, leading us to consider a Riemannian framework based on the so-called Shahshahani metric. Using this geometric construction, we introduce a class of incompressible games, and we establish the following surprising results: First, in addition to being volume-preserving, the dynamics in any incompressible game admit a constant of motion, which ultimately leads to Poincaré recurrence - that is, almost every trajectory of play comes arbitrarily close to its starting point infinitely often. Second, we establish a deep connection with a well-known strategic decomposition of games into a potential and harmonic component (where the players' objectives are aligned and anti-aligned respectively). Specifically, we show that a game is incompressible if and only if it is harmonic, showing in this way that no-regret learning in harmonic games leads to Poincaré recurrence, and resolving a long-standing question in the field.

Live content is unavailable. Log in and register to view live content