# Extensive-Form Perfect Equilibrium Computation in Two-Player Games

arXiv: https://arxiv.org/abs/1611.05011 · HTML: https://mlsanity.com/paper/1611.05011/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2016.

## Built on by (most cited first, 2 of 2)

- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Temporal Induced Self-Play for Stochastic Bayesian Games](https://mlsanity.com/paper/2108.09444/) (2021)

## Abstract (arXiv)

We study the problem of computing an Extensive-Form Perfect Equilibrium (EFPE) in 2-player games. This equilibrium concept refines the Nash equilibrium requiring resilience w.r.t. a specific vanishing perturbation (representing mistakes of the players at each decision node). The scientific challenge is intrinsic to the EFPE definition: it requires a perturbation over the agent form, but the agent form is computationally inefficient, due to the presence of highly nonlinear constraints. We show that the sequence form can be exploited in a non-trivial way and that, for general-sum games, finding an EFPE is equivalent to solving a suitably perturbed linear complementarity problem. We prove that Lemke's algorithm can be applied, showing that computing an EFPE is textsfPPAD-complete. In the notable case of zero-sum games, the problem is in textsfFP and can be solved by linear programming. Our algorithms also allow one to find a Nash equilibrium when players cannot perfectly control their moves, being subject to a given execution uncertainty, as is the case in most realistic physical settings.