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 proceedingConference 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 languageEnglish
Title of host publicationAlgorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages231-243
Number of pages12
ISBN (Electronic)978-3-662-44803-8
ISBN (Print)978-3-662-44802-1
DOIs
Publication statusPublished - 2014
EventSAGT 2014 - 7th International Symposium - Haifa, Israel
Duration: 30 Sep 20142 Oct 2014

Conference

ConferenceSAGT 2014 - 7th International Symposium
Country/TerritoryIsrael
CityHaifa
Period30/09/142/10/14

Fingerprint

Dive into the research topics of 'The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form'. Together they form a unique fingerprint.

Cite this