Stochastic game

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 processes and repeated games.

Two-player games

Stochastic two-player games on directed graphs are widely used for modeling and analysis of discrete systems operating in an unknown (adversarial) environment. Possible configurations of a system and its environment are represented as vertices, and the transitions correspond to actions of the system, its environment, or "nature". A run of the system then corresponds to an infinite path in the graph. Thus, a system and its environment can be seen as two players with antagonistic objectives, where one player (the system) aims at maximizing the probability of "good" runs, while the other player (the environment) aims at the opposite.

In many cases, there exists an equilibrium value of this probability, but optimal strategies for both players may not exist.

We introduce basic concepts and algorithmic questions studied in this area, and we mention some long-standing open problems. Then, we mention selected recent results.

Theory

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

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

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

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

The "undiscounted" game $\Gamma_\infty$ is the game where the payoff to player $i$ is the "limit" of the averages of the stage payoffs. Some precautions are needed in defining the value of a two-person zero-sum $\Gamma_{\infty}$ and in defining equilibrium payoffs of a non-zero-sum $\Gamma_{\infty}$ . The uniform value $v_{\infty}$ of a two-person zero-sum stochastic game $\Gamma_\infty$ exists if for every $\varepsilon>0$ there is a positive integer $N$ and a strategy pair $\sigma_{\varepsilon}$ of player 1 and $\tau_{\varepsilon}$ of player 2 such that for every $\sigma$ and $\tau$ and every $n\geq N$ the expectation of $\bar{g}^i_n$ with respect to the probability on plays defined by $\sigma_{\varepsilon}$ and $\tau$ is at least $v_{\infty} -\varepsilon$ , and the expectation of $\bar{g}^i_n$ with respect to the probability on plays defined by $\sigma$ and $\tau_{\varepsilon}$ is at most $v_{\infty} +\varepsilon$ . 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.

The non-zero-sum stochastic game $\Gamma_\infty$ has a uniform equilibrium payoff $v_{\infty}$ if for every $\varepsilon>0$ there is a positive integer $N$ and a strategy profile $\sigma$ such that for every unilateral deviation by a player $i$ , i.e., a strategy profile $\tau$ with $\sigma^j=\tau^j$ for all $j\neq i$ , and every $n\geq N$ the expectation of $\bar{g}^i_n$ with respect to the probability on plays defined by $\sigma$ is at least $v^i_{\infty} -\varepsilon$ , and the expectation of $\bar{g}^i_n$ with respect to the probability on plays defined by $\tau$ is at most $v^i_{\infty} +\varepsilon$ . Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a uniform equilibrium payoff.

The non-zero-sum stochastic game $\Gamma_\infty$ has a limiting-average equilibrium payoff $v_{\infty}$ if for every $\varepsilon>0$ there is a strategy profile $\sigma$ such that for every unilateral deviation by a player $i$ , the expectation of the limit inferior of the averages of the stage payoffs with respect to the probability on plays defined by $\sigma$ is at least $v^i_{\infty} -\varepsilon$ , and the expectation of the limit superior of the averages of the stage payoffs with respect to the probability on plays defined by $\tau$ is at most $v^i_{\infty} +\varepsilon$ . Jean-François Mertens and Abraham Neyman (1981) proves that every two-person zero-sum stochastic game with finitely many states and actions has a limiting-average value, and Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a limiting-average equilibrium payoff. In particular, these results imply that these games have a value and an approximate equilibrium payoff, called the liminf-average (respectively, the limsup-average) equilibrium payoff, when the total payoff is the limit inferior (or the limit superior) of the averages of the stage payoffs.

Whether every stochastic game with finitely many players, states, and actions, has a uniform equilibrium payoff, or a limiting-average equilibrium payoff, or even a liminf-average equilibrium payoff, 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.^[1] They are generalizations of repeated games 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 Processes and two-person stochastic games. They coin the term Competitive MDPs to encompass both one- and two-player stochastic games.

External links

Lecture on Stochastic Two-Player Games by Antonin Kucera

Notes

↑ Constrained Stochastic Games in Wireless Networks by E.Altman, K.Avratchenkov, N.Bonneau, M.Debbah, R.El-Azouzi, D.S.Menasche

Condon, A. (1992). "The complexity of stochastic games". Information and Computation 96: 203–224. doi:10.1016/0890-5401(92)90048-K.
H. Everett (1957). "Recursive games". In Melvin Dresher, Albert William Tucker, Philip Wolfe. Contributions to the Theory of Games, Volume 3. Annals of Mathematics Studies. Princeton University Press. pp. 67–78. ISBN 978-0-691-07936-3. (Reprinted in Harold W. Kuhn, ed. Classics in Game Theory, Princeton University Press, 1997. ISBN 978-0-691-01192-9).
Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag. ISBN 0-387-94805-8.
Mertens, J. F. & Neyman, A. (1981). "Stochastic Games". International Journal of Game Theory 10 (2): 53–66. doi:10.1007/BF01769259.
Neyman, A. & Sorin, S. (2003). "Stochastic Games and Applications". Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9.
Shapley, L. S. (1953). "Stochastic games". PNAS 39 (10): 1095–1100. doi:10.1073/pnas.39.10.1095.
Vieille, N. (2002). "Stochastic games: Recent results". Handbook of Game Theory. Amsterdam: Elsevier Science. pp. 1833–1850. ISBN 0-444-88098-4.
Yoav Shoham; Kevin Leyton-Brown (2009). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7. (suitable for undergraduates; main results, no proofs)

Topics in game theory

Definitions	Normal-form game Extensive-form game Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian-Nash Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Cake cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Screening game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Kenneth Arrow Robert Aumann Kenneth Binmore Samuel Bowles Melvin Dresher Merrill M. Flood Drew Fudenberg Donald B. Gillies John Harsanyi Leonid Hurwicz David K. Levine Daniel Kahneman David M. Kreps Harold W. Kuhn Eric Maskin Jean-François Mertens Paul Milgrom Oskar Morgenstern Roger Myerson John Nash John von Neumann Ariel Rubinstein Thomas Schelling Reinhard Selten Herbert Simon Lloyd Shapley John Maynard Smith Jean Tirole Albert W. Tucker Amos Tversky William Vickrey Robert B. Wilson Peyton Young

See also	Tragedy of the commons Tyranny of small decisions All-pay auction List of games in game theory Confrontation analysis List of game theorists Combinatorial game theory Alpha–beta pruning Bertrand paradox Bounded rationality No-win situation