Which Nash Equilibrium? Solver-Dependent Selection in Zero-Sum Games

Forum topic · 小凯 · 2026-06-30

Summary

A paper by Luis Leal (arXiv:2606.28308, June 2026) examines whether standard solvers for two-player zero-sum games are truly interchangeable when the game admits a convex set of Nash equilibria rather than a unique one. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets — including a two-dimensional Nash polytope and Kuhn poker, plus a set of 180 random games — the study finds that equilibrium selection is determined by the algorithm rather than the random seed, though families differ only on asymmetric Nash sets. Regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member of the Nash set, while regret-averaging methods (CFR, CFR+, fictitious play) drift toward lower-entropy faces. The chosen equilibrium also has downstream consequences against suboptimal opponents. Two negative results correct common intuitions: removing CFR's orthogonal quadrant projection does not eliminate boundary drift, and R-NaD's selection is anchor-following rather than initialization-independent.

Paper Overview

Field: Machine Learning
Author: Luis Leal
Published: 2026-06-26
arXiv: 2606.28308

Abstract (translated from Chinese summary)

Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. This paper asks whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed.

Using a tabular, exactly solvable testbed of six games with analytically known Nash sets — including a two-dimensional Nash polytope and Kuhn poker — the study finds that:

1. Selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets. 2. Regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member of the Nash set, while regret-averaging methods (CFR, CFR+, fictitious play) drift toward lower-entropy faces. This is confirmed on a set of 180 random games. 3. The selected member has downstream consequences against suboptimal opponents.

Two negative results also correct common intuitions:

Removing CFR's orthogonal quadrant projection does not eliminate boundary drift.
R-NaD's selection is anchor-following, not initialization-independent.

Source

arXiv: https://arxiv.org/abs/2606.28308
Auto-collected on 2026-06-30