A formula for the value of a stochastic game

DOI10.1073/PNAS.1908643116zbMATH Open1456.91008arXiv1809.06102OpenAlexW2995576095WikidataQ92023374 ScholiaQ92023374MaRDI QIDQ5854792FDOQ5854792

Miquel Oliu-Barton, Luc Attia

Publication date: 12 March 2021

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Abstract: In 1953, Lloyd Shapley defined the model of stochastic games, which were the first general dynamic model of a game to be defined, and proved that competitive stochastic games have a discounted value. In 1982, Jean-Franc{c}ois Mertens and Abraham Neyman proved that competitive stochastic games admit a robust solution concept, the value, which is equal to the limit of the discounted values as the discount rate goes to 0. Both contributions were published in PNAS. In the present paper, we provide a tractable formula for the value of competitive stochastic games.

Full work available at URL: https://arxiv.org/abs/1809.06102

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A new polynomial-time algorithm for linear programming
• Stochastic Games
• A zero-sum stochastic game with compact action sets and no asymptotic value
• Definable Zero-Sum Stochastic Games
• Stochastic games
• A Tauberian theorem for nonexpansive operators and applications to zero-sum stochastic games
• Existence of the limit value of two person zero-sum discounted repeated games via comparison theorems
• Stochastic games with short-stage duration
• The Asymptotic Theory of Stochastic Games
• The Asymptotic Value in Finite Stochastic Games
• Repeated games with public uncertain duration process
• Explicit formulas for repeated games with absorbing states
• The Big Match
• A first course on zero-sum repeated games
• On general minimax theorems
• Multiparameter eigenvalue problems. Volume I: Matrices and compact operators
• Computing uniformly optimal strategies in two-player stochastic games
• Repeated games with absorbing states
• Algorithms for discounted stochastic games
• On Nonterminating Stochastic Games
• Recursive Concurrent Stochastic Games
• Stochastic limit-average games are in EXPTIME
• Asymptotic properties of optimal trajectories in dynamic programming
• Stochastic games have a value
• On the Puiseux Series Expansion of the Limit Discount Equation of Stochastic Games
• Stochastic games
• Exact algorithms for solving stochastic games
• A formula for the value of a stochastic game
• Asymptotically optimal strategies in repeated games with incomplete information and vanishing weights

Cited In (9)

• Stationary equilibria in discounted stochastic games
• New Algorithms for Solving Zero-Sum Stochastic Games
• A formula for the value of a stochastic game
• Shapley–Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games
• Title not available (Why is that?)
• Uniformly supported approximate equilibria in families of games
• Constant payoff in zero-sum stochastic games
• Equilibrium in two-player stochastic games with shift-invariant payoffs
• Absorbing games with irrational values

This page was built for publication: A formula for the value of a stochastic game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854792)