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

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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.

Originalsprog	Engelsk
Titel	Reachability Problems : 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings
Redaktører	Parosh Aziz Abdulla, Igor Potapov
Antal sider	13
Forlag	Springer VS
Publikationsdato	2013
Sider	122-134
ISBN (Trykt)	978-3-642-41035-2
ISBN (Elektronisk)	978-3-642-41036-9
DOI	https://doi.org/10.1007/978-3-642-41036-9_12
Status	Udgivet - 2013
Begivenhed	International Workshop on Reachability Problems - Uppsala, Sverige Varighed: 24 sep. 2013 → 26 sep. 2013 Konferencens nummer: 7

Konference

Konference	International Workshop on Reachability Problems
Nummer	7
Land/Område	Sverige
By	Uppsala
Periode	24/09/2013 → 26/09/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8169
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

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. red. / Parosh Aziz Abdulla ; Igor Potapov. Springer VS, 2013. s. 122-134 (Lecture Notes in Computer Science, Bind 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. i PA Abdulla & I Potapov (red), Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. Springer VS, Lecture Notes in Computer Science, bind 8169, s. 122-134 , International Workshop on Reachability Problems, Uppsala, Sverige, 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. red. / Parosh Aziz Abdulla; Igor Potapov. Springer VS, 2013. s. 122-134 (Lecture Notes in Computer Science, Bind 8169).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › 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. I Abdulla PA, Potapov I, red., Reachability Problems: 7th International Workshop, RP 2013, Uppsala, Sweden, September 24-26, 2013 Proceedings. Springer VS. 2013. s. 122-134 . (Lecture Notes in Computer Science, Bind 8169). doi: 10.1007/978-3-642-41036-9_12