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

Algorithms

Aarhus Universitet
University of Edinburgh

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Vol/bind	8768
Sider (fra-til)	231-243
Antal sider	12
ISSN	0302-9743
Status	Udgivet - 2014

Emneord

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

Citationsformater

@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, 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",

}

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.
I: Lecture Notes in Computer Science, Bind 8768, 2014, s. 231-243.

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

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 -

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

Abstract

Emneord

Fingeraftryk

Citationsformater