{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:46:45Z","timestamp":1777520805234,"version":"3.51.4"},"reference-count":56,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>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\u2013Frobenius theory.<\/jats:p>","DOI":"10.1142\/s0218196711006674","type":"journal-article","created":{"date-parts":[[2011,6,29]],"date-time":"2011-06-29T08:01:02Z","timestamp":1309334462000},"page":"1250001","source":"Crossref","is-referenced-by-count":85,"title":["TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES"],"prefix":"10.1142","volume":"22","author":[{"given":"MARIANNE","family":"AKIAN","sequence":"first","affiliation":[{"name":"INRIA Saclay\u2013\u00cele-de-France, France"},{"name":"CMAP, \u00c9cole Polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ST\u00c9PHANE","family":"GAUBERT","sequence":"additional","affiliation":[{"name":"INRIA Saclay\u2013\u00cele-de-France, France"},{"name":"CMAP, \u00c9cole Polytechnique, Route de Saclay, 91128 Palaiseau Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER","family":"GUTERMAN","sequence":"additional","affiliation":[{"name":"Moscow State University, Leninskie Gory, 119991, GSP-1, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","series-title":"Discrete Mathematics and Its Applications","volume-title":"Handbook of Linear Algebra","volume":"39","author":"Akian M.","year":"2006"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2010.04.003"},{"key":"rf7","author":"Allamigeon X.","journal-title":"Linear Algebra Appl."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1080\/02331930410001695283"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.016"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.11.007"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210500002274"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.10.004"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00104-T"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00655-9"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.029"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-006-9104-9"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.09.008"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S1367-5788(99)90091-3"},{"key":"rf21","unstructured":"G.\u00a0Cohen, S.\u00a0Gaubert and J. P.\u00a0Quadrat, Optimal Control and Partial Differential Equations, eds. J. L.\u00a0Menaldi, E.\u00a0Rofman and A.\u00a0Sulem (IOS Press, 2001)\u00a0pp. 325\u2013334."},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.08.010"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/377\/06987"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1080\/026811199281967"},{"key":"rf28","unstructured":"M.\u00a0Develin, F.\u00a0Santos and B.\u00a0Sturmfels, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ\u00a052 (Cambridge Univ. Press, Cambridge, 2005)\u00a0pp. 213\u2013242."},{"key":"rf29","first-page":"139","volume":"601","author":"Einsiedler M.","journal-title":"J. Reine Angew. Math."},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"rf32","volume-title":"Competitive Markov Decision Processes","author":"Filar J. A.","year":"1997"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/S0764-4442(97)82710-3"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-04-03470-1"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.09.019"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.03.012"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-010-0246-4"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"rf42","first-page":"67","volume":"1","author":"Gondran M.","journal-title":"E.D.F., Bulletin de la Direction des Etudes et recherches, S\u00e9rie C, Math\u00e9matiques, Informatique"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9207-x"},{"key":"rf46","doi-asserted-by":"publisher","DOI":"10.1007\/BF01440235"},{"key":"rf47","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00235-9"},{"key":"rf48","volume-title":"Tropical Algebraic Geometry","author":"Itenberg I.","year":"2007"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1080\/00927870902828793"},{"key":"rf52","unstructured":"M.\u00a0Joswig, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ\u00a052 (Cambridge University Press, Cambridge, 2005)\u00a0pp. 409\u2013431."},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.1137\/070686652"},{"key":"rf55","first-page":"187","volume":"1","author":"Joswig M.","journal-title":"Albanian J. Math."},{"key":"rf56","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90078-X"},{"key":"rf57","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2006.890478"},{"key":"rf58","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.3.366"},{"key":"rf60","doi-asserted-by":"publisher","DOI":"10.1137\/090747191"},{"key":"rf61","doi-asserted-by":"publisher","DOI":"10.1137\/1011093"},{"key":"rf62","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010266012029"},{"key":"rf63","doi-asserted-by":"crossref","first-page":"519","DOI":"10.3934\/dcds.2002.8.519","volume":"8","author":"Mallet-Paret J.","journal-title":"Discrete Contin. Dyn. Syst."},{"key":"rf64","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970037727X"},{"key":"rf66","doi-asserted-by":"publisher","DOI":"10.1080\/02331930600819852"},{"key":"rf67","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90233-8"},{"key":"rf68","doi-asserted-by":"publisher","DOI":"10.1007\/BF01805562"},{"key":"rf70","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/377\/06998"},{"key":"rf71","doi-asserted-by":"publisher","DOI":"10.1007\/BF02802505"},{"key":"rf72","doi-asserted-by":"publisher","DOI":"10.1080\/02331930108844567"},{"key":"rf74","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1993.1013"},{"key":"rf75","first-page":"209","volume":"7","author":"Vincent J. M.","journal-title":"DEDS: Theory and Applications"},{"key":"rf76","first-page":"179","volume":"13","author":"Zimmermann K.","journal-title":"Ekonomicko-matematicky Obzor"},{"key":"rf77","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196711006674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T23:24:29Z","timestamp":1592695469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196711006674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":56,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1142\/S0218196711006674"],"URL":"https:\/\/doi.org\/10.1142\/s0218196711006674","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2]]}}}