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

Research output: Contribution to journalArticlepeer-review

Abstract

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 FIXPa-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 FIXPa and containment in PPAD. Hardness follows from earlier results for simpler games.) 
Original languageEnglish
Pages (from-to)107-140
Number of pages34
JournalGames and Economic Behavior
Volume125
Early online date26 Aug 2020
DOIs
Publication statusPublished - 1 Jan 2021

Fingerprint Dive into the research topics of 'The complexity of computing a (quasi-)perfect equilibrium for an <i>n</i>-player extensive form game'. Together they form a unique fingerprint.

Cite this