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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

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

In: Theory of Computing Systems, Vol. 63, No. 7, 10.2019, p. 1554-1571.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@article{6880e8d96c414718a4f61ebadd673f6b,
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 of perfect recall. 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 SQRT-SUM-hardness of the decision problems to completeness for there exists 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 Stefankovic giving there exists R-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.",
keywords = "Computational complexity, Existential theory of the reals, Minmax value, Nash equilibrium refinements",
author = "Hansen, {Kristoffer Arnsfelt}",
note = "A preliminary version [23] of this paper appeared in the proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT 2017). This article is part of the Topical Collection on Special Issue on Algorithmic Game Theory (SAGT 2017)",
year = "2019",
month = oct,
doi = "10.1007/s00224-018-9887-9",
language = "English",
volume = "63",
pages = "1554--1571",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York LLC",
number = "7",

}

RIS

TY - JOUR

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

AU - Hansen, Kristoffer Arnsfelt

N1 - A preliminary version [23] of this paper appeared in the proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT 2017). This article is part of the Topical Collection on Special Issue on Algorithmic Game Theory (SAGT 2017)

PY - 2019/10

Y1 - 2019/10

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 of perfect recall. 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 SQRT-SUM-hardness of the decision problems to completeness for there exists 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 Stefankovic giving there exists 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 of perfect recall. 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 SQRT-SUM-hardness of the decision problems to completeness for there exists 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 Stefankovic giving there exists R-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.

KW - Computational complexity

KW - Existential theory of the reals

KW - Minmax value

KW - Nash equilibrium refinements

UR - http://www.scopus.com/inward/record.url?scp=85053665772&partnerID=8YFLogxK

U2 - 10.1007/s00224-018-9887-9

DO - 10.1007/s00224-018-9887-9

M3 - Journal article

AN - SCOPUS:85053665772

VL - 63

SP - 1554

EP - 1571

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 7

ER -