Strategy Logic with Imperfect Information

Authors: Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin and Moshe Vardi

Paper Information

Title:Strategy Logic with Imperfect Information
Authors:Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin and Moshe Vardi
Proceedings:SR SR18 papers
Editors: Nicolas Markey and Patricia Bouyer
Keywords:Strategy Logic, Model checking, Imperfect information, Hierarchical information

ABSTRACT. We introduce an extension of Strategy logic for the imperfect-information setting, called SLii, and study its model-checking problem. As this logic naturally captures multi-player games with imperfect information, the problem turns out to be undecidable. We introduce a syntactical class of "hierarchical instances" for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model. We prove that model-checking SLii restricted to hierarchical instances is decidable. This result, because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises previous ones, such as decidability of multi-player games with imperfect information and hierarchical observations, and decidability of distributed synthesis for hierarchical systems.

Talk:Jul 08 16:40 (Session 42Q: Strategy Logic)