Stochastic mean payoff games: Smoothed analysis and approximation schemes
dc.bibliographicCitation.seriesTitle | Oberwolfach Preprints (OWP) | eng |
dc.bibliographicCitation.volume | 2010-22 | |
dc.contributor.author | Boros, Endre | |
dc.contributor.author | Elbassioni, Khaled | |
dc.contributor.author | Fouz, Mahmoud | |
dc.contributor.author | Gurvich, Vladimir | |
dc.contributor.author | Makino, Kazuhisa | |
dc.contributor.author | Manthey, Bodo | |
dc.date.available | 2019-06-28T08:02:04Z | |
dc.date.issued | 2010 | |
dc.description.abstract | We consider two-person zero-sum stochastic mean payoff games with perfect information modeled by a digraph with black, white, and random vertices. These BWR-games games are polynomially equivalent with the classical Gillette games, which include many well-known subclasses, such as cyclic games, simple stochastic games, stochastic parity games, and Markov decision processes. They can also be used to model parlor games such as Chess or Backgammon. It is a long-standing open question whether a polynomial algorithm exists that solves BWR-games. In fact, a pseudo-polynomial algorithm for these games with an arbitrary number of random nodes would already imply their polynomial solvability. Currently, only two classes are known to have such a pseudo-polynomial algorithm: BW-games (the case with no random nodes) and ergodic BWR-games (i.e., in which the game's value does not depend on the initial position) with constant number of random nodes. In this paper, we show that the existence of a pseudo-polynomial algorithm for BWR-games with constant number of random vertices implies smoothed polynomial time complexity and the existence of absolute and relative polynomial-time approximation schemes. In particular, we obtain smoothed polynomial time complexity and derive absolute and relative approximation schemes for the above two classes. | eng |
dc.description.version | publishedVersion | eng |
dc.format | application/pdf | |
dc.identifier.issn | 1864-7596 | |
dc.identifier.uri | https://doi.org/10.34657/3272 | |
dc.identifier.uri | https://oa.tib.eu/renate/handle/123456789/1702 | |
dc.language.iso | eng | eng |
dc.publisher | Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach | eng |
dc.relation.doi | https://doi.org/10.14760/OWP-2010-22 | |
dc.rights.license | This document may be downloaded, read, stored and printed for your own use within the limits of § 53 UrhG but it may not be distributed via the internet or passed on to external parties. | eng |
dc.rights.license | Dieses Dokument darf im Rahmen von § 53 UrhG zum eigenen Gebrauch kostenfrei heruntergeladen, gelesen, gespeichert und ausgedruckt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. | ger |
dc.subject.ddc | 510 | eng |
dc.title | Stochastic mean payoff games: Smoothed analysis and approximation schemes | eng |
dc.type | Report | eng |
dc.type | Text | eng |
tib.accessRights | openAccess | eng |
wgl.contributor | MFO | eng |
wgl.subject | Mathematik | eng |
wgl.type | Report / Forschungsbericht / Arbeitspapier | eng |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- OWP2010_22.pdf
- Size:
- 474.65 KB
- Format:
- Adobe Portable Document Format
- Description: