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