Computational Complexity of Computing a Quasi-Proper Equilibrium

Troels Bjerre Lund; Kristoffer Arnsfelt Hansen

Computational Complexity of Computing a Quasi-Proper Equilibrium

Troels Bjerre Lund
, Kristoffer Arnsfelt Hansen

Aarhus University

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings
Number of pages	13
Place of Publication	Cham
Publication date	2021
Pages	259-271
ISBN (Print)	978-3-030-86592-4
ISBN (Electronic)	978-3-030-86593-1
Publication status	Published - 2021
Event	International Symposium on Fundamentals of Computation Theory - Athens, Greece Duration: 12 Sept 2021 → … Conference number: 23

Conference

Conference	International Symposium on Fundamentals of Computation Theory
Number	23
Country/Territory	Greece
City	Athens
Period	12/09/2021 → …

Series	Lecture Notes in Computer Science
Volume	12867
ISSN	0302-9743

Keywords

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

Access to Document

Computational Complexity of Computing a Quasi-Proper EquilibriumFinal published version, 228 KB

https://arxiv.org/abs/2107.04300

Cite this

@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); International Symposium on Fundamentals of Computation Theory ; Conference date: 12-09-2021",

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",

}

Lund, TB & Hansen, KA 2021, Computational Complexity of Computing a Quasi-Proper Equilibrium. in Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham, Lecture Notes in Computer Science, vol. 12867, pp. 259-271, International Symposium on Fundamentals of Computation Theory, Athens, Greece, 12/09/2021. <https://arxiv.org/abs/2107.04300>

Computational Complexity of Computing a Quasi-Proper Equilibrium. / Lund, Troels Bjerre; Hansen, Kristoffer Arnsfelt.
Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham, 2021. p. 259-271 (Lecture Notes in Computer Science, Vol. 12867).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Computational Complexity of Computing a Quasi-Proper Equilibrium

AU - Lund, Troels Bjerre

AU - Hansen, Kristoffer Arnsfelt

N1 - Conference code: 23

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Computational Complexity

KW - Quasi-Proper Equilibrium

KW - Extensive Form Games

KW - PPAD-complete

KW - Linear Programming

KW - Computational Complexity

KW - Quasi-Proper Equilibrium

KW - Extensive Form Games

KW - PPAD-complete

KW - Linear Programming

M3 - Article in proceedings

SN - 978-3-030-86592-4

T3 - Lecture Notes in Computer Science

SP - 259

EP - 271

BT - Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings

CY - Cham

T2 - International Symposium on Fundamentals of Computation Theory

Y2 - 12 September 2021

ER -

Computational Complexity of Computing a Quasi-Proper Equilibrium

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this