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

Yun Kuen Cheung, Georgios Piliouras

Abstract

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 by examining them in a dual payoff space and exploring how the volume of a set of initial conditions evolves over time. We demonstrate that whereas MWU expands volume in zero-sum games (leading to Lyapunov chaos), OMWU contracts volume, explaining its convergent behavior. However, we prove a "no-free-lunch" theorem: in coordination games, the roles are reversed. Finally, we prove that MWU in zero-sum games inevitably leads to "extremism," where players recurrently get stuck near pure-strategy profiles even when balanced mixed equilibria exist.

Introduction

In the development of multi-agent systems and Generative Adversarial Networks (GANs), iterative learning algorithms are essential for finding optimal strategies. However, the day-to-day behavior of these algorithms is notoriously difficult to predict; some converge to stable equilibria, while others cycle or diverge wildly. Traditional tools from Computer Science often fail to explain why these dynamics occur. This paper addresses this gap by applying tools from Dynamical Systems—specifically volume analysis—to understand the fundamental stability of Multiplicative Weights Updates (MWU) and its "optimistic" variant (OMWU).

Methodology: Volume Analysis in Dual Space

The authors employ two key analytical shifts to study game dynamics:

  1. Dual Space Analysis: Instead of looking at the "primal space" of action probabilities, they analyze the "dual space" of aggregate payoffs. This transformation makes the mathematical representation of the dynamics significantly cleaner.
  2. Volume Analysis: They track how a set of initial starting conditions (a "volume" in the dual space) evolves over time. If the volume expands, the system is Lyapunov chaotic—tiny changes in starting conditions lead to wildly different outcomes (the "butterfly effect"). If it contracts, the system tends toward stability.

Technically, they calculate the Jacobian matrix of the update rules and use Liouville’s theorem to determine if the volume integrand is greater than or less than one.

Key Insights: The No-Free-Lunch Theorem

The paper establishes a fundamental symmetry between game types and learning algorithms, summarized in the table below:

Summary of volume expansion (+) and contraction (-) for MWU and OMWU across different game types.

As shown, MWU expands volume (is chaotic) in zero-sum games but contracts it in coordination games. OMWU does the exact opposite: it is stable in zero-sum games but expands volume exponentially fast in coordination games. This suggests that no single algorithm is universally stable across all game environments.

Extremism and Unavoidability

In zero-sum games, MWU exhibits a property called "extremism." Even if the only fair equilibrium is to mix strategies (like in Rock-Paper-Scissors), the system will recurrently get stuck near "pure" strategies where players play one move almost exclusively for long periods. Furthermore, the authors formalize "unavoidability": if a region of "good" states is volume-expanding, the system must eventually leave it and hit "bad" states. In zero-sum games, MWU cannot avoid these undesirable points indefinitely.

Key Results

The theoretical analysis is supported by several key findings:

  • Zero-Sum Dynamics: MWU expands volume at a rate of $1 + \Omega(\epsilon^2)$, leading to chaos. In contrast, OMWU contracts volume, providing an alternative understanding for its known convergent behavior.
  • Coordination Dynamics: OMWU expands volume at a rate of $1 + \Omega(\epsilon^2 \delta^2 \alpha_1^2)$, proving it is chaotic in this setting, while MWU contracts volume.
  • Visual Evidence: The difference in behavior is stark when visualized. In zero-sum games, MWU dynamics resemble an expanding "tornado," while OMWU dynamics resemble a shrinking, stabilizing spiral.
Visualizing the dynamics: MWU in zero-sum games (left) shows volume expansion, while OMWU (right) shows volume contraction toward stability.

Conclusion and Future Work

This work provides a rigorous framework for understanding why popular learning algorithms succeed or fail in different game-theoretic contexts. While the current analysis focuses on two-player games, future research could extend these volume arguments to multi-player or graphical games. Additionally, investigating "general-sum" games—which combine elements of competition and cooperation—remains an important open question for the field.

Summary updated

Abstract

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.
BibTeX
@inproceedings{cheung2020chaos,
  author = {Yun Kuen Cheung and Georgios Piliouras},
  title = {{Chaos, Extremism and Optimism: Volume Analysis of Learning in Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=WgDaFW4dfQn},
}
Figure