A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticle

Abstract

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V,E), with local rewards r:E→Z, and three types of positions: black V B , white V W , and random V R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when |V R |=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, 1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |V R |=O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |V W |+|V B |, the maximum absolute local reward, and the common denominator of the transition probabilities.

Original languageEnglish (US)
Pages (from-to)74-95
Number of pages22
JournalInformation and Computation
Volume267
DOIs
StatePublished - Aug 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Equilibrium computation
  • Perfect information
  • Pseudo-polynomial algorithm
  • Stochastic games
  • Zero-sum games

Fingerprint Dive into the research topics of 'A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions'. Together they form a unique fingerprint.

  • Cite this