English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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.

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