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)

184 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 New York",

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