Randomise Alone, Reach as a Team

We study concurrent stochastic games in which a team of agents plays against an adversarial environment. If the agents could access a shared source of randomness, then these games reduce to two-player games. Despite being common in the literature on coalition games, this assumption does not accurately model real-world systems. In this paper, we consider the setting where the agents only have access to individual sources of randomness, and must satisfy a given reachability or safety objective. The limit-sure problem asks whether the team can ensure that the objective is satisfied with probability at least $1-λ$ for every $λ>0$. For reachability objectives, we show that this problem is $\mathsf{NP}$-complete. For safety objectives, we show that limit-sure winning coincides with almost-sure winning, which is known to lie in $\mathsf{P}$. As a corollary of these results, we conclude that model checking of the qualitative fragment of the logic Individually Randomised ATL -- introduced in the recent work of Brice et al. -- is $\mathsf{P}^{\mathsf{NP}}$-complete.

Reachability games are two-player games played on a graph, where the objective of $\texttt{REACH}$ player is to reach the target set whereas the objective of $\texttt{SAFE}$ player is to stay away from the target set. Reachability games have important applications in artificial intelligence and reactive synthesis, and many of these applications give rise to infinite-state reachability games. In this paper, we study turn-based reachability games on infinite-state graphs defined over valuations of a finite set of real variables. We consider the problem of determining the existence of and computing a winning strategy for $\texttt{REACH}$ player. Our contributions are twofold. First, we propose ranking certificates for reachability games, a sound and complete proof rule for proving that $\texttt{REACH}$ player has a winning strategy from the specified initial state. Second, we consider polynomial reachability games, where transitions and objectives are described by polynomial constraints over real variables, and propose a fully automated algorithm for computing a winning strategy for $\texttt{REACH}$ player together with a formal correctness witness in the form of a ranking certificate. The algorithm is sound, semi-complete, and runs in sub-exponential time. Our experiments demonstrate the ability of our method to solve challenging examples from the literature that were out of the reach of existing methods. Specifically, for the classical Cinderella-Stepmother game, we are able to compute an optimal winning strategy for an arbitrary precision parameter for the first time.

Alternating-time temporal logic and its extensions provide several ways of combining strategic and quantitative reasoning. We study a particular combination: whether a coalition has a single strategy that enforces a temporal objective while guaranteeing given long-run mean-payoff thresholds. We introduce ATL_mp, an extension of ATL over weighted concurrent game structures in which each strategic modality carries a conjunctive mean-payoff constraint. The temporal and quantitative requirements must hold against every behaviour of the remaining agents, and the existence of such a strategy cannot in general be reduced to the two requirements considered separately. For one-dimensional constraints, model checking is 2EXPTIME-complete under both perfect-recall and finite-memory semantics, matching ATL*. For the pure quantitative fragment and fragments restricted to ATL or GR(1) temporal objectives, model checking has lower complexity. With multi-dimensional conjunctive constraints, model checking under finite-memory semantics remains 2EXPTIME-complete. We show that memoryless, finite-memory, and perfect-recall abilities form a strict hierarchy, while finite-memory strategies still achieve every threshold strictly below the perfect-recall supremum. We give tight linear upper and lower bounds on the required memory as a function of the denominator of the threshold, even when the game and temporal monitor are fixed. We give several examples of properties expressible in the logic, including temporal synthesis with performance guarantees and aggregate and multi-criteria objectives. We also relate the logic to cooperative rational verification, showing that it can express beneficial deviations from fixed payoff baselines, but not directly reproduce the standard ATL* encoding of the core for dichotomous preferences.