Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games

Abstract

We study 2-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 $\epsilon$-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, since 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: $\epsilon$-optimal Max strategies for the combined Büchi and Transience objective require exactly 1 bit of public memory. Moreover, $\epsilon$-optimal Max strategies for the Transience objective alone can be chosen as memoryless.

Full version of a paper presented at EC '25