Tropical polyhedra are equivalent to mean payoff games

Marianne Akian 1, 2 Stéphane Gaubert 1, 2 A. Guterman 3
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : 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.
Type de document :
Article dans une revue
Internat. J. Algebra Comput., e, 2012, 22 (1), pp.1250001, 43. 〈10.1142/S0218196711006674〉
Liste complète des métadonnées
Contributeur : Canimogy Cogoulane <>
Soumis le : vendredi 18 janvier 2013 - 16:22:56
Dernière modification le : jeudi 10 mai 2018 - 02:05:54

Lien texte intégral




Marianne Akian, Stéphane Gaubert, A. Guterman. Tropical polyhedra are equivalent to mean payoff games. Internat. J. Algebra Comput., e, 2012, 22 (1), pp.1250001, 43. 〈10.1142/S0218196711006674〉. 〈hal-00778078〉



Consultations de la notice