# A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights

arXiv: https://arxiv.org/abs/2405.07224 · HTML: https://mlsanity.com/paper/2405.07224/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 85 references that are in the map.
- First posted on arXiv 12 May 2024.

## Builds on (most cited first, 17 of 17)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Riemannian game dynamics](https://mlsanity.com/paper/1603.09173/) (2016)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [A continuous-time approach to online optimization](https://mlsanity.com/paper/1401.6956/) (2014)
- [Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions](https://mlsanity.com/paper/2008.00540/) (2020)
- [On the robustness of learning in games with stochastically perturbed payoff observations](https://mlsanity.com/paper/1412.6565/) (2014)
- [Strategic Decompositions of Normal Form Games: Zero-sum Games and Potential Games](https://mlsanity.com/paper/1602.06648/) (2016)
- [Decomposition of games: some strategic considerations](https://mlsanity.com/paper/1901.06048/) (2019)
- [From Darwin to Poincar'e and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory](https://mlsanity.com/paper/1910.01334/) (2019)
- [Inertial game dynamics and applications to constrained optimization](https://mlsanity.com/paper/1305.0967/) (2013)
- [A Note On Orthogonal Decomposition of Finite Games](https://mlsanity.com/paper/1905.08112/) (2019)

## Built on by (most cited first, 4 of 4)

- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [The impact of uncertainty on regularized learning in games](https://mlsanity.com/paper/2506.13286/) (2025)
- [Nested replicator dynamics, nested logit choice, and similarity-based learning](https://mlsanity.com/paper/2407.17815/) (2024)
- [On the Decomposition of Differential Game](https://mlsanity.com/paper/2411.03802/) (2024)

## Abstract (arXiv)

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.