Wiebe Van Der Hoek

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 (theory) belief revision [1] to the dynamic epistemic logics introduced here.

FoLLI-LNCS is the publication platform for the Association of Logic, Language and Information. The Association was founded in 1991 to advance research and education on the interface between logic, linguistics, computer science, and cognitive science. The FoLLI Publications on Logic, Language and Information aim to disseminate results of cutting-edge research and tutorial materials in these interdisciplinary areas. This LNCS volume is part of FoLLi book serie and contains the papers presented at the 5th International Workshop on Logic, Rationality and Interaction/, held in October 2015 in Taipei, Taiwan. The topics covered in this program well represent the span and depth that hasby now become a trademark of the LORI workshop series, where logic interfaceswith disciplines as diverse as game theory and decision theory, philosophyand epistemology, linguistics, computer science and artificial intelligence.

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.

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.

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.

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.

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

We define a multi-modal version of Computation Tree Logic (CTL) by extending the language with path quantifiers $E^\delta $ and $E^\delta $ 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.

Although normative systems, or social laws, have proved to be a highly influential approach to coordination in multi-agent systems, the issue of compliance to such normative systems remains problematic. In all real systems, it is possible that some members of an agent population will not comply with the rules of a normative system, even if it is in their interests to do so. It is therefore important to consider the extent to which a normative system is robust, i.e., the extent to which it remains effective even if some agents do not comply with it. We formalise and investigate three different notions of robustness and related decision problems. We begin by considering sets of agents whose compliance is necessary and/or sufficient to guarantee the effectiveness of a normative system; we then consider quantitative approaches to robustness, where we try to identify the proportion of an agent population that must comply in order to ensure success; and finally, we consider a more general approach, where we characterise the compliance conditions required for success as a logical formula. We furthermore introduce a logic for specifying properties of norm compliance in general and norm robustness in particular.

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.

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.

In this paper a formal framework is proposed in which variousinformative actions are combined, corresponding to the different ways in whichrational agents can acquire information. In order to solve the variousconflicts that could possibly occur when acquiring information fromdifferent sources, we propose a classification of the informationthat an agent possesses according to credibility. Based on this classification, we formalize what itmeans for agents to have seen or heard something, or to believesomething by default. We present a formalization of observations,communication actions, and the attempted jumps to conclusions thatconstitutes default reasoning. To implement these informative actionswe use a general belief revision action which satisfies theAGM postulates; dependent on the credibility of the incominginformation this revision action acts on one or more parts ofthe classified belief sets of the agents. The abilities of agents formalizeboth the limited capacities of agents to acquire information, and the preference of one kind of information acquisition to another. A very important feature of our approach is that it shows how to integratevarious aspects of agency, in particular the (informational) attitudesof dealing with information from observation, communication and defaultreasoning into one coherent framework, both model-theoretically andsyntactically.

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.