Strategy Complexity of Reachability in Countable Stochastic 2-Player Games

Stefan Kiefer (), Richard Mayr (), Mahsa Shirmohammadi () and Patrick Totzke ()
Additional contact information
Stefan Kiefer: University of Oxford
Richard Mayr: University of Edinburgh
Mahsa Shirmohammadi: Université Paris cité
Patrick Totzke: University of Liverpool

Dynamic Games and Applications, 2025, vol. 15, issue 3, No 10, 980-1036

Abstract: Abstract 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.

Keywords: Stochastic games; Discrete-time games; Strategy complexity; 91A15; 60J05; 91A60; 60G40; 60J05 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13235-024-00575-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:dyngam:v:15:y:2025:i:3:d:10.1007_s13235-024-00575-6

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/13235

DOI: 10.1007/s13235-024-00575-6

Access Statistics for this article

Dynamic Games and Applications is currently edited by Georges Zaccour

More articles in Dynamic Games and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().