The computational complexity of trembling hand perfection and other equilibrium refinements

Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre Sørensen

doi:10.1007/978-3-642-16170-4_18

The computational complexity of trembling hand perfection and other equilibrium refinements

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Konferenceartikel › Forskning › peer review

Abstract

The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB.
The proofs all use a reduction from the problem of comparing the minmax value of a three-player game in strategic form to a given rational number. This problem was previously shown to be NP-hard by Borgs et al., while a Sqrt-Sum hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a three-player game that may be of independent interest.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Vol/bind	6386
Sider (fra-til)	198-209
Antal sider	12
ISSN	0302-9743
DOI	https://doi.org/10.1007/978-3-642-16170-4_18
Status	Udgivet - 2010
Begivenhed	Algorithmic Game Theory, Third International Symposium - Athen, Grækenland Varighed: 18 okt. 2010 → 20 okt. 2010 Konferencens nummer: 3

Konference

Konference	Algorithmic Game Theory, Third International Symposium
Nummer	3
Land/Område	Grækenland
By	Athen
Periode	18/10/2010 → 20/10/2010

Adgang til dokumentet

10.1007/978-3-642-16170-4_18

Citationsformater

@inproceedings{927c68c0dd3b11dfa891000ea68e967b,

title = "The computational complexity of trembling hand perfection and other equilibrium refinements",

abstract = "The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB. The proofs all use a reduction from the problem of comparing the minmax value of a three-player game in strategic form to a given rational number. This problem was previously shown to be NP-hard by Borgs et al., while a Sqrt-Sum hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a three-player game that may be of independent interest. ",

author = "Hansen, {Kristoffer Arnsfelt} and Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

note = "Title of the vol.: Algorithmic Game Theory, international Symposium, SAGT. Proceedings. / Spyros Kontogiannis, Elias Koutsoupias and Paul G. Spirakis (eds.) ISBN: 978-3-642-16169-8; Algorithmic Game Theory, Third International Symposium ; Conference date: 18-10-2010 Through 20-10-2010",

year = "2010",

doi = "10.1007/978-3-642-16170-4_18",

language = "English",

volume = "6386",

pages = "198--209",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

The computational complexity of trembling hand perfection and other equilibrium refinements. / Hansen, Kristoffer Arnsfelt ; Miltersen, Peter Bro; Sørensen, Troels Bjerre.
I: Lecture Notes in Computer Science, Bind 6386, 2010, s. 198-209.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Konferenceartikel › Forskning › peer review

TY - GEN

T1 - The computational complexity of trembling hand perfection and other equilibrium refinements

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 3

PY - 2010

Y1 - 2010

N2 - The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB. The proofs all use a reduction from the problem of comparing the minmax value of a three-player game in strategic form to a given rational number. This problem was previously shown to be NP-hard by Borgs et al., while a Sqrt-Sum hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a three-player game that may be of independent interest.

AB - The king of refinements of Nash equilibrium is trembling hand perfection. We show that it is NP-hard and Sqrt-Sum-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. Analogous results are shown for a number of other solution concepts, including proper equilibrium, (the strategy part of) sequential equilibrium, quasi-perfect equilibrium and CURB. The proofs all use a reduction from the problem of comparing the minmax value of a three-player game in strategic form to a given rational number. This problem was previously shown to be NP-hard by Borgs et al., while a Sqrt-Sum hardness result is given in this paper. The latter proof yields bounds on the algebraic degree of the minmax value of a three-player game that may be of independent interest.

U2 - 10.1007/978-3-642-16170-4_18

DO - 10.1007/978-3-642-16170-4_18

M3 - Conference article

SN - 0302-9743

VL - 6386

SP - 198

EP - 209

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Algorithmic Game Theory, Third International Symposium

Y2 - 18 October 2010 through 20 October 2010

ER -

The computational complexity of trembling hand perfection and other equilibrium refinements

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater