On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing
This addresses a problem for researchers and practitioners in formal verification of multi-agent systems by enabling richer specification of AI-related properties, though it is incremental as it extends an existing logic.
The paper tackles the limitation of Alternating-time temporal logic (ATL*) in comparing multiple strategic interactions and enforcing strategy sharing among agents, by proposing HyperATL*_S, an extension that enables such comparisons and sharing, and shows its model checking is decidable with an implemented tool.
Alternating-time temporal logic (ATL$^*$) is a well-established framework for formal reasoning about multi-agent systems. However, while ATL$^*$ can reason about the strategic ability of agents (e.g., some coalition $A$ can ensure that a goal is reached eventually), we cannot compare multiple strategic interactions, nor can we require multiple agents to follow the same strategy. For example, we cannot state that coalition $A$ can reach a goal sooner (or more often) than some other coalition $A'$. In this paper, we propose HyperATLS$^*_S$, an extension of ATL$^*$ in which we can (1) compare the outcome of multiple strategic interactions w.r.t. a hyperproperty, i.e., a property that refers to multiple paths at the same time, and (2) enforce that some agents share the same strategy. We show that HyperATL$^*_S$ is a rich specification language that captures important AI-related properties that were out of reach of existing logics. We prove that model checking of HyperATL$^*_S$ on concurrent game structures is decidable. We implement our model-checking algorithm in a tool we call HyMASMC and evaluate it on a range of benchmarks.