# Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 32 references that are in the map.
- First posted on arXiv 30 Sep 2025.

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

- [Fast Complete Algorithm for Multiplayer Nash Equilibrium](https://mlsanity.com/paper/2002.04734/) (2020)
- [Fictitious Play with Maximin Initialization](https://mlsanity.com/paper/2203.10774/) (2022)
- [Dominated Actions in Imperfect-Information Games](https://mlsanity.com/paper/2504.09716/) (2025)
- [Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium](https://mlsanity.com/paper/2508.10204/) (2025)

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

- [Computing Evolutionarily Stable Strategies in Imperfect-Information Games](https://mlsanity.com/paper/2512.10279/) (2025)
- [Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games](https://mlsanity.com/paper/2606.25997/) (2026)
- [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. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.