Some algorithmic results on two-person zero-sum limit average payoff stochastic games

Besides their mathematical beauty, this class of games have found numerous applications in different areas. The existence of $\eps$-equilibria, that is, a pair of strategies of the players, such that a deviating player would not be better off by more than
$\eps$, is already known from the 80's. Moreover, for several interesting classes, there exist optimal strategies that do not depend on the history of the play, the so-called stationary strategies. Nevertheless, the computational complexity of finding such equilibria, even in the simplest cases, remains an outstanding open problem.

In general locally optimal strategies played independently at each state are not globally optimal. A natural question therefore arises: Is it possible to apply potential transformations (which do not change value of the game) such that, in the transformed game, each player can apply a locally optimal strategy at each state and yet still guarantee global optimality? It turns out that this is indeed the case in a very general setting. I will give a sketch of these results, and some of their algorithmic consequences in deriving approximation schemes and smoothed complexity for the class of stochastic games with perfect information.