New algorithm computes proper equilibria in two-player zero-sum games in polynomial time
A preprint describes a deterministic polynomial-time method for finding exact extensive-form proper equilibria in finite two-player zero-sum games with perfect recall and rational data.
In plain words
Researchers often model sequential games, like chess-like decision trees, where players must weigh risky moves. The paper presents a fast, exact computer procedure that finds a 'proper equilibrium'—a stable set of strategies that penalizes clearly worse moves. The method works for two-player, zero-sum games with perfect recall.
What was announced
The authors define properness in the agent normal form: at each information set, an action is penalized relative to a better one while all other local choices, including the player's own future moves, stay fixed. Their algorithm assigns each information set a geometric permutahedron of allowable action probabilities and uses a scaled doubly stochastic representation to embed these restrictions in a polynomial-size sequence-form polytope, where a saddle point satisfies the local ε-properness inequalities.
To reach an exact equilibrium rather than one at an arbitrarily small numerical perturbation, the paper establishes sign stability of a parametric linear system, builds a persistent feasible basis, and extracts limits of behavioral ratios. The resulting probabilities are rational with polynomial encoding length, including at information sets whose realization probabilities vanish.
What it does not show
- The evidence is the paper's abstract only; the full article's proofs, benchmarks, and implementation details are not covered here.
- No independent verification of the algorithm's correctness or performance is provided in the supplied passages.
Sources
Source-support review completed 13 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.
Coverage: arXiv: abstract.
Updates and corrections
No corrections so far.
First published 13 Nov 2026
New to the subject? AI from the Ground Up starts from the beginning.