Zur Kurzanzeige

dc.contributor.authorBoros, Endre
dc.contributor.authorElbassioni, Khaled
dc.contributor.authorGurvich, Vladimir
dc.contributor.authorMakino, Kazuhisa
dc.date.accessioned2016-02-06T12:00:01Z
dc.date.accessioned2016-10-05T14:14:03Z
dc.date.available2016-02-06T12:00:01Z
dc.date.available2016-10-05T14:14:03Z
dc.date.issued2015
dc.identifier.urihttp://publications.mfo.de/handle/mfo/1106
dc.descriptionResearch in Pairs 2015en_US
dc.description.abstractWe suggest a new algorithm for two-person zero-sum undiscounted stochastic games focusing on stationary strategies. Given a positive real $\epsilon$, let us call a stochastic game $\epsilon$-ergodic, if its values from any two initial positions differ by at most $\epsilon$. The proposed new algorithm outputs for every $\epsilon > 0$ in finite time either a pair of stationary strategies for the two players guaranteeing that the values from any initial positions are within an $\epsilon$-range, or identifies two initial positions $u$ and $v$ and corresponding stationary strategies for the players proving that the game values starting from $u$ and $v$ are at least $\epsilon/24$ apart.In particular, the above result shows that if a stochastic game is $0$-ergodic, then there are stationary strategies for the players proving $24\epsilon$-ergodicity. This result strengthens and provides a constructive version of an existential result by Vrieze (1980)claiming that if a stochastic game is $0$-ergodic, then there are $\epsilon$-optimal stationary strategies for every $\epsilon>0$. The suggested algorithm is based on a potential transformation technique that changes the range of local values at all positions without changing the normal form of the game.en_US
dc.language.isoenen_US
dc.publisherMathematisches Forschungsinstitut Oberwolfachen_US
dc.relation.ispartofseriesOberwolfach Preprints;2015,19
dc.subjectundiscounted stochastic gamesen_US
dc.subjectlimiting average payoffen_US
dc.subjectmean payoffen_US
dc.subjectlocal rewarden_US
dc.subjectpotential transformationen_US
dc.subjectcomputational game theoryen_US
dc.titleA potential reduction algorithm for two-person zero-sum mean payoff stochastic gamesen_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-19
local.scientificprogramResearch in Pairs 2015
local.series.idOWP-2015-19
dc.identifier.urnurn:nbn:de:101:1-201602053959
dc.identifier.ppn1653735287


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige