Stochastic game
In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a repeated 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 Markov decision processes to multiple interacting decision makers, as well as strategic-form games to dynamic situations in which the environment changes in response to the players’ choices. 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 formula_1; a state space formula_2 (either a finite set or a measurable space formula_3); for each player formula_4, an action set formula_5 (either a finite set or a measurable space formula_6); a transition probability formula_7 from formula_8, where formula_9 is the action profiles, to formula_2, where formula_11 is the probability that the next state is in formula_12 given the current state formula_13 and the current action profile  formula_14; and a payoff function formula_15 from formula_8 to formula_17, where the formula_18-th coordinate of formula_15, formula_20, is the payoff to player formula_18 as a function of the state formula_13 and the action profile formula_14. The game starts at some initial state formula_24. At stage formula_25, players first observe formula_26, then simultaneously choose actions formula_27, then observe the action profile formula_28, and then nature selects formula_29 according to the probability formula_30. A play of the stochastic game, formula_31, defines a stream of payoffs formula_32, where formula_33. The discounted game formula_34 with discount factor formula_35 (formula_36) is the game where  the payoff to player formula_18 is formula_38. The formula_39-stage game is the game where the payoff to player formula_18 is formula_41. The value formula_42, respectively formula_43, of a two-person zero-sum stochastic game formula_44, respectively formula_45, with finitely many states and actions exists, and Truman Bewley and Elon Kohlberg (1976) proved that formula_42 converges to a limit as formula_39 goes to infinity and that formula_43 converges to the same limit as formula_49 goes to formula_50. The "undiscounted" game formula_51 is the game where the payoff to player formula_18 is the "limit" of the averages of the stage payoffs . Some precautions are needed in defining the value of a two-person zero-sum formula_53 and in defining equilibrium payoffs of a non-zero-sum formula_53. The uniform value formula_55 of a two-person zero-sum stochastic game formula_51 exists if for every formula_57 there is a positive integer formula_58 and a strategy pair formula_59 of player 1 and formula_60 of player 2 such that for every formula_61 and formula_62 and every formula_63 the expectation of formula_64 with respect to the probability on plays defined by formula_65 and formula_62 is at least formula_67, and the expectation of formula_64 with respect  to the probability on plays defined by formula_69 and formula_60 is at most formula_71. 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 formula_51  has a uniform equilibrium payoff formula_55 if for every formula_57 there is a positive integer formula_58 and a strategy profile formula_61 such that for every unilateral deviation by a player formula_18, i.e., a strategy profile formula_62 with formula_79 for all formula_80, and every formula_63 the expectation of formula_64 with respect to the probability on plays defined by formula_61 is at least formula_84, and the expectation of formula_64 with respect to the probability on plays defined by formula_62 is at most formula_87. 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 formula_51 has a limiting-average equilibrium payoff formula_55 if for every formula_57 there is a strategy profile formula_61 such that for every unilateral deviation by a player formula_18, the expectation of the limit inferior of the averages of the stage payoffs with respect to the probability on plays defined by formula_61 is at least formula_84, and the expectation of the limit superior of the averages of the stage payoffs with respect to the probability on plays defined by formula_62 is at most formula_87. 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. Stochastic games have been combined with Bayesian games to model uncertainty over player strategies. The resulting stochastic Bayesian game model is solved via a recursive combination of the Bayesian Nash equilibrium equation and the Bellman optimality equation. Applications. Stochastic games have applications in economics, evolutionary biology and computer networks. They are generalizations of repeated games which correspond to the special case  where there is only one state.