Towards Partial Order Reductions for Strategic Ability
Wojciech Jamroga, Wojciech Penczek, Teofil Sidoruk, Piotr Dembiński, Antoni Mazurkiewicz · Journal of Artificial Intelligence Research · 2018
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, with as well as without the fairness assumption. We also demonstrate the effectiveness of the reduction on a number of benchmarks. Interestingly, the reduction does not work for strategic abilities under perfect information.