Stochastic game

Stochastic game

In game theory, a stochastic game is a dynamic, competitive 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.

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. Vieille has shown that all two-person stochastic games with finite state and action spaces have
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.

Stochastic games have applications in economics and evolutionary biology. They are generalizations of repeated games which correspond to the special case where there is only one state.

Stochastic games were invented by Lloyd Shapley in the early 1950's. 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 1- and 2-player stochastic games.

References

* L.S. Shapley. Stochastic games Proc. Nat. Acad. Science, 39:1095-1100, 1953.
* A. Condon. The complexity of stochastic games. Information and Computation, 96:203–224, 1992.
* J. Filar and K. Vrieze. Competitive Markov Decision Processes. Springer-Verlag, 1997.
* N. Vieille. Stochastic games: Recent results. In Handbook of Game Theory,pages 1833–1850. Elsevier Science, 2002.
* A. Neyman and S. Sorin, editors, Stochastic Games and Applications. Kluwer Academic Press, 2003.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Stochastic Diffusion Search — (SDS), was first described in 1989 as a population based, pattern matching algorithm [Bishop, 1989] . It belongs to a family of Swarm Intelligence and naturally inspired search and optimisation algorithms which includes Ant Colony Optimization,… …   Wikipedia

  • Stochastic — (from the Greek Στόχος for aim or guess ) means random.A stochastic process is one whose behavior is non deterministic in that a state s next state is determined both by the process s predictable actions and by a random element. Stochastic crafts …   Wikipedia

  • Game theory — is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, engineering, political science, computer science (mainly for artificial intelligence), and philosophy. Game theory attempts to… …   Wikipedia

  • Stochastic matrix — For a matrix whose elements are stochastic, see Random matrix In mathematics, a stochastic matrix (also termed probability matrix, transition matrix, substitution matrix, or Markov matrix) is a matrix used to describe the transitions of a Markov… …   Wikipedia

  • Game of chance — A game of chance is a game whose outcome is strongly influenced by some randomizing device, and upon which contestants may or may not wager money or anything of monetary value. Common devices used include dice, spinning tops, playing cards,… …   Wikipedia

  • Chicken (game) — For other uses, see Chicken (disambiguation). The game of chicken, also known as the hawk dove or snowdrift[1] game, is an influential model of conflict for two players in game theory. The principle of the game is that while each player prefers… …   Wikipedia

  • Cooperative game — This article is about a part of game theory. For video gaming, see Cooperative gameplay. For the similar feature in some board games, see cooperative board game In game theory, a cooperative game is a game where groups of players ( coalitions )… …   Wikipedia

  • Coordination game — In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies. Coordination games are a formalization of the idea of a coordination problem, which… …   Wikipedia

  • Strategy (game theory) — In game theory, a player s strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player s behaviour. A player s strategy will determine the action the player will take at any stage of the… …   Wikipedia

  • Dictator game — The dictator game is a game in experimental economics, similar to the ultimatum game. Experimental results offer evidence against the rationally self interested individual (sometimes called the homo economicus) concept of economic behavior,[1]… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”