nucleation

LIT-1509: Open-ended Learning in Symmetric Zero-sum Games

2 min read

Properties4
StatusActive — read in full 2026-10-24 (NOTE-1143) from arXiv v2 (13 May 2019, the authors' "ICML 2019, final version"); worth reading for one invariant and one reframing. The invariant: the value of the zero-sum game between two populations, which does not depend on the choice of Nash, ignores members that are behavioural mixtures of others, and cannot be positive for a population inside another's hull. The reframing: in a cyclic game an individual agent's performance means nothing, so progress is the growth of a population's gamescape. Its functional Hodge decomposition is right but is stated with a degenerate inner product, and it depends on a measure over agents. Experiments are two small resource-allocation games.
Tagsgame-theory, learning-theory, anthology-candidate
Cited as “paper” byNOTE-1143 — Balduzzi et al. — Open-ended learning in symmetric zero-sum games
Cited as “source” byTHEORY-940 — In a finite symmetric zero-sum game, successive Nash clusters are weakly ordered by relative population performance, and a strategy that beats every member of a population containing a whole cluster lies in a strictly earlier cluster, THEORY-944 — The value of the zero-sum game between two populations' evaluation matrices does not depend on which Nash equilibrium is used, is unchanged by adding agents that behave as mixtures of existing members, and is not positive for a population whose agents are all behavioural mixtures of the other's

Graph View

Balduzzi, Garnelo, Bachrach, Czarnecki, Pérolat, Jaderberg & Graepel (2019), Proceedings of the 36th International Conference on Machine Learning, PMLR 97: 434–443 — arXiv:1901.08106

Key takeaways

From the reading, NOTE-1143. Page numbers are the PDF’s.

  • Transitive plus cyclic, relative to a measure. Every antisymmetric φ(v, w) is grad(f) + ψ, with f the mean payoff against agents drawn from a chosen probability measure and ψ divergence-free (Theorem 1). The split is correct. The paper calls it orthogonal “with respect to the inner product on games”, but the form it states, ∫φ(v, w)ψ(v′, w′) over four independent variables, is zero for every pair of antisymmetric functions. The ordinary L² product makes the claim true.
  • Individuals stop meaning anything. “In a cyclic game, the performance of individual agents is meaningless” (p. 5). The paper measures populations instead.
  • A population invariant. The value of the zero-sum game between two populations does not depend on which Nash equilibrium is used. Members that behave as mixtures of others do not change it, and a population inside another’s hull cannot beat it (Propositions 2 and 5; THEORY-944).
  • Algorithms. Response to the Nash mixture (PSRO_N) strictly enlarges the gamescape while some agent beats the Nash, and stalls once the game’s Nash lies inside it. Response to the rectified Nash (PSRO_rN) trains each supported agent against what it beats or ties. In Blotto and differentiable Lotto it beats PSRO_N, PSRO_U and self-play on relative population performance.
  • Corrections. Proposition 5(ii) prints max f − max f for monotonic games where σ(max f − max f) is meant. Effective diversity depends on which Nash is used, and the definition does not fix one.

Why this is here

Filed 2026-10-24 for the record’s governance and cycles lines. The population value is a scoring invariant that, unlike Nash averaging (LIT-1508), needs no uniqueness and covers behavioural mixtures. Its monotonic-versus-transitive distinction is the record’s own ordinal-versus-cardinal one (CLAIM-434, TERM-077). It bears on CLAIM-451 and CASE-124 (NOTE-1143). It carries anthology-candidate because its algorithms are for training ML agents. It is filed for understanding, not as an instruction for practice.

Backlinks