cs.GTNov 4, 2026

Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games

Authors: Sam Ganzfried

Organizations: Ganzfried Research, Cornell University

Abstract

We give a deterministic polynomial-time algorithm for computing an exact extensive-form proper equilibrium in a finite two-player zero-sum extensive-form game with perfect recall and rational data. Properness is understood in the agent normal form: an action at an information set is penalized relative to a better action while all other local behavioral choices, including the player's own future actions, remain fixed. Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities. A scaled doubly stochastic representation embeds these restrictions in a polynomial-size sequence-form polytope; a saddle point then satisfies the local ε\varepsilon-properness inequalities. To obtain an exact equilibrium rather than a solution at an arbitrarily small numerical perturbation, we establish sign stability of a parametric linear system, construct a persistent feasible basis, and extract the limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.

Figures & tables

Explore similar work

Jan 12, 2022

Safe Equilibrium

The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. If we follow a Nash equilibrium and opponents are irrational (or follow strategies from a different Nash equilibrium), then we may obtain an extremely low payoff. On the other hand, a maximin strategy assumes that all opposing agents are playing to minimize our payoff (even if it is not in their best interest), and ensures the maximal possible worst-case payoff, but results in exceedingly conservative play. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability and behaving potentially arbitrarily with the remaining probability. We prove that a safe equilibrium exists in all strategic-form games (for all possible values of the rationality parameters), and prove that its computation is PPAD-hard. We present exact algorithms for computing a safe equilibrium in both 2 and nn-player games, as well as scalable approximation algorithms.
Sep 30, 2025

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

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.
May 31, 2026

Fairness in two-player zero-sum games with bandit feedback

We study two-player zero-sum games (TPZSGs) with bandit feedback under fairness constraints requiring every action to be played with probability at least α/mα/m. Existing instance-dependent results target pure\textit{pure} Nash equilibria, while fairness generically produces mixed\textit{mixed} equilibria, a harder learning target. Our key technical tool is a reparametrization: every fair strategy decomposes as p=(α/m)1+(1−α)p~p = (α/m)\mathbf{1} + (1-α)\widetilde{p} with p~∈Δm\widetilde{p} \in Δ_m, and substituting into the payoff form yields p⊤Aq=p~⊤A~qp^{\top}Aq = \widetilde{p}^{\top}\widetilde{A} q for a fair payoff matrix A~:=(1−α)A+α1c⊤\widetilde{A} := (1-α)A + α\mathbf{1} c^{\top}, where cj=1m∑iA(i,j)c_j = \tfrac{1}{m}\sum_i A(i,j) is the column-mean vector. The fair game on AA is then equivalent to a standard zero-sum game on A~\widetilde{A}, so equilibrium existence, KKT structure, and LP basis stability reduce to classical results applied to A~\widetilde{A}. We derive the fair minimax value, fair Nash equilibrium, fair regret, and a clean dual representation showing the price of fairness is at most α(1−1/m)α(1-1/m) and vanishes whenever the unconstrained equilibrium already has full support. Our main result is an O~(T2/3)\widetilde{O}(T^{2/3}) regret bound for an Explore-Then-Commit algorithm, Fair-ETC-TPZSG\texttt{Fair-ETC-TPZSG}, applicable to general mixed fair equilibria, together with a discussion of why naive action elimination does not readily improve it. When the fair equilibrium has a single dominant action, equivalently when p~⋆\widetilde{p}^{\star} is a vertex of ΔmΔ_m, the bound sharpens to instance-dependent O~(1/Δ~(α)2)\widetilde{O}(1/\widetildeΔ(α)^{2}), where Δ~(α)\widetildeΔ(α) is the LP-margin gap.