Quadratic Programs and Some Constrained Stochastic Games

N. Hemachandra Indian Institute of Technology Industrial Engineering and Operations Research Powai Mumbai 40
Thursday, 12 May 2011 (all day)
A-212 (STCS Seminar Room)
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).