On Friday April 1st, we will have a LIRa session with Nils Bulling.
Everyone is cordially invited!
Speaker: Nils Bulling (TU Delft)
Date and Time: Friday, April 1st 2016, 13:00-14:30
Venue: ILLC Seminar Room F1.15, Science Park 107
Title: Agents with Truly Perfect Recall.
Abstract. Alternating-time temporal logics are modal logic that allow to reason about agents’ abilities in game-like scenarios. The basic logic ATL [1] comes in different variants which are based on different assumptions about the capabilities of agents and properties of the game. They include, for example, the agents’ knowledge about the world (perfect vs. imperfect information) as well as how agents remember and make use of past events (memoryless vs. memory-based strategies). In previous years the different variants of ATL have been extensively studied, but mostly in the context of model checking. The contribution of this talk is twofold.
Firstly, I shall review ATL as well as its semantic variants and compare them with respect to their validity sets. It will be shown that they yield different strategic logics [2]; thus, they model different general properties of games. Secondly, it will be argued that the standard definition of perfect recall can be counter intuitive in settings where agents have limited observational capabilities. This is due to the way nested strategic modalities are interpreted: the strategy which is bound by the nested operator does not take into account the history of events. Thus, although agents are assumed to have perfect recall they may forget the past. Intuitively, it does not fit the assumption of agents having perfect recall. To fix this, I shall present a new semantics where agents have truly prefect recall [3]. The new semantics will be compared with the standard one; in particular, it will be shown that they coincide for perfect information but differ in the case of imperfect information.
(The talk is based on joint work with Wojtek Jamroga and Matei Popovici.)
References
[1] R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time Temporal Logic. Journal of the ACM, 49: 672–713, 2002.
[2] Nils Bulling and Wojciech Jamroga. Comparing variants of strategic ability: how uncertainty and memory influence general properties of games. Journal of Autonomous Agents and Multi-Agent Systems, 28(3): 474–518, 2014.
[3] Nils Bulling, Wojciech Jamroga, and Matei Popovici. ATL* with truly perfect recall: Expressivity and validities. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pages 177–182, Prague, Czech Republic, August 2014.