TY - JOUR

T1 - ∃ℝ-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:
An extended abstract of thiswork appeared in the proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP). This work is supported by NSF Grants CCF-0914732 and CCF-1216019.
Publisher Copyright:
© 2018 ACM.

PY - 2018/2

Y1 - 2018/2

N2 - As a result of a series of important works [7-9, 15, 23], the complexity of two-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 Štefankovic [28]: that checking whether a three-player Nash Equilibrium (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ∃ℝ-complete, where ∃ℝ is the class of decision problems that can be reduced in polynomial time to Existential Theory of the Reals. Building on their work, we show that the following decision versions of 3-Nash are also ∃ℝ-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 [25]. This yields ∃ℝ-completeness 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 a series of important works [7-9, 15, 23], the complexity of two-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 Štefankovic [28]: that checking whether a three-player Nash Equilibrium (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ∃ℝ-complete, where ∃ℝ is the class of decision problems that can be reduced in polynomial time to Existential Theory of the Reals. Building on their work, we show that the following decision versions of 3-Nash are also ∃ℝ-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 [25]. This yields ∃ℝ-completeness 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.

KW - Decision problems

KW - Existential theory of reals

KW - FIXP

KW - Nash equilibrium

KW - Symmetric games

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

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

U2 - 10.1145/3175494

DO - 10.1145/3175494

M3 - Article

AN - SCOPUS:85045356563

VL - 6

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

SN - 2167-8375

IS - 1

M1 - 1

ER -