Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions

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

doi:10.1007/s00453-017-0372-7

Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions

Endre Boros
, Khaled Elbassioni
, Mahmoud Fouz
, Vladimir Gurvich
, Kazuhisa Makino
, Bodo Manthey (Corresponding Author)

Discrete Mathematics and Mathematical Programming

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

1 Citation (Scopus)

238 Downloads (Pure)

Abstract

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

Original language	English
Pages (from-to)	3132-3157
Number of pages	26
Journal	Algorithmica
Volume	80
Issue number	11
DOIs	https://doi.org/10.1007/s00453-017-0372-7
Publication status	Published - 1 Nov 2018

Keywords

UT-Hybrid-D
Approximation schemes
Approximation algorithms
Nash equilibrium
Stochastic mean payoff games

Access to Document

10.1007/s00453-017-0372-7Licence: CC BY

Boros2018_Article_ApproximationSchemesForStochasFinal published version, 588 KBLicence: CC BY

Cite this

@article{437d93e129384039bb15270b5c154293,

title = "Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions",

abstract = "We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.",

keywords = "UT-Hybrid-D, Approximation schemes, Approximation algorithms, Nash equilibrium, Stochastic mean payoff games",

author = "Endre Boros and Khaled Elbassioni and Mahmoud Fouz and Vladimir Gurvich and Kazuhisa Makino and Bodo Manthey",

note = "Springer deal",

year = "2018",

month = nov,

day = "1",

doi = "10.1007/s00453-017-0372-7",

language = "English",

volume = "80",

pages = "3132--3157",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "11",

}

TY - JOUR

T1 - Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Fouz, Mahmoud

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

AU - Manthey, Bodo

N1 - Springer deal

PY - 2018/11/1

Y1 - 2018/11/1

N2 - We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

AB - We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

KW - UT-Hybrid-D

KW - Approximation schemes

KW - Approximation algorithms

KW - Nash equilibrium

KW - Stochastic mean payoff games

U2 - 10.1007/s00453-017-0372-7

DO - 10.1007/s00453-017-0372-7

M3 - Article

SN - 0178-4617

VL - 80

SP - 3132

EP - 3157

JO - Algorithmica

JF - Algorithmica

IS - 11

ER -

Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions

Abstract

Keywords

Access to Document

Fingerprint

Cite this