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 $\varepsilon$-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: $\varepsilon$-optimal Max strategies for the combined Büchi and Transience objective require exactly 1 bit of public memory. Moreover, $\varepsilon$-optimal Max strategies for the Transience objective alone can be chosen as memoryless.
From: Richard Mayr [view email]
[v1]
Tue, 23 Apr 2024 19:49:50 UTC (101 KB)
[v2]
Thu, 5 Jun 2025 12:52:48 UTC (108 KB)
[v3]
Wed, 18 Jun 2025 18:33:48 UTC (108 KB)
[v4]
Sun, 13 Sep 2026 16:45:32 UTC (148 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。