Semidefinite programming can be considered over any real closed field, including fields of Puiseux series equipped with their nonarchimedean valuation. Nonarchimedean semidefinite programs encode parametric families of classical semidefinite programs, for sufficiently large values of the parameter. Recently, a correspondence has been established between nonarchimedean semidefinite programs and stochastic mean payoff games with perfect information. This correspondence relies on tropical geometry. It allows one to solve generic nonarchimedean semidefinite feasibility problems, of large scale, by means of stochastic game algorithms. In this paper, we show that the mean payoff of these games can be interpreted as a condition number for the corresponding nonarchimedean feasibility problems. This number measures how close a feasible instance is from being infeasible, and vice versa. We show that it coincides with the maximal radius of a ball in Hilbert's projective metric, that is included in the feasible set. The geometric interpretation of the condition number relies in particular on a duality theorem for tropical semidefinite feasibility programs. Then, we bound the complexity of the feasibility problem in terms of the condition number. We finally give explicit bounds for this condition number, in terms of the characteristics of the stochastic game. As a consequence, we show that the simplest algorithm to decide whether a stochastic mean payoff game is winning, namely value iteration, has a pseudopolynomial complexity when the number of random positions is fixed.
@cite_9: 
@cite_15: We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V, E), with local rewards r: E→ℝ, and three types of vertices: black VB, white VW, and random VR forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not. In fact, a pseudo-polynomial algorithm for these games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random nodes can be solved in pseudo-polynomial time. That is, for any such game with a few random nodes |VR|=O(1), a saddle point in pure stationary strategies can be found in time polynomial in |VW|+|VB|, the maximum absolute local reward R, and the common denominator of the transition probabilities.
@cite_16: Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4^r r^ O(1) n^ O(1) . In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2^r (r log r + n)), thus improving both time bounds. While the algorithm is simple, the analysis leading to this time bound is involved, using techniques of extremal combinatorics to identify worst case instances for the algorithm.
When specialized to stochastic mean payoff games with perfect information, our bounds should be compared with the one of Boros, Elbassioni, Gurvich, and Makino @cite_15 . The authors of @cite_15 generalize the pumping'' algorithm, developed for deterministic games by Gurvich, Karzanov, and Khachiyan @cite_9 , to the case of stochastic games. The resulting algorithm is also pseudopolynomial if the number of random positions is fixed. The algorithm of Ibsen-Jensen and Miltersen @cite_16 yields a stronger bound in the case of simple stochastic games, still assuming that the number of random positions is fixed.