The Hidden Bias in Game Solvers: Why Your Choice of Algorithm Matters

We've been treating game-solving algorithms as interchangeable black boxes. Pick any solver, run it on a zero-sum game, and out pops a Nash equilibrium. But this comforting assumption is wrong, and the consequences matter.

A new study, 'Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes', reveals that when multiple Nash equilibria exist, different solvers consistently select different ones. This isn't just academic trivia; it reshapes how we should approach algorithmic game-solving.

The researchers constructed a testbed of six two-player zero-sum games with analytically known 'Nash polytopes', sets of equilibria that yield the same game value but prescribe different behaviors. Their findings cut through several layers of conventional wisdom:

1. Algorithm, not randomness, determines selection: The choice of solver, not the random seed, dictates which equilibrium is found. This effect only appears in games with asymmetric Nash sets.

2. A stark divide in equilibrium preference: , Regularized last-iterate methods (R-NaD, magnetic mirror descent) consistently select the maximum-entropy equilibrium. , Regret-averaging methods (CFR, CFR+, fictitious play) drift towards lower-entropy solutions on the boundary of the Nash set.

3. Real-world impact: The selected equilibrium matters when facing sub-optimal opponents, especially in games with sequential structure or hidden information.

To quantify these effects, the team ran a large-scale experiment on 180 randomly generated games:

R-NaD achieved the maximum-entropy equilibrium in 100% of converged games. CFR+ selected a strictly lower-entropy solution in 94% of cases. This isn't noise; it's a fundamental property of these algorithms.

The practical implications are non-trivial. In Kuhn poker, the maximum-entropy equilibrium proved a better hedge against sub-optimal opponents. For simpler matrix games, different equilibria led to varied performance without a clear winner. But the key point stands: your choice of solver shapes the strategic landscape you explore.

Two common beliefs also fall:

1. Removing CFR's positive-orthant projection doesn't fix its boundary-seeking behavior.
2. R-NaD's selection isn't initialization-independent; it follows its anchor point.

This research exposes a blind spot in how we approach Nash equilibrium computation. The choice of solver isn't just an implementation detail, it's a decision that bakes in specific biases. As we deploy these algorithms in domains from poker AI to cybersecurity, understanding these subtle leanings becomes critical.

The study stops short of a formal proof, offering instead a 'strongly data-supported conjecture' that regularized methods select the maximum-entropy equilibrium via information projection. This opens a clear path for future theoretical work.

The takeaway is clear: in the world of game-solving, algorithms are not interchangeable. Your choice of method doesn't just affect how quickly you find an equilibrium; it determines which equilibrium you find. As we push into more complex game-theoretic territories, this hidden bias in our tools demands our attention.