From tropical linear algebra to zero-sum games

Stéphane Gaubert 1, 2
1 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 : Recently, some relations have appeared between tropical algebra, linear programming, Perron-Frobenius theory, and zero-sum games. This talk is devoted to these relations and to their consequences. In particular, we shall make a connection between two well known unsolved questions. The first is the existence of a strongly polynomial pivoting rule in linear programming. Such a rule would allow us to solve a linear program in a number of arithmetic operations bounded only by the number of variables and the number of constraints. The second question is the existence of a polynomial algorithm to solve mean payoff games. In work with Allamigeon, Benchimol, and Joswig, we showed that a positive answer to the first question would yield a positive answer to the second, provided the pivoting rule satisfies certain conditions. This uses the equivalence between mean payoff games and tropical linear programs, established in an earlier work with Akian and Guterman. The proof of these results will give us the opportunity to see at work non-linear Perron-Frobenius theory, as well as a number of basic tropical tools: tropical eigenvalues, extensions or symmetrization of semirings, tropical analogues of Cramer theorem.
Type de document :
Communication dans un congrès
The 19th International Linear Algebra Society Conference, Aug 2014, Seoul, South Korea. 2014, 〈http://www.ilas2014.org/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01112709
Contributeur : Stephane Gaubert <>
Soumis le : mardi 3 février 2015 - 15:01:46
Dernière modification le : jeudi 10 mai 2018 - 02:03:57

Identifiants

  • HAL Id : hal-01112709, version 1

Collections

Citation

Stéphane Gaubert. From tropical linear algebra to zero-sum games. The 19th International Linear Algebra Society Conference, Aug 2014, Seoul, South Korea. 2014, 〈http://www.ilas2014.org/〉. 〈hal-01112709〉

Partager

Métriques

Consultations de la notice

347