∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria

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