Satisfiability in Strategy Logic Can Be Easier than Model Checking.

Erman Acar, Massimo Benerecetti, Fabio MogaveroAAAI 2019 · OpenReview

Abstract

In the design of complex multi-agent systems, two fundamental decision problems arise: model checking (verifying if a given system meets specifications) and satisfiability (determining if any such system exists). Traditionally, satisfiability is the more computationally demanding problem. However, this research identifies a specific fragment of Strategy Logic (SL) where this hierarchy is reversed. By restricting strategic quantifications from appearing within the scope of temporal operators, the authors demonstrate that satisfiability for this fragment is PSPACE-complete, while model checking remains 2EXPTIME-hard. This discovery suggests that for certain complex specifications, it is computationally more efficient to synthesize a system from scratch than to verify an existing one.

The Challenge of Strategy Logic

Strategy Logic (SL) is a powerful framework for reasoning about multi-agent systems, extending Linear Temporal Logic (LTL) with first-order quantifiers over strategies. It allows designers to explicitly formalize the strategic abilities of agents, expressing complex game-theoretic properties such as the existence of Nash Equilibria. However, this expressiveness comes at a high cost: satisfiability for full SL is undecidable, and model checking is non-elementary. To make SL practical for system synthesis, researchers seek "fragments"—subsets of the logic that remain expressive yet become computationally tractable.

A Surprising Complexity Reversal

This paper focuses on Flat Conjunctive-Goal Strategy Logic (FSL[CG]). The "flat" constraint prevents strategic quantifiers (e.g., "there exists a strategy $x$") from being nested inside temporal operators (e.g., "always" or "eventually").

In most logical frameworks, checking if a specific model satisfies a formula is easier than searching the entire space of possible models for one that works. In FSL[CG], the opposite occurs. The authors prove that satisfiability is PSPACE-complete—the same complexity class as standard LTL—while model checking is 2EXPTIME-hard. This "complexity flip" makes FSL[CG] a unique and powerful tool for automated synthesis.

Methodology: Taming the Logic

To establish these complexity bounds, the researchers employed several innovative techniques:

  1. First-Order Encoding: They developed a method to translate FSL[CG] formulas into FOL[CB] (Conjunctive-Binding First-Order Logic), a recently discovered decidable fragment of First-Order Logic.
  2. SMT-like Procedure: Rather than a direct, exhaustive translation, they proposed a non-deterministic procedure using LTL as a background theory. This allows for checking consistency without explicitly constructing the entire state space.
  3. Bounded-Width Model Property: A critical proof shows that if an FSL[CG] formula is satisfiable, it can be satisfied by a model with a manageable number of actions, preventing the search space from exploding.
Figure 1: A tree-like model structure illustrating strategic branching from an initial state $s_0$. The labels $d_i$ represent different strategic directions available to agents, used to reason about outcomes in Strategy Logic.

Key Results and Implications

The primary contribution is the establishment of the PSPACE-complete bound for satisfiability. Despite its "flatness," FSL[CG] remains highly expressive, capable of formalizing:

  • Nash Equilibria: Scenarios where no player can benefit by changing their strategy if others keep theirs unchanged.
  • Immune Equilibria: Strategies that protect a player against deviations by others.
  • Rational Synthesis: The problem of building a system that achieves its goal even when environment agents act in their own self-interest.

The massive gap between PSPACE and 2EXPTIME suggests that for these properties, automated synthesis (via SAT) is exponentially more efficient than manual design followed by verification (model checking).

Future Directions

While the theoretical results are promising, practical implementation remains the next hurdle. The authors suggest that the "flatness" constraint might be slightly relaxed—for instance, by allowing nesting within specific temporal operators like "Until"—without losing PSPACE-completeness. Future work will focus on developing tools that implement the SMT-like procedure to solve real-world multi-agent coordination and synthesis problems.

Summary updated

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.
BibTeX
@inproceedings{acar2019satisfiability,
  author = {Erman Acar and Massimo Benerecetti and Fabio Mogavero},
  title = {{Satisfiability in Strategy Logic Can Be Easier than Model Checking.}},
  booktitle = {AAAI},
  year = {2019},
  url = {https://openreview.net/forum?id=SolxZlezldaS},
}
Figure