×

Constant payoff in zero-sum stochastic games. (English) Zbl 1481.91017

Summary: In a zero-sum stochastic game, at each stage, two adversary players take decisions and receive a stage payoff determined by them and by a controlled random variable representing the state of nature. The total payoff is the normalized discounted sum of the stage payoffs. In this paper we solve the “constant payoff” conjecture formulated by S. Sorin et al. [Sankhyā, Ser. A 72, No. 1, 237–245 (2010; Zbl 1209.49035)]: if both players use optimal strategies, then for any \(\alpha > 0\), the expected discounted payoff between stage \(1\) and stage \(\alpha /\lambda\) tends to the limit discounted value of the game, as the discount rate \(\lambda\) goes to \(0\).

MSC:

91A15 Stochastic games, stochastic differential games
91A10 Noncooperative games
15B51 Stochastic matrices

Citations:

Zbl 1209.49035

References:

[1] L. Attia and M. Oliu-Barton. A formula for the value of a stochastic game. Proc. Natl. Acad. Sci. USA 116 (52) (2019) 26435-26443. · Zbl 1456.91008 · doi:10.1073/pnas.1908643116
[2] T. Bewley and E. Kohlberg. The asymptotic theory of stochastic games. Math. Oper. Res. 1 (3) (1976) 197-208. · Zbl 0364.93031 · doi:10.1287/moor.1.3.197
[3] T. Bewley and E. Kohlberg. On stochastic games with stationary optimal strategies. Math. Oper. Res. 3 (2) (1978) 104-125. · Zbl 0395.90091 · doi:10.1287/moor.3.2.104
[4] O. Catoni. Simulated annealing algorithms and Markov chains with rare transitions. In Séminaire de probabilités XXXIII 69-119. Springer, 1999. · Zbl 0944.90053 · doi:10.1007/BFb0096510
[5] W. Feller. An Introduction to Probability Theory and Its Applications Vol. II. John Wiley & Sons, 1971. · Zbl 0219.60003
[6] D. Gillette. Stochastic games with zero stop probabilities. In Contributions to the Theory of Games, III 179-187. M. Dresher, A. W. Tucker and P. Wolfe (Eds). Annals of the Mathematical Studies 39. Princeton University Press, 1957. · Zbl 0078.33001
[7] E. Lehrer and S. Sorin. A uniform Tauberian theorem in dynamic programming. Math. Oper. Res. 17 (2) (1992) 303-307. · Zbl 0771.90099 · doi:10.1287/moor.17.2.303
[8] J.-F. Mertens and A. Neyman. Stochastic games. Internat. J. Game Theory 10 (2) (1981) 53-66. · Zbl 0486.90096 · doi:10.1007/BF01769259
[9] M. Oliu-Barton. The asymptotic value in stochastic games. Math. Oper. Res. 39 (3) (2014) 712-721. · Zbl 1308.91028 · doi:10.1287/moor.2013.0642
[10] M. Oliu-Barton. The splitting game: Value and optimal strategies. Dyn. Games Appl. 8 (1) (2018) 157-179. · Zbl 1390.91040 · doi:10.1007/s13235-017-0216-8
[11] M. Oliu-Barton. New algorithms for solving zero-sum stochastic games. Math. Oper. Res. (2020). · Zbl 1466.91022 · doi:10.1287/moor.2020.1055
[12] J. Renault. Basics of game theory (class notes), 2017.
[13] L. S. Shapley. Stochastic games. Proc. Natl. Acad. Sci. USA 39 (10) (1953) 1095-1100. · Zbl 0051.35805 · doi:10.1073/pnas.39.10.1953
[14] S. Sorin. A First Course on Zero-Sum Repeated Games. Springer, 2002. · Zbl 1005.91019
[15] S. Sorin. The operator approach to zero-sum stochastic games. In Stochastic Games and Applications 417-426. NATO Science Series C, Mathematical and Physical Sciences 570, 2003. · Zbl 1092.91502
[16] S. Sorin, X. Venel and G. Vigeral. Asymptotic properties of optimal trajectories in dynamic programming. Sankhya A 72 (1) (2010) 237-245. · Zbl 1209.49035 · doi:10.1007/s13171-010-0011-8
[17] S. Sorin and G. Vigeral. Limit optimal trajectories in zero-sum stochastic games. Dyn. Games Appl. (2019) 1-18. · Zbl 1444.91024 · doi:10.1007/s13235-019-00333-z
[18] G. Vigeral. A zero-sum stochastic game with compact action sets and no asymptotic value. Dyn. Games Appl. 3 (2) (2013) 172-186. · Zbl 1280.91026 · doi:10.1007/s13235-013-0073-z
[19] B. Ziliotto. Zero-sum repeated games: Counterexamples to the existence of the asymptotic value and the conjecture maxmin= lim v (n). Ann. Probab. 44 (2) (2016) 1107-1133. · Zbl 1344.91006 · doi:10.1214/14-AOP997
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.