Skip to Main content Skip to Navigation
Conference papers

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
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.
Document type :
Conference papers
Complete list of metadata
Contributor : Stephane Gaubert Connect in order to contact the contributor
Submitted on : Tuesday, February 3, 2015 - 3:01:46 PM
Last modification on : Saturday, June 25, 2022 - 9:09:23 PM


  • HAL Id : hal-01112709, version 1



Stéphane Gaubert. From tropical linear algebra to zero-sum games. The 19th International Linear Algebra Society Conference, Aug 2014, Seoul, South Korea. ⟨hal-01112709⟩



Record views