Stochastic game

Last updated December 16, 2023

In game theory, a stochastic game (or Markov game), introduced by Lloyd Shapley in the early 1950s,^[1] 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.

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^{[ citation needed ]}. 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 $S$ (either a finite set or a measurable space $(S,{\mathcal {S}})$ ); for each player $i\in I$ , an action set $A^{i}$ (either a finite set or a measurable space $(A^{i},{\mathcal {A}}^{i})$ ); a transition probability $P$ from $S\times A$ , where $A=\times _{i\in I}A^{i}$ is the action profiles, to $S$ , where $P(S\mid s,a)$ is the probability that the next state is in $S$ given the current state $s$ and the current action profile $a$ ; and a payoff function $g$ from $S\times A$ to $R^{I}$ , where the $i$ -th coordinate of $g$ , $g^{i}$ , is the payoff to player $i$ as a function of the state $s$ and the action profile $a$ .

The game starts at some initial state $s_{1}$ . At stage $t$ , players first observe $s_{t}$ , then simultaneously choose actions $a_{t}^{i}\in A^{i}$ , then observe the action profile $a_{t}=(a_{t}^{i})_{i}$ , and then nature selects $s_{t+1}$ according to the probability $P(\cdot \mid s_{t},a_{t})$ . A play of the stochastic game, $s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots$ , defines a stream of payoffs $g_{1},g_{2},\ldots$ , where $g_{t}=g(s_{t},a_{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_{t}^{i}$ . The $n$ -stage game is the game where the payoff to player $i$ is ${\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}$ .

The value $v_{n}(s_{1})$ , respectively $v_{\lambda }(s_{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}(s_{1})$ converges to a limit as $n$ goes to infinity and that $v_{\lambda }(s_{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}}_{n}^{i}$ 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}}_{n}^{i}$ 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.^[3]

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}}_{n}^{i}$ with respect to the probability on plays defined by $\sigma$ is at least $v_{\infty }^{i}-\varepsilon$ , and the expectation of ${\bar {g}}_{n}^{i}$ with respect to the probability on plays defined by $\tau$ is at most $v_{\infty }^{i}+\varepsilon$ . Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a uniform equilibrium payoff.^[4]

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_{\infty }^{i}-\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_{\infty }^{i}+\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,^[3] and Nicolas Vieille has shown that all two-person stochastic games with finite state and action spaces have a limiting-average equilibrium payoff.^[4] 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.^[5] 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.^[6]^[7] They are generalizations of repeated games which correspond to the special case where there is only one state.

Notes

↑ Shapley, L. S. (1953). "Stochastic games". PNAS . 39 (10): 1095–1100. Bibcode:1953PNAS...39.1095S. doi: 10.1073/pnas.39.10.1095 . PMC 1063912 . PMID 16589380.
↑ Solan, Eilon; Vieille, Nicolas (2015). "Stochastic Games". PNAS. 112 (45): 13743–13746. doi: 10.1073/pnas.1513508112 . PMC 4653174 . PMID 26556883.
1 2 Mertens, J. F. & Neyman, A. (1981). "Stochastic Games". International Journal of Game Theory. 10 (2): 53–66. doi:10.1007/BF01769259. S2CID 189830419.
1 2 Vieille, N. (2002). "Stochastic games: Recent results". Handbook of Game Theory. Amsterdam: Elsevier Science. pp. 1833–1850. ISBN 0-444-88098-4.
↑ Albrecht, Stefano; Crandall, Jacob; Ramamoorthy, Subramanian (2016). "Belief and Truth in Hypothesised Behaviours". Artificial Intelligence . 235: 63–94. arXiv: 1507.07688 . doi:10.1016/j.artint.2016.02.004. S2CID 2599762.
↑ Constrained Stochastic Games in Wireless Networks by E.Altman, K.Avratchenkov, N.Bonneau, M.Debbah, R.El-Azouzi, D.S.Menasche
↑ Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (2017-09-27). "Mean-Field-Type Games in Engineering". AIMS Electronics and Electrical Engineering. 1: 18–73. arXiv: 1605.03281 . doi:10.3934/ElectrEng.2017.1.18. S2CID 16055840.

External links

Lecture on Stochastic Two-Player Games by Antonin Kucera

{{Navbox | name = Game theory | title = Topics in game theory | listclass = hlist | state = autocollapse | selected =

| group1 = Definitions | list1 =

| group2 = Equilibrium
concepts | list2 =

| group3 = Strategies | list3 =

| group4 = Classes
of games | list4 =

| group5 = Games | list5 =

| grouwrp6 = Theorems | listr6 =

| group7 = Key
figures | list7 =

| group8 = Miscellaneous | list8 =

}}

Related Research Articles

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

In mathematics, an infinite series of numbers is said to converge absolutely if the sum of the absolute values of the summands is finite. More precisely, a real or complex series $is said to converge absolutely if for some real number Similarly, an improper integral of a function, is said to converge absolutely if the integral of the absolute value of the integrand is finite—that is, if$

<span class="mw-page-title-main">Fokker–Planck equation</span> Partial differential equation

In statistical mechanics and information theory, the Fokker–Planck equation is a partial differential equation that describes the time evolution of the probability density function of the velocity of a particle under the influence of drag forces and random forces, as in Brownian motion. The equation can be generalized to other observables as well. The Fokker-Planck equation has multiple applications in information theory, graph theory, data science, finance, economics etc.

In calculus and real analysis, absolute continuity is a smoothness property of functions that is stronger than continuity and uniform continuity. The notion of absolute continuity allows one to obtain generalizations of the relationship between the two central operations of calculus—differentiation and integration. This relationship is commonly characterized in the framework of Riemann integration, but with absolute continuity it may be formulated in terms of Lebesgue integration. For real-valued functions on the real line, two interrelated notions appear: absolute continuity of functions and absolute continuity of measures. These two notions are generalized in different directions. The usual derivative of a function is related to the Radon–Nikodym derivative, or density, of a measure. We have the following chains of inclusions for functions over a compact subset of the real line:

In mathematics, the Radon–Nikodym theorem is a result in measure theory that expresses the relationship between two measures defined on the same measurable space. A measure is a set function that assigns a consistent magnitude to the measurable subsets of a measurable space. Examples of a measure include area and volume, where the subsets are sets of points; or the probability of an event, which is a subset of possible outcomes within a wider probability space.

The Laplace–Stieltjes transform, named for Pierre-Simon Laplace and Thomas Joannes Stieltjes, is an integral transform similar to the Laplace transform. For real-valued functions, it is the Laplace transform of a Stieltjes measure, however it is often defined for functions with values in a Banach space. It is useful in a number of areas of mathematics, including functional analysis, and certain areas of theoretical and applied probability.

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by $ρ(\cdot)$ .

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

A granular material is a conglomeration of discrete solid, macroscopic particles characterized by a loss of energy whenever the particles interact. The constituents that compose granular material are large enough such that they are not subject to thermal motion fluctuations. Thus, the lower size limit for grains in granular material is about 1 μm. On the upper size limit, the physics of granular materials may be applied to ice floes where the individual grains are icebergs and to asteroid belts of the Solar System with individual grains being asteroids.

In probability theory and related fields, Malliavin calculus is a set of mathematical techniques and ideas that extend the mathematical field of calculus of variations from deterministic functions to stochastic processes. In particular, it allows the computation of derivatives of random variables. Malliavin calculus is also called the stochastic calculus of variations. P. Malliavin first initiated the calculus on infinite dimensional space. Then, the significant contributors such as S. Kusuoka, D. Stroock, J-M. Bismut, S. Watanabe, I. Shigekawa, and so on finally completed the foundations.

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

In game theory, trembling hand perfect equilibrium is a type of refinement of a Nash equilibrium that was first proposed by Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In mathematics, the Weyl character formula in representation theory describes the characters of irreducible representations of compact Lie groups in terms of their highest weights. It was proved by Hermann Weyl. There is a closely related formula for the character of an irreducible representation of a semisimple Lie algebra. In Weyl's approach to the representation theory of connected compact Lie groups, the proof of the character formula is a key step in proving that every dominant integral element actually arises as the highest weight of some irreducible representation. Important consequences of the character formula are the Weyl dimension formula and the Kostant multiplicity formula.

The Newman–Penrose (NP) formalism is a set of notation developed by Ezra T. Newman and Roger Penrose for general relativity (GR). Their notation is an effort to treat general relativity in terms of spinor notation, which introduces complex forms of the usual variables used in GR. The NP formalism is itself a special case of the tetrad formalism, where the tensors of the theory are projected onto a complete vector basis at each point in spacetime. Usually this vector basis is chosen to reflect some symmetry of the spacetime, leading to simplified expressions for physical observables. In the case of the NP formalism, the vector basis chosen is a null tetrad: a set of four null vectors—two real, and a complex-conjugate pair. The two real members often asymptotically point radially inward and radially outward, and the formalism is well adapted to treatment of the propagation of radiation in curved spacetime. The Weyl scalars, derived from the Weyl tensor, are often used. In particular, it can be shown that one of these scalars— $in the appropriate frame—encodes the outgoing gravitational radiation of an asymptotically flat system.$

In mathematical analysis, the Russo–Vallois integral is an extension to stochastic processes of the classical Riemann–Stieltjes integral

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

In probability theory, the Palm–Khintchine theorem, the work of Conny Palm and Aleksandr Khinchin, expresses that a large number of renewal processes, not necessarily Poissonian, when combined ("superimposed") will have Poissonian properties.

In game theory, Mertens stability is a solution concept used to predict the outcome of a non-cooperative game. A tentative definition of stability was proposed by Elon Kohlberg and Jean-François Mertens for games with finite numbers of players and strategies. Later, Mertens proposed a stronger definition that was elaborated further by Srihari Govindan and Mertens. This solution concept is now called Mertens stability, or just stability.

Stochastic chains with memory of variable length are a family of stochastic chains of finite order in a finite alphabet, such as, for every time pass, only one finite suffix of the past, called context, is necessary to predict the next symbol. These models were introduced in the information theory literature by Jorma Rissanen in 1983, as a universal tool to data compression, but recently have been used to model data in different areas such as biology, linguistics and music.

In dual decomposition a problem is broken into smaller subproblems and a solution to the relaxed problem is found. This method can be employed for MRF optimization. Dual decomposition is applied to markov logic programs as an inference technique.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Shapley, L. S. (1953). "Stochastic games". PNAS . 39 (10): 1095–1100. Bibcode:1953PNAS...39.1095S. doi: 10.1073/pnas.39.10.1095 . PMC 1063912 . PMID 16589380.

[2] Solan, Eilon; Vieille, Nicolas (2015). "Stochastic Games". PNAS. 112 (45): 13743–13746. doi: 10.1073/pnas.1513508112 . PMC 4653174 . PMID 26556883.

[MertensNeyman-3] 1 2 Mertens, J. F. & Neyman, A. (1981). "Stochastic Games". International Journal of Game Theory. 10 (2): 53–66. doi:10.1007/BF01769259. S2CID 189830419.

[Vieille-4] 1 2 Vieille, N. (2002). "Stochastic games: Recent results". Handbook of Game Theory. Amsterdam: Elsevier Science. pp. 1833–1850. ISBN 0-444-88098-4.

[5] Albrecht, Stefano; Crandall, Jacob; Ramamoorthy, Subramanian (2016). "Belief and Truth in Hypothesised Behaviours". Artificial Intelligence . 235: 63–94. arXiv: 1507.07688 . doi:10.1016/j.artint.2016.02.004. S2CID 2599762.

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

[7] Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (2017-09-27). "Mean-Field-Type Games in Engineering". AIMS Electronics and Electrical Engineering. 1: 18–73. arXiv: 1605.03281 . doi:10.3934/ElectrEng.2017.1.18. S2CID 16055840.

[1]

[2]

[3]

[4]

[5]

[6]

[7]