Скачать или смотреть Stéphane Gaubert - Ambitropical Convexity, Mean Payoff Games and Nonarchimedean Convex Programming

Convex sets can be defined over ordered fields with a non-archimedean valuation. Then, tropical convex sets arise as images by the valuation of non-archimedean convex sets. The tropicalization of polyhedra and spectrahedra can be described in terms of deterministic and stochastic games with mean payoff, being characterized in terms of sub or super-fixed point sets of Shapley operators, which determine the value of the game. This is motivated by open complexity issues in linear programming. We shall discuss here especially a generalization of tropical convexity: considering fixed point sets of Shapley operators, instead of sub or super-fixed points sets, leads to a richer “ambitropical” theory, which includes tropical convexity and its dual in a unified framework. We shall present several characterizations of ambitropical convex sets, with features related to normed spaces (nonexpansive retracts and hyperconvexity), lattice theory (order preserving retracts), or of a combinatorial nature (cell decompositions in alcoved polyhedra).

The results on ambitropical convexity is from a work with Akian and Vannucci; the ones on the tropicalization of nonarchimedean convex sets are from works with Allamigeon, Benchimol, Joswig and Skomra.

Stéphane Gaubert (INRIA & Ecole Polytechnique)