Approximation of values and equilibria in stochastic games: Complexity and algorithms

We study the computational aspects of the two central solution concepts of stochastic games played on finite graphs for an infinite number of steps: the value in two-player zero-sum games, and Nash equilibria in multi-player games. In both settings, exact solutions are in tractable. Fortwo-playerzero-sumconcurrentstochasticgames,valuescanbeirrational,and the associated decision problem is SQRT-SUM hard. For multi-player turn-based stochastic games,theequilibriumprobabilitiescanbeirrational,anddecidingtheconstrainedexistence of a Nash equilibrium is undecidable in the presence of memory, and ∃R-complete when the players are restricted to stationary strategies. Hence, in both settings, the natural computational problem is the approximation of the solution within an arbitrary additive error. In this thesis, we present improved complexity results and algorithms for such approximation problems. The first part of the thesis considers two-player zero-sum concurrent stochastic games with two classic objectives: (a) stateful-discounted objectives, which are similar to the classic discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order. The value-approximation problem is known to be in EXPSPACE for the limit value of stateful-discounted objectives and in PSPACEforparityobjectives,andthebest-knownalgorithmsforbothproblemsareatleast exponential time, with an exponential dependence on the number of states and actions. Our main results for the value-approximation problem for the limit value of stateful-discounted objectives and parity objectives areas follows: (a)we establish TFNPNP complexity; and (b)we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time. The second part of the thesis considers multi-player turn-based stochastic games with terminal payoffs, where the players are restricted to stationary strategies. We study the approximate constrained existence problem of Nash equilibria: given a game that has a Nash equilibrium in which the payoff of every player lies in a given interval, compute a strategy profile that is an ε-Nash equilibrium and that satisfies the same constraints up to an additive error ε. Our main results are as follows: (a) we present an FNPNP algorithm for the problem; and(b)we establish that its decision version is NP-hard, already with two players. For the upperbound,weshowthatifaconstrainedNashequilibriumexists,thenthereexists one in which the non-zero probabilities are at least an inverse of a double-exponential in the i input size, and that such a strategy profile can be represented, up to an additive error ε, with floating-point numbers of polynomial size. We complement the upper bound with a lower bound on this approach: we present a game with only five players in which every constrained Nash equilibrium requires double-exponentially small probabilities. The two parts share a common technical toolkit: bounds on solutions of systems of polynomial inequalities that arise from real algebraic geometry, the floating-point representation of doubly-exponentially small numbers, and guess-and-verify procedures that resolve single-player games with an NP oracle.