A formula for the value of a stochastic game

Abstract

Introduced by the Nobel-prize winner Lloyd Shapley in the 1950s, stochastic games are the first model of dynamic game to be ever defined. On the one hand, they extend Von Neumann's strategic-form games to dynamic situations; on the other, they extend the model of Markov chains and Markov decision processes, to a competitive setting. The existence and robustness of a value was established in 1976 and 1981 respectively. This paper solves a central problem which remained open for nearly 40 years: To find a tractable formula for the value of a stochastic game. (Proceedings of the National Academy of Sciences of the USA, 2019, co-authored with Luc Attia).