A solution for stochastic games

Abstract

The value of a two-player zero-sum game represents what playing the game is worth to the players. The problems of existence and characterisation of the value are at the core of game theory. To illustrate the difference between the two problems, consider the game of chess. Since Zermelo (1913), we know that any finite zero-sum game with perfect information has a value, so chess has a value. However, no one has ever been able to determine it: is it a win for white, a draw or a win for black? The situation is similar for stochastic games: the value is known to exist since Bewley and Kohlberg (1976), but a characterisation has been missing since then. In the present paper, we solve this long-standing open problem by providing a formula for the value of stochastic games. Our result is constructive, as it allows to derive an efficient algorithm to compute it.