The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. / Hansen, Kristoffer Arnsfelt.

Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. ed. / Vittorio Bilò; Michele Flammini. Cham : Springer VS, 2017. p. 119-130 (Lecture Notes in Computer Science, Vol. 10504).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Hansen, KA 2017, The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. in V Bilò & M Flammini (eds), Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. Springer VS, Cham, Lecture Notes in Computer Science, vol. 10504, pp. 119-130, 10th International Symposium, L’Aquila, Italy, 12/09/2017. https://doi.org/10.1007/978-3-319-66700-3_10

APA

Hansen, K. A. (2017). The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. In V. Bilò, & M. Flammini (Eds.), Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017 (pp. 119-130). Springer VS. Lecture Notes in Computer Science, Vol.. 10504 https://doi.org/10.1007/978-3-319-66700-3_10

CBE

Hansen KA. 2017. The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. Bilò V, Flammini M, editors. In Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. Cham: Springer VS. pp. 119-130. (Lecture Notes in Computer Science, Vol. 10504). https://doi.org/10.1007/978-3-319-66700-3_10

MLA

Hansen, Kristoffer Arnsfelt "The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games". and Bilò, Vittorio Flammini, Michele (editors). Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. Cham: Springer VS. (Lecture Notes in Computer Science, Vol. 10504). 2017, 119-130. https://doi.org/10.1007/978-3-319-66700-3_10

Vancouver

Hansen KA. The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. In Bilò V, Flammini M, editors, Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. Cham: Springer VS. 2017. p. 119-130. (Lecture Notes in Computer Science, Vol. 10504). https://doi.org/10.1007/978-3-319-66700-3_10

Author

Hansen, Kristoffer Arnsfelt. / The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017. editor / Vittorio Bilò ; Michele Flammini. Cham : Springer VS, 2017. pp. 119-130 (Lecture Notes in Computer Science, Vol. 10504).

Bibtex

@inproceedings{a001541f639c427bbdd9147208e60a22,
title = "The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games",
abstract = "We show that for several solution concepts for finite n-player games, where n≥3, the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where n≥3, is also equivalent to the decision problem for the existential theory of the reals. Our results thus improve previous results of NP-hardness as well as SORT-SUM-hardness of the decision problems to completeness for ∃R, the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and {\v S}tefankovi{\v c} giving ∃R-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.",
author = "Hansen, {Kristoffer Arnsfelt}",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-66700-3_10",
language = "English",
isbn = "9783319666990",
series = "Lecture Notes in Computer Science",
publisher = "Springer VS",
pages = "119--130",
editor = "Vittorio Bil{\`o} and Michele Flammini",
booktitle = "Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings",
note = "10th International Symposium : International Symposium on Algorithmic Game Theory, SAGT 2017 ; Conference date: 12-09-2017 Through 14-12-2017",
url = "http://cs.gssi.infn.it/sagt2017/",

}

RIS

TY - GEN

T1 - The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games

AU - Hansen, Kristoffer Arnsfelt

N1 - Conference code: 10

PY - 2017/1/1

Y1 - 2017/1/1

N2 - We show that for several solution concepts for finite n-player games, where n≥3, the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where n≥3, is also equivalent to the decision problem for the existential theory of the reals. Our results thus improve previous results of NP-hardness as well as SORT-SUM-hardness of the decision problems to completeness for ∃R, the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and Štefankovič giving ∃R-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.

AB - We show that for several solution concepts for finite n-player games, where n≥3, the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where n≥3, is also equivalent to the decision problem for the existential theory of the reals. Our results thus improve previous results of NP-hardness as well as SORT-SUM-hardness of the decision problems to completeness for ∃R, the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and Štefankovič giving ∃R-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.

U2 - 10.1007/978-3-319-66700-3_10

DO - 10.1007/978-3-319-66700-3_10

M3 - Article in proceedings

SN - 9783319666990

T3 - Lecture Notes in Computer Science

SP - 119

EP - 130

BT - Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings

A2 - Bilò, Vittorio

A2 - Flammini, Michele

PB - Springer VS

CY - Cham

T2 - 10th International Symposium

Y2 - 12 September 2017 through 14 December 2017

ER -