The complexity of ergodic mean payoff games
LNCS
Chatterjee, Krishnendu
Ibsen-Jensen, Rasmus
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.
Springer
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/2162
Chatterjee K, Ibsen-Jensen R. The complexity of ergodic mean payoff games. In: Vol 8573. Springer; 2014:122-133. doi:<a href="https://doi.org/10.1007/978-3-662-43951-7_11">10.1007/978-3-662-43951-7_11</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-662-43951-7_11
info:eu-repo/semantics/altIdentifier/arxiv/1404.5734
info:eu-repo/grantAgreement/FWF/P 23499-N23
info:eu-repo/grantAgreement/FWF/S11407
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/semantics/openAccess