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

Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

doi:10.1007/s11590-017-1140-y

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

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

4 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 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, even when | V_R| = 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 language	British English
Pages (from-to)	1499-1512
Number of pages	14
Journal	Optimization Letters
Volume	11
Issue number	8
DOIs	https://doi.org/10.1007/s11590-017-1140-y
State	Published - 1 Dec 2017

Keywords

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

Access to Document

10.1007/s11590-017-1140-y

Cite this

@article{d49c2c8de049439f9fea14e5c3296e46,

title = "A convex programming-based algorithm for mean payoff stochastic games with perfect information",

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.",

keywords = "Convex programming, Mean payoff, Perfect information, Pseudo-polynomial algorithm, Stochastic games",

author = "Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino",

note = "Publisher Copyright: {\textcopyright} 2017, Springer-Verlag Berlin Heidelberg.",

year = "2017",

month = dec,

day = "1",

doi = "10.1007/s11590-017-1140-y",

language = "British English",

volume = "11",

pages = "1499--1512",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "8",

}

TY - JOUR

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

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - Convex programming

KW - Mean payoff

KW - Perfect information

KW - Pseudo-polynomial algorithm

KW - Stochastic games

UR - http://www.scopus.com/inward/record.url?scp=85017186754&partnerID=8YFLogxK

U2 - 10.1007/s11590-017-1140-y

DO - 10.1007/s11590-017-1140-y

M3 - Article

AN - SCOPUS:85017186754

SN - 1862-4472

VL - 11

SP - 1499

EP - 1512

JO - Optimization Letters

JF - Optimization Letters

IS - 8

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this