AltGDA method guarantees steady convergence in matrix game solutions
AltGDA Achieves Global $O(1/T)$ Ergodic Convergence in Matrix Games
Computer Science and Game Theory
Summary
Two-player zero-sum games, like rock-paper-scissors, can be solved by finding a balance where neither player benefits from changing their strategy. The authors show that a simple method called alternating gradient descent-ascent (AltGDA) reliably gets closer to this balance at a steady rate, no matter where it starts or the length of play. Their proof uses a new technique to track performance and confirms that averaging moves is necessary for steady progress. They also verified their result with formal computer checking to ensure accuracy.
What this means in practice
- •For algorithm designers: Use AltGDA knowing it has a guaranteed convergence rate for solving finite matrix games in constrained and unconstrained cases.
- •For financial modelers: Apply AltGDA for strategy optimization in competitive financial scenarios modeled as zero-sum games where reliable convergence speed is critical.
A theory result. No direct application yet.
Authors
Tianlong Nan, Garud Iyengar, Christian Kroer, Shuvomoy Das Gupta
Abstract
Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an $O(1/T)$ ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon $T$: the uniform averages of the AltGDA iterates satisfy an $O(1/T)$ duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an $O(1/T)$ rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.