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

https://hal.inria.fr/hal-01112709
Contributor : Stephane Gaubert <>
Submitted on : Tuesday, February 3, 2015 - 3:01:46 PM
Last modification on : Saturday, May 1, 2021 - 3:38:23 AM

Identifiers

  • HAL Id : hal-01112709, version 1

Citation

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⟩

Share

Metrics

Record views

426