New Algorithms for Solving Zero-Sum Stochastic Games

Miquel Oliu-Barton ()
Additional contact information
Miquel Oliu-Barton: Université Paris-Dauphine, Paris Sciences et Lettres Research University, Centre de Recherche en Mathématiques de la Décision, 75016 Paris, France

Mathematics of Operations Research, 2021, vol. 46, issue 1, 255-267

Abstract: 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.

Keywords: stochastic games; complexity; linear programming; minimax; discounted values; limit value; algorithms (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2020.1055 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:1:p:255-267

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().