From tropical linear algebra to zero-sum games

Invited Plenary TalkInternational audienceRecently, some relations have appeared between tropicalalgebra, linear programming, Perron-Frobenius theory, and zero-sumgames. This talk is devoted to these relations and to theirconsequences. In particular, we shall make a connection between twowell known unsolved questions. The first is the existence of astrongly polynomial pivoting rule in linear programming. Such a rulewould allow us to solve a linear program in a number of arithmeticoperations bounded only by the number of variables and the number ofconstraints. The second question is the existence of a polynomialalgorithm to solve mean payoff games. In work with Allamigeon,Benchimol, and Joswig, we showed that a positive answer to the firstquestion would yield a positive answer to the second, provided thepivoting rule satisfies certain conditions. This uses the equivalencebetween mean payoff games and tropical linear programs, established inan earlier work with Akian and Guterman. The proof of these resultswill give us the opportunity to see at work non-linearPerron-Frobenius theory, as well as a number of basic tropical tools:tropical eigenvalues, extensions or symmetrization of semirings,tropical analogues of Cramer theorem