Randomise Alone, Reach as a Team
This work addresses the problem of cooperative multi-player games with distributed randomness, which is a fundamental challenge in game theory and multi-agent systems, particularly for scenarios where agents cannot share random sources.
This paper investigates concurrent graph games where multiple players cooperate against an opponent to reach target states, specifically under distributed randomisation where players have independent, private random sources. They demonstrate that memoryless strategies suffice for the threshold problem, placing it in the Existential Theory of the Reals and enabling value iteration algorithms, and prove the problem is NP-hard. For almost-sure reachability, they prove NP-completeness.
We study concurrent graph games where n players cooperate against an opponent to reach a set of target states. Unlike traditional settings, we study distributed randomisation: team players do not share a source of randomness, and their private random sources are hidden from the opponent and from each other. We show that memoryless strategies are sufficient for the threshold problem (deciding whether there is a strategy for the team that ensures winning with probability that exceeds a threshold), a result that not only places the problem in the Existential Theory of the Reals (\exists\mathbb{R}) but also enables the construction of value iteration algorithms. We additionally show that the threshold problem is NP-hard. For the almost-sure reachability problem, we prove NP-completeness. We introduce Individually Randomised Alternating-time Temporal Logic (IRATL). This logic extends the standard ATL framework to reason about probability thresholds, with semantics explicitly designed for coalitions that lack a shared source of randomness. On the practical side, we implement and evaluate a solver for the threshold and almost-sure problem based on the algorithms that we develop.