Polynomial stochastic games via sum of squares optimization

Stochastic games are an important class of games that generalize Markov decision processes to game theoretic scenarios. We consider finite state two-player zero-sum stochastic games over an infinite time horizon with discounted rewards. The players are assumed to have infinite strategy spaces and th...

Full description

Saved in:
Bibliographic Details
Main Authors: Shah, P., Parrilo, P.A.
Format: Conference Proceeding
Language:English
Subjects:
Game theory
Linear programming
Minimax techniques
Nash equilibrium
Polynomials
Power system modeling
Space technology
State-space methods
Stochastic processes
USA Councils
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Stochastic games are an important class of games that generalize Markov decision processes to game theoretic scenarios. We consider finite state two-player zero-sum stochastic games over an infinite time horizon with discounted rewards. The players are assumed to have infinite strategy spaces and the payoffs are assumed to be polynomials. In this paper we restrict our attention to a very special class of games for which the single-controller assumption holds. It is shown that minimax equilibria and optimal strategies for such games may be obtained via semidefinite programming.
ISSN:0191-2216
DOI:10.1109/CDC.2007.4434492