Monomial strategies for concurrent reachability games and other stochastic games

Søren Kristoffer Stiil Frederiksen; Peter Bro Miltersen

doi:10.1007/978-3-642-41036-9_12

Monomial strategies for concurrent reachability games and other stochastic games

Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

2 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Reachability Problems : 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings
Editors	Parosh Aziz Abdulla, Igor Potapov
Number of pages	13
Publisher	Springer VS
Publication date	2013
Pages	122-134
ISBN (Print)	978-3-642-41035-2
ISBN (Electronic)	978-3-642-41036-9
DOIs	https://doi.org/10.1007/978-3-642-41036-9_12
Publication status	Published - 2013
Event	International Workshop on Reachability Problems - Uppsala, Sweden Duration: 24 Sept 2013 → 26 Sept 2013 Conference number: 7

Conference

Conference	International Workshop on Reachability Problems
Number	7
Country/Territory	Sweden
City	Uppsala
Period	24/09/2013 → 26/09/2013

Series	Lecture Notes in Computer Science
Volume	8169
ISSN	0302-9743

Access to Document

10.1007/978-3-642-41036-9_12

Cite this

Frederiksen, Søren Kristoffer Stiil ; Miltersen, Peter Bro. / Monomial strategies for concurrent reachability games and other stochastic games. Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. editor / Parosh Aziz Abdulla ; Igor Potapov. Springer VS, 2013. pp. 122-134 (Lecture Notes in Computer Science, Vol. 8169).

@inproceedings{ea1232622f624bfc9567d33c36225f32,

title = "Monomial strategies for concurrent reachability games and other stochastic games",

abstract = "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.",

author = "Frederiksen, {S{\o}ren Kristoffer Stiil} and Miltersen, {Peter Bro}",

year = "2013",

doi = "10.1007/978-3-642-41036-9_12",

language = "English",

isbn = "978-3-642-41035-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "122--134 ",

editor = "Abdulla, {Parosh Aziz } and Igor Potapov",

booktitle = "Reachability Problems",

note = "International Workshop on Reachability Problems ; Conference date: 24-09-2013 Through 26-09-2013",

}

Frederiksen, SKS & Miltersen, PB 2013, Monomial strategies for concurrent reachability games and other stochastic games. in PA Abdulla & I Potapov (eds), Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. Springer VS, Lecture Notes in Computer Science, vol. 8169, pp. 122-134 , International Workshop on Reachability Problems, Uppsala, Sweden, 24/09/2013. https://doi.org/10.1007/978-3-642-41036-9_12

Monomial strategies for concurrent reachability games and other stochastic games. / Frederiksen, Søren Kristoffer Stiil; Miltersen, Peter Bro.
Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. ed. / Parosh Aziz Abdulla; Igor Potapov. Springer VS, 2013. p. 122-134 (Lecture Notes in Computer Science, Vol. 8169).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Monomial strategies for concurrent reachability games and other stochastic games

AU - Frederiksen, Søren Kristoffer Stiil

AU - Miltersen, Peter Bro

N1 - Conference code: 7

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-41036-9_12

DO - 10.1007/978-3-642-41036-9_12

M3 - Article in proceedings

SN - 978-3-642-41035-2

T3 - Lecture Notes in Computer Science

SP - 122

EP - 134

BT - Reachability Problems

A2 - Abdulla, Parosh Aziz

A2 - Potapov, Igor

PB - Springer VS

T2 - International Workshop on Reachability Problems

Y2 - 24 September 2013 through 26 September 2013

ER -

Frederiksen SKS, Miltersen PB. Monomial strategies for concurrent reachability games and other stochastic games. In Abdulla PA, Potapov I, editors, Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. Springer VS. 2013. p. 122-134 . (Lecture Notes in Computer Science, Vol. 8169). doi: 10.1007/978-3-642-41036-9_12