Personal tools
You are here: Home Events Lab Lunch by Kousha Etessami

Lab Lunch by Kousha Etessami

— filed under:

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

  • Lab Lunch
When Jan 20, 2015
from 01:00 PM to 02:00 PM
Add event to calendar vCal

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.

Document Actions