Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

Technical Summary: Solver-Dependent Selection on Zero-Sum Nash Polytopes

Problem Statement
In two-player zero-sum (2p0s) games, the minimax theorem guarantees a unique game value $V^\star$, but it does not guarantee a unique Nash equilibrium profile. Many games possess a convex set of equilibria (a Nash polytope) where every member achieves $V^\star$ against a best-responding opponent, yet members differ in their off-path behavior, support, and robustness to imperfect opponents. Standard solvers are often treated as interchangeable, but this paper investigates whether different solver families systematically select different members of the Nash set based on their algorithmic structure rather than random initialization.

Methodology
The authors employ a minimal, fully transparent testbed using a tabular extensive-form engine with exact counterfactual values, eliminating sampling and function-approximation variance. This allows for verification against analytically known ground truth. The study utilizes six specific games with characterized Nash sets:

1. Symmetric controls: pennies safe, two safe, and dup action (1-D Nash segments).
2. Asymmetric games: asym safe (1-D asymmetric face), polytope4 (genuinely 2-D Nash polytope), and Kuhn poker (imperfect-information extensive-form game with a 1-D family of equilibria).

The solvers are categorized into two families:

• Regret-averaging methods: Counterfactual Regret Minization (CFR), CFR+, Fictitious Play (FP), and Hedge (ablation). These deploy time-averaged strategies.
• Regularized last-iterate methods: Regularized Nash Dynamics (R-NaD), Magnetic Mirror Descent (MMD), and Multiplicative Weights Update (MWU/NeuRD). These deploy the final iterate of dynamics anchored to a reference policy.

The primary metric is the "selection coordinate" within the Nash polytope, compared against the analytically derived maximum-entropy member ($\sigma_{ME}$), which is equivalent to the information projection (I-projection) of the uniform distribution onto the Nash set.

Key Contributions and Results

1. Algorithmic Selection is Geometry-Gated:
   Equilibrium selection is determined by the algorithm, not the random seed (within-algorithm variation is zero due to deterministic tabular updates) or the iteration budget. Differences between solver families emerge only on geometrically asymmetric Nash sets. On symmetric games, all converging solvers (except Fictitious Play) agree on the maximum-entropy coordinate. On asymmetric games, the families diverge.

2. Regularized Methods Select the Maximum-Entropy Member:
   Regularized last-iterate methods (specifically R-NaD with a uniform reference) select the maximum-entropy equilibrium.

   • On the 2-D polytope4 game, R-NaD lands exactly on the analytic maximum-entropy point $(0.161, 0.256)$.
   • On Kuhn poker, R-NaD achieves 99.7% of the maximum entropy.
   • This behavior is confirmed on a randomized ensemble of 180 asymmetric matrix games: R-NaD attains the maximum-entropy member in 100% of converged games, whereas CFR+ sits strictly below the maximum entropy in 94% of cases (mean entropy gap $+0.121$, $p < 10^{-27}$).
   • The authors conjecture that regularized solvers compute the I-projection of their reference policy onto the Nash polytope. With a uniform reference, this yields the maximum-entropy equilibrium.

3. Regret-Averaging Methods Drift to Lower Entropy:
   Regret-averaging methods (CFR, CFR+) drift toward lower-entropy faces on asymmetric games. For instance, on asym safe, CFR+ selects a coordinate of 0.275 versus the maximum-entropy 0.218. This drift increases with the iteration budget, indicating it is a selection property of the dynamics, not incomplete convergence. Fictitious Play also drifts to the boundary on matrix games, matching maximum entropy only in Kuhn (an unexplained anomaly).

4. Refutation of Common Mechanisms:

   • Projection Cause: The authors refute the common intuition that CFR’s boundary drift is caused by the positive-orthant projection $\max(R, 0)$. Replacing this with a softmax (Hedge) while keeping regrets fixed increases boundary drift, proving the projection is not the cause.
   • Initialization Independence: R-NaD’s selection is "anchor-following." Changing the initial reference policy shifts the selected equilibrium. The maximum-entropy selection is a special case of uniform initialization, not an unconditional structural attractor.

5. Downstream Consequences:
   The selected equilibrium has bounded downstream consequences against sub-optimal opponents.

   • In Kuhn poker (sequential/hidden-information), the maximum-entropy member (R-NaD) is a strictly better hedge against flawed opponents than the CFR+ member.
   • In matrix games, neither member dominates; the hedging advantage tracks sequential structure rather than maximum entropy itself.
   • The absolute magnitude of the robustness gap is small ($< 0.02$ in Kuhn), scaling with structure but remaining bounded.

Significance and Claims
The paper establishes that solver choice is not interchangeable when Nash equilibria are non-unique. It provides strong empirical evidence for a conjecture that regularized last-iterate methods compute the I-projection of their reference onto the Nash set. The authors emphasize the distinction between demonstrated phenomena (algorithmic selection differences) and conjectured mechanisms (I-projection characterization). They explicitly correct common intuitions regarding the causes of boundary drift in CFR and the initialization independence of regularized methods. The work highlights that while selection differences are systematic and theoretically grounded in regularization principles, their practical impact is bounded and dependent on game structure (sequential vs. simultaneous).