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". The key insight in (...) ATL is that the path quantifiers of CTL could be replaced by "cooperation modalities", of the form $\langle \langle \Gamma \rangle \rangle $, where Γ is a set of agents. The intended interpretation of an ATL formula $\langle \langle \Gamma \rangle \rangle \varphi $ is that the agents Γ can cooperate to ensure that φ holds. 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 -- 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)

Although the change of beliefs in the face of new information has been widely studied with some success, the revision of other mental states has received little attention from the theoretical perspective. In particular, intentions are widely recognised as being a key attitude for rational agents, and while several formal theories of intention have been proposed in the literature, the logic of intention revision has been hardly considered. There are several reasons for this: perhaps most importantly, intentions are very closely (...) connected with other mental states—in particular, beliefs about the future and the abilities of the agent. So, we cannot study them in isolation. We must consider the interplay between intention revision and the revision of other mental states, which complicates the picture considerably. In this paper, we present some first steps towards a theory of intention revision. We develop a simple model of an agent’s mental states, and define intention revision operators. Using this model, we develop a logic of intention dynamics, and then investigate some of its properties. (shrink)

Tim French, Wiebe van der Hoek, Petar Iliev and Barteld Kooi. Succinctness of Epistemic Languages. In: T. Walsh (editor). Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI-11), pp. 881-886, AAAI Press, Menlo Park.

Since it was first proposed by Moses, Shoham, and Tennenholtz, the social laws paradigm has proved to be one of the most compelling approaches to the offline coordination of multiagent systems. In this paper, we make four key contributions to the theory and practice of social laws in multiagent systems. First, we show that the Alternating-time Temporal Logic (atl) of Alur, Henzinger, and Kupferman provides an elegant and powerful framework within which to express and understand social laws for multiagent systems. (...) Second, we show that the effectiveness, feasibility, and synthesis problems for social laws may naturally be framed as atl model checking problems, and that as a consequence, existing atl model checkers may be applied to these problems. Third, we show that the complexity of the feasibility problem in our framework is no more complex in the general case than that of the corresponding problem in the Shoham–Tennenholtz framework (it is np-complete). Finally, we show how our basic framework can easily be extended to permit social laws in which constraints on the legality or otherwise of some action may be explicitly required. We illustrate the concepts and techniques developed by means of a running example. (shrink)

We study several modal languages in which some (sets of) generalized quantifiers can be represented; the main language we consider is suitable for defining any first order definable quantifier, but we also consider a sublanguage thereof, as well as a language for dealing with the modal counterparts of some higher order quantifiers. These languages are studied both from a modal logic perspective and from a quantifier perspective. Thus the issues addressed include normal forms, expressive power, completeness both of modal systems (...) and of systems in the quantifier tradition, complexity as well as syntactic characterizations of special semantic constraints. Throughout the paper several techniques current in the theory of generalized quantifiers are used to obtain results in modal logic, and conversely. (shrink)

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a (...) complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof. (shrink)

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E δ and A δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as “every coalition satisfying property P can achieve φ” and “there exists a coalition C satisfying property P such that C can achieve φ”. We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it is (...) nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We extend our general approach to characterizing information to multi-agent systems. In particular, we provide a formal description of an agent's knowledge containing exactly the information conveyed by some (honest) formula φ. Only knowing is important for dynamic agent systems in two ways. First of all, one wants to compare different states of knowledge of an agent and, secondly, for agent a's decisions, it may be relevant that (he knows that) agent b does not know more than φ. There are (...) three ways to study the question whether a formula φ can be interpreted as minimal information. The first method is semantic and inspects 'minimal' models for φ (with respect to some information order ≤ on states). The second one is syntactic and searches for stable expansions, minimal with respect to some language $\scr{L}^{\ast}$ . The third method is a deductive test, known as the disjunction property. We present a condition under which the three methods are equivalent. Then, we show how to construct the order ≤ by collecting 'layered orders'. Focusing on the multi-agent case we identify languages $\scr{L}^{\ast}$ for various orders ≤, and show how they yield different notions of honesty for different multi-modal systems. We then provide several tools for studying honesty types and illustrate their usefulness on a number of examples, for three modal systems of particular interest. Finally, we relate the different notions of minimal knowledge, and describe possible patterns of honesty for these systems. (shrink)

We propose an epistemic logic in which knowledge is fully introspective and implies truth, although truth need not imply epistemic possibility. The logic is presented in sequential format and is interpreted in a natural class of partial models, called balloon models. We examine the notions of honesty and circumscription in this logic: What is the state of an agent that only knows and which honest enable such circumscription? Redefining stable sets enables us to provide suitable syntactic and semantic criteria for (...) honesty. The rough syntactic definition of honesty is the existence of a minimal stable expansion, so the problem resides in the ordering relation underlying minimality. We discuss three different proposals for this ordering, together with their semantic counterparts, and show their effects on the induced notions of honesty. (shrink)

We demonstrate ways to incorporate nondeterminism in a system designed to formalize the reasoning of agents concerning their abilities and the results of the actions that they may perform. We distinguish between two kinds of nondeterministic choice operators: one that expresses an internal choice, in which the agent decides what action to take, and one that expresses an external choice, which cannot be influenced by the agent. The presence of abilities in our system is the reason why the usual approaches (...) towards nondeterminism cannot be used here. The semantics that we define for nondeterministic actions is based on the idea that composite actions are unravelled in the strings of atomic actions and tests that constitute them. The main notions used in defining this semantics are finite computation sequences and finite computation runs of actions. The results that we obtain meet our intuitions regarding events and abilities in the presence of nondeterminism. (shrink)

Hans van Ditmarsch, Wiebe van der Hoek and Barteld Kooi (2011). Reasoning about local properties in modal logic. In K. Tumer and P. Yolum and L. Sonenberg and P. Stone (editors). Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 711-718.

We define balance games, which describe the formation of friendships and enmity in social networks. We show that if the agents give high priority to future profits over short term gains, all Pareto optimal strategies will eventually result in a balanced network. If, on the other hand, agents prioritize short term gains over the long term, every Nash equilibrium eventually results in a network that is stable but that might not be balanced.

This contribution is a gentle introduction to so-called dynamic epistemic logics, that can describe how agents change their knowledge and beliefs. We start with a concise introduction to epistemic logic, through the example of one, two and finally three players holding cards; and, mainly for the purpose of motivating the dynamics, we also very summarily introduce the concepts of general and common knowledge. We then pay ample attention to the logic of public announcements, wherein agents change their knowledge as the (...) result of, indeed, public announcements. One crucial topic in that setting is that of unsuccessful updates: formulas that become false when announced. The Moore-sentences that were already extensively discussed at the conception of epistemic logic in [15] give rise to such unsuccessful updates. After that, we present a few examples of more complex epistemic updates. Our closing observations are on recent developments that link the ‘standard’ topic of belief revision [1] to the dynamic epistemic logics introduced here. (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)