Towards Partial Order Reductions for Strategic Ability

Wojciech Jamroga, Wojciech Penczek, Teofil Sidoruk, Piotr Dembinski, Antoni W. Mazurkiewicz

JAIR 2020 pp. 817-850

doi:10.1613/JAIR.1.11936 /jair/2020/jamroga2020jair-partial/

Abstract

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.

PDF JAIR Semantic Scholar

Cite

Text

Jamroga et al. "Towards Partial Order Reductions for Strategic Ability." Journal of Artificial Intelligence Research, 2020. doi:10.1613/JAIR.1.11936

Markdown

[Jamroga et al. "Towards Partial Order Reductions for Strategic Ability." Journal of Artificial Intelligence Research, 2020.](https://mlanthology.org/jair/2020/jamroga2020jair-partial/) doi:10.1613/JAIR.1.11936

BibTeX

@article{jamroga2020jair-partial,
  title     = {{Towards Partial Order Reductions for Strategic Ability}},
  author    = {Jamroga, Wojciech and Penczek, Wojciech and Sidoruk, Teofil and Dembinski, Piotr and Mazurkiewicz, Antoni W.},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2020},
  pages     = {817-850},
  doi       = {10.1613/JAIR.1.11936},
  volume    = {68},
  url       = {https://mlanthology.org/jair/2020/jamroga2020jair-partial/}
}