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

Paper: 2606.28308
Authors: Luis Leal
Categories: cs.GT, cs.AI, cs.LG, cs.MA

The Gap

Two-player zero-sum games can have a convex set of Nash equilibria — a polytope of mixed strategies, all with the same minimax value, but prescribing different behaviour.
Standard solvers (CFR, Fictitious Play, R-NaD, etc.) are treated as interchangeable: they converge to some equilibrium, and we assume the particular one doesn’t matter.

This paper challenges that assumption.
Prior work acknowledged that different initializations can lead to different equilibria, but treated this as seed-dependent noise.
Here the authors ask: Is selection actually driven by the algorithm itself, independent of seed?
They construct a tabular testbed of six small games whose Nash polytopes are known analytically (including a 2-D polytope and Kuhn poker), run a battery of algorithms, and check which member of the polytope each converges to.

The logical path:

Problem: Nash polytope exists           Assumption: solvers are interchangeable
    |                                         |
    v                                         v
Method: compare algorithms on games with known Nash sets
    |
    +-----------------------------------------+
    v
Evidence: R-NaD picks max-entropy always; CFR drifts to low-entropy face
    |
    v
Conclusion: solver-dependent selection is systematic, not random

The Increment

One sentence: Before this paper, we knew solvers converge to *a Nash equilibrium but not which one; after this paper, we know that regularized last-iterate methods (R-NaD, Magnetic Mirror Descent) select the maximum-entropy member, while regret-minimizing methods (CFR, CFR+, Fictitious Play) drift to lower-entropy faces — and that this has measurable downstream consequences against suboptimal opponents.

Core Mechanism

The authors exploit a small set of exactly solvable zero-sum games with known Nash polytopes.
For each game, they run multiple solvers from many seeds, record the mixed strategy profile at convergence, and project it onto the polytope (to handle numerical drift).
They then compute the Shannon entropy of each converged profile and compare it to the unique maximum-entropy member of the polytope (the point closest to uniform under KL divergence, i.e., the I-projection of the uniform distribution onto the Nash set).

The key comparison is between two algorithm families:

• Regularized last-iterate methods (R-NaD, Magnetic Mirror Descent) — these add a regularization term (like KL from a reference) to the payoff, which biases them toward high-entropy strategies.
• Regret-averaging methods (CFR, CFR+, Fictitious Play) — these average decisions over time and have no explicit entropy bias.

The experiment also includes negative results: removing CFR’s positive-orthant projection doesn’t stop boundary drift, and R-NaD’s selection is anchor-following (depends on the reference distribution), not initialization-independent.

Algorithm input: tabular game (payoff matrix, chance nodes)
         |
         v
    [Baseline: compute Nash polytope via linear programming]
         |
         v
    Run solver from multiple seeds:
         |
         +-> R-NaD / MMD: regularized, last-iterate
         |       |-> Converged strategy -> project onto polytope
         |       |-> Compute entropy -> compare to max-entropy member
         |
         +-> CFR / CFR+ / FP: regret-averaging
                 |-> Converged (average) strategy -> same pipeline
                 
    Also: random 180-game ensemble for statistical validation

Structural metaphor: Think of the Nash polytope as a crowded rooftop lounge — a convex area where everyone is equally happy (same value).
Different solvers are different people trying to find a spot:

• R-NaD is someone with a strong anchor — they keep a bungee cord attached to the center of the room (the uniform distribution).
  No matter where they start, the cord pulls them toward the most central, spacious spot — the maximum-entropy equilibrium.
• CFR is someone who keeps walking to the spot where they’d regret past moves the least, averaging over time.
  Without any central pull, they drift toward the edges and corners — low-entropy faces — because those are flat and stable under regret minimization.
• Seed variation is like starting from different doors; the regularized person ends up at the same center, the regret-minimizer might end up on different edges but always staying away from the middle.

The metaphor is load-bearing: the bungee anchor (reference distribution) explains both the consistent max-entropy selection and the negative result that selection changes if you swap the reference (anchor-following).

Key Concepts

• Nash Polytope: The convex set of all Nash equilibrium strategy profiles in a zero-sum game.
  Example: In Kuhn poker (3-card, limit betting), there is a one-parameter family of equilibria — each choice of bluff frequency along the line is a Nash equilibrium.
  The polytope captures the trade-off: different mixed strategies achieve the same minimax value but give different probabilities to specific actions.

• Maximum-Entropy Equilibrium: The unique member of the Nash polytope that maximizes the Shannon entropy of the strategies.
  It is the “most random” equilibrium consistent with rationality.
  Example: In the 2-D polytope studied (a biased rock-paper-scissors variant), the max-entropy point is the one closest to uniform play, not the one that heavily biases toward one action.
  The authors compute this as the I-projection of the uniform distribution onto the polytope (minimizing KL divergence).

• I-projection (Information Projection): Given a reference distribution (here uniform over actions), the I-projection onto a convex set is the point in the set with minimal KL divergence from the reference.
  For the Nash polytope, the max-entropy member is exactly the I-projection of the uniform distribution.
  This characterization matches R-NaD’s selection exactly on the 2-D polytope and at 99.7% max entropy in Kuhn poker.

Framework Shift

Before (mainstream view): solvers are interchangeable — the specific Nash equilibrium reached is noise, a function of seed and implementation details.

  Algorithm A     Algorithm B
      |               |
      v               v
   (some eq.)       (some eq.)
      |               |
      +---- No map ---+
      v
   "It doesn't matter which equilibrium"

After (this paper): solver families systematically select different regions of the polytope — a deterministic function of the algorithm’s inductive bias.

  Algorithm A (reg.)   Algorithm B (regret)
      |                    |
      v                    v
   max-entropy face    low-entropy face
      |                    |
      +---- Systematic ---+
      v
   "Different equilibria matter for downstream behaviour"

One sentence: From “any equilibrium is as good as any other” to “the solver’s inductive bias determines which equilibrium you get, and the max-entropy one is a better hedge.”

Expert Assessment

Problem choice: Real gap. The community has long known that multiple equilibria exist but assumed they are interchangeable. This paper cleanly shows they are not — and that algorithmic bias is systematic, not random. The problem sits at the intersection of game theory and algorithmic learning, where practical deployment (e.g., poker AI) cares which equilibrium is found.

Method maturity: Clever testbed design rather than brute force. The authors deliberately use small, analytically traceable games to ground truth against exact polytopes. That’s the right approach for a first systematic study. The negative results (CFR projection does not cause drift) are a nice counterpoint to common intuition. However, the method does not scale — the analysis relies on knowing the polytope exactly. The random 180-game ensemble is a good robustness check but still limited to tiny games (likely 2x2 or 3x3).

Experimental integrity: Baselines are fair and well-chosen (R-NaD, MMD, CFR, CFR+, FP). The paired Wilcoxon test (p < 10⁻²⁷) is appropriate. The fact that R-NaD hits 100% max-entropy on converged games is striking. One red flag: the “convergence” criteria for CFR family might be loose — CFR is known to require many iterations. The abstract reports CFR+ sitting strictly below max-entropy in 94% of games, which is consistent but could be exacerbated by early stopping.

Writing quality: Solid overall. The introduction clearly states the gap. The negative result sections are well-motivated. However, the description of the 2-D polytope example is dense and could use a graphical figure (though ASCII is enough in a blog). The “anchor-following” result is explained in only one paragraph — it deserves more space, as it refines the understanding of R-NaD’s behaviour.

Verdict: Weak accept — solid contribution with clear evidence, but limited in scale. The conjecture (max-entropy = I-projection) is well-supported and likely correct for regularized methods. The paper is worth reading for anyone training solvers on games with multiple equilibria.

Takeaways

• If you care about which Nash equilibrium emerges, choose your solver deliberately.
  Regularized last-iterate methods give you the max-entropy one; regret methods give you something on a lower-entropy face.

• The max-entropy equilibrium is a better hedge against suboptimal opponents in sequential games (Kuhn poker: it is strictly better).
  In matrix games the difference is bounded and neither dominates, but the downstream consequences are real.

• CFR’s positive-orthant projection is not the cause of boundary drift.
  Removing it doesn’t push CFR toward the interior — the drift is baked into the regret-minimization dynamics.

• R-NaD’s equilibrium selection is anchor-following, not initialization-independent.
  If you want a different max-entropy-like equilibrium, you can change the reference distribution.

• The I-projection characterization is a clean tool: given any algorithm that regularizes toward a known reference, you can predict which Nash equilibrium it will find (provided the Nash set is convex).
  This could be used to design solvers that target specific equilibrium properties.