Reference : Comparing variants of strategic ability: how uncertainty and memory influence general...
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Comparing variants of strategic ability: how uncertainty and memory influence general properties of games
Bulling, Nils [> >]
Jamroga, Wojciech mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems
Autonomous Agents and Multi-agent Systems
International Foundation for Autonomous Agents and Multiagent Systems
[en] Alternating-time temporal logic ; Validity and satisfiability ; Properties of games ; Games with imperfect information
[en] Alternating-time temporal logic (ATL) is a modal logic that allows to reason about agents’ abilities in game-like scenarios. Semantic variants of ATL are usually built upon different assumptions about the kind of game that is played, including capabilities of agents (perfect vs. imperfect information, perfect vs. imperfect memory, etc.). ATL has been studied extensively in previous years; however, most of the research focused on model checking. Studies of other decision problems (e.g., satisfiability) and formal meta-properties of the logic (like axiomatization or expressivity) have been relatively scarce, and mostly limited to the basic variant of ATL where agents possess perfect information and perfect memory. In particular, a comparison between different semantic variants of the logic is largely left untouched. In this paper, we show that different semantics of ability in ATL give rise to different validity sets. The issue is important for several reasons. First, many logicians identify a logic with its set of true sentences. As a consequence, we prove that different notions of ability induce different strategic logics. Secondly, we show that different concepts of ability induce different general properties of games. Thirdly, the study can be seen as the first systematic step towards satisfiability-checking algorithms for ATL with imperfect information. We introduce sophisticated unfoldings of models and prove invariance results that are an important technical contribution to formal analysis of strategic logics.

File(s) associated to this reference

Fulltext file(s):

Open access
Comparing variants of strategic ability.pdfPublisher postprint1.48 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.