Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming.

Semidefinite programming can be considered over any real closed field,including fields of Puiseux series equipped with their nonarchimedeanvaluation. Nonarchimedean semidefinite programs encode parametric families ofclassical semidefinite programs, for sufficiently large values of theparameter. Recently, a correspondence has been established betweennonarchimedean semidefinite programs and stochastic mean payoff games withperfect information. This correspondence relies on tropical geometry. It allowsone to solve generic nonarchimedean semidefinite feasibility problems, of largescale, by means of stochastic game algorithms. In this paper, we show that themean payoff of these games can be interpreted as a condition number for thecorresponding nonarchimedean feasibility problems. This number measures howclose a feasible instance is from being infeasible, and vice versa. We showthat it coincides with the maximal radius of a ball in Hilbert's projectivemetric, that is included in the feasible set. The geometric interpretation ofthe condition number relies in particular on a duality theorem for tropicalsemidefinite feasibility programs. Then, we bound the complexity of thefeasibility problem in terms of the condition number. We finally give explicitbounds for this condition number, in terms of the characteristics of thestochastic game. As a consequence, we show that the simplest algorithm todecide whether a stochastic mean payoff game is winning, namely valueiteration, has a pseudopolynomial complexity when the number of randompositions is fixed.