Dynamic Logic Montréal
Abstracts 
Horacio ArlóCosta
(Carnegie Mellon University)
Indeterminacy and belief change
Most of the literature on belief change and dynamic epistemic logic
presupposes a theory of rationality according to which rational agents are
optimizers: they chose the best among the feasible epistemic options
available to them. But when epistemic values are indeterminate this view of
rationality is not applicable. In this situation is still rational to
maximize, i.e. to deem an option as choosable when it is not known to be
worse that any other (Sen, 1997). We present here basic results about a
notion of liberal contraction based on maximizing preference relations that
need not be complete.
We study as well a more liberal view than the one usually assumed in the
literature on belief change (based on insights first proposed by Isaac Levi)
about the structure of the feasible set used for maximization. We conclude
by considering the epistemological roots of some counterexamples against the
most fundamental axioms of choice functions used in the formulation of
liberal contraction and by showing that some bounded methods of choice (like
Simon's satisficing) can be accommodated in the proposed framework.
Guillaume Aucher (LILaC, Toulouse)
Private Revision in a MultiAgent Setting
In this talk, we will tackle the issue of how a particular and specified agent Y revises his/her beliefs about the world and about the other agents' beliefs when she privately receives new (and supposedly truthful) information. The models we consider are supposed to represent the way she personally views the world (which can then be erroneous). The announcement is privately made to the agent Y which means that the beliefs of the other agents should not change in reality. Thus there is no real dynamic aspect but everything is static, which makes the revision process very close in nature to the one classically studied in belief revision for a single agent. This process will be described and the technics employed are indeed very close in spirit to the ones of the AGM approach. Finally, in Sect. 4 we provide a constructive way to determine the revised models based on the notion of “canonical model of degree n" and show the connection between the expansion operation and the revision operation.
Alexandru Baltag (Oxford) and Sonja Smets (Brussels)
Dynamic Logic meets Knowledge and Belief
In the classical work of Hintikka and other philosophers, epistemic and doxastic logics were taken as the formal logical settings of most relevance to epistemological issues. These modal logics can direct express static properties of knowledge and belief, and thus were applied to the analysis of a range of controversial issues and paradoxes surrounding these notions. However, these logics are unable to deal with the dynamics of knowledge or belief, and thus cannot analyze information flow, information exchanges and changes of belief.
Traditionally, such issues were treated using either Belief Revision theory or combinations of Temporal and Epistemicdoxastic logics. However, the last decade has seen the successful development of a number of approaches based on Dynamic Logic, approaches collectively known as "Dynamic Epistemic Logic" (DEL). For a long while concerned mainly with knowledge, DEL logicians have recently started exploring the dynamics of belief, borrowing heavily from classical Belief Revision theory and (less visibly, but essentially) from Probabilistic (Bayesian) approaches to belief change.
Is the dynamic logic approach (as some wellknown experts seem to imply) a simple translation of old concepts and issues into a different formalism, destined only to fight again old fights and rediscover old solutions to the same old problems? Or does it add anything of value to the discussion, anything that could not be expressed using classical epistemicdoxastic logic, belief revision theory, temporalepistemic logics or Bayesian updates? After borrowing so much from all these older approaches, can DEL pay back its dues, giving a new perspective to information flow, and maybe even throwing a new light to the issues that were
most controversial in the old approaches?
In our talk, we try to answer these questions.
First, we argue that, in common with temporalepistemic logics and other modal approaches, but in contrast to Belief Revision, DEL is grounded in a realistic ontology: this is due to the fact that the "actual world", the "real state" plays a central role. This simple formal feature allows one to clearly distinguish between real "knowledge" and any form of "true, welljustified, completely safe belief" (however persistent, or "robust", or "defeasible", or unrevisable). The distinction has of course been made before, but only modal logic approaches incorporate in an essential way in their semantics. This can be used to solve old epistemicdoxastic paradoxes, as well as to give a new perspective on old debates about negative introspection and weak notions of "knowledge".
Second, this realism applies to "changes of state", and not only to states: the DEL
approach is "truly dynamic" in a very specific (and realistic) sense. In Belief Revision theory, beliefs change, but their object remains the same (an unchanged state of the world, in classical AGM theory) or (in other approaches) is at most affected by "neutral", objective changes (that have nothing to do with our beliefs). In this sense, traditional belief revision is "static" in a fundamental sense!
Moreover, only DEL can express and explore the sense in which the world itself is changed by our changes of belief. (Cf. Moore sentences and other puzzles.) In this context, the "revision" of AGM theory can be recovered as a "static", "hypothetical", "conditional" preencoding of the true dynamics of belief: an (incomplete) revision plan, constraining one's responses to possible future informational events. The distinction can be used to give elegant and illuminating solutions to some classical problems (e.g. the necessary failure of the socalled "Ramsey test") encountered by the "conditional" approach to belief revision.
Third, this realism applies to "actions" (including "epistemic actions", or better said "epistemic events"), and not just to indifferent, amorphous, unstructured belief changes. DEL can capture, analyze and classify specific types of belief changes: concrete actions such as (sincere, truthful) public announcements, private exchanges of messages over secure channels, unsecure communication, lying, information obtained from unreliable sources, information obtained by secret thirdpart interception ("wiretapping") etc. Other approaches (probabilistic, temporal) can say something about some of these issues, but only DEL can directly and completely express them, and can classify them into types of information exchange: each of the above actions is of a different "type", even when their propositional content is the same. From the DEL perspective, "revising one's beliefs with a proposition P " is just an underdefined expression: one has to specify how the message P was obtained, if the source was truthful, trustable or sincere, who else was meant to receive it, who did in fact receive it etc.
In other words: beliefs are never revised by "propositions", they are revised by doxastic actions. We argue that this throws a fresh light to ongoing debates in Belief Revision theory about the "right" notion of revision: the various revision or update operators (with the same new propositional information P) considered in the literature can be recovered in this context as simply the updates induced by different doxastic actions (with the same propositional content P). There is no unique, no "best", beliefrevision mechanism, but many types of doxastic actions leading to different revisions.
Finally, our last argument for DEL's novelty and power are the various Reduction Axioms, such as the socalled "ActionKnowledge Axiom" and its generalizations and analogues (to probabilistic settings, conditional beliefs, common knowledge, levels of knowledge etc.). The Reduction Axiom connect all the above issues and approaches, offering beautiful mathematical formulas as solutions to the central scientific/philosophical problem of information change: these axioms put together the "ontic facts" about the initial (actual) state of the world, the agents' preexisting knowledge, their conditional beliefs (pre encoding their individual strategy of doxastic responses to new propositional information) and the doxastic/epistemic "type" of the ongoing action, in order to predict, compute, explain and justify the agents' new beliefs after the action.
Johan van Benthem (Amsterdam & Stanford)
Dynamic Logics of Model Change
Current dynamic logics of knowledge, belief, and preference can model a wide variety of scenarios where information or attitudes change over time. I will discuss the mathematical background of these logics, when viewed as systems of model change. First, I show how logical operations that "switch between models" have come up in various settings over the last ten years, including the "information links" that underlie situation theory. Next, I show how dynamic logics point the way toward a more systematic program of axiomatizing parts of the "metatheory of model theory".
Paul Egré (CNRS, Institut JeanNicod)
Realistic Models of Common Knowledge
(joint work with Denis Bonnay, Paris)
According to the iterative definition of common knowledge, an information P is common knowledge among a group of agents if P is true, everyone knows P, everyone knows that everyone knows P, and so on and so forth. A problematic feature of this definition is its infinitary character: several paradoxical examples exist in the gametheoretic and epistemic logic literature, suggesting that the definition is at odds with our ordinary intuition concerning the amount of shared knowledge needed to attain common knowledge or to induce coordinated actions in a game. These examples include versions of the Conway Paradox, like the puzzle of Consecutive Numbers (van Ditmarsch & al. 2003), or the Electronic Mail Game (Rubinstein 1989), a variant of the Coordinated Attack Problem. The aim of the paper will be to discuss realistic models of common knowledge, namely models of common knowledge compatible with situations of bounded rationality. The paper will develop some aspects of a particular resourcesensitive Kripke semantics proposed in earlier work by Bonnay & Egré (2006), in which a notion of approximate common knowledge is formally defined. Three aspects of the logic will be more specifically examined: the way in which it formalizes Rubinstein's informal notion of "almost common knowledge"; the link of the approach with fixedpoint definitions of common knowledge; the integration of the two notions of "almost common knowledge" (effortless, intuitive) and "strict common knowledge" (demanding, computational) within the "twosystem" picture of the cognitive architecture proposed by Kahneman.
Patrick Girard (Stanford)
Ceteris Paribus Logic in Action
Ceteris paribus logic is a generalization of basic modal logic in which modalities are defined over the intersection of two relations: the accessibility relation and the modal equivalence with respect to a set of formulas. This generalization allows to express a strict sense of ceteris paribus, the “all other things being equal” vs “all other things being normal”. In this paper, I study the dynamification of ceteris paribus logic, and see how it behaves when actions such as public announcement are involved. I also investigate the role of the ceteris paribus in model change. One interpretation that is natural is that the accessibility relation is restricted according to an agenda (those things that have to stay equal), and our framework can introduce actions such as “adding A to the agenda”.
Andreas Herzig (LILaC, Toulouse)
Converse Actions and Action Models
(joint work with Guillaume Aucher, Toulouse)
Update logic as viewed by Baltag, Moss and Solecki (BMS) and Dynamic Doxastic Logic as viewed by Segerberg (DDL) both deal from a logical point of view with the same kind of phenomenon, namely the dynamics of beliefs. It makes sense to draw parallels between these two approaches. On the one hand, BMS introduces an action model as a syntactical object of the language, unlike DDL. On the other hand, by the very nature of DDL, one can easily introduce converse actions, unlike BMS. We will show that BMS can be translated into DDL thanks to this use of converse actions. They will indeed enable us to translate the structure of the action model directly within a particular axiomatization of DDL, without having to refer to a particular action model in the language (as it is done in BMS). This suggests that DDL is more expressive and general than BMS.
John Horty (Maryland)
Double Time References in the Evaluation of Actions
I define a rigorous theory of action, including group action, in the context of branching time. After introducing a notion of value into the framework, and after a brief detour through Aristotle's seabattle, I then show how the appeal to double time references resolves a problem that arises when we try to define the notion of a right action in an indeterministic setting. If time permits, I will explore some of the ramifications of this approach for the relation between right and wrong group and individual actions.
Ray Jennings and Kam Sing Leung (SimonFraser University)
Resituating Obligations
We present a deontic interpretation of JonssonTarski nary modal logics and demonstrate an embedding in Standard Deontic Logic. The translation illustrates a new, nonstatic understanding of obligation and of the consequences of unfulfilled obligations.
Eric Pacuit (Amsterdam)
Logics of Knowledge and Action for Social Software
The main intuition behind social software is that there is a close analogy between computer software and social procedures. For example, just as registers in a computer are continually updated as a program is executed, the information of each agent changes as a social procedure is executed. We discuss a number of logics for reasoning about social software.
Michel Paquette (Collège de Maisonneuve)
Coherent Deliberation and DecisionMaking
It is arguable that the process of deliberation in decisionmaking must obey various structural constraints in order to lead to rational choice. The principles of decision kinematics have been investigated by B. Skyrms and R. Jeffrey in terms of coherence constraints on the possible courses of evolution of the chooser’s probability and desirability functions. Coherence has also been investigated from the perspective of dynamic choice by T. Seidenfeld and E. McLennen. These investigations raise important and difficult questions. What should remain persistent and stable during deliberation? For instance, should we agree with Jeffrey that the desirability of an act must remain constant throughout deliberation in a genuine decision problem? In this paper, we review and discuss such requirements of coherence on desires and beliefs in deliberation with the aim of establishing the general principles of a basic logic of deliberation.
Rohit Parikh (Brooklyn College & CUNY Graduate Center)
Knowledge and Structure in Social Algorithms
The first third of the XXth century saw two important developments. One of these was Ramsey’s tracing of personal probabilities to an agent’s choices. This was a precursor to the work of de Finetti, von Neumann and Morgenstern, and Savage. The other one was Turing’s invention of the Turing machine and the formulation of the ChurchTuring thesis according to which all computable functions on natural numbers were recursive or Turing computable.
Game theory has depended heavily on the first of these developments, since of course von Neumann and Morgenstern can be regarded as the fathers of Game theory. But the other development has received less attention. This development led to the development and design of computers and also to fields like logic of programs, complexity theory and analysis of algorithms. It also resulted in much deeper understanding of algorithms, but only computer algorithms. Social algorithms remain largely unanalyzed except in special subfields like social choice theory or fair division [2]. These fields do not tend to analyze complex social algorithms as is done in computer science.
A later development, going back to the work of Hintikka, Lewis and a little later Aumann [3, 4, 1], brought in the issue of knowledge. The notion of common knowledge is of course very important for Aumann as common knowledge of rationality can be seen as a justification for backward induction arguments.
But knowledge too has received less attention than it might. We all know that the Plame affair had something to do with someone knowing something which they should not have, and someone revealing something which they should not have. But why should they not? Clearly because of certain possible consequences. Knowledge and knowledge transfer are ubiquitous in how social algorithms work.
We will try in this paper to bring attention to the importance of the two issues of
knowledge and logical structure of algorithms, and show the way to a broader arena in which game theorists might want to play. Hopefully, in fact almost certainly, there is a rich general theory to be developed.
References:
[1] R. Aumann, “Agreeing to disagree”, Annals of Statistics, 4 (1976) 12361239.
[2] Steven Brams and Alan Taylor, The WinWin Solution: guaranteeing fair shares to everybody, Norton 1999.
[3] Jaakko Hintikka, Knowledge and Belief: an introduction to the logic of the two notions, Cornell University press, 1962.
[4] D. Lewis, Convention, a Philosophical Study, Harvard U. Press, 1969.
Bryan Renne (CUNY Graduate Center)
Epistemic Updates in Justification Logics
Plato defined knowledge as justified, true belief. In our usual formalization of this definition, we take as belief Hintikka's notion: I believe a statement if that statement holds in all the possibilities relevant to my current situation. To combine Hintikkabelief with a notion of truth, we use Kripke semantics, which then leads us to our usual epistemic reading of multimodal logics. While this reading captures a notion of true belief in the sense just described, we see that it fails to capture justification, by the following considerations. Take the statement "if I know A, then I know B." This is a statement of conditional knowledge that says my knowledge of one fact follows from my knowledge of another; however, this statement fails to account for the reason why my knowledge of B follows from my knowledge of A  something we'd certainly like to account for if we are to say that we have captured a notion of justification.
Justification logics aim to remedy this difficulty by replacing the usual modals with formulalabeling terms that have a certain structure  a structure that mimics deduction within the system. In reading the termlabeled formulas as knowledge statements, we see that justification logics are logics of knowing for a reason: if t is a term and A a formula, then we read the new formula t:A as "A is known
for reason t." This gives us a notion of justification within the theory itself. Using a Kripkelike semantics, these logics then also capture true Hintikkabelief, and they hence handle all three components of Plato's definition.
In this talk, I will discuss recent work in updates for justification logics. In particular, I will focus on expressivity of the language when it is extended with various kinds of updates.
Hans Rott (Regensburg)
TwoDimensional Belief Change
The idea of twodimensional belief change operators is that a belief state is transformed in such a way that a sentence A (the input) gets accepted with at least the strength or certainty of a sentence B (the reference sentence). The input of such a transformation may alternatively be conceived as 'B ≤ A' ['B lessorequalto A'], making explicit that the model is basically one of preference change. The principal case is when B is a prior belief which is more strongly accepted than both A and notA, but the nonprincipal cases are interesting in their own right. Various twodimensional revision operators were studied by Cantwell (1997), Fermé and Rott (2003), and Rott (2007). Special choices of fixed input or reference sentences lead to some wellknown unary oparators of belief change. The talk gives an overview of several variants of twodimensional belief change and their representations. I argue that twodimensional belief change operators offer an interesting qualitative model with an expressive power 'between' (all too poor) unary operators and (all too demanding) quantitative models of belief change.
Olivier Roy (Amsterdam)
Deliberation and Updates of Plans (joint work with Martin van Hees, Groningen)
Given the important role that intentions and play in the way we make decisions, we would expect them to occupy a substantial place in any theory of action. Surprisingly enough, in what is perhaps the most influential theory of action, rational choice theory, explicit references is made to actions, strategies, information, outcomes and preferences, but not to intentions. This is not to say that no attention has been paid to the relation between rational choice and intentions. On the contrary, there is a rich philosophical literature on that topic, notably in the work of Michael Bratman. In this presentation, I will use tools developed in dynamic logic to study intentionbased deliberation within a rational choice theoretical framework.
Mehrnoosh Sadrzadeh (Southampton)
Epistemic Update: from Kripke to Algebra and Coalgebra
Hoare Logic and Dynamic Algebras of Pratt are logics originally developed to reason about dynamics of computer programs. Once enhances with further Epistemic modalities, they can also reason about knowledge of agents in multiagent systems. I present an algebraic model of this enhancement and argue that
it is more efficient in dealing with real life scenarios, where agents are not honest or perfect reasoners, than the usual Kripke style model of BaltagMossSolecki. I then show how looking at the algebra from a coalgebraic perspective provides us with modular ways of incorporating new features such as probabilistic knowledge and provides us with even more efficient proof techniques.
Darko Sarenac (Stanford University, IHUM)
Spatial Reasoning
In this paper, we use various techniques of modal logic and topology to devise a class of increasingly stronger logics of space. The underlying intuition is that for lots of applications spatial intuition and spatial reasoning seem basic. And this not
only in applications such as guiding robots or automated vehicles through real threedimensional space, but also for such diverse applications as reasoning about knowledge, processing and updating of information. The paper makes some initial steps in understanding the structure of space with efficient languages of modal logic, with an ultimate aim of applying them to cognitive settings.
Krister Segerberg (Uppsala)
Dynamic deontic logic?
The original AGM paradigm was inspired by philosophical questions concerning two different kinds of change: normative change (Alchourron) and belief change (Gärdenfors). Later developments have focussed almost exclusively on the latter topic, leading among other things to a new branch of modal logic called dynamic doxastic logic (DDL). In this talk I will focus on the former topic instead, and discuss what a dynamic deontic logic (D \Delta L) might look like.
Daniel Vanderveken (Université du Québec à TroisRivières)
On the Logic of Attitudes
Contemporary logic is confined to a few paradigmatic attitudes such as belief, knowledge, desire and intention. My purpose is to develop the logic of all propositional attitudes. I will recursively define the set of all modes of attitudes. As Descartes anticipated, the two primitive psychological modes are belief and desire. Other more complex modes are obtained by adding to them special cognitive and volitive ways, special conditions on the propositional content or special preparatory conditions.
I will define inductively conditions of possession and of satisfaction of all propositional attitudes. To that end, I will exploit a nonstandard predicative logic that distinguishes strictly equivalent propositions that do not have the same cognitive value. I will consider subjective as well as objective possibilities in order to account for the fact that human agents are not perfectly but only minimally rational. I will present an axiomatization of my logic of attitudes. I will also analyze the basic principles according to which agents dynamically revise their attitudes of any mode.
Audrey Yap (Victoria)
Product Update and Temporal Modalities
Dynamic epistemic logic allows us to model agents who learn new information about the world from events which they observe. In this paper, I add a backwardlooking modality to the dynamic language, to allow for our expressing statements about what an agent knew before an event took place. This allows us more completely to model what an agent learns from an event, since we can now talk about the difference in their knowledge before and after its occurrence. It is known that the addition of forwardlooking temporal modalities require restrictions, since allowing for infinite forward iteration causes undecidability. However, our product update models have only finite pasts, which makes backwardlooking modalities much more manageable. Yet they still allow for a rich increase in expressive power.



