The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form

Autor:	Etessami, Kousha, Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Sorensen, Troels Bjerre
Rok vydání:	2014
Předmět:	Computer Science - Computer Science and Game Theory Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	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. Comment: conference version to appear at SAGT'14
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1408.1017 Zobrazit plný text záznamu View this record from Arxiv