"On Nash Equilibria in Stochastic Games"
by Krishnendu Chatterjee, Rupak Majumdar, and Marcin Jurdzinski

We study infinite stochastic games played by $n$-players on a finite
graph with goals given by sets of infinite traces.
The games are {\em stochastic} (each player simultaneously and
independently chooses an action at each round, and the next state is
determined by a probability distribution depending on the current
state and the chosen actions), {\em infinite} (the game continues for
an infinite number of rounds), {\em nonzero sum} (the players' goals
are not necessarily conflicting), and undiscounted. 
We show that if each player has a reachability objective, that is, if
the goal for each player $i$ is to visit some subset $R_i$ of the
states, then there exists an $\epsilon$-Nash equilibrium in memoryless
strategies, for every $\epsilon >0$.  
However, exact Nash equilibria need not exist.
We study the complexity of finding such Nash equilibria, and show that
the payoff of some $\epsilon$-Nash equilibrium can be
$\epsilon$-approximated in NP. 

We study the important subclass of $n$-player {\em turn-based
probabilistic} games, where at each state atmost one player has a
nontrivial choice of moves. 
For turn-based probabilistic games, we show the existence of
$\epsilon$-Nash equilibria in pure strategies for games where the
objective of player $i$ is a {\em Borel} set $B_i$ of infinite traces.
However, exact Nash equilibria may not exist.
For the special case of $\omega$-regular objectives, we show exact
Nash equilibria exist, and can be computed in NP when the
$\omega$-regular objectives are expressed as parity objectives.