Simple stochastic games are turn-based 2½-player zero-sum graph games with a
reachability objective. The problem is to compute the winning probabilities as well as the …

Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum
games played on directed graphs with probabilistic transitions. The goal of player-max is to …

We present a generic strategy iteration algorithm (GSIA) to find an optimal strategy of a
simple stochastic game (SSG). We prove the correctness of GSIA, and derive a general …

We consider concurrent games played on graphs. At every round of a game, each player
simultaneously and independently selects a move; the moves jointly determine the transition …

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 an …

We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state
graph. We focus on the important sub-class of ergodic games where all states are visited …

Semidefinite programming can be considered over any real closed field, including fields of
Puiseux series equipped with their nonarchimedean valuation. Nonarchimedean …

An irreducible stochastic matrix with rational entries has a stationary distribution given by a
vector of rational numbers. We give an upper bound on the lowest common denominator of …

We consider two player, zero-sum, finite-state concurrent reachability games, played for an
infinite number of rounds, where in every round, each player simultaneously and …

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized
algorithm which works in expected $2^{O (\sqrt {n})} $ time. We first give a simpler iterative …