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 Universitet

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings
Antal sider	13
Udgivelsessted	Cham
Publikationsdato	2021
Sider	259-271
ISBN (Trykt)	978-3-030-86592-4
ISBN (Elektronisk)	978-3-030-86593-1
Status	Udgivet - 2021
Begivenhed	International Symposium on Fundamentals of Computation Theory - Athens, Grækenland Varighed: 12 sep. 2021 → … Konferencens nummer: 23

Konference

Konference	International Symposium on Fundamentals of Computation Theory
Nummer	23
Land/Område	Grækenland
By	Athens
Periode	12/09/2021 → …

Navn	Lecture Notes in Computer Science
Vol/bind	12867
ISSN	0302-9743

Emneord

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

Adgang til dokumentet

Computational Complexity of Computing a Quasi-Proper EquilibriumForlagets udgivne version, 228 KB

https://arxiv.org/abs/2107.04300

Citationsformater

@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. i Fundamentals of Computation Theory : 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham, Lecture Notes in Computer Science, bind 12867, s. 259-271, International Symposium on Fundamentals of Computation Theory, Athens, Grækenland, 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. s. 259-271 (Lecture Notes in Computer Science, Bind 12867).

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater