An accretive operator approach to ergodic zero-sum stochastic games

Antoine Hochart

doi:10.3934/jdg.2019003

Article Contents

2019, Volume 6, Issue 1: 27-51. Doi: 10.3934/jdg.2019003

This issue Previous Article Local completeness, Pareto efficiency and Mackey Bishop-Phelps cones Next Article On the pricing of Asian options with geometric average of American type with stochastic interest rate: A stochastic optimal control approach

An accretive operator approach to ergodic zero-sum stochastic games

Antoine Hochart

Universidad Adolfo Ibáñez, Santiago, Chile

Received: July 31, 2017

Revised: June 30, 2018

Published: December 2018

The author is funded by FONDECYT grant 3180662.

Abstract Full Text(HTML) Related Papers Cited by

Abstract

We study some ergodicity property of zero-sum stochastic games with a finite state space and possibly unbounded payoffs. We formulate this property in operator-theoretical terms, involving the solvability of an optimality equation for the Shapley operators (i.e., the dynamic programming operators) of a family of perturbed games. The solvability of this equation entails the existence of the uniform value, and its solutions yield uniform optimal stationary strategies. We first provide an analytical characterization of this ergodicity property, and address the generic uniqueness, up to an additive constant, of the solutions of the optimality equation. Our analysis relies on the theory of accretive mappings, which we apply to maps of the form $Id - T$ where $T$ is nonexpansive. Then, we use the results of a companion work to characterize the ergodicity of stochastic games by a geometrical condition imposed on the transition probabilities. This condition generalizes classical notion of ergodicity for finite Markov chains and Markov decision processes.

Keywords:

Mathematics Subject Classification: Primary: 91A15, 47H25; Secondary: 47H09, 47H06, 47H04.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	M. Akian, S. Gaubert and A. Hochart, Ergodicity conditions for zero-sum games, Discrete Contin. Dyn. Syst., 35 (2015), 3901-3931. doi: 10.3934/dcds.2015.35.3901.
[2]	M. Akian, S. Gaubert and A. Hochart, Hypergraph conditions for the solvability of the ergodic equation for zero-sum games, in 54th IEEE Conference on Decision and Control, Osaka, Japan, 2015, 5845-5850, arXiv: 1510.05396. doi: 10.3934/dcds.2015.35.3901.
[3]	M. Akian, S. Gaubert and A. Hochart, A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors, 2018, Preprint, arXiv: 1812.09871.
[4]	C. D. Aliprantis and K. C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide, 3rd edition, Springer, Berlin, 2006.
[5]	E. Altman, A. Hordijk and F. M. Spieksma, Contraction conditions for average and $α$-discount optimality in countable state Markov games with unbounded rewards, Math. Oper. Res., 22 (1997), 588-618. doi: 10.1287/moor.22.3.588.
[6]	E. Asplund, Positivity of duality mappings, Bull. Amer. Math. Soc., 73 (1967), 200-203. doi: 10.1090/S0002-9904-1967-11678-1.
[7]	J.-P. Aubin and H. Frankowska, Set-valued Analysis, Modern Birkhäuser Classics, Birkhäuser Boston, Inc., Boston, MA, 2009, Reprint of the 1990 edition. doi: 10.1007/978-0-8176-4848-0.
[8]	J. Bather, Optimal decision procedures for finite Markov chains. Ⅱ. Communicating systems, Advances in Appl. Probability, 5 (1973), 521-540. doi: 10.2307/1425832.
[9]	T. Bewley and E. Kohlberg, The asymptotic theory of stochastic games, Math. Oper. Res., 1 (1976), 197-208. doi: 10.1287/moor.1.3.197.
[10]	J. Bolte, S. Gaubert and G. Vigeral, Definable zero-sum stochastic games, Math. Oper. Res., 40 (2015), 171-191. doi: 10.1287/moor.2014.0666.
[11]	V. S. Borkar and M. K. Ghosh, Denumerable state stochastic games with limiting average payoff, J. Optim. Theory Appl., 76 (1993), 539-560. doi: 10.1007/BF00939382.
[12]	E. Boros, K. Elbassioni, V. Gurvich and K. Makino, A pumping algorithm for ergodic stochastic mean payoff games with perfect information, in Integer Programming and Combinatorial Optimization, vol. 6080 of Lecture Notes in Comput. Sci., Springer, Berlin, 2010, 341-354. doi: 10.1007/978-3-642-13036-6_26.
[13]	F. E. Browder, Nonlinear operators and nonlinear equations of evolution in Banach spaces, Nonlinear functional analysis (Proc. Sympos. Pure Math., Vol. XVIII, Part 2, Chicago, Ill., 1968), Amer. Math. Soc., Providence, R. I., 1976, 1-308.
[14]	I. Cioranescu, Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems, vol. 62 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1990. doi: 10.1007/978-94-009-2121-4.
[15]	M. G. Crandall and L. Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc., 78 (1980), 385-390. doi: 10.1090/S0002-9939-1980-0553381-X.
[16]	H. Everett, Recursive games, in Contributions to the Theory of Games, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N. J., 3 (1957), 47-78.
[17]	P. M. Fitzpatrick, P. Hess and T. Kato, Local boundedness of monotone-type operators, Proc. Japan Acad., 48 (1972), 275-277. doi: 10.3792/pja/1195519662.
[18]	S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950 (electronic). doi: 10.1090/S0002-9947-04-03470-1.
[19]	M. K. Ghosh and A. Bagchi, Stochastic games with average payoff criterion, Appl. Math. Optim., 38 (1998), 283-301. doi: 10.1007/s002459900092.
[20]	V. A. Gurvich and V. N. Lebedev, A criterion and verification of the ergodicity of cyclic game forms, Uspekhi Mat. Nauk, 44 (1989), 193-194. doi: 10.1070/RM1989v044n01ABEH002010.
[21]	O. Hernández-Lerma and J. B. Lasserre, Zero-sum stochastic games in Borel spaces: Average payoff criteria, SIAM J. Control Optim., 39 (2000), 1520-1539. doi: 10.1137/S0363012999361962.
[22]	A. Hochart, An accretive operator approach to ergodic problems for zero-sum games, in 22nd International Symposium on Mathematical Theory of Networks and Systems, Minneapolis, Minnesota, USA, 2016,315-318, arXiv: 1605.04520, hdl: 11299/181518.
[23]	A. J. Hoffman and R. M. Karp, On nonterminating stochastic games, Management Sci., 12 (1966), 359-370. doi: 10.1287/mnsc.12.5.359.
[24]	A. Jaśkiewicz and A. S. Nowak, On the optimality equation for zero-sum ergodic stochastic games, Math. Methods Oper. Res., 54 (2001), 291-301. doi: 10.1007/s001860100144.
[25]	M. Jurdziński, M. Paterson and U. Zwick, A deterministic subexponential algorithm for solving parity games, SIAM J. Comput., 38 (2008), 1519-1532. doi: 10.1137/070686652.
[26]	J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer-Verlag, New York-Heidelberg, 1976, Reprinting of the 1960 original, Undergraduate Texts in Mathematics.
[27]	W. A. Kirk and R. Schöneberg, Zeros of $m$-accretive operators in Banach spaces, Israel J. Math., 35 (1980), 1-8. doi: 10.1007/BF02760935.
[28]	E. Kohlberg, Repeated games with absorbing states, Ann. Statist., 2 (1974), 724-738. doi: 10.1214/aos/1176342760.
[29]	H.-U. Küenle, On multichain Markov games, in Advances in Dynamic Games and Applications (Maastricht, 1998), vol. 6 of Ann. Internat. Soc. Dynam. Games, Birkhäuser Boston, Boston, MA, 2001,147-163.
[30]	B. Lemmens and R. D. Nussbaum, Nonlinear Perron-Frobenius Theory, vol. 189 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 2012. doi: 10.1017/CBO9781139026079.
[31]	J.-F. Mertens and A. Neyman, Stochastic games, Internat. J. Game Theory, 10 (1981), 53-66. doi: 10.1007/BF01769259.
[32]	J.-F. Mertens, A. Neyman and D. Rosenberg, Absorbing games with compact action spaces, Math. Oper. Res., 34 (2009), 257-262. doi: 10.1287/moor.1080.0372.
[33]	J.-F. Mertens, S. Sorin and S. Zamir, Repeated Games, Econometric Society Monographs, Cambridge University Press, New York, 2015, With a foreword by Robert J. Aumann. doi: 10.1017/CBO9781139343275.
[34]	A. Neyman, Stochastic games and nonexpansive maps, in Stochastic Games and Applications (Stony Brook, NY, 1999), vol. 570 of NATO Sci. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 2003, 397-415. doi: 10.1007/978-94-010-0189-2_26.
[35]	A. Neyman and S. Sorin, Stochastic Games and Applications, vol. 570 of Nato Science Series C, Springer Netherlands, 2003.
[36]	R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps Mem. Amer. Math. Soc., 75 (1988), ⅳ+137pp. doi: 10.1090/memo/0391.
[37]	W. V. Petryshyn, A characterization of strict convexity of Banach spaces and other uses of duality mappings, J. Functional Analysis, 6 (1970), 282-291. doi: 10.1016/0022-1236(70)90061-3.
[38]	S. Reich, Approximating fixed points of nonexpansive mappings, Panamer. Math. J., 4 (1994), 23-28.
[39]	J. Renault, Uniform value in dynamic programming, J. Eur. Math. Soc. (JEMS), 13 (2011), 309-330. doi: 10.4171/JEMS/254.
[40]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, vol. 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[41]	D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel J. Math., 121 (2001), 221-246. doi: 10.1007/BF02802505.
[42]	L. I. Sennott, Zero-sum stochastic games with unbounded costs: Discounted and average cost cases, Z. Oper. Res., 39 (1993), 209-225. doi: 10.1007/BF01415582.
[43]	L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U. S. A., 39 (1953), 1095-1100. doi: 10.1073/pnas.39.10.1953.
[44]	S. Sorin, The operator approach to zero-sum stochastic games, in Stochastic Games and Applications (Stony Brook, NY, 1999), vol. 570 of NATO Sci. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 2003, 417-426.
[45]	S. Sorin, Asymptotic properties of monotonic nonexpansive mappings, Discrete Event Dyn. Syst., 14 (2004), 109-122. doi: 10.1023/B:DISC.0000005011.93152.d8.
[46]	S. Sorin and G. Vigeral, Operator approach to values of stochastic games with varying stage duration, Internat. J. Game Theory, 45 (2016), 389-410. doi: 10.1007/s00182-015-0512-8.
[47]	G. Vigeral, Evolution equations in discrete and continuous time for nonexpansive operators in Banach spaces, ESAIM Control Optim. Calc. Var., 16 (2010), 809-832. doi: 10.1051/cocv/2009026.
[48]	G. Vigeral, A zero-zum stochastic game with compact action sets and no asymptotic value, Dyn. Games Appl., 3 (2013), 172-186. doi: 10.1007/s13235-013-0073-z.
[49]	O. J. Vrieze, Stochastic games and stationary strategies, in Stochastic Games and Applications (Stony Brook, NY, 1999), vol. 570 of NATO Sci. Ser. C Math. Phys. Sci., Kluwer Acad. Publ., Dordrecht, 2003, 37-50.
[50]	B. Ziliotto, A tauberian theorem for nonexpansive operators and applications to zero-sum stochastic games, Math. Oper. Res., 41 (2016), 1522-1534. doi: 10.1287/moor.2016.0788.
[51]	B. Ziliotto, Zero-sum repeated games: Counterexamples to the existence of the asymptotic value and the conjecture ${\text{maxmin}}=\lim \ {{v}_{n}}$, Ann. Probab., 44 (2016), 1107-1133. doi: 10.1214/14-AOP997.