Reference : Towards Partial Order Reductions for Strategic Ability
Scientific journals : Article
Engineering, computing & technology : Computer science
Security, Reliability and Trust
Towards Partial Order Reductions for Strategic Ability
Jamroga, Wojciech mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA >]
Penczek, Wojciech []
Sidoruk, Teofil []
Dembiński, Piotr []
Mazurkiewicz, Antoni []
Journal of Artificial Intelligence Research
[en] multiagent systems ; formal verification ; temporal reasoning
[en] 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.
FnR ; FNR12685695 > Peter Y. A. Ryan > STV > Socio-technical Verification Of Information Security And Trust In Voting Systems > 01/09/2019 > 31/08/2022 > 2018

File(s) associated to this reference

Fulltext file(s):

Open access
POR4ATL-JAIR[1].pdfAuthor preprint794.13 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.