2024/05/12 by Davide Legacci, Panayotis Mertikopoulos, Legacci, Davide +3 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · #68Q32 #68T05 #91A26 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Primary 91A10 #secondary 91A68
paper · pdf · doi:10.48550/arxiv.2405.07224
openalex publication_date 2024/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In view of the complexity of the dynamics of learning in games, we seek to decompose a game into simpler components where the dynamics' long-run behavior is well understood. A natural starting point for this is Helmholtz's theorem, which decomposes a vector field into a potential and an incompressible component. However, the geometry of game dynamics - and, in particular, the dynamics of exponential / multiplicative weights (EW) schemes - is not compatible with the Euclidean underpinnings of Helmholtz's theorem. This leads us to consider a specific Riemannian framework based on the so-called Shahshahani metric, and introduce the class of incompressible games, for which we establish the following results: First, in addition to being volume-preserving, the continuous-time EW dynamics in incompressible games admit a constant of motion and are Poincaré recurrent - i.e., almost every trajectory of play comes arbitrarily close to its starting point infinitely often. Second, we establish a deep connection with a well-known decomposition of games into a potential and harmonic component (where the players' objectives are aligned and anti-aligned respectively): a game is incompressible if and only if it is harmonic, implying in turn that the EW dynamics lead to Poincaré recurrence in harmonic games.