mlsanityData to 7 Oct 2026

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

arXiv 2606.28308 ↗First posted 26 Jun 2026cs.GT cs.AI cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

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 -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 21 references that are in the map. First posted on arXiv 26 Jun 2026.

Builds on

10 of 21 references.

References · 10

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  3. 2017Cycles in adversarial regularized learningcited by 122
  4. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  5. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  6. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  7. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  8. 2018Re-evaluating Evaluationcited by 47
  9. 2018An explicit analysis of the entropic penalty in linear programmingcited by 23
  10. 2021Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descentcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.