Memoryless strategies in stochastic reachability games

Stefan Kiefer; Richard Mayr; Mahsa Shirmohammadi; Patrick Totzke

doi:10.1007/978-3-031-56222-8_13

Memoryless strategies in stochastic reachability games

Stefan Kiefer^*, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

Abstract / Description of output

We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of target states. We prove that Max has a memoryless strategy that is optimal from all states that have an optimal strategy. Our construction provides an alternative proof of this result by Bordais, Bouyer and Le Roux [4], and strengthens it, as we allow Max’s action sets to be countably infinite.

Original language	English
Title of host publication	Taming the Infinities of Concurrency
Subtitle of host publication	Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday
Editors	Stefan Kiefer, Jan Křetínský, Antonín Kučera
Publisher	Springer
Pages	225–242
Number of pages	18
Volume	14660
ISBN (Electronic)	9783031562228
ISBN (Print)	9783031562211
DOIs	https://doi.org/10.1007/978-3-031-56222-8_13
Publication status	Published - 20 Mar 2024
Event	Taming the Infinities of Concurrency: Workshop and festschrift in honour of Javier Esparza at the occasion of his 60th birthday - Luxembourg, Luxembourg, Luxembourg Duration: 7 Apr 2024 → 7 Apr 2024 https://www7.in.tum.de/~kretinsk/Javier60.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham

Workshop

Workshop	Taming the Infinities of Concurrency
Country/Territory	Luxembourg
City	Luxembourg
Period	7/04/24 → 7/04/24
Internet address	https://www7.in.tum.de/~kretinsk/Javier60.html

Keywords / Materials (for Non-textual outputs)

stochastic games
reachability
strategy complexity

Access to Document

10.1007/978-3-031-56222-8_13

KieferEtalSpringer2024MemorylessStrategiesInStochasticReachabilityGamesAccepted author manuscript, 646 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2024). Memoryless strategies in stochastic reachability games. In S. Kiefer, J. Křetínský, & A. Kučera (Eds.), Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday (Vol. 14660, pp. 225–242). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-031-56222-8_13

Kiefer, Stefan ; Mayr, Richard ; Shirmohammadi, Mahsa et al. / Memoryless strategies in stochastic reachability games. Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday. editor / Stefan Kiefer ; Jan Křetínský ; Antonín Kučera. Vol. 14660 Springer, 2024. pp. 225–242 (Lecture Notes in Computer Science).

@inbook{d08a06b8209c4c94b8758c8c05d7bf82,

title = "Memoryless strategies in stochastic reachability games",

abstract = "We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of target states. We prove that Max has a memoryless strategy that is optimal from all states that have an optimal strategy. Our construction provides an alternative proof of this result by Bordais, Bouyer and Le Roux [4], and strengthens it, as we allow Max{\textquoteright}s action sets to be countably infinite.",

keywords = "stochastic games, reachability, strategy complexity",

author = "Stefan Kiefer and Richard Mayr and Mahsa Shirmohammadi and Patrick Totzke",

year = "2024",

month = mar,

day = "20",

doi = "10.1007/978-3-031-56222-8_13",

language = "English",

isbn = "9783031562211",

volume = "14660",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "225–242",

editor = "Stefan Kiefer and Jan K{\v r}et{\'i}nsk{\'y} and Anton{\'i}n Ku{\v c}era",

booktitle = "Taming the Infinities of Concurrency",

address = "United Kingdom",

note = "Taming the Infinities of Concurrency : Workshop and festschrift in honour of Javier Esparza at the occasion of his 60th birthday ; Conference date: 07-04-2024 Through 07-04-2024",

url = "https://www7.in.tum.de/~kretinsk/Javier60.html",

}

Kiefer, S, Mayr, R, Shirmohammadi, M & Totzke, P 2024, Memoryless strategies in stochastic reachability games. in S Kiefer, J Křetínský & A Kučera (eds), Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday. vol. 14660, Lecture Notes in Computer Science, Springer, pp. 225–242, Taming the Infinities of Concurrency, Luxembourg, Luxembourg, 7/04/24. https://doi.org/10.1007/978-3-031-56222-8_13

Memoryless strategies in stochastic reachability games. / Kiefer, Stefan; Mayr, Richard; Shirmohammadi, Mahsa et al.
Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday. ed. / Stefan Kiefer; Jan Křetínský; Antonín Kučera. Vol. 14660 Springer, 2024. p. 225–242 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

TY - CHAP

T1 - Memoryless strategies in stochastic reachability games

AU - Kiefer, Stefan

AU - Mayr, Richard

AU - Shirmohammadi, Mahsa

AU - Totzke, Patrick

PY - 2024/3/20

Y1 - 2024/3/20

N2 - We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of target states. We prove that Max has a memoryless strategy that is optimal from all states that have an optimal strategy. Our construction provides an alternative proof of this result by Bordais, Bouyer and Le Roux [4], and strengthens it, as we allow Max’s action sets to be countably infinite.

AB - We study concurrent stochastic reachability games played on finite graphs. Two players, Max and Min, seek respectively to maximize and minimize the probability of reaching a set of target states. We prove that Max has a memoryless strategy that is optimal from all states that have an optimal strategy. Our construction provides an alternative proof of this result by Bordais, Bouyer and Le Roux [4], and strengthens it, as we allow Max’s action sets to be countably infinite.

KW - stochastic games

KW - reachability

KW - strategy complexity

U2 - 10.1007/978-3-031-56222-8_13

DO - 10.1007/978-3-031-56222-8_13

M3 - Chapter (peer-reviewed)

SN - 9783031562211

VL - 14660

T3 - Lecture Notes in Computer Science

SP - 225

EP - 242

BT - Taming the Infinities of Concurrency

A2 - Kiefer, Stefan

A2 - Křetínský, Jan

A2 - Kučera, Antonín

PB - Springer

T2 - Taming the Infinities of Concurrency

Y2 - 7 April 2024 through 7 April 2024

ER -

Kiefer S, Mayr R, Shirmohammadi M, Totzke P. Memoryless strategies in stochastic reachability games. In Kiefer S, Křetínský J, Kučera A, editors, Taming the Infinities of Concurrency: Essays Dedicated to Javier Esparza on the Occasion of His 60th Birthday. Vol. 14660. Springer. 2024. p. 225–242. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-56222-8_13

Memoryless strategies in stochastic reachability games

Abstract / Description of output

Publication series

Workshop

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this