10.1007/978-3-662-43951-7_11
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Ibsen-Jensen, Rasmus
Rasmus
Ibsen-Jensen
The complexity of ergodic mean payoff games
LNCS
Springer
2014
2018-12-11T11:56:04Z
2020-01-21T13:19:17Z
conference
https://research-explorer.app.ist.ac.at/record/2162
https://research-explorer.app.ist.ac.at/record/2162.json
1404.5734
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 infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games.