Zur Kurzanzeige

dc.contributor.authorBoros, Endre
dc.contributor.authorElbassioni, Khaled
dc.contributor.authorGurvich, Vladimir
dc.contributor.authorMakino, Kazuhisa
dc.date.accessioned2016-02-06T12:00:02Z
dc.date.accessioned2016-10-05T14:14:04Z
dc.date.available2016-02-06T12:00:02Z
dc.date.available2016-10-05T14:14:04Z
dc.date.issued2015
dc.identifier.urihttp://publications.mfo.de/handle/mfo/1107
dc.descriptionResearch in Pairs 2015en_US
dc.description.abstractWe 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 \to \mathbb{Z}$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$ . It is a longstanding open question whether a polynomial time algorithm for BWR-games exists, or not, even when $|V_R| = 0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with $|V_R| = O(1)$, a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in $|V_W| + |V_B|$, the maximum absolute local reward, and the common denominator of the transition probabilities.en_US
dc.language.isoenen_US
dc.publisherMathematisches Forschungsinstitut Oberwolfachen_US
dc.relation.ispartofseriesOberwolfach Preprints;2015,20
dc.titleA Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positionsen_US
dc.typePreprinten_US
dc.rights.licenseDieses 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.de
dc.rights.licenseThis 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.en
dc.identifier.doi10.14760/OWP-2015-20
local.scientificprogramResearch in Pairs 2015
local.series.idOWP-2015-20
dc.identifier.urnurn:nbn:de:101:1-201602053963
dc.identifier.ppn1653735945


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige