EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Strategy Complexity of Reachability in Countable Stochastic 2-Player Games

Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Discrete-time gamesStochastic gamesStrategy complexity

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}
}
Kostenlos starten →