The Complexity of Ergodic Games

Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus (2013) The Complexity of Ergodic Games. Technical Report. IST Austria.

[img] Text
ergodic.pdf - Published Version
Available under License All rights reserved.
[IST-2013-127-v1+1]
Download (374Kb)

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.

Item Type: Monograph (Technical Report)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Chatterjee Group
Depositing User: Prof Krishnendu Chatterjee
Date Deposited: 08 Jul 2013 08:29
Last Modified: 16 Jul 2019 00:27
URI: https://repository.ist.ac.at/id/eprint/127

Actions (login required)

View Item View Item