Speaker: Stephane Gaubert

Title: Zero-sum games, non-archimedean convexity and sinuous central paths

Abstract: Tropical geometry allows one to relate convex programming over non-archimedean ordered fields, like the field of Puiseux series with real coefficients, with zero-sum games with “mean” or “ergodic” payoff. The optimality certificates, called bias vectors or potentials, in the ergodic game litterature, appear to constitute tropical convex sets, i.e., log-limits of classical convex sets. In this way, special classes of games, like deterministic games or perfect information stochastic games with finite state and action spaces, correspond to special classes of convex sets, like polyhedra or spectrahedra. This approach allows one to transfer complexity results from mathematical programming to algorithmic game theory, relating in particular the complexity of mean payoff games with the complexity of pivoting methods in linear programming. It also allows one to construct a classical linear program in which the central path makes a number of “sharp turns”. Aaaaexponential in the number of constraints, disproving the continuous analogue of the Hirsch’s conjecture, proposed by Deza, Terlaky et Zinchenko. This talk will be intended as a general introduction to tropical methods in optimization and game theory, leading to the previous recent results. It is based in particular on the following works:

 - M. Akian, S. Gaubert, and A. Guterman. Tropical polyhedra are equivalent to mean payoff games ,

 International of Algebra and Computation, 22(1), 2012.

 - X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig. Tropicalizing the simplex algorithm. SIAM J. Disc. Math., 29(2):751–795, 2015

 - X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig, Long and winding central paths, 2014.

 arXiv:1405.4161.

 - X. Allamigeon, S. Gaubert, and M. Skomra. Solving generic nonarchimedean semidefinite programs

 using stochastic game algorithms, 2016. To appear in the Proc. of ISSAC, arXiv:1603.06916