Bounding Solver Variables Speeds Up a Three-Player Poker Equilibrium Search

A small poker game with a difficult search

A Nash equilibrium is a collection of strategies in which no player can improve their expected payoff by changing strategy alone. Computing one is challenging in multiplayer games with hidden information. Methods with convergence guarantees in two-player zero-sum games do not necessarily retain those guarantees when more players participate.

In the preprint Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games, Sam Ganzfried investigates a targeted improvement to an existing optimization approach. Rather than changing the game or removing actions, the method restricts the ranges of auxiliary mathematical variables using bounds derived from the game’s structure and payoffs.

The reported experiment concerns full three-player Kuhn poker: a simplified game with four cards, private hands and one betting round. Despite its compact rules, equilibrium strategies can involve bluffing and checking strong hands to induce bets. The full game has 48 information sets and 601 nodes.

Giving the solver less room to search

The underlying formulation assumes finite games with perfect recall: players do not forget information they previously knew. It uses the sequence-form representation, which describes players’ action sequences rather than enumerating every complete pure strategy.

The optimization constraints combine valid strategy probabilities with conditions requiring each player’s strategy to be a best response to the others. Products of variables make this a nonlinear complementarity problem. It can be expressed as a quadratically constrained feasibility problem and passed to Gurobi’s nonconvex solver.

Gurobi uses spatial branch-and-bound, repeatedly refining variable ranges and solving convex relaxations of nonlinear relationships. Bounds therefore matter: they can strengthen the approximations used during the search.

Strategy variables already lie between zero and one. The earlier implementation, however, left slack variables without finite upper bounds and multiplier variables unrestricted. These are auxiliary quantities associated with players’ best-response optimization problems, not additional choices available to the players.

Ganzfried derives finite bounds for both families. A simple slack bound is the difference between a player’s largest and smallest terminal payoffs. A finer result relates a sequence’s slack to the loss in best-response value caused by requiring that sequence. Multiplier bounds use payoff magnitudes and counts of descendant information sets.

Because the finer slack result depends on unknown opponent strategies, the implementation constructs conservative bounds valid across opponent strategies, rather than evaluating the formula at an already known equilibrium.

Eight bounded configurations, eight numerical solutions

For full Kuhn poker, raw terminal payoffs range from minus two to four. The uniform bounds therefore cap slacks at six and multiplier magnitudes at 170, before small numerical margins. Finer bounds reduce these limits for individual variables.

The experiment compares three choices for each variable family: no finite bounds, uniform bounds and finer proposition-based bounds. All nine configurations retain identical objectives and constraints; only variable bounds differ.

With neither family bounded, the solver reached the 300-second limit without finding a feasible solution. All eight configurations with bounds returned numerically verified equilibria in under 17 seconds.

The fastest configuration used only the uniform multiplier bounds, taking 0.642 seconds. Uniform slack bounds alone took 1.849 seconds. Combining both uniform bounds took 16.271 seconds, while combining both finer bounds took 10.698 seconds.

That ordering is important. Although tighter domains can strengthen relaxations, they did not consistently reduce computational effort. The paper also reports solver work units, and their results likewise show that finer bounds can slow some configurations while helping others.

What the evidence establishes

These are narrowly specified computational results. Each table entry represents one run, using Gurobi 13.0.3, a fixed seed, eight threads and the same laptop hardware. Reported solver times exclude model construction, bound preprocessing and verification. Calculating the finer bounds and subtree counts took less than 0.1 seconds per run.

The returned strategies underwent checks against the full game. Maximum best-response gains were below one trillionth, and maximum absolute constraint residuals were below ten trillionths. Independent dynamic-programming calculations agreed closely with best-response linear programs. These are numerical checks, not exact-arithmetic certificates.

An earlier implementation’s 24-hour timeout provides historical context, not a controlled speed comparison. The relevant matched baseline here is the new 300-second run without finite slack or multiplier bounds.

The preprint demonstrates a substantial improvement on this benchmark without removing actions. It does not establish performance across multiplayer games generally. As Ganzfried notes, additional games and seeds are needed—and the best bound configuration cannot be identified simply by choosing the tightest available limits.