@inproceedings{edb5646bcdb6475ca851ebc31613a273,
title = "Computational Complexity of Computing a Quasi-Proper Equilibrium",
abstract = "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.",
keywords = "Computational Complexity, Quasi-Proper Equilibrium, Extensive Form Games, PPAD-complete, Linear Programming, Computational Complexity, Quasi-Proper Equilibrium, Extensive Form Games, PPAD-complete, Linear Programming",
author = "Lund, {Troels Bjerre} and Hansen, {Kristoffer Arnsfelt}",
note = "Doesn't seem to count as OA? (jcg: 14/02/2022) OA has been added (ms: 16/03/2022)",
year = "2021",
language = "English",
isbn = "978-3-030-86592-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "259--271",
booktitle = "Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings",
}