The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game

We study the complexity of computing or approximating refinements of Nash equilibrium for finite n-player extensive form games of perfect recall (EFGPR), n ≥ 3. Our results apply to a number of well-studied refinements, including sequential equilibrium, extensive-form perfect equilibrium, and quasi-perfect equilibrium.

Informally, we show that, for all these refinements, approximating such a refined equilibriumfor an n-player EFGPR is not any harder than (i.e., can be efficiently reduced to) approximating a Nash equilibrium for a 3-player normal form game. More specifically, we show that approximating such a refined equilibrium for a given EFGPR, within given desired precision, is FIXP_a-complete. We also study corresponding notions of “almost” equilibrium for these refinements, and we show that computing one is PPAD-complete. (In all these cases our main results show containment in FIXP_a and containment in PPAD. Hardness follows from earlier results for simpler games.)