Strategy logic with simple goals: tractable reasoning about strategies
File(s)slsg19ijcai-submission.pdf (339.09 KB)
Accepted version
Author(s)
Belardinelli, Francesco
Jamroga, Wojciech
Kurpiewski, Damian
Malvone, Vadim
Murano, Aniello
Type
Conference Paper
Abstract
In this paper we introduceStrategy Logic with Sim-ple Goals(SL[SG]), a fragment of Strategy Logicthat strictly extends the well-known Alternating-time Temporal LogicATLby introducing arbitraryquantification over the agents’ strategies. Our mo-tivation comes from game-theoretic applications,such as expressing Stackelberg equilibria in games,coercion in voting protocols, as well as modulechecking for simple goals. Most importantly, weprove that the model checking problem forSL[SG]isP-complete, the same asATL. Thus, the extraexpressive power comes at no computational costas far as verification is concerned.
Date Issued
2019-08-10
Date Acceptance
2019-05-10
Citation
IJCAI : proceedings of the conference / sponsored by the International Joint Conferences on Artificial Intelligence, 2019, pp.88-94
ISSN
1045-0823
Publisher
IJCAI
Start Page
88
End Page
94
Journal / Book Title
IJCAI : proceedings of the conference / sponsored by the International Joint Conferences on Artificial Intelligence
Copyright Statement
© 2019, IJCAI
Source
International Joint Conference in Artificial Intelligence
Publication Status
Published
Start Date
2019-08-10
Finish Date
2019-08-16
Coverage Spatial
Macao, China