Math Conjectures

Polynomial-Time Computation of a Bimatrix Nash Equilibrium

OPENLandmarkOpen problemProposed 1994 · Standard version

Canonical statement

Is there a deterministic polynomial-time algorithm that, given two rational payoff matrices A,B∈Qm×nA,B\in\mathbb Q^{m\times n}, outputs mixed strategies x∈Δmx\in\Delta_m and y∈Δny\in\Delta_n satisfying
xTAy≥x′TAy(x′∈Δm),xTBy≥xTBy′(y′∈Δn)? x^{\mathsf T}Ay\ge {x'}^{\mathsf T}Ay\quad(x'\in\Delta_m),\qquad x^{\mathsf T}By\ge x^{\mathsf T}By'\quad(y'\in\Delta_n)?
View source LaTeX
Is there a deterministic polynomial-time algorithm that, given two rational payoff matrices \(A,B\in\mathbb Q^{m\times n}\), outputs mixed strategies \(x\in\Delta_m\) and \(y\in\Delta_n\) satisfying
\[
  x^{\mathsf T}Ay\ge {x'}^{\mathsf T}Ay\quad(x'\in\Delta_m),\qquad
  x^{\mathsf T}By\ge x^{\mathsf T}By'\quad(y'\in\Delta_n)?
\]
GAME-003:[Papadimitriou1994PPAD][DaskalakisEtAl2009Nash]
Game theory and mathematical economicsTheoretical computer science

Notes

Nash guarantees an equilibrium exists in every finite bimatrix game, but existence does not supply an efficient algorithm. Papadimitriou introduced PPAD to capture parity-based total search [Papadimitriou1994PPAD], and computing an exact bimatrix equilibrium was later proved PPAD-complete [DaskalakisEtAl2009Nash]. Thus a polynomial-time algorithm is equivalent to the major class collapse FP=PPADFP=PPAD; zero-sum and structured games remain important tractable exceptions.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.