30 November 2021 to 2 December 2021
Le Bois-Marie
Europe/Paris timezone

Ambitropical Convexity, Mean Payoff Games and Nonarchimedean Convex Programming (in person)

2 Dec 2021, 14:50
50m
Centre de conférences Marilyn et James Simons (Le Bois-Marie)

Centre de conférences Marilyn et James Simons

Le Bois-Marie

35, route de Chartres 91440 Bures-sur-Yvette

Speaker

Stéphane Gaubert (INRIA & Ecole Polytechnique)

Description

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.

Presentation Materials