Towards Partial Order Reductions for Strategic Ability

We propose a general semantics for strategic abilities of agents in asynchronous systems, with and without perfect information. Based on the semantics, we show some general complexity results for verification of strategic abilities in asynchronous interaction. More importantly, we develop a methodology for partial order reduction in verification of agents with imperfect information. We show that the reduction preserves an important subset of strategic properties, both with and without the fairness assumption. Interestingly, the reduction does not work for strategic abilities under perfect information.