# Lab Lunch by Kousha Etessami

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

Extensive form games are the fundamental mathematical model of games
that transpire as a sequence of moves by players over time. A
standard sanity condition for extensive form games of imperfect
information, introduced already by Kuhn (1953), is "perfect recall".
In this talk, after defining the basic concepts, I will discuss the
computational complexity of computing various refinements of
equilibrium for finite extensive form games of perfect recall
(EFGPRs).

Selten's seminal work (1975), for which he was awarded a Nobel prize
in Economics (together with Nash and Harsanyi), made clear that Nash
equilibrium is not an adequately refined solution concept for
extensive form games. In particular, Nash equilibria can involve
"non-credible threats" which render them implausible. Motivated by
this, Selten defined a more refined notion of "(trembling hand)
perfect equilibrium" and showed that it always exists in any finite
EFGPR. Subsequently, various other important refinements of
equilibrium were studied by other game theorists, including
"sequential equilibrium" (Kreps & Wilson, 1982) and
"quasi-perfect equilibrium" (van Damme, 1984).

We show that, for all of these refined notions of equilibrium,
approximating one such equilibrium for a given n-player EFGPR (for
any n) to within desired precision is not any harder than
approximating a Nash equilibrium for a 3-player ***normal form
game*** to within desired
precision. Namely, all of these approximation problems are
FIXP_a-complete, and futhermore computing a suitably-defined
"epsilon-almost" approximation of each such equilibrium refinement
for EFGPRs is PPAD-complete.