# Natural Strategic Ability in Stochastic Multi-Agent Systems

arXiv: https://arxiv.org/abs/2401.12170 · HTML: https://mlsanity.com/paper/2401.12170/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 45 references that are in the map.
- First posted on arXiv 22 Jan 2024.

## Builds on (most cited first, 7 of 7)

- [Counterexample Explanation by Learning Small Strategies in Markov Decision Processes](https://mlsanity.com/paper/1502.02834/) (2015)
- [A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs](https://mlsanity.com/paper/1511.08456/) (2015)
- [Natural Strategic Abilities in Voting Protocols](https://mlsanity.com/paper/2007.12424/) (2020)
- [Alternating-time temporal logic with finite-memory strategies](https://mlsanity.com/paper/1307.4476/) (2013)
- [Reasoning about Human-Friendly Strategies in Repeated Keyword Auctions](https://mlsanity.com/paper/2201.09616/) (2022)
- [Strategic Abilities of Forgetful Agents in Stochastic Environments](https://mlsanity.com/paper/2310.17240/) (2023)
- [Alternating Tree Automata with Qualitative Semantics](https://mlsanity.com/paper/2002.03664/) (2020)

## Built on by (most cited first, 1 of 1)

- [A Neuro-Symbolic Approach to Strategy Synthesis for Strategic Logics](https://mlsanity.com/paper/2606.17962/) (2026)

## Abstract (arXiv)

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*.