Show simple item record

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.identifier.doi10.14760/OWP-2015-19
local.scientificprogramResearch in Pairs 2015
local.series.idOWP-2015-19


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record