Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Comparing variants of strategic ability: how uncertainty and memory influence general properties of games
Bulling, Nils; Jamroga, Wojciech
2014In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems
Peer reviewed
 

Files


Full Text
Comparing variants of strategic ability.pdf
Publisher postprint (1.51 MB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Alternating-time temporal logic; Validity and satisfiability; Properties of games; Games with imperfect information
Abstract :
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.
Disciplines :
Computer science
Author, co-author :
Bulling, Nils
Jamroga, Wojciech ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
yes
Language :
English
Title :
Comparing variants of strategic ability: how uncertainty and memory influence general properties of games
Publication date :
2014
Event name :
Autonomous Agents and Multi-agent Systems
Event organizer :
International Foundation for Autonomous Agents and Multiagent Systems
Event place :
Paris, France
Event date :
2014
Main work title :
Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems
ISBN/EAN :
978-1-4503-2738-1
Pages :
474-518
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
Available on ORBilu :
since 08 March 2016

Statistics


Number of views
147 (3 by Unilu)
Number of downloads
332 (2 by Unilu)

Scopus citations®
 
65
Scopus citations®
without self-citations
37
WoS citations
 
52

Bibliography


Similar publications



Contact ORBilu