New Algorithms for Solving Zero-Sum Stochastic Games
成果类型：
Article
署名作者：
Oliu-Barton, Miquel
署名单位：
Universite PSL; Universite Paris-Dauphine
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2020.1055
发表日期：
2021
页码：
255-267
关键词：
摘要：
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.
来源URL：