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

We study the complexity of computing or approximating an equilibrium for a given finite n-player extensive form game of perfect recall (EFGPR), where n ≥ 3. Our results apply not only to Nash equilibrium (NE), but also to various important refinements of NE for EFGPRs, including: subgame-perfect equilibrium in behavior strategies, sequential equilibrium (SE), and extensive form trembling-hand perfect equilibrium (PE). Of these, the most refined notion is PE. By a classic result of Selten, a PE exists for any EFGPR. We also study quasi-perfect equilibrium (QPE), which is a refinement that is incompatible with PE but refines the other mentioned notions. QPE was introduced by van Damme, who also showed that a QPE exists for any EFGPR. We show that, for all these notions of equilibrium, approximating an equilibrium for a given EFGPR, to within a given desired precision, is FIXPa-complete. We also show that computing a δ-almost subgame-perfect equilibrium in behavior strategies for a given EFGPR and given δ > 0, is PPAD-complete. (By definition, this is a behavior profile where no player can improve its own payoff in any subgame by more than δ, by switching its strategy unilaterally in that subgame.) In doing so, we also define the more refined notions of δ-almost ǫ-(quasi-)perfect equilibrium, and show that computing one for a given EFGPR, given δ > 0 and ǫ > 0, is PPAD-complete. Thus, approximating one such (δ-almost) equilibrium for n-player EFGPRs, n ≥ 3, is P-time equivalent to approximating a (δ-almost) NE for a normal form game with 3 or more players. Normal form games are trivially encodable as EFGPRs without blowup in size. Thus our results extend the celebrated complexity results for normal form games to the considerably more general setting of EFGPRs. For 2-player EFGPRs, analogous complexity results follow from the algorithms of Koller, Megiddo, and von Stengel [15, 40], and von Stengel, van den Elzen, and Talman [41]. However, prior to the present paper, no analogous results were known for EFGPRs with 3 or more players. By contrast to the prior work on 2-player EFGPRs, our results make no use of the sequence form for EFGPRs. Instead, we combine older insights from Kuhn and Selten’s original agent normal form for EFGPRs, and Myerson’s alternative definition of PE via ǫ-PEs, with insights from new algebraic fixed point functions for (ǫ-perfect) equilibria of n-player normal form games, n ≥ 3, developed recently in [10] and [9].