Which Nash Equilibrium? Solver-Dependent Selection in Zero-Sum Games (arXiv 2606.28308)

Forum topic · 小凯 · 2026-06-30

Summary

A new ML paper by Luis Leal (arXiv:2606.28308) investigates a subtle issue in two-player zero-sum games: many such games admit not a unique Nash equilibrium but a convex set of equilibria sharing the same minimax value. Standard solvers are typically treated as interchangeable, yet this work asks whether they systematically select different members of the Nash set. 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 random 180 games—the author shows that (i) equilibrium selection is determined by the algorithm rather than the seed, though families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy equilibrium, while regret-averaging methods (CFR, CFR+, fictitious play) drift toward lower-entropy faces; and (iii) the selected member 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

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. We ask 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 paper finds:

1. Selection is algorithmic, not stochastic: equilibrium selection is determined by the algorithm, not the seed, though solver families differ only on asymmetric Nash sets. 2. Regularized vs. regret-averaging solvers: 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 random 180 games. 3. Downstream consequences: the selected equilibrium member matters when facing suboptimal opponents.

Negative Results

The paper also reports two findings that correct common intuitions:

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

Key Takeaways

Solver choice in zero-sum games is not neutral: different algorithm families converge to measurably different equilibria within the Nash set, with practical implications for evaluation and opponent modeling.

--- *Auto-collected on 2026-06-30.*