66 citations · 468 across the 34 of their papers we have counts for
3 papers · 1 filter
Sharper bounds on the thresholds for sensitive and Blackwell optimality
Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément +1
In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount o…
Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games
Xavier Allamigeon, Stéphane Gaubert, Ricardo D. Katz +1
We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on a…
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…