ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria

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_{\infty }$$

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 ETR-completeness for symmetric 3-Nash for the last two problems stated above as well as completeness for the class

$$\rm {FIXP_a}$$

FIXP

a

, a variant of FIXP for strong approximation. All our results extend to

k

-Nash, for any constant

$$k \ge 3$$

k

≥

3

.