Can I read Natural Strategic Ability in Stochastic Multi-Agent Systems on EtoBox?

Natural Strategic Ability in Stochastic Multi-Agent Systems by Berthon, Raphaël; Katoen, Joost-Pieter; Mittelmann, Munyque; Murano, Aniello is a scholarly article available to read on EtoBox.

What is Natural Strategic Ability in Stochastic Multi-Agent Systems about?

Strategies synthesized using formal methods can be complex and often require infinite memory, which does not correspond to the expected behavior when trying to model Multi-Agent Systems (MAS). To capture such behaviors, natural strategies are a recently proposed framework striking a balance between the ability of agents to strategize with memory and the model-checking complexity, but until now has been restricted to fully deterministic settings. For the first time, we consider the probabilistic temporal logics PATL and PATL* under natural strategies (NatPATL and NatPATL*, resp.). As main result we show that, in stochastic MAS, NatPATL model-checking is NP-complete when the active coalition is restricted to deterministic strategies. We also give a 2NEXPTIME complexity result for NatPATL* with the same restriction. In the unrestricted case, we give an EXPSPACE complexity for NatPATL and 3EXPSPACE complexity for NatPATL*.

Author

Berthon, Raphaël; Katoen, Joost-Pieter; Mittelmann, Munyque; Murano, Aniello

Published

2024

Language

EN