On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games

We study the problem of computing stationary Nash equilibria in discounted perfect information stochastic games from the viewpoint of computational complexity. For two-player games we prove the problem to be in PPAD, which together with a previous PPAD-hardness result precisely classifies the problem as PPAD-complete. In addition to this we give an improved and simpler PPAD-hardness proof for computing a stationary epsilon-Nash equilibrium. For 3-player games we construct games showing that rational-valued stationary Nash equilibria are not guaranteed to exist, and we use these to prove SqrtSum-hardness of computing a stationary Nash equilibrium in 4-player games.