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

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 |