  We study the complexity of computing stationary Nash equilibrium (NE) in
n-player infinite-horizon general-sum stochastic games. We focus on the problem
of computing NE in such stochastic games when each player is restricted to
choosing a stationary policy and rewards are discounted. First, we prove that
computing such NE is in PPAD (in addition to clearly being PPAD-hard). Second,
we consider turn-based specializations of such games where at each state there
is at most a single player that can take actions and show that these
(seemingly-simpler) games remain PPAD-hard. Third, we show that under further
structural assumptions on the rewards computing NE in such turn-based games is
possible in polynomial time. Towards achieving these results we establish
structural facts about stochastic games of broader utility, including
monotonicity of utilities under single-state single-action changes and
reductions to settings where each player controls a single state.
