Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games
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 -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
| Refinement | Main distinction | Polynomial-time result |
|---|---|---|
| Normal-form trembling-hand perfect (NFPE) | Trembles over complete contingent plans | Miltersen and Sørensen (2006) [ 10 ] |
| Sequential equilibrium (SE) | Consistent beliefs and sequential rationality | Miltersen and Sørensen (2006) [ 10 ] |
| Normal-form proper (NFPropE) | Payoff-ranked trembles over full contingent plans | Miltersen and Sørensen (2008) [ 11 ] |
| Quasi-perfect (QPE) | Best responses do not anticipate own future mistakes | Miltersen and Sørensen (2010) [ 12 ] |
| Extensive-form trembling-hand perfect (EFPE) | Trembles at individual information sets (agent form) | Farina and Gatti (2017) [ 1 ] |
| One-sided quasi-perfect (OSQPE) | Only the potentially imperfect opponent trembles | Farina and Sandholm (2021) [ 3 ] |
Zero-Sum Games
Zero-sum games study strategic settings where one player's gain is another's loss and equilibrium play protects against worst-case opponents.
See all 50 papers