# Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

arXiv: https://arxiv.org/abs/2606.25997 · HTML: https://mlsanity.com/paper/2606.25997/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 10 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Builds on (most cited first, 2 of 2)

- [Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games](https://mlsanity.com/paper/2509.25618/) (2025)
- [Dominated Actions in Imperfect-Information Games](https://mlsanity.com/paper/2504.09716/) (2025)

## Built on by (most cited first, 1 of 1)

- [Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games](https://mlsanity.com/paper/2606.29169/) (2026)

## Abstract (arXiv)

There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. Recently, an approach has been presented for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically constrained program based on a nonlinear complementarity problem formulation derived from the sequence-form game representation. This formulation was solved using Gurobi's nonconvex quadratic solver, which employs spatial branch-and-bound to iteratively refine variable bounds by solving convex relaxations of bilinear terms via McCormick envelopes. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal MIQCP reformulation. This approach was demonstrated to outperform prior algorithms from the Gambit software suite and quickly solve three-player Kuhn poker after removal of dominated actions; however, the algorithm was not able to solve the full version of the game within 24 hours. In this paper, we derive finite bounds on slack and multiplier variables in the nonlinear complementarity formulation. These bounds strengthen the convex relaxations used within spatial branch-and-bound and lead to substantial computational improvements. We demonstrate the impact of the proposed bounds on exact Nash equilibrium computation in three-player Kuhn poker.