A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors

Marianne Akian; Stéphane Gaubert; Antoine Hochart

doi:10.3934/dcds.2020009

Article Contents

2020, Volume 40, Issue 1: 207-231. Doi: 10.3934/dcds.2020009

This issue Previous Article Singularities of certain finite energy solutions to the Navier-Stokes system Next Article Convergence of the follow-the-leader scheme for scalar conservation laws with space dependent flux

A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors

1.
Inria and CMAP, CNRS, École polytechnique, Institut Polytechnique de Paris, Route de Saclay, 91128 Palaiseau Cedex, France
2.
Facultad de Ingeniería y Ciencia, Universidad Adolfo Ibáñez, Diagonal Las Torres 2640, Santiago, Chile

^* Corresponding author
^* Corresponding author

The first and second authors were partially supported by the Gaspard Monge corporate sponsorship Program (PGMO) of EDF, Orange, Thales and Fondation Mathématique Jacques Hadmard, by the iCODE Institute, research project of the IDEX Paris-Saclay, and by the Hadamard Mathematics LabEx (LMH) through the grant number ANR-11-LABX-0056-LMH in the "Programme des Investissements d'Avenir"

Received: December 31, 2018

Revised: March 31, 2019

Published: October 2019

The third author is supported by FONDECYT grant 3180662

Abstract Full Text(HTML) Figure(3) Related Papers Cited by

Abstract

We establish a generalized Perron-Frobenius theorem, based on a combinatorial criterion which entails the existence of an eigenvector for any nonlinear order-preserving and positively homogeneous map $ f $ acting on the open orthant $ \mathbb{R}_{ >0}^n $. This criterion involves dominions, i.e., sets of states that can be made invariant by one player in a two-person game that only depends on the behavior of $ f $ "at infinity". In this way, we characterize the situation in which for all $ \alpha, \beta > 0 $, the "slice space" $ \mathcal{S}_\alpha^\beta : = \{ x \in \mathbb{R}_{ >0}^n \mid \alpha x \leqslant f(x) \leqslant \beta x \} $ is bounded in Hilbert's projective metric, or, equivalently, for all uniform perturbations $ g $ of $ f $, all the orbits of $ g $ are bounded in Hilbert's projective metric. This solves a problem raised by Gaubert and Gunawardena (Trans. AMS, 2004). We also show that the uniqueness of an eigenvector is characterized by a dominion condition, involving a different game depending now on the local behavior of $ f $ near an eigenvector. We show that the dominion conditions can be verified by directed hypergraph methods. We finally illustrate these results by considering specific classes of nonlinear maps, including Shapley operators, generalized means and nonnegative tensors.

Keywords:

Mathematics Subject Classification: Primary: 47J10; Secondary: 47H09, 47H07, 91A15.

Citation:

Full Text(HTML)

Figure 1. The hypergraphs $ \mathcal{H}_\infty^\pm(T) $ associated with $ T $ defined by (2)

Download: Full-size image PowerPoint slide

Figure 2. The hypergraphs $ \mathcal{H}_\infty^\pm(T) $ associated with $ T $ (12)

Download: Full-size image PowerPoint slide

Figure 3. The graph $ \mathcal{G}_\infty( \mathcal{F}) $ and the hypergraph $ \mathcal{H}_\infty( \mathcal{F}) $ associated with the nonnegative tensor $ \mathcal{F} $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	M. Akian and S. Gaubert, Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Anal., 52 (2003), 637-679. doi: 10.1016/S0362-546X(02)00170-0.
[2]	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.
[3]	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. doi: 10.1109/CDC.2015.7403138.
[4]	M. Akian, S. Gaubert, B. Lemmens and R. Nussbaum, Iteration of order preserving subhomogeneous maps on a cone, Math. Proc. Cambridge Philos. Soc., 140 (2006), 157-176. doi: 10.1017/S0305004105008832.
[5]	M. Akian, S. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps, Trans. Amer. Math. Soc., 368 (2016), 1271-1320. doi: 10.1090/S0002-9947-2015-06413-7.
[6]	X. Allamigeon, On the complexity of strongly connected components in directed hypergraphs, Algorithmica, 69 (2014), 335-369. doi: 10.1007/s00453-012-9729-0.
[7]	V. Anantharam and V. S. Borkar, A variational formula for risk-sensitive reward, SIAM J. Control Optim., 55 (2017), 961-988. doi: 10.1137/151002630.
[8]	S. Arora and B. Barak, Computational Complexity, Cambridge University Press, Cambridge, 2009. doi: 10.1017/CBO9780511804090.
[9]	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.
[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]	A. Fathi, Weak KAM theorem in Lagrangian dynamics, 2008, Tenth preliminary version, available online.
[12]	W. H. Fleming and D. Hernández-Hernández, Risk-sensitive control of finite state machines on an infinite horizon. I, SIAM J. Control Optim., 35 (1997), 1790-1810. doi: 10.1137/S0363012995291622.
[13]	S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738-749. doi: 10.1016/j.laa.2011.02.042.
[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 (electronic). doi: 10.1090/S0002-9947-04-03470-1.
[16]	S. Gaubert and G. Vigeral, A maximin characterisation of the escape rate of non-expansive mappings in metrically convex spaces, Math. Proc. Cambridge Philos. Soc., 152 (2012), 341-363. doi: 10.1017/S0305004111000673.
[17]	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.
[18]	A. Hochart, An accretive operator approach to ergodic zero-sum stochastic games, J. Dyn. Games, 6 (2019), 27-51. doi: 10.3934/jdg.2019003.
[19]	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.
[20]	V. N. Kolokoltsov and V. P. Maslov, Idempotent Analysis and Its Applications, vol. 401 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1997. doi: 10.1007/978-94-015-8901-7.
[21]	U. Krause, Positive Dynamical Systems in Discrete Time, vol. 62 of De Gruyter Studies in Mathematics, De Gruyter, Berlin, 2015. doi: 10.1515/9783110365696.
[22]	B. Lemmens, B. Lins and R. Nussbaum, Detecting fixed points of nonexpansive maps by illuminating the unit ball, Israel J. Math., 224 (2018), 231-262. doi: 10.1007/s11856-018-1641-0.
[23]	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.
[24]	L.-H. Lim, Singular values and eigenvalues of tensors: A variational approach, in 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Puerto Vallarta, Mexico, 2005,129–132. doi: 10.1109/CAMAP.2005.1574201.
[25]	A. Macintyre and A. J. Wilkie, On the decidability of the real exponential field, in Kreiseliana, A K Peters, Wellesley, MA, 1996,441–467.
[26]	J. Mallet-Paret and R. D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete Contin. Dyn. Syst., 8 (2002), 519-562. doi: 10.3934/dcds.2002.8.519.
[27]	V. Metz, The short-cut test, J. Funct. Anal., 220 (2005), 118-156. doi: 10.1016/j.jfa.2004.06.008.
[28]	A. Neyman and S. Sorin (eds.), Stochastic Games and Applications, vol. 570 of NATO Science Series C: Mathematical and Physical Sciences, Kluwer Academic Publishers, Dordrecht, 2003.
[29]	R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988), ⅳ+137pp. doi: 10.1090/memo/0391.
[30]	R. D. Nussbaum, Iterated nonlinear maps and Hilbert's projective metric. Ⅱ, Mem. Amer. Math. Soc., 79 (1989), ⅳ+118pp. doi: 10.1090/memo/0401.
[31]	L. Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput., 40 (2005), 1302-1324. doi: 10.1016/j.jsc.2005.05.007.
[32]	J. Renault, Uniform value in dynamic programming, J. Eur. Math. Soc. (JEMS), 13 (2011), 309-330. doi: 10.4171/JEMS/254.
[33]	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.
[34]	D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games, Israel J. Math., 121 (2001), 221-246. doi: 10.1007/BF02802505.
[35]	C. Sabot, Existence and uniqueness of diffusions on finitely ramified self-similar fractals, Ann. Sci. École Norm. Sup. (4), 30 (1997), 605–673. doi: 10.1016/S0012-9593(97)89934-X.
[36]	S. Sorin, Asymptotic properties of monotonic nonexpansive mappings, Discrete Event Dyn. Syst., 14 (2004), 109-122. doi: 10.1023/B:DISC.0000005011.93152.d8.
[37]	H. R. Thieme, Eigenfunctionals of Homogeneous Order-Preserving Maps with Applications to Sexually Reproducing Populations, J. Dynam. Differential Equations, 28 (2016), 1115-1144. doi: 10.1007/s10884-015-9463-9.
[38]	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.
[39]	K. Yang and Q. Zhao, The balance problem of min-max systems is co-NP hard, Systems Control Lett., 53 (2004), 303-310. doi: 10.1016/j.sysconle.2004.05.009.