View source for Skoda–El Mir theorem

In [[game theory]], a '''stochastic game''', introduced by [[Lloyd Shapley]] in the early 1950s, is a dynamic game with '''probabilistic transitions''' played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some '''state'''. The players select actions and each player receives a '''payoff''' that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.

Stochastic games generalize both [[Markov decision process]]es and [[repeated game]]s.

==Theory==
The ingredients of a stochastic game are: a finite set of players <math>I</math>; a state space <math>M</math> (either a finite set or a measurable space <math>(M,{\mathcal A})</math>); for each player <math>i\in I</math>, an action set <math>S^i</math>
(either a finite set or a measurable space <math>(S^i,{\mathcal S}^i)</math>); a transition probability <math>P</math> from <math>M\times S</math>, where <math>S=\times_{i\in I}S^i</math> is the action profiles, to <math>M</math>, where <math>P(A \mid m, s)</math> is the probability that the next state is in <math>A</math> given the current state <math>m</math> and the current action profile <math>s</math>; and a payoff function <math>g</math> from <math>M\times S</math> to <math>R^I</math>, where the <math>i</math>-th coordinate of <math>g</math>, <math>g^i</math>, is the payoff to player <math>i</math> as a function of the state <math>m</math> and the action profile <math>s</math>.

The game starts at some initial state <math>m_1</math>. At stage <math>t</math>, players  first observe <math>m_t</math>, then simultaneously choose actions <math>s^i_t\in S^i</math>, then observe the action profile <math>s_t=(s^i_t)_i</math>, and then nature selects <math>m_{t+1}</math> according to the probability <math>P(\cdot\mid m_t,s_t)</math>. A play of the stochastic game, <math>m_1,s_1,\ldots,m_t,s_t,\ldots</math>,
defines a stream of payoffs <math>g_1,g_2,\ldots</math>, where <math>g_t=g(m_t,s_t)</math>.

The discounted game <math>\Gamma_\lambda</math> with discount factor <math>\lambda </math> (<math>0<\lambda \leq 1</math>) is the game where the payoff to player <math>i</math> is <math>\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^i_t</math>. The <math>n</math>-stage game
is the game where the payoff to player <math>i</math> is <math>\bar{g}^i_n:=\frac1n\sum_{t=1}^ng^i_t</math>.

The value <math>v_n(m_1)</math>, respectively <math>v_{\lambda}(m_1)</math>, of a two-person zero-sum stochastic game <math>\Gamma_n</math>, respectively <math>\Gamma_{\lambda}</math>, with finitely many states and actions exists, and  [[Truman Bewley]] and [[Elon Kohlberg]] (1976) proved that <math>v_n(m_1)</math> converges to a limit as <math>n</math> goes to infinity and that <math>v_{\lambda}(m_1)</math> converges to the same limit as <math>\lambda</math> goes to <math>0</math>.

The "undiscounted" game  <math>\Gamma_\infty</math> is the game where the payoff to player <math>i</math> is the "limit" of the averages of the stage payoffs. Some precautions are needed in defining the value of a two-person zero-sum <math>\Gamma_{\infty}</math> and in defining equilibrium payoffs of a non-zero-sum <math>\Gamma_{\infty}</math>. The uniform value <math>v_{\infty}</math> of a two-person zero-sum stochastic game <math>\Gamma_\infty</math> exists if  for every <math>\varepsilon>0</math> there is a positive integer <math>N</math>  and a strategy pair <math>\sigma_{\varepsilon}</math> of player 1 and <math>\tau_{\varepsilon}</math> of player 2 such that for every <math>\sigma</math> and <math>\tau</math> and every <math>n\geq N</math>  the expectation of <math>\bar{g}^i_n</math> with respect to the probability on plays defined by <math>\sigma_{\varepsilon} </math> and <math>\tau</math> is at least <math>v_{\infty} -\varepsilon </math>, and the expectation of <math>\bar{g}^i_n</math> with respect to the probability on plays defined by <math>\sigma </math> and  <math>\tau_{\varepsilon}</math> is at most <math>v_{\infty} +\varepsilon </math>. [[Jean-François Mertens]] and [[Abraham Neyman]] (1981) proved that every two-person zero-sum stochastic game with finitely many states and actions has a uniform value.

If there is a finite number of players and the action sets and the set of states are finite, then a stochastic game with a finite number of stages always has a [[Nash equilibrium]]. The same is true for a game with infinitely many stages if the total payoff is the discounted sum. [[Nicolas Vieille]] has shown that all two-person stochastic games with finite state and action spaces have
[[Epsilon-equilibrium|approximate Nash equilibria]] when the total payoff is the limit inferior of the averages of the stage payoffs. Whether such equilibria exist when there are more than two players is a challenging open question.

A [[Markov perfect equilibrium]] is a refinement of the concept of [[sub-game perfect Nash equilibrium]] to stochastic games..

==Applications==
Stochastic games have applications in economics, evolutionary biology and computer networks.<ref>[http://www-net.cs.umass.edu/~sadoc/mdp/main.pdf Constrained Stochastic Games in Wireless Networks] by E.Altman, K.Avratchenkov, N.Bonneau, M.Debbah, R.El-Azouzi, D.S.Menasche</ref>  They are generalizations of [[repeated game]]s which correspond to the special case where there is only one state.

==Referring book==
The most complete reference is the book of articles edited by Neyman and Sorin. The more elementary book of Filar and Vrieze provides a unified rigorous treatment of the theories of [[Markov Decision Process]]es and two-person stochastic games. They coin the term Competitive MDPs to encompass both one- and two-player stochastic games.

==Notes==
{{reflist}}

==Further reading==
*{{cite journal |first=A. |last=Condon|authorlink=Anne Condon |title=The complexity of stochastic games |journal=Information and Computation |volume=96 |issue= |pages=203–224 |year=1992 |doi=10.1016/0890-5401(92)90048-K }}
* {{cite book|author=H. Everett|authorlink=Hugh Everett III |pages=67–78|
chapter=Recursive games|title=Contributions to the Theory of Games, Volume 3|series=Annals of Mathematics Studies|
editors=Melvin Dresher, [[Albert W. Tucker|Albert William Tucker]], [[Philip Wolfe (mathematician)|Philip Wolfe]]|publisher=Princeton University Press|year=1957|isbn=0-691-07936-6, ISBN 978-0-691-07936-3|id=(Reprinted in [[Harold W. Kuhn]], ed. ''Classics in Game Theory'', Princeton University Press, 1997. ISBN 978-0-691-01192-9)}}
*{{cite book |first=J. |last=Filar |lastauthoramp=yes |first2=K. |last2=Vrieze |title=Competitive Markov Decision Processes |location= |publisher=Springer-Verlag |year=1997 |isbn=0-387-94805-8 }}
*{{cite journal |first=J. F. |last=Mertens |lastauthoramp=yes |first2=A. |last2=Neyman |title=Stochastic Games |journal=International Journal of Game Theory |volume=10 |issue=2 |pages=53–66 |year=1981 |doi=10.1007/BF01769259 }}
*{{cite journal |first=A. |last=Neyman |lastauthoramp=yes |first2=S. |last2=Sorin |title=Stochastic Games and Applications |location=Dordrecht |publisher=Kluwer Academic Press |year=2003 |isbn=1-4020-1492-9 }}
*{{cite journal |first=L. S. |last=Shapley |title=Stochastic games |journal=[[Proceedings of the National Academy of Sciences|PNAS]] |volume=39 |issue=10 |pages=1095–1100 |year=1953  |url=http://www.pnas.org/content/39/10/1095 |doi=10.1073/pnas.39.10.1095}}
*{{cite book |first=N. |last=Vieille |chapter=Stochastic games: Recent results |title=Handbook of Game Theory |pages=1833–1850 |location=Amsterdam |publisher=Elsevier Science |year=2002 |isbn=0-444-88098-4 }}
* {{cite book|author1=Yoav Shoham|author2=Kevin Leyton-Brown|title=Multiagent systems: algorithmic, game-theoretic, and logical foundations|year=2009|publisher=Cambridge University Press|isbn=978-0-521-89943-7|pages=153–156}} (suitable for undergraduates; main results, no proofs)

{{Game theory}}

{{DEFAULTSORT:Stochastic Game}}
[[Category:Game theory]]