TY - GEN
T1 - Strategy logic with simple goals
T2 - 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
AU - Belardinelli, Francesco
AU - Jamroga, Wojciech
AU - Kurpiewski, Damian
AU - Malvone, Vadim
AU - Murano, Aniello
N1 - Publisher Copyright:
© 2019 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - In this paper we introduce Strategy Logic with Simple Goals (SL[SG]), a fragment of Strategy Logic that strictly extends Alternating-time Temporal Logic ATL by introducing arbitrary quantification over the agents' strategies. Our motivation comes from game-theoretic applications, such as expressing Stackelberg equilibria in games, coercion in voting protocols, as well as module checking for simple goals. We prove that model checking SL[SG] is P-complete, the same as ATL. Thus, the extra expressive power comes at no computational cost as far as verification is concerned.
AB - In this paper we introduce Strategy Logic with Simple Goals (SL[SG]), a fragment of Strategy Logic that strictly extends Alternating-time Temporal Logic ATL by introducing arbitrary quantification over the agents' strategies. Our motivation comes from game-theoretic applications, such as expressing Stackelberg equilibria in games, coercion in voting protocols, as well as module checking for simple goals. We prove that model checking SL[SG] is P-complete, the same as ATL. Thus, the extra expressive power comes at no computational cost as far as verification is concerned.
U2 - 10.24963/ijcai.2019/13
DO - 10.24963/ijcai.2019/13
M3 - Conference contribution
AN - SCOPUS:85074906382
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 88
EP - 94
BT - Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
A2 - Kraus, Sarit
PB - International Joint Conferences on Artificial Intelligence
Y2 - 10 August 2019 through 16 August 2019
ER -