Earlier Version

The complexity of ergodic games

K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.

Download
OA 517.27 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
Abstract
We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a 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 lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games.
Publishing Year
Date Published
2013-07-03
Page
29
ISSN
IST-REx-ID

Cite this

Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-127-v1-1
Chatterjee, K., & Ibsen-Jensen, R. (2013). The complexity of ergodic games. IST Austria. https://doi.org/10.15479/AT:IST-2013-127-v1-1
Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-127-v1-1.
K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games. IST Austria, 2013.
Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.
Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-127-v1-1.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T11:53:35Z


Material in IST:
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar