Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games

Abstract

We establish that algorithmic experiments in zero-sum games "fail miserably" to confirm the unique, sharp prediction of maxmin equilibration. Contradicting nearly a century of economic thought that treats zero-sum games nearly axiomatically as the exemplar symbol of economic stability, we prove that no meaningful prediction can be made about the day-to-day behavior of online learning dynamics in zero-sum games. Concretely, Multiplicative Weights Updates (MWU) with constant step-size is Lyapunov chaotic in the dual (payoff) space. Simply put, let's assume that an observer asks the agents playing Matching-Pennies whether they prefer Heads or Tails (and by how much in terms of aggregate payoff so far). The range of possible answers consistent with any arbitrary small set of initial conditions blows up exponentially with time everywhere in the payoff space. This result is robust both algorithmically as well as game theoretically: 1) Algorithmic robustness: Chaos is robust to agents using any of a general sub-family of Follow-the-Regularized-Leader (FTRL) algorithms, the well known regret-minimizing dynamics, even when agents mix-and-match dynamics, use different or slowly decreasing step-sizes. 2) Game theoretic robustness: Chaos is robust to all affine variants of zero-sum games (strictly competitive games), network variants with arbitrary large number of agents and even to competitive settings beyond these. Our result is in stark contrast with the time-average convergence of online learning to (approximate) Nash equilibrium, a result widely reported as "(weak) convergence to equilibrium".

arXiv comment25 pages, 1 figure, accepted to COLT 2019

References in corpus (3)

• The Unusual Effectiveness of Averaging in GAN Training
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Negative Momentum for Improved Game Dynamics

Cited by in corpus (8)

• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• No-regret learning and mixed Nash equilibria: They do not mix
• Near-Optimal No-Regret Learning in General Games
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Hedging in games: Faster convergence of external and swap regrets
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• The route to chaos in routing games: When is Price of Anarchy too optimistic?
• Extragradient with player sampling for faster Nash equilibrium finding