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