Satisfiability in Strategy Logic Can Be Easier than Model Checking

Authors

  • Erman Acar Vrije Universiteit Amsterdam
  • Massimo Benerecetti Università degli Studi di Napoli Federico II
  • Fabio Mogavero Università degli Studi di Napoli Federico II

DOI:

https://doi.org/10.1609/aaai.v33i01.33012638

Abstract

In the design of complex systems, model-checking and satisfiability arise as two prominent decision problems. While model-checking requires the designed system to be provided in advance, satisfiability allows to check if such a system even exists. With very few exceptions, the second problem turns out to be harder than the first one from a complexity-theoretic standpoint. In this paper, we investigate the connection between the two problems for a non-trivial fragment of Strategy Logic (SL, for short). SL extends LTL with first-order quantifications over strategies, thus allowing to explicitly reason about the strategic abilities of agents in a multi-agent system. Satisfiability for the full logic is known to be highly undecidable, while model-checking is non-elementary.

The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important game-theoretic properties of multi-agent systems, such as existence of Nash and immune equilibria, as well as to formalize the rational synthesis problem. We show that satisfiability for such a fragment is PSPACE-COMPLETE, while its model-checking complexity is 2EXPTIME-HARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctive-binding first-order logic, a recently discovered decidable fragment of first-order logic.

Downloads

Published

2019-07-17

How to Cite

Acar, E., Benerecetti, M., & Mogavero, F. (2019). Satisfiability in Strategy Logic Can Be Easier than Model Checking. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2638-2645. https://doi.org/10.1609/aaai.v33i01.33012638

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning