We present 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 defined 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. The algorithm assigns each information set a geometric permutahedron that restricts admissible action probabilities. A scaled doubly stochastic representation embeds these restrictions into 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 with polynomial encoding length, even at information sets whose realization probabilities vanish.
Review