The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

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

doi:10.1007/978-3-662-44803-8_20

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

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

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

Abstract

We consider the task of computing an approximation of a
trembling hand perfect equilibrium for an n-player game in strategic form, n ≥ 3. We show that this task is complete for the complexity class FIXPa. In particular, the task is polynomial time equivalent to the task of computing an approximation of a Nash equilibrium in strategic form games with three (or more) players.

Original language	English
Title of host publication	Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings
Publisher	Springer
Pages	231-243
Number of pages	12
ISBN (Electronic)	978-3-662-44803-8
ISBN (Print)	978-3-662-44802-1
DOIs	https://doi.org/10.1007/978-3-662-44803-8_20
Publication status	Published - 2014
Event	SAGT 2014 - 7th International Symposium - Haifa, Israel Duration: 30 Sept 2014 → 2 Oct 2014

Conference

Conference	SAGT 2014 - 7th International Symposium
Country/Territory	Israel
City	Haifa
Period	30/09/14 → 2/10/14

Access to Document

10.1007/978-3-662-44803-8_20

Etessami Hansen ET AL 2014 The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multiplayer Game in Strategic FormAccepted author manuscript, 192 KB

http://dx.doi.org/10.1007/978-3-662-44803-8_20

Kousha Etessami
- koushainf.ed.acuk
- School of Informatics - Personal Chair in Algorithms, Games, Logic and Complexity
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active

Cite this

Etessami, K., Hansen, K. A., Miltersen, P. B., & Sørensen, T. B. (2014). The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. In Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings (pp. 231-243). Springer. https://doi.org/10.1007/978-3-662-44803-8_20

@inproceedings{d9c577d7fdc14802a1e058976f2863ee,

title = "The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form",

abstract = "We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n ≥ 3. We show that this task is complete for the complexity class FIXPa. In particular, the task is polynomial time equivalent to the task of computing an approximation of a Nash equilibrium in strategic form games with three (or more) players.",

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

year = "2014",

doi = "10.1007/978-3-662-44803-8\_20",

language = "English",

isbn = "978-3-662-44802-1",

pages = "231--243",

booktitle = "Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings",

publisher = "Springer",

address = "United Kingdom",

note = "SAGT 2014 - 7th International Symposium ; Conference date: 30-09-2014 Through 02-10-2014",

}

Etessami, K, Hansen, KA, Miltersen, PB & Sørensen, TB 2014, The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. in Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings. Springer, pp. 231-243, SAGT 2014 - 7th International Symposium, Haifa, Israel, 30/09/14. https://doi.org/10.1007/978-3-662-44803-8_20

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. / Etessami, Kousha; Hansen, Kristoffer Arnsfelt; Miltersen, Peter Bro et al.
Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings. Springer, 2014. p. 231-243.

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

TY - GEN

T1 - The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

AU - Etessami, Kousha

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

PY - 2014

Y1 - 2014

N2 - We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n ≥ 3. We show that this task is complete for the complexity class FIXPa. In particular, the task is polynomial time equivalent to the task of computing an approximation of a Nash equilibrium in strategic form games with three (or more) players.

AB - We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n ≥ 3. We show that this task is complete for the complexity class FIXPa. In particular, the task is polynomial time equivalent to the task of computing an approximation of a Nash equilibrium in strategic form games with three (or more) players.

U2 - 10.1007/978-3-662-44803-8_20

DO - 10.1007/978-3-662-44803-8_20

M3 - Conference contribution

SN - 978-3-662-44802-1

SP - 231

EP - 243

BT - Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings

PB - Springer

T2 - SAGT 2014 - 7th International Symposium

Y2 - 30 September 2014 through 2 October 2014

ER -

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

Abstract

Conference

Access to Document

Fingerprint

Profiles

Kousha Etessami

Cite this