TY - GEN

T1 - ETR-completeness for decision versions of multi-player (Symmetric) nash equilibria

AU - Garg, Jugal

AU - Mehta, Ruta

AU - Vazirani, Vijay V.

AU - Yazdanbod, Sadra

N1 - Funding Information:
Supported by NSF Grants CCF-0914732 and CCF-1216019.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - As a result of some important works [4–6, 10, 15], the complexity of 2-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player games, when equilibria with special properties are desired, the only result known is due to Schaefer and Štefankovič [18]: that checking whether a 3-player NE (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ETR-complete, where ETR is the class Existential Theory of Reals. Building on their work, we show that the following decision versions of 3-Nash are also ETR-complete: checking whether (i) there are two or more equilibria, (ii) there exists an equilibrium in which each player gets at least h payoff, where h is a rational number, (iii) a given set of strategies are played with non-zero probability, and (iv) all the played strategies belong to a given set. Next, we give a reduction from 3-Nash to symmetric 3-Nash, hence resolving an open problem of Papadimitriou [14]. This yields ETRcompleteness for symmetric 3-Nash for the last two problems stated above as well as completeness for the class FIXPa, a variant of FIXP for strong approximation. All our results extend to k-Nash, for any constant k ≥ 3.

AB - As a result of some important works [4–6, 10, 15], the complexity of 2-player Nash equilibrium is by now well understood, even when equilibria with special properties are desired and when the game is symmetric. However, for multi-player games, when equilibria with special properties are desired, the only result known is due to Schaefer and Štefankovič [18]: that checking whether a 3-player NE (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ETR-complete, where ETR is the class Existential Theory of Reals. Building on their work, we show that the following decision versions of 3-Nash are also ETR-complete: checking whether (i) there are two or more equilibria, (ii) there exists an equilibrium in which each player gets at least h payoff, where h is a rational number, (iii) a given set of strategies are played with non-zero probability, and (iv) all the played strategies belong to a given set. Next, we give a reduction from 3-Nash to symmetric 3-Nash, hence resolving an open problem of Papadimitriou [14]. This yields ETRcompleteness for symmetric 3-Nash for the last two problems stated above as well as completeness for the class FIXPa, a variant of FIXP for strong approximation. All our results extend to k-Nash, for any constant k ≥ 3.

UR - http://www.scopus.com/inward/record.url?scp=84950114411&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950114411&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-47672-7_45

DO - 10.1007/978-3-662-47672-7_45

M3 - Conference contribution

AN - SCOPUS:84950114411

SN - 9783662476710

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 554

EP - 566

BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings

A2 - Halldorsson, Magnus M.

A2 - Kobayashi, Naoki

A2 - Speckmann, Bettina

A2 - Iwama, Kazuo

PB - Springer

T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015

Y2 - 6 July 2015 through 10 July 2015

ER -