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

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: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

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 FIXP_a. 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
Book series	Lecture Notes in Computer Science
Volume	8768
Pages (from-to)	231-243
Number of pages	12
ISSN	0302-9743
Publication status	Published - 2014

Keywords

trembling hand perfect equilibrium
n-player game
FIXP_a complexity
Nash equilibrium approximation
strategic form games

Cite this

@article{3ef73faa47004be7a9d31958327cd275,

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 FIXP_a. 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.",

keywords = "trembling hand perfect equilibrium, n-player game, FIXP_a complexity, Nash equilibrium approximation, strategic form games",

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

year = "2014",

language = "English",

volume = "8768",

pages = "231--243",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

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 FIXP_a. 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 FIXP_a. 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.

KW - trembling hand perfect equilibrium

KW - n-player game

KW - FIXP_a complexity

KW - Nash equilibrium approximation

KW - strategic form games

M3 - Journal article

SN - 0302-9743

VL - 8768

SP - 231

EP - 243

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

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

Abstract

Keywords

Fingerprint

Cite this