
New algorithms for solving zero-sum stochastic games
Oliu Barton, Miquel (2020), New algorithms for solving zero-sum stochastic games, Mathematics of Operations Research
Type
Article accepté pour publication ou publiéExternal document link
https://pubsonline.informs.org/doi/10.1287/moor.2020.1055Date
2020Journal name
Mathematics of Operations ResearchPublisher
INFORMS
Metadata
Show full item recordAuthor(s)
Oliu Barton, MiquelAbstract (EN)
Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players’ behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the value, which are polynomial in the number of pure stationary strategies of the players. This result considerably improves all the existing algorithms, including the most efficient one, due to Hansen, Koucký, Lauritzen, Miltersen and Tsigaridas (STOC 2011).Subjects / Keywords
zero-sum stochastic games; game theoryRelated items
Showing items related by title and author.
-
Catoni, Olivier; Oliu-Barton, Miquel; Ziliotto, Bruno (2021) Article accepté pour publication ou publié
-
Oliu-Barton, Miquel; Gensbittel, Fabien (2020) Article accepté pour publication ou publié
-
Gensbittel, Fabien; Oliu-Barton, Miquel; Venel, Xavier (2014) Article accepté pour publication ou publié
-
Attia, Luc; Oliu Barton, Miquel (2019) Article accepté pour publication ou publié
-
Ziliotto, Bruno (2018) Article accepté pour publication ou publié