Quadratic Programs and Some Constrained Stochastic Games

We consider two player non-zero sum discounted cost single controller stochastic games. For such a player two controlled stochastic game, suppose, player one has subscription type constraints and player two has realization based constraints that do not depend on first player's strategies. We show that Nash equilibria of such constrained stochastic games are in one-to-one correspondence with global minima of certain non-convex quadratic programs. We show similar results for separable reward and state independent stochastic games with subscription type constraints. Nash equilibria for the above games can be computed in finite number of steps using the available algorithms for computing global minima of non-convex QPs (joint work with Vikas Vikram Singh).