Natural Strategic Ability in Stochastic Multi-Agent Systems


  • Raphaël Berthon RWTH Aachen University
  • Joost-Pieter Katoen RWTH Aachen University
  • Munyque Mittelmann University of Naples Federico II
  • Aniello Murano University of Naples Federico II



MAS: Multiagent Systems under Uncertainty, KRR: Computational Complexity of Reasoning, MAS: Other Foundations of Multi Agent Systems


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 complexity of the model-checking problem, 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∗). 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*.




How to Cite

Berthon, R., Katoen, J.-P., Mittelmann, M., & Murano, A. (2024). Natural Strategic Ability in Stochastic Multi-Agent Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 38(16), 17308-17316.



AAAI Technical Track on Multiagent Systems