A Geometric Decomposition of Finite Games: Convergence vs. Recurrence under Exponential Weights
Authors: Davide Legacci, Panayotis Mertikopoulos, Bary Pradelski
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 volumepreserving, 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. |
| Researcher Affiliation | Academia | 1Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France 2CNRS, Maison Française d Oxford, 2 10 Norham Road, Oxford, OX2 6SE, United Kingdom. |
| Pseudocode | No | The paper is theoretical and does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository. |
| Open Datasets | No | This is a theoretical paper that does not conduct experiments with datasets, thus no training data information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve experimental data, therefore no dataset split information (e.g., training, validation, test) is provided. |
| Hardware Specification | No | This is a theoretical paper and does not describe any computational experiments or hardware specifications used. |
| Software Dependencies | No | This is a theoretical paper and does not list any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup, hyperparameters, or training settings. |