Two-player stochastic games. I: A reduction (Q1594889): Difference between revisions

This paper contains the first part of the proof that every two--person (undiscounted) stochastic game has an equilibrium (the rest of the proof is published in two further articles in the same issue of the Israel Journal of Mathematics). More precisely, it is shown here that given such a game, there exists a positive recursive absorbing game whose equilibrium payoffs are contained in those of the original game. The reduction is probably the most difficult part of the whole proof, because while to show that a payoff vector is an equilibrium of a given game one has to construct strategies which support it, here the task is to construct a game which has a simpler structure and yet does not have more equilibria than the original game. This three-part work is a major achievement of the theory of repeated games: the problem had been open for more than twenty years, since Mertens and Neyman solved the zero-sum case in 1981. The latter also came after almost thirty years since Shapley solved the zero-sum discounted casein 1953; however, while the Mertens-Neyman contribution was to notice that the problem they tackled had a relatively simple solution and proof, the general case solved by Vieille has required a long and involved proof, and especially for the construction of the reduced game which is the content of the part under review here, it is difficult to think of substantial shortcuts. On the other hand, the proof as such sheds light on equilibrium strategies, and this is no doubt an important by-product of the result.