Abstract
We study the links between the values of stochastic games with varying stage duration h, the corresponding Shapley operators \(\mathbf{T}\) and \(\mathbf{T}_h= h\mathbf{T}+ (1-h ) Id\) and the solution of the evolution equation \(\dot{f}_t = (\mathbf{T}- Id )f_t\). Considering general non expansive maps we establish two kinds of results, under both the discounted or the finite length framework, that apply to the class of “exact” stochastic games. First, for a fixed length or discount factor, the value converges as the stage duration go to 0. Second, the asymptotic behavior of the value as the length goes to infinity, or as the discount factor goes to 0, does not depend on the stage duration. In addition, these properties imply the existence of the value of the finite length or discounted continuous time game (associated to a continuous time jointly controlled Markov process), as the limit of the value of any time discretization with vanishing mesh.
Similar content being viewed by others
References
Brézis H (1973) Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland
Brézis H, Pazy A (1970) Accretive sets and differential equations in Banach spaces. Isr J Math 8:367–383
Guo X, Hernandez-Lerma O (2003) Zero-sum games for continuous-time Markov chains with unbounded transition and average payoff rates. J Appl Probab 40:327–345
Guo X, Hernandez-Lerma O (2005) Zero-sum continuous-time Markov games with unbounded transition and discounted payoff rates. Bernoulli 11:1009–1029
Kolokoltsov VN (1992) On linear, additive, and homogeneous operators in idempotent analysis. In: Maslov VP, Samborski SN (eds) Advances in Soviet Mathematics, vol 13. Idempotent analysis, pp 87–101
Mertens J-F, Sorin S, Zamir S (2015) Repeated games. Cambridge University Press, Cambridge
Miyadera I, Oharu S (1970) Approximation of semi-groups of nonlinear operators. Tôhoku Math J 22:24–47
Neyman A (2003) Stochastic games and nonexpansive maps. In: Neyman A, Sorin S (eds) Stochastic games and applications. NATO science series, vol C 570. Kluwer Academic Publishers, pp 397–415
Neyman A (2012) Continuous-time stochastic games, DP 616. CSR, Jerusalem
Neyman A (2013) Stochastic games with short-stage duration. Dyn Games Appl 3:236–278
Neyman A, Sorin S (2010) Repeated games with public uncertain duration process. Int J Game Theory 39:29–52
Nowak AS (1985) Universally measurable strategies in zero-sum stochastic games. Ann Probab 13:269–287
Nowak AS (2003) Zero-sum stochastic games with Borel state spaces. In: Neyman A,Sorin S (eds) Stochastic games and applications. NATO science series, vol C 570. Kluwer Academic Publishers, pp 77–91
Prieto-Rumeau T, Hernandez-Lerma O (2012) Selected topics on continuous-time controlled Markov chains and Markov games. Imperial College Press, London
Rosenberg D, Sorin S (2001) An operator approach to zero-sum repeated games. Isr J Math 121:221–246
Shapley LS (1953) Stochastic games. Proc Natl Acad Sci USA 39:1095–1100
Sorin S (2003) The operator approach to zero-sum stochastic games. In: Neyman A, Sorin S (eds) Stochastic games and applications. NATO science series, vol C 570. Kluwer Academic Publishers, pp 375–395
Sorin S (2004) Asymptotic properties of monotonic nonexpansive mappings. Discrete Event Dyn Syst 14:109–122
Sorin S (2015) Limit value of dynamic zero-sum games with vanishing stage duration, preprint
Tanaka K, Wakuta K (1977) On continuous Markov games with the expected average reward criterion. Sci Rep Niigata Univ Ser A 14:15–24
Vigeral G (2009) Propriétés asymptotiques des jeux répétés à somme nulle, PhD Thesis, UPMC-Paris 6
Vigeral G (2010) Evolution equations in discrete and continuous time for non expansive operators in Banach spaces. ESAIM COCV 16:809–832
Vigeral G (2013) A zero-sum stochastic game with compact action sets and no asymptotic value. Dyn Games Appl 3:172–186
Zachrisson LE (1964) Markov games. In: Dresher M, Shapley LS, Tucker AW (eds) Advances in game theory. Annals of mathematical studies, vol 52. Princeton University Press, pp 210–253
Ziliotto B (2013) Zero-sum repeated games: counterexamples to the existence of the asymptotic value and the conjecture \(maxmin=lim v_{n}\), preprint hal-00824039, to appear in Annals of Probability
Author information
Authors and Affiliations
Corresponding author
Additional information
This was co-funded by PGMO 2014-LMG. The second author was partially supported by the French Agence Nationale de la Recherche (ANR) “ANR GAGA: ANR-13-JS01-0004-01”.
Rights and permissions
About this article
Cite this article
Sorin, S., Vigeral, G. Operator approach to values of stochastic games with varying stage duration. Int J Game Theory 45, 389–410 (2016). https://doi.org/10.1007/s00182-015-0512-8
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-015-0512-8