Computational Complexity of Computing a Quasi-Proper Equilibrium

Troels Bjerre Lund, Kristoffer Arnsfelt Hansen

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


We study the computational complexity of computing or approximating a quasi-proper equilibrium for a given finite extensive form game of perfect recall. We show that the task of computing a symbolic quasi-proper equilibrium is PPAD-complete for two-player games. For the case of zero-sum games we obtain a polynomial time algorithm based on Linear Programming. For general n-player games we show that computing an approximation of a quasi-proper equilibrium is FIXPa-complete. Towards our results for two-player games we devise a new perturbation of the strategy space of an extensive form game which in particular gives a new proof of existence of quasi-proper equilibria for general n-player games.
Original languageEnglish
Title of host publicationFundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings
Number of pages13
Place of PublicationCham
Publication date2021
ISBN (Print)978-3-030-86592-4
ISBN (Electronic)978-3-030-86593-1
Publication statusPublished - 2021
SeriesLecture Notes in Computer Science


  • Computational Complexity
  • Quasi-Proper Equilibrium
  • Extensive Form Games
  • PPAD-complete
  • Linear Programming


Dive into the research topics of 'Computational Complexity of Computing a Quasi-Proper Equilibrium'. Together they form a unique fingerprint.

Cite this