A convex programming-based algorithm for mean payoff stochastic games with perfect information

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 VB, white VW, and random VR forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when | VR| = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.

Original languageBritish English
Pages (from-to)1499-1512
Number of pages14
JournalOptimization Letters
Volume11
Issue number8
DOIs
StatePublished - 1 Dec 2017

Keywords

  • Convex programming
  • Mean payoff
  • Perfect information
  • Pseudo-polynomial algorithm
  • Stochastic games

Fingerprint

Dive into the research topics of 'A convex programming-based algorithm for mean payoff stochastic games with perfect information'. Together they form a unique fingerprint.

Cite this