Aarhus University Seal

Dansk

You are here: » Computational Complexity of Computing a Quasi-Proper Equi...

About Aarhus University

Computational Complexity of Computing a Quasi-Proper Equilibrium

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Standard

Computational Complexity of Computing a Quasi-Proper Equilibrium. / Hansen, Kristoffer Arnsfelt; Lund, Troels Bjerre.

Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. ed. / Evripidis Bampis; Aris Pagourtzis. Cham : Springer, 2021. p. 259-271 (Lecture Notes in Computer Science, Vol. 12867).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Harvard

Hansen, KA & Lund, TB 2021, Computational Complexity of Computing a Quasi-Proper Equilibrium. in E Bampis & A Pagourtzis (eds), Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Springer, Cham, Lecture Notes in Computer Science, vol. 12867, pp. 259-271, 23rd International Symposium on Fundamentals of Computation Theory
, 12/09/2021. https://doi.org/10.1007/978-3-030-86593-1_18

APA

Hansen, K. A., & Lund, T. B. (2021). Computational Complexity of Computing a Quasi-Proper Equilibrium. In E. Bampis, & A. Pagourtzis (Eds.), Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings (pp. 259-271). Springer. Lecture Notes in Computer Science Vol. 12867 https://doi.org/10.1007/978-3-030-86593-1_18

CBE

Hansen KA, Lund TB. 2021. Computational Complexity of Computing a Quasi-Proper Equilibrium. Bampis E, Pagourtzis A, editors. In Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham: Springer. pp. 259-271. (Lecture Notes in Computer Science, Vol. 12867). https://doi.org/10.1007/978-3-030-86593-1_18

MLA

Hansen, Kristoffer Arnsfelt and Troels Bjerre Lund "Computational Complexity of Computing a Quasi-Proper Equilibrium". and Bampis, Evripidis Pagourtzis, Aris (editors). Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham: Springer. (Lecture Notes in Computer Science, Vol. 12867). 2021, 259-271. https://doi.org/10.1007/978-3-030-86593-1_18

Vancouver

Hansen KA, Lund TB. Computational Complexity of Computing a Quasi-Proper Equilibrium. In Bampis E, Pagourtzis A, editors, Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings. Cham: Springer. 2021. p. 259-271. (Lecture Notes in Computer Science, Vol. 12867). doi: 10.1007/978-3-030-86593-1_18

Author

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

Bibtex

@inproceedings{66c65af218684e7d8eb74df88d584376,
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.",
author = "Hansen, {Kristoffer Arnsfelt} and Lund, {Troels Bjerre}",
year = "2021",
doi = "10.1007/978-3-030-86593-1_18",
language = "English",
isbn = "978-3-030-86592-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "259--271",
editor = "Evripidis Bampis and Aris Pagourtzis",
booktitle = "Fundamentals of Computation Theory",
address = "Netherlands",
note = "null ; Conference date: 12-09-2021 Through 15-09-2021",
url = "https://www.corelab.ntua.gr/fct2021/",

}

RIS

TY - GEN

T1 - Computational Complexity of Computing a Quasi-Proper Equilibrium

AU - Hansen, Kristoffer Arnsfelt

AU - Lund, Troels Bjerre

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.

U2 - 10.1007/978-3-030-86593-1_18

DO - 10.1007/978-3-030-86593-1_18

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

A2 - Bampis, Evripidis

A2 - Pagourtzis, Aris

PB - Springer

CY - Cham

Y2 - 12 September 2021 through 15 September 2021

ER -