We study the logic of strategic ability of coalitions of agents with bounded memory by introducing Alternating-time Temporal Logic with Bounded Memory (ATLBM), a variant of Alternating-time Temporal Logic (ATL). ATLBM accounts for two main consequences of the assumption that agents have bounded memory. First, an agent can only remember a strategy that specifies actions in a bounded number of different circumstances. While the ATL-formula means that coalition C has a joint strategy which will make φ true forever, the ATLBM-formula (...) means that C has a joint strategy which for each agent in C specifies what to do in no more than n different circumstances and which will make φ true forever. Second, an agent has bounded recall—a strategy can only take the last m states of the system into account. We use the logic to study the interaction between strategic ability, bounded number of decisions, bounded recall and incomplete information. We discuss the logical properties and expressiveness of ATLBM, and its relationship to ATL. We show that ATLBM can express properties of strategic ability under bounded memory which cannot be expressed in ATL. (shrink)

We propose a non-standard interpretation of Alternating-time Temporal Logic with imperfect information, for which no commonly accepted semantics has been proposed yet. Rather than changing the semantic structures, we generalize the usual interpretation of formulae in single states to sets of states. We also propose a new epistemic operator for ?practical? or ?constructive? knowledge, and we show that the new logic (which we call Constructive Strategic Logic) is strictly more expressive than most existing solutions, while it retains the same model (...) checking complexity. Finally, we study properties of constructive knowledge and other operators in this non-standard semantics. (shrink)

Alternating-time temporal logic (ATL) is a branching time temporal logic in which statements about what coalitions of agents can achieve by strategic cooperation can be expressed. Alternating-time temporal epistemic logic (ATEL) extends ATL by adding knowledge modalities, with the usual possible worlds interpretation. This paper investigates how properties of agents’ actions can be expressed in ATL in general, and how properties of the interaction between action and knowledge can be expressed in ATEL in particular. One commonly discussed property is that (...) an agent should know about all available actions, i.e., that the same actions should be available in indiscernible states. Van der Hoek and Wooldridge suggest a syntactic expression of this semantic property. This paper shows that this correspondence in fact does not hold. Furthermore, it is shown that the semantic property is not expressible in ATEL at all. In order to be able to express common and interesting properties of action in general and of the interaction between action and knowledge in particular, a generalization of the coalition modalities of ATL is proposed. The resulting logics, ATL-A and ATEL-A, have increased expressiveness without loosing ATL’s and ATEL’s tractability of model checking. (shrink)

Branching-time temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as Alternating-time Temporal Logic (ATL). The key insight (...) in ATL is that the path quantifiers of CTL could be replaced by cooperation modalities, of the form , where is a set of agents. The intended interpretation of an ATL formula is that the agents can cooperate to ensure that holds (equivalently, that have a winning strategy for ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as group can cooperate to bring about iff it is common knowledge in that . The resulting logic — Alternating-time Temporal Epistemic Logic (ATEL) — shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about game-like multiagent systems. (shrink)