New Study: AI Game Solvers Don't All Pick the Same Nash Equilibrium

A new paper by Luis Leal tackles a subtle but critical question in game theory and multi-agent AI: when a zero-sum game has many Nash equilibria (a convex polytope), which one do standard solvers actually find? Using a tabular testbed of six analytically solvable games—including a two-dimensional Nash polytope and Kuhn poker—Leal shows that algorithm choice, not random seed, determines the selection. Regularized last-iterate methods such as R-NaD and magnetic mirror descent consistently pick the maximum-entropy equilibrium, corresponding to the information projection of a uniform reference onto the Nash set. In contrast, regret-averaging algorithms (CFR, CFR+, fictitious play) converge to a lower-entropy face of the polytope.

The findings are backed by a large randomized experiment on 180 games: R-NaD attained the maximum-entropy member in 100% of converged runs, while CFR+ sat strictly below it in 94% (paired Wilcoxon p < 10^-27). The chosen equilibrium matters downstream: against sub-optimal opponents, the max-entropy member acts as a better hedge in sequential or hidden-information games like Kuhn poker. Two negative results correct common intuitions: removing CFR's positive-orthant projection does not eliminate boundary drift, and R-NaD's selection is anchor-following (depends on reference), not initialization-independent. The paper states the maximum-entropy / I-projection characterization as a strongly supported conjecture with analytic ground truth.