×

Tropical polyhedra are equivalent to mean payoff games. (English) Zbl 1239.14054

Summary: We show that several decision problems originating from max-plus or tropical convexity are equivalent to zero-sum two player game problems. In particular, we set up an equivalence between the external representation of tropical convex sets and zero-sum stochastic games, in which tropical polyhedra correspond to deterministic games with finite action spaces. Then, we show that the winning initial positions can be determined from the associated tropical polyhedron. We obtain as a corollary a game theoretical proof of the fact that the tropical rank of a matrix, defined as the maximal size of a submatrix for which the optimal assignment problem has a unique solution, coincides with the maximal number of rows (or columns) of the matrix which are linearly independent in the tropical sense. Our proofs rely on techniques from non-linear Perron-Frobenius theory.

MSC:

14T05 Tropical geometry (MSC2010)
91A50 Discrete-time games
15A80 Max-plus and related algebras
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Akian M., Discrete Mathematics and Its Applications 39, in: Handbook of Linear Algebra (2006)
[2] DOI: 10.1016/j.jcta.2010.04.003 · Zbl 1246.14078
[3] Allamigeon X., Linear Algebra Appl.
[4] DOI: 10.1080/02331930410001695283 · Zbl 1144.90506
[5] DOI: 10.1016/j.dam.2008.03.016 · Zbl 1178.68637
[6] DOI: 10.1016/j.ipl.2009.11.007 · Zbl 1206.68284
[7] DOI: 10.1017/S0308210500002274 · Zbl 1048.47040
[8] DOI: 10.1016/j.laa.2006.10.004 · Zbl 1119.15018
[9] DOI: 10.1016/0166-218X(92)00104-T · Zbl 0804.06017
[10] DOI: 10.1016/S0024-3795(02)00655-9 · Zbl 1022.15017
[11] DOI: 10.1016/j.dam.2006.04.029 · Zbl 1176.68087
[12] DOI: 10.1007/s10801-006-9104-9 · Zbl 1097.52506
[13] DOI: 10.1016/j.dam.2005.09.008 · Zbl 1090.68119
[14] DOI: 10.1016/S1367-5788(99)90091-3
[15] G. Cohen, S. Gaubert and J. P. Quadrat, Optimal Control and Partial Differential Equations, eds. J. L. Menaldi, E. Rofman and A. Sulem (IOS Press, 2001) pp. 325–334.
[16] DOI: 10.1016/j.laa.2003.08.010 · Zbl 1042.46004
[17] DOI: 10.1090/conm/377/06987
[18] DOI: 10.1016/0890-5401(92)90048-K · Zbl 0756.90103
[19] DOI: 10.1080/026811199281967 · Zbl 0958.47028
[20] M. Develin, F. Santos and B. Sturmfels, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ 52 (Cambridge Univ. Press, Cambridge, 2005) pp. 213–242.
[21] Einsiedler M., J. Reine Angew. Math. 601 pp 139–
[22] DOI: 10.1007/BF01768705 · Zbl 0499.90098
[23] Filar J. A., Competitive Markov Decision Processes (1997) · Zbl 0934.91002
[24] DOI: 10.1016/S0764-4442(97)82710-3 · Zbl 0933.49017
[25] DOI: 10.1090/S0002-9947-04-03470-1 · Zbl 1067.47064
[26] DOI: 10.1016/j.laa.2006.09.019 · Zbl 1110.52002
[27] DOI: 10.1016/j.laa.2009.03.012 · Zbl 1172.52002
[28] DOI: 10.1007/s10801-010-0246-4 · Zbl 1218.52001
[29] DOI: 10.1016/0041-5553(88)90012-2 · Zbl 0695.90105
[30] Gondran M., E.D.F., Bulletin de la Direction des Etudes et recherches, Série C, Mathématiques, Informatique 1 pp 67–
[31] DOI: 10.1007/s00454-009-9207-x · Zbl 1219.14071
[32] DOI: 10.1007/BF01440235 · Zbl 0841.93029
[33] DOI: 10.1016/S0304-3975(02)00235-9 · Zbl 1036.93045
[34] Itenberg I., Tropical Algebraic Geometry (2007) · Zbl 1162.14300
[35] DOI: 10.1080/00927870902828793 · Zbl 1184.15003
[36] M. Joswig, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ 52 (Cambridge University Press, Cambridge, 2005) pp. 409–431.
[37] DOI: 10.1137/070686652 · Zbl 1173.91326
[38] Joswig M., Albanian J. Math. 1 pp 187–
[39] DOI: 10.1016/0012-365X(78)90078-X
[40] DOI: 10.1109/TAC.2006.890478 · Zbl 1366.93351
[41] DOI: 10.1287/moor.5.3.366 · Zbl 0442.90102
[42] DOI: 10.1137/090747191 · Zbl 1213.93128
[43] DOI: 10.1137/1011093 · Zbl 0193.19602
[44] DOI: 10.1023/A:1010266012029 · Zbl 1017.46034
[45] Mallet-Paret J., Discrete Contin. Dyn. Syst. 8 pp 519–
[46] DOI: 10.1137/S009753970037727X · Zbl 1112.90034
[47] DOI: 10.1080/02331930600819852 · Zbl 1121.52002
[48] DOI: 10.1016/0024-3795(86)90233-8 · Zbl 0588.15016
[49] DOI: 10.1007/BF01805562 · Zbl 0747.93014
[50] DOI: 10.1090/conm/377/06998
[51] DOI: 10.1007/BF02802505 · Zbl 1054.91014
[52] DOI: 10.1080/02331930108844567 · Zbl 1007.26010
[53] DOI: 10.1006/aima.1993.1013 · Zbl 0776.13009
[54] Vincent J. M., DEDS: Theory and Applications 7 pp 209–
[55] Zimmermann K., Ekonomicko-matematicky Obzor 13 pp 179–
[56] DOI: 10.1016/0304-3975(95)00188-3 · Zbl 0871.68138
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.