Abstract

We show that a real-valued function on a topological vector space is positively homogeneous of degree one and nonexpansive with respect to a weak Minkowski norm if and only if it can be written as a minimax of linear forms that are nonexpansive with respect to the same norm. We derive a representation of monotone, additively and positively homogeneous functions on L∞L^\infty spaces and on Rn\mathbb{R}^n, which extends results of Kolokoltsov, Rubinov, Singer, and others. We apply this representation to nonconvex risk measures and to zero-sum games. We derive in particular results of representation and polyhedral approximation for the class of Shapley operators arising from games without instantaneous payments (Everett's recursive games).

Author information

Contact details are reproduced from the original publication and may be historical.

Marianne Akian

INRIA Saclay-Ile-de-France, École Polytechnique, Route de Saclay, 91128 Palaiseau, France

marianne.akian@inria.fr

Stéphane Gaubert

INRIA Saclay-Ile-de-France, École Polytechnique, Route de Saclay, 91128 Palaiseau, France

stephane.gaubert@inria.fr

Keywords

  • Nonexpansive maps
  • weak Minkowski norms
  • zero-sum games
  • recursive games
  • Shapley operators
  • risk measures
  • minimax representation

Mathematics Subject Classification

49J35, 91A15, 26B25

References

  1. M. Akian, S. Gaubert: Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Anal., Theory, Meth. Appl., Ser. A 52(2) (2003) 637–679.https://doi.org/10.1016/S0362-546X(02)00170-0Google Scholar
  2. M. Akian, S. Gaubert, A. Hochart: Ergodicity conditions for zero-sum games, Discrete Contin. Dyn. Syst. 35(9) (2015) 3901–3931.https://doi.org/10.3934/dcds.2015.35.3901Google Scholar
  3. M. Akian, S. Gaubert, V. Kolokoltsov: Set coverings and invertibility of functional Galois connections, in: Idempotent Mathematics and Mathematical Physics, Contemp. Math. 377, Amer. Math. Soc., Providence (2005) 19–51.https://doi.org/10.1090/conm/377/06983Google Scholar
  4. M. Akian, S. Gaubert, A. Lakhoua: The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control Optim. 47(2) (2008) 817–848.https://doi.org/10.1137/060655286Google Scholar
  5. C. D. Aliprantis, K. C. Border: Infinite Dimensional Analysis - A Hitchhiker’s Guide, Springer, Berlin (2006).Google Scholar
  6. P. Artzner, F. Delbaen, J.-M. Eber, D. Heath: Coherent measures of risk, Math. Finance 9(3) (1999) 203–228.https://doi.org/10.1111/1467-9965.00068Google Scholar
  7. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  8. D. Blackwell: Discounted dynamic programming, Ann. Math. Statist. 36 (1965) 226–235.https://doi.org/10.1214/aoms/1177700285Google Scholar
  9. M. G. Crandall, L. Tartar: Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78(3) (1980) 385–390.https://doi.org/10.1090/S0002-9939-1980-0553381-XGoogle Scholar
  10. F. Delbaen: Coherent risk measures on general probability spaces, in: Advances in Finance and Stochastics, Springer, Berlin (2002) 1–37.https://doi.org/10.1007/978-3-662-04790-3_1Google Scholar
  11. N. Dunford, J. T. Schwartz: Linear Operators. Part I, Wiley, New York (1988).Google Scholar
  12. J. Dutta, J. E. Martínez-Legaz, A. M. Rubinov: Monotonic analysis over cones I, Optimization 53(2) (2004) 129–146.https://doi.org/10.1080/02331930410001684654Google Scholar
  13. J. Dutta, J. E. Martínez-Legaz, A. M. Rubinov: Monotonic analysis over cones III, J. Convex Analysis 15(3) (2008) 561–579.https://doi.org/10.68381/jca15040Google Scholar
  14. I. Ekeland, R. Témam: Convex Analysis and Variational Problems, Classics in Applied Mathematics 28, SIAM, Philadelphia (1999).https://doi.org/10.1137/1.9781611971088Google Scholar
  15. L. C. Evans: Some min-max methods for the Hamilton-Jacobi equation, Indiana Univ. Math. J. 33(1) (1984) 31–50.https://doi.org/10.1512/iumj.1984.33.33002Google Scholar
  16. H. Everett: Recursive games, in: Contributions to the theory of games 3, Annals of Math. Studies 39, Princeton University Press, Princeton (1957) 47–78.https://doi.org/10.1515/9781400882151-004Google Scholar
  17. J. Filar, K. Vrieze: Competitive Markov Decision Processes, Springer, New York (1997).https://doi.org/10.1007/978-1-4612-4054-9Google Scholar
  18. H. Föllmer, A. Schied: Convex measures of risk and trading constraints, Finance and Stochastics 6(4) (2002) 429–447.https://doi.org/10.1007/s007800200072Google Scholar
  19. H. Föllmer, A. Schied: Stochastic Finance. An Introduction in Discrete Time, extended edition, Walter de Gruyter, Berlin (2011).https://doi.org/10.1515/9783110218053Google Scholar
  20. M. Frittelli, E. Rosazza Gianin: Putting order in risk measures, J. Banking Finance 26(7) (2002) 1473–1486.https://doi.org/10.1016/S0378-4266(02)00270-4Google Scholar
  21. K. Fukuda, A. Prodon: Double description method revisited, in: Combinatorics and Computer Science, Brest 1995, Lecture Notes in Comput. Sci. 1120, Sringer, Berlin (1996) 91–111.https://doi.org/10.1007/3-540-61576-8_77Google Scholar
  22. S. Gaubert, J. Gunawardena: The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc. 356(12) (2004) 4931–4950.https://doi.org/10.1090/S0002-9947-04-03470-1Google Scholar
  23. S. Gaubert, G. Vigeral: A maximin characterisation of the escape rate of nonexpansive mappings in metrically convex spaces, Math. Proc. Cambridge Philos. Soc., 152(2) (2012) 341–363.https://doi.org/10.1017/S0305004111000673Google Scholar
  24. J. Gunawardena: From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems, Theoret. Comput. Sci. 293(1) (2003) 141–167.https://doi.org/10.1016/S0304-3975(02)00235-9Google Scholar
  25. J. Gunawardena, M. Keane: On the existence of cycle times for some nonexpansive maps, Technical Report HPL-BRIMS-95-003, Hewlett-Packard Labs (1995).Google Scholar
  26. V. N. Kolokoltsov: On linear, additive, and homogeneous operators in idempotent analysis, in: Idempotent Analysis, Adv. Soviet Math. 13 (1992) 87–101.https://doi.org/10.1090/advsov/013/04Google Scholar
  27. J.-E. Martínez-Legaz, A. M. Rubinov, I. Singer: Downward sets and their separation and approximation properties, J. Global Optim. 23(2) (2002) 111–137.https://doi.org/10.1023/A:1015583411806Google Scholar
  28. W. M. McEneaney: Max-Plus Methods for Nonlinear Control and Estimation, Systems and Control: Foundations and Applications, Birkhäuser, Boston (2006).Google Scholar
  29. W. M. McEneaney: Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms, Automatica 47(3) (2011) 443–451.https://doi.org/10.1016/j.automatica.2010.10.006Google Scholar
  30. W. M. McEneaney, A. Pandey: Development of an idempotent algorithm for a network-delay game, in: Proc. Conf. Control Applications 2015, chap. 59, SIAM, Philadelphia (2015) 439–446.https://doi.org/10.1137/1.9781611974072.60Google Scholar
  31. J.-J. Moreau: Inf-convolution, sous-additivité, convexité des fonctions numériques, J. Math. Pures Appl. (9) 49 (1970) 109–154.Google Scholar
  32. A. Neyman, S. Sorin: Stochastic Games and Applications, NATO Science Series C 570, Springer, Berlin (2003).https://doi.org/10.1007/978-94-010-0189-2Google Scholar
  33. A. Papadopoulos, M. Troyanov: Weak Minkowski spaces, in: Handbook of Hilbert Geometry, IRMA Lect. Math. Theor. Phys. 22, Eur. Math. Soc., Zürich (2014) 11–32.https://doi.org/10.4171/147-1/1Google Scholar
  34. V. I. Paulsen, M. Tomforde: Vector spaces with an order unit, Indiana Univ. Math. J. 58(3) (2009) 1319–1359.https://doi.org/10.1512/iumj.2009.58.3518Google Scholar
  35. D. Rosenberg, S. Sorin: An operator approach to zero-sum repeated games, Israel J. Math. 121 (2001) 221–246.https://doi.org/10.1007/BF02802505Google Scholar
  36. A. M. Rubinov, I. Singer: Topical and sub-topical functions, downward sets and abstract convexity, Optimization 50(5-6) (2001) 307–351.https://doi.org/10.1080/02331930108844567Google Scholar
  37. H. H. Schaefer: Banach Lattices and Positive Operators, Grundlehren math. Wissenschaften 215, Springer-Verlag, Berlin (1974).https://doi.org/10.1007/978-3-642-65970-6Google Scholar
  38. S. Sorin: Asymptotic properties of monotonic nonexpansive mappings, Discrete Event Dyn. Syst. 14(1) (2004) 109–122.https://doi.org/10.1023/B:DISC.0000005011.93152.d8Google Scholar

Suggested citation

M. Akian, S. Gaubert, A. Hochart. “Minimax Representation of Nonexpansive Functions and Application to Zero-Sum Recursive Games.” Journal of Convex Analysis 25 (2018), No. 1, 225–240. https://doi.org/10.68381/jca25014

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press.