American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets
  • DCDS Home
  • This Issue
  • Next Article
    On the system of partial differential equations arising in mean field type control
September  2015, 35(9): 3901-3931. doi: 10.3934/dcds.2015.35.3901

Ergodicity conditions for zero-sum games

Marianne Akian 1, , Stéphane Gaubert 1, and  Antoine Hochart 1,

1. 

INRIA and CMAP, Ecole polytechnique, CNRS, CMAP, Ecole polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France, France, France

Received  May 2014 Revised  December 2014 Published  April 2015

A basic question for zero-sum repeated games consists in determining whether the mean payoff per time unit is independent of the initial state. In the special case of ``zero-player'' games, i.e., of Markov chains equipped with additive functionals, the answer is provided by the mean ergodic theorem. We generalize this result to repeated games. We show that the mean payoff is independent of the initial state for all state-dependent perturbations of the rewards if and only if an ergodicity condition is verified. The latter is characterized by the uniqueness modulo constants of nonlinear harmonic functions (fixed points of the recession function associated to the Shapley operator), or, in the special case of stochastic games with finite action spaces and perfect information, by a reachability condition involving conjugate subsets of states in directed hypergraphs. We show that the ergodicity condition for games only depends on the support of the transition probability, and that it can be checked in polynomial time when the number of states is fixed.
Keywords: fixed point, mean ergodic theorem, Shapley operators, dynamic programming, nonexpansive mappings, zero-sum games, mean payoff, directed hypergraphs., Nonlinear ergodic theorem, Galois connections, semigroups of contractions, Poisson equation.
Mathematics Subject Classification: Primary: 47H25; Secondary: 91A20, 05C65, 06A1.
Citation: Marianne Akian, Stéphane Gaubert, Antoine Hochart. Ergodicity conditions for zero-sum games. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 3901-3931. doi: 10.3934/dcds.2015.35.3901
References:
[1]

M. Akian and S. Gaubert, Spectral theorem for convex monotone homogeneous maps and ergodic control, Nonlinear Analysis, T.M.A., 52 (2003), 637-679. doi: 10.1016/S0362-546X(02)00170-0.

[2]

M. Akian, S. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps,, Trans. Amer. Math. Soc., ().  doi: 10.1090/S0002-9947-2015-06413-7.

[3]

M. Akian, S. Gaubert and C. Walsh, The max-plus Martin boundary, Documenta Mathematica, 14 (2009), 195-240, URL http://www.math.uni-bielefeld.de/documenta/vol-14/09.html.

[4]

M. Akian, S. Gaubert and A. Hochart, Fixed point sets of payment-free shapley operators and structural properties of mean payoff games, in Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, July 7-11, Groningen, The Netherlands, (2014), 1438-1441.

[5]

X. Allamigeon, On the complexity of strongly connected components in directed hypergraphs, Algorithmica, 69 (2014), 335-369. doi: 10.1007/s00453-012-9729-0.

[6]

F. Baccelli, G. Cohen, G. Olsder and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley Series in Probability and Mathematical Statistics, John Wiley, 1992.

[7]

A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, vol. 9 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994, Revised reprint of the 1979 original. doi: 10.1137/1.9781611971262.

[8]

G. Birkhoff, Lattice Theory, vol. 25 of Colloquium publications, American Mathematical Society, Providence, 1995 (first edition, 1940).

[9]

J. Bolte, S. Gaubert and G. Vigeral, Definable zero-sum stochastic games, Mathematics of Operations Research, 40 (2014), 171-191, URL http://arxiv.org/abs/1301.1967, Published online. doi: 10.1287/moor.2014.0666.

[10]

R. Cavazos-Cadena and D. Hernández-Hernández, Poisson equations associated with a homogeneous and monotone function: necessary and sufficient conditions for a solution in a weakly convex case, Nonlinear Anal., 72 (2010), 3303-3313. doi: 10.1016/j.na.2009.12.010.

[11]

H. Everett, Recursive games, in Contributions to the theory of games Vol. III, vol. 39 of Ann. Math. Studies, Princeton University Press, (1957), 47-78.

[12]

A. Fathi and A. Siconolfi, PDE aspects of Aubry-Mather theory for quasiconvex hamiltonians, Calc. Var. Partial Differential Equations, 22 (2005), 185-228. doi: 10.1007/s00526-004-0271-z.

[13]

A. Fathi, The Weak KAM Theorem in Lagrangian Dynamics, Cambridge Studies in Advanced Mathematics, 2014, To appear.

[14]

G. Gallo, G. Longo, S. Nguyen and S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math., 42 (1993), 177-201. doi: 10.1016/0166-218X(93)90045-P.

[15]

S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950. doi: 10.1090/S0002-9947-04-03470-1.

[16]

O. Hernández-Lerma and J. B. Lasserre, Further Topics on Discrete-Time Markov Control Processes, vol. 42 of Applications of Mathematics (New York), Springer-Verlag, New York, 1999, URL http://dx.doi.org/10.1007/978-1-4612-0561-6. doi: 10.1007/978-1-4612-0561-6.

[17]

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.

[18]

E. Kohlberg and A. Neyman, Asymptotic behavior of nonexpansive mappings in normed linear spaces, Israel J. Math., 38 (1981), 269-275. doi: 10.1007/BF02762772.

[19]

B. Lemmens and R. Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge university Press, 2012. doi: 10.1017/CBO9781139026079.

[20]

J.-F. Mertens and A. Neyman, Stochastic games, Internat. J. Game Theory, 10 (1981), 53-66. doi: 10.1007/BF01769259.

[21]

A. Neyman and S. Sorin, Stochastic Games and Applications, vol. 570 of Nato Science Series C, Kluwer Academic Publishers, 2003. doi: 10.1007/978-94-010-0189-2.

[22]

R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988), iv+137pp. doi: 10.1090/memo/0391.

[23]

R. D. Nussbaum, Iterated nonlinear maps and Hilbert's projective metric. II, Mem. Amer. Math. Soc., 79 (1989), iv+118pp. doi: 10.1090/memo/0401.

[24]

O. Ore, Galois connexions, Trans. Amer. Math. Soc., 55 (1944), 493-513. doi: 10.1090/S0002-9947-1944-0010555-7.

[25]

J. Renault, Uniform value in dynamic programming, Journal of the European Mathematical Society, 13 (2011), 309-330. doi: 10.4171/JEMS/254.

[26]

R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, 1998. doi: 10.1007/978-3-642-02431-3.

[27]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel J. Math., 121 (2001), 221-246. doi: 10.1007/BF02802505.

[28]

S. Sorin, Asymptotic properties of monotonic nonexpansive mappings, Discrete Event Dynamic Systems, 14 (2004), 109-122. doi: 10.1023/B:DISC.0000005011.93152.d8.

[29]

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.

[30]

P. Whittle, Optimization Over Time. Vol. II, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1983, Dynamic programming and stochastic control.

[31]

K. Yang and Q. Zhao, The balance problem of min-max systems is co-NP hard, Systems & Control Letters, 53 (2004), 303-310. doi: 10.1016/j.sysconle.2004.05.009.

show all references

References:
[1]

M. Akian and S. Gaubert, Spectral theorem for convex monotone homogeneous maps and ergodic control, Nonlinear Analysis, T.M.A., 52 (2003), 637-679. doi: 10.1016/S0362-546X(02)00170-0.

[2]

M. Akian, S. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps,, Trans. Amer. Math. Soc., ().  doi: 10.1090/S0002-9947-2015-06413-7.

[3]

M. Akian, S. Gaubert and C. Walsh, The max-plus Martin boundary, Documenta Mathematica, 14 (2009), 195-240, URL http://www.math.uni-bielefeld.de/documenta/vol-14/09.html.

[4]

M. Akian, S. Gaubert and A. Hochart, Fixed point sets of payment-free shapley operators and structural properties of mean payoff games, in Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, July 7-11, Groningen, The Netherlands, (2014), 1438-1441.

[5]

X. Allamigeon, On the complexity of strongly connected components in directed hypergraphs, Algorithmica, 69 (2014), 335-369. doi: 10.1007/s00453-012-9729-0.

[6]

F. Baccelli, G. Cohen, G. Olsder and J.-P. Quadrat, Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley Series in Probability and Mathematical Statistics, John Wiley, 1992.

[7]

A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, vol. 9 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994, Revised reprint of the 1979 original. doi: 10.1137/1.9781611971262.

[8]

G. Birkhoff, Lattice Theory, vol. 25 of Colloquium publications, American Mathematical Society, Providence, 1995 (first edition, 1940).

[9]

J. Bolte, S. Gaubert and G. Vigeral, Definable zero-sum stochastic games, Mathematics of Operations Research, 40 (2014), 171-191, URL http://arxiv.org/abs/1301.1967, Published online. doi: 10.1287/moor.2014.0666.

[10]

R. Cavazos-Cadena and D. Hernández-Hernández, Poisson equations associated with a homogeneous and monotone function: necessary and sufficient conditions for a solution in a weakly convex case, Nonlinear Anal., 72 (2010), 3303-3313. doi: 10.1016/j.na.2009.12.010.

[11]

H. Everett, Recursive games, in Contributions to the theory of games Vol. III, vol. 39 of Ann. Math. Studies, Princeton University Press, (1957), 47-78.

[12]

A. Fathi and A. Siconolfi, PDE aspects of Aubry-Mather theory for quasiconvex hamiltonians, Calc. Var. Partial Differential Equations, 22 (2005), 185-228. doi: 10.1007/s00526-004-0271-z.

[13]

A. Fathi, The Weak KAM Theorem in Lagrangian Dynamics, Cambridge Studies in Advanced Mathematics, 2014, To appear.

[14]

G. Gallo, G. Longo, S. Nguyen and S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math., 42 (1993), 177-201. doi: 10.1016/0166-218X(93)90045-P.

[15]

S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950. doi: 10.1090/S0002-9947-04-03470-1.

[16]

O. Hernández-Lerma and J. B. Lasserre, Further Topics on Discrete-Time Markov Control Processes, vol. 42 of Applications of Mathematics (New York), Springer-Verlag, New York, 1999, URL http://dx.doi.org/10.1007/978-1-4612-0561-6. doi: 10.1007/978-1-4612-0561-6.

[17]

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.

[18]

E. Kohlberg and A. Neyman, Asymptotic behavior of nonexpansive mappings in normed linear spaces, Israel J. Math., 38 (1981), 269-275. doi: 10.1007/BF02762772.

[19]

B. Lemmens and R. Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge university Press, 2012. doi: 10.1017/CBO9781139026079.

[20]

J.-F. Mertens and A. Neyman, Stochastic games, Internat. J. Game Theory, 10 (1981), 53-66. doi: 10.1007/BF01769259.

[21]

A. Neyman and S. Sorin, Stochastic Games and Applications, vol. 570 of Nato Science Series C, Kluwer Academic Publishers, 2003. doi: 10.1007/978-94-010-0189-2.

[22]

R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988), iv+137pp. doi: 10.1090/memo/0391.

[23]

R. D. Nussbaum, Iterated nonlinear maps and Hilbert's projective metric. II, Mem. Amer. Math. Soc., 79 (1989), iv+118pp. doi: 10.1090/memo/0401.

[24]

O. Ore, Galois connexions, Trans. Amer. Math. Soc., 55 (1944), 493-513. doi: 10.1090/S0002-9947-1944-0010555-7.

[25]

J. Renault, Uniform value in dynamic programming, Journal of the European Mathematical Society, 13 (2011), 309-330. doi: 10.4171/JEMS/254.

[26]

R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, 1998. doi: 10.1007/978-3-642-02431-3.

[27]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel J. Math., 121 (2001), 221-246. doi: 10.1007/BF02802505.

[28]

S. Sorin, Asymptotic properties of monotonic nonexpansive mappings, Discrete Event Dynamic Systems, 14 (2004), 109-122. doi: 10.1023/B:DISC.0000005011.93152.d8.

[29]

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.

[30]

P. Whittle, Optimization Over Time. Vol. II, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 1983, Dynamic programming and stochastic control.

[31]

K. Yang and Q. Zhao, The balance problem of min-max systems is co-NP hard, Systems & Control Letters, 53 (2004), 303-310. doi: 10.1016/j.sysconle.2004.05.009.

[1]

Antoine Hochart. An accretive operator approach to ergodic zero-sum stochastic games. Journal of Dynamics and Games, 2019, 6 (1) : 27-51. doi: 10.3934/jdg.2019003
[2]

Salah Eddine Choutri, Boualem Djehiche, Hamidou Tembine. Optimal control and zero-sum games for Markov chains of mean-field type. Mathematical Control and Related Fields, 2019, 9 (3) : 571-605. doi: 10.3934/mcrf.2019026
[3]

René Carmona, Kenza Hamidouche, Mathieu Laurière, Zongjun Tan. Linear-quadratic zero-sum mean-field type games: Optimality conditions and policy optimization. Journal of Dynamics and Games, 2021, 8 (4) : 403-443. doi: 10.3934/jdg.2021023
[4]

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa. Average optimal strategies for zero-sum Markov games with poorly known payoff function on one side. Journal of Dynamics and Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105
[5]

Alexander J. Zaslavski. Structure of approximate solutions of dynamic continuous time zero-sum games. Journal of Dynamics and Games, 2014, 1 (1) : 153-179. doi: 10.3934/jdg.2014.1.153
[6]

Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete and Continuous Dynamical Systems, 2021, 41 (7) : 3021-3029. doi: 10.3934/dcds.2020395
[7]

Xiangxiang Huang, Xianping Guo, Jianping Peng. A probability criterion for zero-sum stochastic games. Journal of Dynamics and Games, 2017, 4 (4) : 369-383. doi: 10.3934/jdg.2017020
[8]

Shui-Hung Hou. On an application of fixed point theorem to nonlinear inclusions. Conference Publications, 2011, 2011 (Special) : 692-697. doi: 10.3934/proc.2011.2011.692
[9]

Alexander J. Zaslavski. Turnpike properties of approximate solutions of dynamic discrete time zero-sum games. Journal of Dynamics and Games, 2014, 1 (2) : 299-330. doi: 10.3934/jdg.2014.1.299
[10]

Shaotao Hu, Yuanheng Wang, Bing Tan, Fenghui Wang. Inertial iterative method for solving variational inequality problems of pseudo-monotone operators and fixed point problems of nonexpansive mappings in Hilbert spaces. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022060
[11]

Zhihong Xia, Peizheng Yu. A fixed point theorem for twist maps. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022045
[12]

Sylvain Sorin, Guillaume Vigeral. Reversibility and oscillations in zero-sum discounted stochastic games. Journal of Dynamics and Games, 2015, 2 (1) : 103-115. doi: 10.3934/jdg.2015.2.103
[13]

Qingmeng Wei, Zhiyong Yu. Time-inconsistent recursive zero-sum stochastic differential games. Mathematical Control and Related Fields, 2018, 8 (3&4) : 1051-1079. doi: 10.3934/mcrf.2018045
[14]

Beatris A. Escobedo-Trujillo. Discount-sensitive equilibria in zero-sum stochastic differential games. Journal of Dynamics and Games, 2016, 3 (1) : 25-50. doi: 10.3934/jdg.2016002
[15]

Cecilia González-Tokman, Anthony Quas. A concise proof of the multiplicative ergodic theorem on Banach spaces. Journal of Modern Dynamics, 2015, 9: 237-255. doi: 10.3934/jmd.2015.9.237
[16]

Shrey Sanadhya. A shrinking target theorem for ergodic transformations of the unit interval. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022042
[17]

Jingzhen Liu, Ka Fai Cedric Yiu, Alain Bensoussan. Ergodic control for a mean reverting inventory model. Journal of Industrial and Management Optimization, 2018, 14 (3) : 857-876. doi: 10.3934/jimo.2017079
[18]

Libin Mou, Jiongmin Yong. Two-person zero-sum linear quadratic stochastic differential games by a Hilbert space method. Journal of Industrial and Management Optimization, 2006, 2 (1) : 95-117. doi: 10.3934/jimo.2006.2.95
[19]

Fabien Gensbittel, Miquel Oliu-Barton, Xavier Venel. Existence of the uniform value in zero-sum repeated games with a more informed controller. Journal of Dynamics and Games, 2014, 1 (3) : 411-445. doi: 10.3934/jdg.2014.1.411
[20]

Chandan Pal, Somnath Pradhan. Zero-sum games for pure jump processes with risk-sensitive discounted cost criteria. Journal of Dynamics and Games, 2022, 9 (1) : 13-25. doi: 10.3934/jdg.2021020

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (89)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy