The aim of this paper, is to provide a logical framework for reasoning about actions, agency, and powers of agents and coalitions in game-like multi-agent systems. First we define our basic Dynamic Logic of Agency ( ). Differently from other logics of individual and coalitional capability such as Alternating-time Temporal Logic (ATL) and Coalition Logic, in cooperation modalities for expressing powers of agents and coalitions are not primitive, but are defined from more basic dynamic logic operators of action and (historic) (...) necessity. We show that STIT logic can be reconstructed in . We then extend with epistemic operators, which allows us to distinguish capability and power. We finally characterize the conditions under which agents are aware of their capabilities and powers. (shrink)

This paper explores the analysis of ability, where ability is to be understood in the epistemic sense—in contrast to what might be called a causal sense. There are plenty of cases where an agent is able to perform an action that guarantees a given result even though she does not know which of her actions guarantees that result. Such an agent possesses the causal ability but lacks the epistemic ability. The standard analysis of such epistemic abilities relies on the notion (...) of action types—as opposed to action tokens—and then posits that an agent has the epistemic ability to do something if and only if there is an action type available to her that she knows guarantees it. We show that these action types are not needed: we present a formalism without action types that can simulate analyzes of epistemic ability that rely on action types. Our formalism is a standard epistemic extension of the theory of “seeing to it that”, which arose from a modal tradition in the logic of action. (shrink)

As a new type of epistemic logics, the logics of knowing how capture the high-level epistemic reasoning about the knowledge of various plans to achieve certain goals. Existing work on these logics focuses on axiomatizations; this paper makes the first study of their model theoretical properties. It does so by introducing suitable notions of bisimulation for a family of five knowing how logics based on different notions of plans. As an application, we study and compare the expressive power of these (...) logics. (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)

In previous works, we presented a modification of the usual possible world semantics by introducing an independent temporal structure in each world and using accessibility functions to represent the relation among them. Different properties ofthe accessibility functions have been considered and axiomatic systems which define these properties have been given. Only a few ofthese systems have been proved tobe complete. The aim ofthis paper is to make a progress in the study ofcompleteness for functional systems. For this end, we use (...) indexes as names for temporal flows and give new proofs of completeness. Specifically, we focus our attention on the system which defines injectivity, because the system which defines this property without using indexes was proved to be incomplete in previous works. The only system considered which remains incomplete is the one which defines surjectivity, even ifwe consider a sequence ofnatural extensions ofthe previous one. (shrink)

Qualitative coalitional games (QCGs) were introduced as abstract formal models of goal-oriented cooperative systems. A QCG is a game in which each agent is assumed to have some goal to achieve, and in which agents must typically cooperate with others in order to satisfy their goals. In this paper, we show how it is possible to reason about QCGs using Coalition Logic (CL), a formalism intended to facilitate reasoning about coalitional powers in game-like multiagent systems. We introduce a correspondence relation (...) between QCGs and interpretations for CL, which defines the circumstances under which a CL interpretation correctly characterises a QCG. The complexity of deciding correspondence between QCGs and interpretations for CL is shown to vary from being tractable up to Πp 2-complete, depending on the representation chosen for the QCG and interpretation. We then show how various properties and solution concepts of QCGs can be characterised as CL formula schemes. The ideas are illustrated via a detailed worked example, in which we demonstrate how a model checker can be deployed to investigate whether a particular system has the properties in question. (shrink)

The importance of potential intentions has been demonstrated both in the construction of agent systems and in the formalisation of teamwork behaviour. However, there still lacks an adequate semantics for the notion of potential intentions as introduced by Grosz and Kraus in their SharedPlans framework. In this paper, we give a formal semantics to intentions and potential intentions, drawing upon both the representationalist approach and the accessibility-based approach. The model captures the dynamic relationship among intentions and potential intentions by providing (...) semantic rules and conditions. Also, the model treats norms as a special class of intentional context, and it is shown that norms play a critical role in the dynamics of intentions in multiagent systems. The formal semantics allows us to validate some properties that are widely-accepted for intention attitudes. (shrink)

Dynamic epistemic logic, broadly conceived, is the study of logics of information change. This is the first paper in a two-part series introducing this research area. In this paper, I introduce the basic logical systems for reasoning about the knowledge and beliefs of a group of agents.

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)

Understanding the flow of knowledge in multi-agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic settings. In this paper we show that such situations can be understood as a special type of game – a knowledge condition game – in which a coalition “wins” if it is able to (...) bring about some epistemic condition. This paper summarizes some results relating to these games. Two proofs are presented for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Σ2P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but requires a different proof. (shrink)

We present a variant of ATL with incomplete information which includes the distributed knowledge operators corresponding to synchronous action and perfect recall. The cooperation modalities assume the use the distributed knowledge of coalitions and accordingly refer to perfect recall incomplete information strategies. We propose a model-checking algorithm for the logic. It is based on techniques for games with imperfect information and partially observable objectives, and involves deciding emptiness for automata on infinite trees. We also propose an axiomatic system and prove (...) its completeness for a rather expressive subset. As for the constructs left outside this completely axiomatised subset, we present axioms by which they can be defined in the subset on the class of models in which every state has finitely many successors and give a complete axiomatisation for a “flat” subset of the logic with these constructs included. (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)