Summary
The paper shows that understanding simple two-player zero-sum games, called scalar games, is enough to predict how more complex network zero-sum games behave when using gradient-based learning. If a learning rule works well for scalar games with certain size limits, it will also work for larger network games bounded by those same limits. This means studying these simpler games can tell us about convergence and speed of learning in more complicated games. The authors use a mathematical technique to break down complex games into basic parts that behave like scalar games, simplifying analysis and design of learning methods.
What this means in practice
- •For machine learning engineers: Simplify convergence checks in multi-agent training by analyzing only scalar game cases, reducing complexity when designing network game learning algorithms.
- •For ai system testers: Create worst-case scenario tests for gradient-based training methods by focusing on scalar game modes rather than full network games.
A theory result. No direct application yet.
Abstract
We show that, for a broad class of gradient-based learning rules, scalar zero-sum games form a complete test family for convergence in unconstrained network zero-sum games. Specifically, suppose a learning rule achieves last-iterate or time-average convergence on every scalar game of magnitude $a$ whenever $η\leq f(a)$, where $f$ is nonincreasing. Then the same guarantee holds on an arbitrary network zero-sum game with stacked game operator $\mathbf{G}$ whenever $η\leq f(\lVert\mathbf{G}\rVert_2)$. More generally, finite-time rate guarantees transfer mode by mode: the network response is bounded by the largest response of its scalar canonical games, and under compatible linear initialization conventions the worst-case finite-time network response is exactly the largest scalar canonical rate. Thus, understanding the learning dynamics on scalar games is sufficient to characterize universal convergence and worst-case rates over the corresponding class of network games. The result follows from the classical planar decomposition of real skew-symmetric game operators. Related mode-wise reasoning has appeared implicitly in spectral analyses of particular learning algorithms and in prior work using these decompositions for game representation and visualization; here we isolate the resulting transfer principle for gradient-based learning. We discuss implications for simplifying convergence analysis, time-average guarantees, low-dimensional geometric arguments, accelerated-method design, and worst-case numerical testing.