Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
Dynamic Games and Applications · 2025-07 · 15 (3) · 980-1036
DOI: 10.1007/s13235-024-00575-6 ↗Kurz gefasst
Fachartikel in der Zeitschrift Dynamic Games and Applications, online erschienen am 14.09.2024. Verfasst von Stefan Kiefer und 3 weiteren Autor:innen. Beteiligte Einrichtung: University of Oxford, Oxford, UK. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Royal Society, Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
We study countably infinite stochastic 2-player games with reachability objectives. Our results provide a complete picture of the memory requirements of $$\varepsilon $$ ε -optimal (resp. optimal) strategies. These results depend on the size of the players’ action sets and on whether one requires strategies that are uniform (i.e., independent of the start state). Our main result is that $$\varepsilon $$ ε -optimal (resp. optimal) Maximizer strategies requires infinite memory if Minimizer is allowed infinite action sets. This lower bound holds even under very strong restrictions. Even in the special case of infinitely branching turn-based reachability games, even if all states allow an almost surely winning Maximizer strategy, strategies with a step counter plus finite private memory are still useless. Regarding uniformity , we show that for Maximizer there need not exist memoryless (i.e., positional) uniformly $$\varepsilon $$ ε -optimal strategies even in the special case of finite action sets or in finitely branching turn-based games. On the other hand, in games with finite action sets, there always exists a uniformly $$\varepsilon $$ ε -optimal Maximizer strategy that uses just one bit of public memory.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- University of Oxford, Oxford, UK.
- University of Edinburgh, Edinburgh, UK.
- IRIF & CNRS, Université Paris cité, Paris, France.
- University of Liverpool, Liverpool, UK.
Förderung
- Royal Society
- Engineering and Physical Sciences Research Council
Zitieren
APA
Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2025). Strategy Complexity of Reachability in Countable Stochastic 2-Player Games. Dynamic Games and Applications, 15(3), 980-1036. https://doi.org/10.1007/s13235-024-00575-6
Vancouver
Kiefer S, Mayr R, Shirmohammadi M, Totzke P. Strategy Complexity of Reachability in Countable Stochastic 2-Player Games. Dynamic Games and Applications. 2025;15(3):980-1036. doi:10.1007/s13235-024-00575-6
BibTeX
@article{Kiefer2025,
author = {Kiefer, Stefan and Mayr, Richard and Shirmohammadi, Mahsa and Totzke, Patrick},
title = {Strategy Complexity of Reachability in Countable Stochastic 2-Player Games},
journal = {Dynamic Games and Applications},
year = {2025},
volume = {15},
number = {3},
pages = {980--1036},
doi = {10.1007/s13235-024-00575-6}
}
EUVIMED