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)

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 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 *. 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 * 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 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)

Contemporary epistemological and cognitive studies, as well as recent trends in computer science and game theory have revealed an increasingly important and intimate relationship between Information, Interaction, and Agency. Agents perform actions based on the available information and in the presence of other interacting agents. From this perspective Information, Interaction, and Agency neatly ties together classical themes like rationality, decision-making and belief revision with games, strategies and learning in a multi-agent setting. Unified by the central notions Information, Interaction, and Agency, (...) the essays in this volume provide refreshing methodological perspectives on belief revision, dynamic epistemic logic, von Neumann games, and evolutionary game theory; all of which in turn are central approaches to understanding our own rationality and that of other agents. (shrink)

This volume concerns Rational Agents - humans, players in a game, software or institutions - which must decide the proper next action in an atmosphere of partial information and uncertainty. The book collects formal accounts of Uncertainty, Rationality and Agency, and also of their interaction. It will benefit researchers in artificial systems which must gather information, reason about it and then make a rational decision on which action to take.

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)

Rational agents are important objects of study in several research communities, including economics, philosophy, cognitive science, and most recently computer science and artificial intelligence. Crudely, a rational agent is an entity that is capable of acting on its environment, and which chooses to act in such a way as to further its own best interests. There has recently been much interest in the use of mathematical logic for developing formal theories of such agents. Such theories view agents as practical reasoning (...) systems, deciding moment by moment which action to perform next, given the beliefs they have about the world and their desires with respect to how they would like the world to be. In this article, we survey the state of the art in developing logical theories of rational agency. Following a discussion on the dimensions along which such theories can vary, we briefly survey the logical tools available in order to construct such theories. We then review and critically assess three of the best known theories of rational agency: Cohen and Levesque's intention logic, Rao and Georgeff's BDI logics, and the KARO framework of Meyer et al. We then discuss the various roles that such logics can play in helping us to engineer rational agents, and conclude with a discussion of open problems. (shrink)

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 present an epistemic default logic, based on the metaphore of a meta-level architecture. Upward reflection is formalized by a nonmonotonic entailment relation, based on the objective facts that are either known or unknown at the object level. Then, the meta (monotonic) reasoning process generates a number of default-beliefs of object-level formulas. We extend this framework by proposing a mechanism to reflect these defaults down. Such a reflection is seen as essentially having a temporal flavour: defaults derived at the meta-level (...) are projected as facts in a next object level state. In this way, we obtain temporal models for default reasoning in meta-level formalisms which can be conceived as labeled branching trees. Thus, descending the tree corresponds to shifts in time that model downward reflection, whereas the branching of the tree corresponds to ways of combining possible defaults. All together, this yields an operational or procedural semantics of reasoning by default, which admits one to reason about it by means of branching-time temporal logic. Finally, we define sceptical and credulous entailment relations based on these temporal models and we characterize Reiter extensions in our semantics. (shrink)

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. (shrink)

Dynamic Epistemic Logic is the logic of knowledge change. This book provides various logics to support such formal specifications, including proof systems. Concrete examples and epistemic puzzles enliven the exposition. The book also offers exercises with answers. It is suitable for graduate courses in logic. Many examples, exercises, and thorough completeness proofs and expressivity results are included. A companion web page offers slides for lecturers and exams for further practice.

We give a model for iterated belief change in multi-agent systems. The formal tool we use for this is a combination of modal and dynamic logic. Two core notions in our model are the expansion of the knowledge and beliefs of an agent, and the processing of new information. An expansion is defined as the change in the knowledge and beliefs of an agent when it decides to believe an incoming formula while holding on to its current propositional beliefs. To (...) prevent our agents from forming inconsistent beliefs they do not expand with every piece of information they receive. Instead, our agents remember their original beliefs and every piece of information they receive. After every receipt of information they decide which subset of the received information should be incorporated into their original beliefs. This procedure is called the processing of new information. We show that our model of belief update behaves in an intuitive way and that it is not sensitive to criticism on comparable models. (shrink)

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 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 Hintikka’s ‘Knowledge and Belief ’ (1962) give rise to such unsuccessful updates. After that, we present a few examples of more complex epistemic updates. (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)

Qualitative Coalitional Games are a variant of coalitional games in which an agent's desires are represented as goals that are either satisfied or unsatisfied, and each choice available to a coalition is a set of goals, which would be jointly satisfied if the coalition made that choice. A coalition in a QCG will typically form in order to bring about a set of goals that will satisfy all members of the coalition. Our goal in this paper is to develop and (...) study logics for reasoning about QCGs. We begin by introducing a logic for reasoning about “static” QCGs, where participants play a single game, and we then introduce and study Temporal QCGs , i.e., games in which a sequence of QCGs is played. In order to represent and reason about such games, we introduce a linear time temporal logic of QCGs, called ℒ. We give a complete axiomatisation of ℒ, use it to investigate the properties of TQCGs, identify its expressive power, establish its complexity, characterise classes of TQGCs with formulas from our logical language, and use it to formulate several solution concepts for TQCGs. (shrink)

Epistemic logic has grown from its philosophical beginnings to find diverse applications in computer science, and as a means of reasoning about the knowledge and belief of agents. This book provides a broad introduction to the subject, along with many exercises and their solutions. The authors begin by presenting the necessary apparatus from mathematics and logic, including Kripke semantics and the well-known modal logics K, T, S4 and S5. Then they turn to applications in the context of distributed systems and (...) artificial intelligence. These include the notions of common knowledge, distributed knowledge, explicit and implicit belief, the interplays between knowledge and time, and knowledge and action, as well as a graded (or numerical) variant of the epistemic operators. The authors also discuss extensively the problem of logical omniscience. They cover Halpern & Moses' theory of honest formulas, and they make a digression into the realm of nonmonotonic reasoning and preferential entailment. They discuss Moore's autoepistemic logic, together with Levesque's related logic of "all I know". Furthermore, they show how one can base default and counterfactual reasoning on epistemic logic. Graduate students in philosophy or in computer science, especially those with an interest in AI, will find this book useful. (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 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)

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 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 Hintikka’s ‘Knowledge and Belief’ 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, as in ‘On the Logic of Theory Change: partial meet contraction and revision functions’, by Alchourron et al. , to the dynamic epistemic logics introduced here. (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)

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. (shrink)