Monomial strategies for concurrent reachability games and other stochastic games

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We consider two-player zero-sum finite (but infinite-horizon) stochastic games with limiting average payoffs. We define a family of stationary strategies for Player I parameterized by ε > 0 to be monomial, if for each state k and each action j of Player I in state k except possibly one action, we have that the probability of playing j in k is given by an expression of the form c ε d for some non-negative real number c and some non-negative integer d. We show that for all games, there is a monomial family of stationary strategies that are ε-optimal among stationary strategies. A corollary is that all concurrent reachability games have a monomial family of ε-optimal strategies. This generalizes a classical result of de Alfaro, Henzinger and Kupferman who showed that this is the case for concurrent reachability games where all states have value 0 or 1.
Original languageEnglish
Title of host publicationReachability Problems : 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings
EditorsParosh Aziz Abdulla, Igor Potapov
Number of pages13
PublisherSpringer VS
Publication year2013
ISBN (print)978-3-642-41035-2
ISBN (Electronic)978-3-642-41036-9
Publication statusPublished - 2013
EventInternational Workshop on Reachability Problems - Uppsala, Sweden
Duration: 24 Sep 201326 Sep 2013
Conference number: 7


ConferenceInternational Workshop on Reachability Problems
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 69092547