---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1007/978-3-662-43951-7_11
bibo_issue: Part 2
bibo_volume: 8573
dct_date: 2014^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: The complexity of ergodic mean payoff games@
...