Two-player stochastic games. I: A reduction
type: Item
instance of: scholarly article
title: Two-player stochastic games. I: A reduction
zbMATH Open document ID: 0974.91005
DOI: 10.1007/BF02810663
author: Nicolas Vieille
published in: Israel Journal of Mathematics
publication date: 2001-12-16T00:00:00Z
review text: 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.
reviewed by: Salvatore Modica
Mathematics Subject Classification ID: 91A15
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 1558319
zbMATH Keywords: equilibrium payoffs in stochastic games
MaRDI profile type: Publication
cites work: Repeated games with incomplete information. With the collaboration of Richard E. Stearns
cites work: The Asymptotic Solution of a Recursion Equation Occurring in Stochastic Games
cites work: The Asymptotic Theory of Stochastic Games
cites work: On Stochastic Games with Stationary Optimal Strategies
cites work: Discounted Dynamic Programming
cites work: The Big Match
cites work: Q3245633
cites work: Q5331697
cites work: Q3245641
cites work: Repeated games with absorbing states
cites work: Stochastic games
cites work: Stochastic games have a value
cites work: Q3976308
cites work: Q3245632
cites work: On stochastic games with additive reward and transition structure
cites work: Stochastic Games
cites work: Three-Player Absorbing Games
cites work: Asymptotic properties of a non-zero sum stochastic game
cites work: Perfect information stochastic games and related classes
cites work: Two-player stochastic games. II: The case of recursive games
cites work: On equilibria in repeated games with absorbing states
full work available at URL: https://doi.org/10.1007/bf02810663
OpenAlex ID: W2082868623
description: scientific article; zbMATH DE number 1558319