Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games
Mathematics of Operations Research · 10.11.2026
DOI: 10.1287/moor.2025.1244 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 10.11.2026. Verfasst von Stefan Kiefer und 3 weiteren Autor:innen. Die Arbeit nennt 45 Literaturangaben.
Abstract (Originalsprache)
We study two-player stochastic games on countable graphs. Players Max and Min seek, respectively, to maximize and minimize the probability of satisfying the game objective. The Büchi objective is to visit a given set of states infinitely often. The Transience objective is to visit no state infinitely often. In Büchi games, there exist [Formula: see text]-optimal Max strategies that use just a step counter plus 1 bit of public memory. This upper bound holds for all countable graphs, but is a new result even for finite graphs. It is tight, because Max strategies that use just a step counter, or just finite memory, are not sufficient, even on finite game graphs. This upper bound follows from a slightly stronger new result: [Formula: see text]-optimal Max strategies for the combined Büchi and Transience objective require exactly 1 bit of public memory. Moreover, [Formula: see text]-optimal Max strategies for the Transience objective alone can be chosen as memoryless. Funding: Financial support from Agence Nationale de la Recherche [Grant ANR-22-CE48-0005] and the Engineering and Physical Sciences Research Council [Grant EP/X042596/1] is gratefully acknowledged.
Zitieren
APA
Kiefer, S., Mayr, R., Shirmohammadi, M., & Totzke, P. (2026). Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games. Mathematics of Operations Research. https://doi.org/10.1287/moor.2025.1244
Vancouver
Kiefer S, Mayr R, Shirmohammadi M, Totzke P. Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games. Mathematics of Operations Research. 2026. doi:10.1287/moor.2025.1244
BibTeX
@article{Kiefer2026,
author = {Kiefer, Stefan and Mayr, Richard and Shirmohammadi, Mahsa and Totzke, Patrick},
title = {Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games},
journal = {Mathematics of Operations Research},
year = {2026},
doi = {10.1287/moor.2025.1244}
}
EUVIMED