NONLINEAR-PROGRAMMING AND STATIONARY EQUILIBRIA IN STOCHASTIC GAMES

Stationary equilibria in discounted and limiting average finite state/action space stochastic games are shown to be equivalent to global optima of certain nonlinear programs. For zero sum limiting average games, this formulation reduces to a linear objective, nonlinear constraints program, which finds the "best" stationary strategies, even when epsilon-optimal stationary strategies do not exist, for arbitrarily small epsilon.