On the hardness and existence of quasi-strict equilibria

Felix Brandt; Felix Fischer

doi:10.1007/978-3-540-79309-0_26

On the hardness and existence of quasi-strict equilibria

Felix Brandt, Felix Fischer

University of Munich

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove that deciding the existence of a quasi-strict equilibrium in games with more than two players is NP-complete. We further show that, in contrast to Nash equilibrium, the support of quasi-strict equilibrium in zero-sum games is unique and propose a linear program to compute quasi-strict equilibria in these games. Finally, we prove that every symmetric multi-player game where each player has two actions at his disposal contains an efficiently computable quasi-strict equilibrium which may itself be asymmetric.

Original language	English
Title of host publication	Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings
Pages	291-302
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-79309-0_26
State	Published - 2008
Externally published	Yes
Event	1st International Symposium on Algorithmic Game Theory, SAGT 2008 - Paderborn, Germany Duration: 30 Apr 2008 → 2 May 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4997 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Symposium on Algorithmic Game Theory, SAGT 2008
Country/Territory	Germany
City	Paderborn
Period	30/04/08 → 2/05/08

Access to Document

10.1007/978-3-540-79309-0_26

Cite this

Brandt, F., & Fischer, F. (2008). On the hardness and existence of quasi-strict equilibria. In Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings (pp. 291-302). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4997 LNCS). https://doi.org/10.1007/978-3-540-79309-0_26

@inproceedings{38366693253c4a29a1ea854c95eef463,

title = "On the hardness and existence of quasi-strict equilibria",

abstract = "This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove that deciding the existence of a quasi-strict equilibrium in games with more than two players is NP-complete. We further show that, in contrast to Nash equilibrium, the support of quasi-strict equilibrium in zero-sum games is unique and propose a linear program to compute quasi-strict equilibria in these games. Finally, we prove that every symmetric multi-player game where each player has two actions at his disposal contains an efficiently computable quasi-strict equilibrium which may itself be asymmetric.",

author = "Felix Brandt and Felix Fischer",

note = "Funding Information: This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-2.; 1st International Symposium on Algorithmic Game Theory, SAGT 2008 ; Conference date: 30-04-2008 Through 02-05-2008",

year = "2008",

doi = "10.1007/978-3-540-79309-0_26",

language = "English",

isbn = "3540793089",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "291--302",

booktitle = "Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings",

}

Brandt, F & Fischer, F 2008, On the hardness and existence of quasi-strict equilibria. in Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4997 LNCS, pp. 291-302, 1st International Symposium on Algorithmic Game Theory, SAGT 2008, Paderborn, Germany, 30/04/08. https://doi.org/10.1007/978-3-540-79309-0_26

On the hardness and existence of quasi-strict equilibria. / Brandt, Felix; Fischer, Felix.
Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings. 2008. p. 291-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4997 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the hardness and existence of quasi-strict equilibria

AU - Brandt, Felix

AU - Fischer, Felix

N1 - Funding Information: This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grant BR 2312/3-2.

PY - 2008

Y1 - 2008

N2 - This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove that deciding the existence of a quasi-strict equilibrium in games with more than two players is NP-complete. We further show that, in contrast to Nash equilibrium, the support of quasi-strict equilibrium in zero-sum games is unique and propose a linear program to compute quasi-strict equilibria in these games. Finally, we prove that every symmetric multi-player game where each player has two actions at his disposal contains an efficiently computable quasi-strict equilibrium which may itself be asymmetric.

AB - This paper investigates the computational properties of quasi-strict equilibrium, an attractive equilibrium refinement proposed by Harsanyi, which was recently shown to always exist in bimatrix games. We prove that deciding the existence of a quasi-strict equilibrium in games with more than two players is NP-complete. We further show that, in contrast to Nash equilibrium, the support of quasi-strict equilibrium in zero-sum games is unique and propose a linear program to compute quasi-strict equilibria in these games. Finally, we prove that every symmetric multi-player game where each player has two actions at his disposal contains an efficiently computable quasi-strict equilibrium which may itself be asymmetric.

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

U2 - 10.1007/978-3-540-79309-0_26

DO - 10.1007/978-3-540-79309-0_26

M3 - Conference contribution

AN - SCOPUS:44449101633

SN - 3540793089

SN - 9783540793083

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 302

BT - Algorithmic Game Theory - First International Symposium, SAGT 2008, Proceedings

T2 - 1st International Symposium on Algorithmic Game Theory, SAGT 2008

Y2 - 30 April 2008 through 2 May 2008

ER -

On the hardness and existence of quasi-strict equilibria

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this