334 citations · 2.6k across the 129 of their papers we have counts for
9 papers · 1 filter
Generic uniqueness of the bias vector of mean payoff zero-sum games
Marianne Akian, Stéphane Gaubert, Antoine Hochart
Zero-sum mean payoff games can be studied by means of a nonlinear spectral problem. When the state space is finite, the latter consists in finding an eigenpair solution of…
The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert
We introduce an algorithm which solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a flip invariance property on the set of ac…
Ergodicity conditions for zero-sum games
Marianne Akian, Stéphane Gaubert, Antoine Hochart
A basic question for zero-sum repeated games consists in determining whether the mean payoff per time unit is independent of the initial state. In the special case of "zero-player"…
Long and winding central paths
Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert +1
We disprove a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with inequalities in dimensio…
Non-linear eigenvalue problems arising from growth maximization of positive linear dynamical systems
Vincent Calvez, Pierre Gabriel, Stéphane Gaubert
We study a growth maximization problem for a continuous time positive linear system with switches. This is motivated by a problem of mathematical biology (modeling growth-fragmenta…
Formal Proofs for Nonlinear Optimization
Victor Magron, Xavier Allamigeon, Stéphane Gaubert +1
We present a formally verified global optimization framework. Given a semialgebraic or transcendental function and a compact semialgebraic domain , we use the nonlinear maxp…