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

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.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings : 10th International Symposium, SAGT 2017
EditorsVittorio Bilò, Michele Flammini
Number of pages12
Place of publicationCham
PublisherSpringer VS
Publication year1 Jan 2017
Pages119-130
ISBN (print)9783319666990
DOIs
Publication statusPublished - 1 Jan 2017
Event10th International Symposium: International Symposium on Algorithmic Game Theory - L’Aquila, Italy
Duration: 12 Sep 201714 Dec 2017
Conference number: 10
http://cs.gssi.infn.it/sagt2017/

Conference

Conference10th International Symposium
Nummer10
LandItaly
ByL’Aquila
Periode12/09/201714/12/2017
Internetadresse
SeriesLecture Notes in Computer Science
Volume10504
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 119329581