Stochastic mean payoff games: smoothed analysis and approximation schemes

Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)

Abstract

In this paper, we consider two-player zero-sum stochastic mean payoff games with perfect information modeled by a digraph with black, white, and random vertices. These BWR-games games are polynomially equivalent with the classical Gillette games, which include many well-known subclasses, such as cyclic games, simple stochastic games, stochastic parity games, and Markov decision processes. They can also be used to model parlor games such as Chess or Backgammon. It is a long-standing open question if a polynomial algorithm exists that solves BWR-games. In fact, a pseudo-polynomial algorithm for these games with an arbitrary number of random nodes would already imply their polynomial solvability. Currently, only two classes are known to have such a pseudo-polynomial algorithm: BW-games (the case with no random nodes) and ergodic BWR-games (in which the game’s value does not depend on the initial position) with constant number of random nodes. In this paper, we show that the existence of a pseudo-polynomial algorithm for BWR-games with constant number of random vertices implies smoothed polynomial complexity and the existence of absolute and relative polynomial-time approximation schemes. In particular, we obtain smoothed polynomial complexity and derive absolute and relative approximation schemes for BW-games and ergodic BWR-games (assuming a technical requirement about the probabilities at the random nodes).
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication38th International Colloquium on Automata, Languages and Programming, ICALP 2011
EditorsLuca Aceto, Monika Henzinger, Jiří Sgall
Place of PublicationBerlin
PublisherSpringer
Pages147-158
Number of pages12
ISBN (Electronic)978-3-642-22006-7
ISBN (Print)978-3-642-22005-0
DOIs
Publication statusPublished - 2011
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: 4 Jul 20118 Jul 2011
Conference number: 38

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6755
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th International Colloquium on Automata, Languages and Programming, ICALP 2011
Abbreviated titleICALP
CountrySwitzerland
CityZurich
Period4/07/118/07/11

Keywords

  • METIS-278810
  • EWI-20543
  • IR-78128

Fingerprint Dive into the research topics of 'Stochastic mean payoff games: smoothed analysis and approximation schemes'. Together they form a unique fingerprint.

  • Cite this

    Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., & Manthey, B. (2011). Stochastic mean payoff games: smoothed analysis and approximation schemes. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, Languages and Programming: 38th International Colloquium on Automata, Languages and Programming, ICALP 2011 (pp. 147-158). (Lecture Notes in Computer Science; Vol. 6755). Berlin: Springer. https://doi.org/10.1007/978-3-642-22006-7_13