# Chaos, Extremism and Optimism: Volume Analysis of Learning in Games

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

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

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games](https://mlsanity.com/paper/2106.03579/) (2021)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)
- [The Replicator Dynamic, Chain Components and the Response Graph](https://mlsanity.com/paper/2209.15230/) (2022)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures](https://mlsanity.com/paper/2106.02615/) (2021)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamic](https://mlsanity.com/paper/2502.08063/) (2025)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)
- [Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach](https://mlsanity.com/paper/2605.19392/) (2026)
- [Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos](https://mlsanity.com/paper/2607.21805/) (2026)

## Abstract (arXiv)

We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. Such analyses provide new insights into these game dynamical systems, which seem hard to achieve via the classical techniques within Computer Science and Machine Learning. The first step is to examine these dynamics not in their original space (simplex of actions) but in a dual space (aggregate payoff space of actions). The second step is to explore how the volume of a set of initial conditions evolves over time when it is pushed forward according to the algorithm. This is reminiscent of approaches in Evolutionary Game Theory where replicator dynamics, the continuous-time analogue of MWU, is known to always preserve volume in all games. Interestingly, when we examine discrete-time dynamics, both the choice of the game and the choice of the algorithm play a critical role. So whereas MWU expands volume in zero-sum games and is thus Lyapunov chaotic, we show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. However, we also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts. Using these tools, we prove two novel, rather negative properties of MWU in zero-sum games: (1) Extremism: even in games with unique fully mixed Nash equilibrium, the system recurrently gets stuck near pure-strategy profiles, despite them being clearly unstable from game theoretic perspective. (2) Unavoidability: given any set of good points (with your own interpretation of "good"), the system cannot avoid bad points indefinitely.