Aarhus University Seal

Computational Complexity of Computing a Quasi-Proper Equilibrium

Research output: Contribution to book/anthology/report/proceedingArticle 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
EditorsEvripidis Bampis, Aris Pagourtzis
Number of pages13
Place of publicationCham
PublisherSpringer
Publication year2021
Pages259-271
ISBN (print)978-3-030-86592-4
ISBN (Electronic)978-3-030-86593-1
DOIs
Publication statusPublished - 2021
Event23rd International Symposium on Fundamentals of Computation Theory
-
Duration: 12 Sep 202115 Sep 2021
Conference number: 23
https://www.corelab.ntua.gr/fct2021/

Conference

Conference23rd International Symposium on Fundamentals of Computation Theory
Nummer23
Periode12/09/202115/09/2021
Internetadresse
SeriesLecture Notes in Computer Science
Volume12867
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 222771074