ATL ∗ AS: An Automata-Theoretic Approach and Tool for the Verification of Strategic Abilities in Multi-Agent Systems

Sofia Garcia de Blas Garcia-Alcalde, Francesco Belardinelli · 2025

Read ATL ∗ AS: An Automata-Theoretic Approach and Tool for the Verification of Strategic Abilities in Multi-Agent Systems by Sofia Garcia de Blas Garcia-Alcalde, Francesco Belardinelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17306.txt.

Introduction

Checking whether groups of agents can force a desired outcome is the problem Sofia Garcia de Blas Garcia-Alcalde and Francesco Belardinelli address. They work with ATL star, a logic for stating what coalitions of agents can achieve over time in a multi-agent system. Their paper gives two new symbolic methods for checking such statements automatically.

One method handles endless traces by reducing the check to a contest known as a parity game, and the other handles finite traces. Both are built into a tool called ATL star AS. On test problems and a security case, the symbolic methods beat step by step state checks, and the finite trace version ran much faster.

Catalog record

CREATORSofia Garcia de Blas Garcia-Alcalde, Francesco Belardinelli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-17306

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ATL ∗ AS: An Automata-Theoretic Approach and Tool for the Verification of Strategic Abilities in Multi-Agent Systems Sofia Garcia de Blas Garcia-Alcalde, Francesco Belardinelli Abstract We present two novel symbolic algorithms for model checking the Alternating-time Temporal Logic ATL ∗ , over both the infinite-trace and the finite-trace semantics. In particular, for infinite traces we design a novel symbolic reduction to parity games. We implement both methods in the ATL ∗ AS model checker and evaluate it using synthetic benchmarks as well as a cybersecurity scenario. Our results demonstrate that the symbolic approach significantly outperforms the explicit-state representation and we find that our parity-game-based algorithm offers a more scalable and efficient solution for infinite-trace verification, outperforming previously available tools. Our results also confirm that finite-trace model checking yields substantial performance benefits over infinite-trace verification. As such, we provide a comprehensive toolset for verifying multi-agent systems against specifications in ATL ∗ . 1 Introduction Formal verification of multi-agent systems (MAS) is essential for ensuring correctness in strategic, high-stakes settings [ 14 ] . Alternating-time Temporal Logic was originally proposed as a specification language to express strategic abilities of agents in MAS [ 1 ] . Since then, it has been extended in multiple directions to account for specific features of MAS, including imperfect information and knowledge [ 20 ] , stochastic transitions [ 10 ] , quantification on strategies [ 28 , 9 ] , among others. A key distinction in this domain is about modelling system executions as either infinite or finite traces. The tradition of reactive systems has usually considered infinite traces [ 30 ] , suitable to model the system’s readiness to accept inputs from the user. Nonetheless, many scenarios – including games and learning algorithms – naturally lend themselves to finite-trace modelling, where executions terminate after a finite number of steps. This has led to a vast literature translating results available for the infinite-trace setting to the finite-trace case [ 12 , 13 , 3 ] . Besides modelling purposes, finite traces also offer practical advantages regarding the corresponding verification procedures. Specifically, model checking over finite traces might avoid the complexities of \omega -automata and instead use finite automata, yielding simpler algorithms [ 3 ] . Contributions. We advance the state of the art in the formal verification of multi-agent systems by developing, implementing and evaluating effcient, symbolic model checking algorithms for both finite- and infinite-trace variants of ATL ∗ . The core contributions of this work are: 1. A symbolic algorithm for \text{ATL}_{f}^{*} model checking and its implementation , built on the theoretical foundations and complexity result presented in [ 3 ] . Our symbolic algorithm includes several design choices that improve substantially over [ 3 ] and enable scalable implementation. This is accompanied by the full implementation of both the explicit and symbolic model checking algorithms, thus achieving the first tool for verifying \text{ATL}_{f}^{*} . 2. A symbolic reduction of ATL ∗ model checking to parity games , resulting in the first available implementation for full ATL ∗ over infinite traces. 3. Evaluation on a strategic cybersecurity scenario: In Sec. 6.4 , a concrete attacker-defenders MAS is modelled to demonstrate the applicability of the symbolic \text{ATL}_{f}^{*} model checker to realistic verification tasks. 4. Comparative analysis of finite vs. infinite-trace verification: We investigate empirically the practical performance trade-offs between finite- and infinite-trace ATL ∗ model checking, as well as between different algorithms in both domains. The results of these evaluations are presented in Sec. 6 . These algorithms are integrated into ATL ∗ AS, a C++ model checking tool that supports both finite and infinite-trace verification of ATL ∗ . Users can provide a system specification and select among the provided algorithms to verify temporal and strategic properties efficiently. The code of ATL ∗ AS is provided in the supplementary material to this paper. Related Work. The computational complexity of model checking temporal logics varies significantly depending on the language considered and its expressive power. Table 1 summarises the complexity results for model checking some key multi-agent logics, under the assumption of perfect recall strategies. Existing work on ATL {}_{f}^{*} model checking is centered around the explicit-state algorithm introduced in [ 3 ] , which provides the first decidability and complexity results for model checking ATL {}^{*}_{f} . However, this approach suffers from limited scalability due to full state-space enumeration. ATL ∗ over infinite traces lacks dedicated tools, but can be indirectly verified via the SL[1G] fragment of strategy logic, supported by the symbolic MCMAS-SL[1G] checker [ 7 ] , which uses generalised parity games. Parity-game-based model checking has also been developed for logics such as the modal \mu -calculus [ 16 ] and game logic [ 24 ] . The reduction of ATL ∗ model checking to parity games was established in [ 11 ] , showing that control problems over Kripke structures with \omega -regular objectives can be encoded as parity games. However, no concrete algorithm for concurrent game structures was provided, nor were the symbolic aspects required for efficient practical implementation addressed. Table 1: Model Checking Complexity of Relevant Logics Logic Complexity Implementation ATL PTIME-complete [ 1 ] MCMAS [ 25 ] ATL ∗ 2EXPTIME-complete [ 1 ] ATL ∗ AS (here) \text{ATL}_{f}^{*} 2EXPTIME-complete [ 3 ] ATL ∗ AS (here) SL Non-elementary [ 27 ] MCMAS-SLK [ 6 ] SL[1G] 2EXPTIME-complete [ 27 ] MCMAS-SL[1G] [ 7 ] 2 Background In this section we introduce the background on Alternating-time Temporal Logic, including its syntax and semantics (Sec. 2.1 ) and the basics on automata theory to solve the corresponding model checking problem (Sec. 2.2 ). In what follows, give a (possibly infinite) sequence \tau=t_{0},\ldots,t_{n},\ldots of elements from set T , we denote its length as |\tau|\in\mathbb{N}\cup\{\infty\} , the i -th element as \tau_{i}=t_{i} , and the subsequence t_{i},\ldots,t_{n+i},\ldots starting at position i as \tau_{\geq i} . 2.1 Alternating-time Temporal Logic Syntax. We state the syntax for the language ATL ∗ as introduced in [ 1 ] , which is also the syntax for its variant ATL {}^{*}_{f} interpreted over finite traces. Let AP be the set of atomic propositions (or atoms) and Ag the set of agents . Formulas in ATL ∗ are the state formulas \varphi built using path formulas \psi with Boolean operators and strategic quantifiers: \displaystyle\varphi \displaystyle::= \displaystyle p\mid\neg\varphi\mid\varphi_{1}\land\varphi_{2}\mid\langle\!\langle A\rangle\!\rangle\psi \displaystyle\psi \displaystyle::= \displaystyle\varphi\mid\neg\psi\mid\psi\land\psi\mid\mathsf{X}\psi\mid\psi\mathsf{U}\psi where p\in AP and A\subseteq Ag . Operator next \mathsf{X} and until \mathsf{U} are the standard modalities of Linear-time Temporal Logic (LTL) [ 29 ] . Additional temporal operators are also derivable from \mathsf{X} and \mathsf{U} , including finally \mathsf{F}\varphi\equiv\texttt{true}\mathsf{U}\varphi and globally \mathsf{G}\varphi\equiv\neg\mathsf{F}\neg\varphi . For simplicity, we include these derived operators in the syntax. Semantics. We present the semantics of ATL ∗ by means of Concurrent Game Structures. Definition 2.1 (CGS) . A Concurrent Game Structure is a tuple G=\langle Ag,AP,S,s_{0},{Act}_{a\in Ag},\delta,\lambda\rangle where: • Ag is the finite, non-empty set of agents ; • AP is the finite, non-empty set of atoms ; • S is the finite, non-empty set of states , with initial state s_{0}\in S ; • for each agent a\in Ag , Act_{a} is a finite, non-empty set of actions ; • \delta:S\times Jact\rightarrow S is the transition function , where Jact=\prod_{a\

Read the complete text