A geometric decomposition of finite games: Convergence vs recurrence under exponential weights
<|reference_start|>A geometric decomposition of finite games: Convergence vs recurrence under exponential weights: 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\'e 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\'e recurrence in harmonic games.<|reference_end|>
@article{legacci2024a,
    title={A geometric decomposition of finite games: Convergence vs. recurrence
  under exponential weights},
    author={Davide Legacci and Panayotis Mertikopoulos and Bary Pradelski},
    journal={arXiv preprint arXiv:2405.07224},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07224},
    primaryClass={cs.GT cs.LG math.OC}
}