Reference : Towards Partial Order Reductions for Strategic Ability
Scientific journals : Article
Engineering, computing & technology : Computer science
Security, Reliability and Trust
http://hdl.handle.net/10993/45851
Towards Partial Order Reductions for Strategic Ability
English
Jamroga, Wojciech mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA >]
Penczek, Wojciech []
Sidoruk, Teofil []
Dembiński, Piotr []
Mazurkiewicz, Antoni []
2020
Journal of Artificial Intelligence Research
68
817-850
Yes
International
[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.
Researchers
http://hdl.handle.net/10993/45851
10.1613/jair.1.11936
https://www.jair.org/index.php/jair/article/view/11936/26601
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):

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