{'fraction_non_alphanumeric': 0.056678116791270966, 'fraction_numerical': 0.005657708628005658, 'mean_word_length': 4.1226549359554925, 'pattern_counts': {'":': 2, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Conditional Doxastic Models: A Qualitative Approach to Dynamic Belief Revision

In this paper, we present a semantical approach to multi-agent belief revision and belief update. For this, we introduce relational structures called conditional doxastic models (CDM’s, for short). We show this setting to be equivalent to an epistemic version of the classical AGM Belief Revision theory. We present a logic of conditional beliefs that is complete w.r.t. CDM’s. Moving then to belief updates (sometimes called “dynamic” belief revision) induced by epistemic actions, we consider two particular cases: public announcements and private announcements to subgroups of agents. We show how the standard semantics for these types of updates can be appropriately modiﬁed in order to apply it to CDM’s, thus incorporating belief revision into our notion of update. We provide a complete axiomatization of the corresponding dynamic doxastic logics. As an application, we solve a “cheating version” of the Muddy Children Puzzle.


Introduction
Once upon a time there were three very wise children, playing in a garden, under the tall trees. Despite their father's warning, naughty Adam and Eve got mud on their foreheads, but obedient Mary stayed clean. Then the father came to them and said:"Behold, at least one of you is dirty".
The first goal is met by replacing the usual doxastic/epistemic Kripke models with semantic structures called "conditional doxastic models" (CDM's). It is important to note that our approach differs from the recent semantical literature on the topic of (dynamic or static) belief revision (e.g. [3,10,16,22,23]) in the following sense. Most Kripke-style models proposed for multi-agent belief revision are based on specific mechanisms that rely on quantitative notions, such as "degrees of belief", plausibility functions, graded models or probabilistic measures of belief. 5 However, classical (AGM) belief revision theory is a qualitative theory, based on simple postulates concerning a basic operation (revision), of great generality and simplicity. Our approach retains this qualitative flavor of the classical AGM theory.
It is true that we also give a Representation Theorem, showing that any CDM can be represented as arising from a (multi-agent) epistemic plausibility model (based on a family of "well-preorderings"). 6 Such models are closer to the ones encountered in the standard literature on belief revision, being a simple variation on a theme pursued first by Gardenfors (total preorders as plausibility relations) and later by Spohn [24] (ordinal-valued plausibility functions). However, the correspondence between CDM's and plausibility models is not one-to-one: the same CDM corresponds to many different plausibility models. This means that, if we take the conditional doxastic structure as fundamental, we can easily see that all the other above-mentioned descriptions are somewhat redundant by comparison: they include irrelevant features, such as specific ordinal assignments, or plausibility comparisons between states that are epistemically distinguishable. For this and other reasons 7 , we strongly prefer the qualitative description in terms of conditional doxastic maps, which can be seen as a natural extension of the standard definition of doxastic Kripke models, and which gives rise in a natural way to conditional belief operators, and thus to a conditional doxastic logic CDL. Indeed, the semantic structure of our CDM's matches perfectly the structure of our logic CDL, so that a complete axiomatization can be easily obtained by a simple modal translation of our semantic clauses.
In this sense, our approach is close to the one in Johan van Benthem's recent (unpublished) paper [27], of which we became aware only at a late stage of writing this paper. Though based on ("quantitative") models involving degrees of plausibility, the approach in [27] abstracts away from the details of modeling when considering the associated modal logic, which (is not based on any "graded belief" operator, as in e.g. [3,10], but) is a simple language of conditional beliefs and update modalities, virtually identical to ours (for public announcements). As a result, the main "reduction axiom" in [27], which computes (in the style of the Action-Knowledge Axiom in [6,5]) the conditional beliefs after a public announcement in terms of initial beliefs, 5 One could argue that the degrees of belief can be given by a plausibility order relation, so by a qualitative, order-theoretic notion, but in fact the way belief revision or update are defined makes an essential use of the "arithmetic" of these (finite or transfinite) degrees, e.g. in [24] and [3]; hence, the quantitative flavor. 6 This result can be seen as an analogue in our semantic context of Gardenfors' representation theorem in [12], representing the AGM revision operator in terms of the minimal valuations for some total preorder on valuations. 7 The notion of equivalence between models is sensitive to the choice of definition. We think that the "right" such notion for our logic is the natural concept of bisimilarity between CDM's. is identical to our corresponding axiom. In a sense, our approach here is simply to go one step further, and abstract away (from the specific details of a particular quantitative implementation of belief revision operators) on the semantic side as well. This leads to a perfect match between the syntax (based on conditional beliefs) and the semantics (in terms of conditional doxastic models), giving our logic a broader, more general scope of application and a greater transparency. In its turn, this greatly facilitates the move to more general contexts: one can easily produce in this way appropriate analogues of the reduction axioms for private announcements, and in fact (in unpublished work [8]) we obtain natural generalizations to the case of arbitrary epistemic/doxastic actions.
Our concepts of conditional belief and of CDM can also be seen in the context of the wide logical-philosophical literature on notions of conditional, see e.g. [1,25,19,18,9]. One can of course look at our conditional belief operators as nonclassical (and non-monotonic!) implications. Indeed, there have been various attempts and discussions concerning using conditionals to deal with belief revision (see e.g. [11,15,20]). We will show that our operators avoid the known paradoxes arising from such mixtures of conditional and belief revision, by failing to satisfy the so-called Ramsey test (except in absolute, unconditional contexts). Indeed, as argued in [27], the usual statement of the Ramsey test is based on a confusion between knowledge of a conditional with premise φ (or rather, between the "static" belief revision with φ, as captured by our hypothetical beliefs) and the knowledge/belief held after learning φ (i.e. the "dynamic" belief revision). The approach in [21] seems also to be closely related to ours: the "models" considered there for belief revision and belief update are of the same type (except for being single-agent) as our CDM's. They consider some natural semantic conditions, in correspondence with modal axioms, but they do not focus on the same set of postulates as us. 8 The plan of this paper is the following. In the next section we briefly review some basic notions about knowledge-belief (KB) models and doxastic-epistemic logic. In section 3, we "revise" the standard (syntactic) AGM revision theory, to make it applicable to a (multi-agent) epistemic/doxastic language, by considering revision of beliefs against a knowledge base; this imposes a weakening of the standard "Success" postulate. Then we convert the (revised) belief revision postulates into semantic clauses on KB models, obtaining a semantic counterpart of the (revised) AGM theory. In section 4, we define our central semantic notion, conditional doxastic models (CDM's), and we prove this setting to be actually equivalent (modulo the usual KB conditions) with the above-mentioned "semantic AGM" postulates. We also show this to be equivalent to a definition in terms of "well-preordered" plausibility relations. In section 5, we move to belief updates, by changing the usual semantics of public announcements to make them act on CDM's in the natural way, thus allowing beliefs to be "dynamically revised" when learning new information. In section 6, we extend this setting to private announcements to subgroups, we give a complete axiomatization (using "reduction axioms" in the style of [6,5,26,27], and then we apply this logic to the task of "saving Mary" from the cheaters, in the above Muddy-Children-type scenario.

Preliminaries: KB-Models and Belief-Knowledge Logic
A knowledge-belief frame (KB-frame for short, see e.g. [17], pg. 89) is a Kripke frame of the form (S, → a , ∼ a ) a∈A , with a given set of states S and two binary relations for each agent; the first relation ∼ a is meant to capture the knowledge of agent a, while the second → a captures his beliefs. A KB frame is required to satisfy the following natural conditions: (1) each ∼ a is reflexive: s ∼ a s; (2) if s ∼ a t then we have: s → a w iff t → a w, and also s ∼ a w iff t ∼ a w; (3) if s → a t then s ∼ a t ; (4) for every s ∈ S there exists some t ∈ S such that s → a t.
The first clause expresses the truthfulness of knowledge, the second expresses full introspection (an agent knows what he believes/knows and what not), the third says that agents believe everything they know, and the last (seriality) says that beliefs are consistent. A knowledge-belief model (KB-model) is a Kripke model having an underlying KB-frame.
By replacing the accessibility relations with their image-maps 9 , we obtain an equivalent definition of a more "coalgebraic" flavor: a KB-frame is a structure (S, • a , •(a)) a∈A , where S is a set of states and • a , •(a) : S → P(S) are maps satisfying the following conditions: (1) s ∈ s(a) ; (3) s a ⊆ s(a) (2) if t ∈ s(a), then s a = t a , s(a) = t(a) ; (4) s a = ∅. The maps • a and •(a) are called appearance maps: s a is the doxastic appearance of s to a (or the theory of a about s), and s(a) is the epistemic appearance of s to a (or the knowledge of a about s). The equivalence between the two definitions of knowledge-belief models is easily verified 10 .
Given a knowledge-belief model S, an S-proposition (or S-theory) is simply any set P ⊆ S of states in S. This is of course a purely extensional and semantical notion of proposition/theory, to be distinguished from the syntactical and intensional notions of "sentence" and "theory". For any S-proposition P and agent a ∈ A, we can define as usually the S-propositions B a P ("agent a believes P ") and K a P ("agent a knows P ") by the standard Kripke definitions of modalities (for the accessibility relations → a and ∼ a ). In terms of appearance maps, these definitions can be given in the form of Galois dualities (between appearance and knowledge/belief): s ∈ B a P iff s a ⊆ P s∈ K a P iff s(a) ⊆ P We can define operations on S-propositions: negation ¬P := S \ P , conjunction , and the opposite way by putting: s →a t iff t ∈ sa, and s ∼a t iff t ∈ s(a). P ∧ Q := P ∩ Q, general true belief EbP := a∈A B a P ("everybody believes P ") and general knowledge EkP := a∈A K a P . Finally, we define common true belief CbP := n≥0 (Eb) n P = P ∩ EbP ∩ Eb(EbP ) ∩ · · · and common knowledge CkP := The Belief-Knowledge Logic (BKL) is a logic whose syntax is given by: The semantics is given by the obvious compositional clauses: p is given by the valuation, ¬ϕ S := ¬ ϕ S etc. As standard, we also use the notation s |= S ϕ for s ∈ ϕ S . Observe that general belief and general knowledge are definable in BKL , by putting: Ebϕ := a∈A B a ϕ, Ekϕ := a∈A K a ϕ. Under various names, BKL is a well-known logic and its complete proof system, which we will also denote by BKL, is given by familiar axioms and rules, see e.g. [17] (pg. 94, where this proof system is called KL).

A semantic, multi-agent, epistemic AGM theory
Classical AGM theory. Classical belief revision takes a syntactic view of theories: we are given a family T of all "theories", whose members are assumed to be deductively closed sets of sentences (over some given language). Let ⊥ be the inconsistent theory (containing all sentences). The expansion T + ϕ of a theory T ∈ T with a sentence ϕ is defined as T + ϕ := {ψ : T ∪ {ϕ} ψ}. Now the belief revision operator * can be introduced by means of the standard AGM postulates: T * (ϕ ∧ ψ) = (T * ϕ) + ψ Revising the Revision Theory: epistemic AGM. In order to apply belief revision to theories in a doxastic-epistemic language, we need to revise the "Success" postulate (*5) in an obvious way, since agents' beliefs about their own beliefs or knowledge are certain, and thus they should not be revised. More generally, if something is "known", than it should not be subject to revision; or, in other words, any attempt to "revise" with a sentence whose negation is "known" should lead to a contradiction. This leads us to a "revision of this belief revision postulate", by replacing (*5) with its "epistemic version": This revised system, composed of postulates (*1), (*2), (*3-4), (*5e),(*6), (*7-8), is called epistemic AGM . If, as usually, we assume that knowledge satisfies the Necessitation rule (from ϕ infer Kϕ), then from this and (*5e) we obtain as a consequence the desirable half of (*5): if ¬ϕ then T * ϕ = ⊥. Multi-agent AGM. To apply the postulates to theories written in the logic BKL, we need a multi-agent version of Epistemic AGM. So we need to restate postulate (*5e) using the labelled operator K a , for all agents a. But in addition, observe that the notion of "theory" and the "revision" operation become relative to agents: a set of sentences might well be a possible theory for agent a, but not for an agent b. "Theories" in AGM are supposed to be complete descriptions of (the agent's) beliefs about the world. So, for example, a theory that leaves open the question whether K b p holds or not (for some given fact p) cannot ever be the (complete) theory describing agent b's beliefs (though it can perfectly well describe completely agent a's beliefs): due to introspection, b cannot be uncertain about his own knowledge.
So we need to assume as given, for each agent a, a family T a of "a-theories". We assume these to be deductively closed sets of sentences in the logic BKL; as pointed above, we also need to require a minimal notion of introspectiveness: an a-theory should settle all the questions concerning a's beliefs and knowledge. In addition, we want each revision operator * a to act on a-theories, and so to state the postulate (*5e), we need to require the inconsistent theory to be an a-theory.
So we formulate our revised multi-agent (epistemic) AGM postulates, by giving, for every agent a ∈ A: a family T a ⊆ P(BKL) of sets of sentences in the language BKL, called a-theories, and a belief revision operator * a : T a × BKL → T a , taking pairs of a-theories and BKL-sentences into new a-theories; and requiring them to satisfy the following conditions: (T1) ⊥ ∈ T a (where ⊥ := BKL is the inconsistent theory, containing all the sentences in BKL); (T2) every T ∈ T a is deductively closed, w.r.t. the complete proof system of BKL; (T3) for every ϕ ∈ BKL and every T ∈ T a , we have either K a ϕ ∈ T or (¬K a ϕ) ∈ T ; (T4) all the above postulates of epistemic AGM, in which we label with agent names both the knowledge K a and the revision * a operators. Observe that it is not necessary to require an introspective condition corresponding to (T3) for belief, since this follows from the above conditions, given the axioms of BKL. Indeed, one can easily prove that for every ϕ ∈ BKL and every T ∈ T a , we have either B a ϕ ∈ T or (¬B a ϕ) ∈ T . Semantic Belief Revision. To develop a semantical counterpart of multi-agent (epistemic) AGM, we assume as given a KB-model S. We need to replace in the above postulates the syntactic notion of a "theory" as set of sentences with the semantic notion of S-theory (i.e. set of states in S); similarly, we replace sentences by S-propositions (also set of states). Observe that each S-theory T ⊆ S gives rise to a syntactic theory th(T ) = {φ ∈ BKL : t |= S φ for all t ∈ T }. In addition to the above postulates, we have to make our belief revision theory consistent with our theory of beliefs (given by the model S): namely, we have to add a postulate (T0) requiring that, for each agent a, the agent's current beliefs form an a-theory. Finally, we need to replace the operation T + φ and the "deductive closure" of a theory with their semantic counterparts. To do this, observe first that the partial order on theories is inverted for semantic theories: for S-theories T, T ⊆ S we have T ⊆ T iff th(T ) ⊆ th(T ). The inconsistent theory ⊥ is now represented by the empty set of states ∅ ⊆ S. The deductive closure of the union of two syntactic theories corresponds to the intersection of the corresponding semantic theories (sets of states). Hence, expansion T + P of a semantic theory T ⊆ S with a semantic proposition P ⊆ S is simply given by the intersection T ∩ P . As a result, we obtain the following definition: Semantic Version of Epistemic AGM Postulates. Given a KB-model S, an AGM belief revision theory for S is defined by giving, for each agent a, a family of Stheories T a ⊆ P(S), called a-theories over S, and an operation * a : T a × P(S) → T a , such that for all T ∈ T a , P ⊆ S, we have: (T2) if T ∈ T a , then for all s, t ∈ T we have s a = t a and s(a) = t(a).
where we used the notation T (a) := {t(a) : t ∈ T }, to indicate the "knowledge of a in T ". Observe that, in fact, the above semantic version of the AGM postulate (*6) is superfluous: it is always trivially satisfied, due to the extensionality of S-theories.

Conditional Doxastic Models
We give now a setting that is equivalent to semantic (multi-agent epistemic) AGM, though it is much simpler in formulation. Namely, we enrich our knowledge-belief models to capture a notion of conditional belief. A conditional doxastic frame (CDframe, for short) (S, {• P a } a∈A,P ⊆S ) consists of a set of states S, together with a family of conditional (doxastic) appearance maps, one for each agent a and each possible condition P ⊆ S. These are required to satisfy the following conditions: A conditional doxastic model (CDM, for short) is a Kripke model whose underlying frame is a CD-frame. The conditional appearance s P a captures the way a state s appears to an agent a, given some additional (plausible, but not necessarily truthful) information P . More precisely: whenever s is the current state of the world, then after receiving new information P , agent a will come to believe that any of the states s ∈ s P a might have been the current state of the world (as it was before receiving information P ).
Using conditional doxastic appearance, the knowledge s(a) possessed by agent a about state s (i.e. the epistemic appearance of s) can be defined as the union of all conditional doxastic appearances. In other words, something is known iff it is believed in any conditions: s(a) := Q⊆S s Q a . Using this, we can see that the first condition above in the definition of conditional doxastic frames captures the truthfulness of knowledge. The second condition states the success of belief revision, when consistent with knowledge: if something is not known to be false, then it can be consistently entertained as a hypothesis. The third condition expresses full introspection of (conditional) beliefs: agents know their own conditional beliefs, so they cannot revise their beliefs about them. The fourth condition says hypotheses are hypothetically believed: when making a hypothesis, that hypothesis is taken to be true. The last condition describes minimality of revision: when faced with new information Q, agents keep as much as possible of their previous (conditional) beliefs s P a .
These requirements can be seen as strengthenings of the clauses defining a KBframe: indeed, every CD-frame is a KB-frame. To see this, it is enough to define s a := s S a , and check this satisfies all the KB assumptions. In other words: we can recover the unconditional ("default") beliefs as conditional beliefs with respect to some trivially true condition.
Alternatively, we can define a conditional doxastic frame relationally as a tuple then, for all every w ∈ S, we have: It is easy to see that the this definition of conditional doxastic frames is equivalent to the above one 11 .
Applying the standard Kripke relational definition of modalities to the conditional doxastic relations s P → a t, we obtain a new operator B P a on S-propositions, expressing conditional beliefs; in terms of appearance maps, the definition says that conditional belief is the Galois dual of conditional appearance: We read this as saying that agent a believes Q conditional of P . More precisely, this says that: if the agent would learn P , then (after learning) he would come to believe that Q was the case in the current state (before the learning). Notice that beliefs conditional to the trivially true proposition S coincide with the usual, unconditional beliefs: B S a Q = B a Q. As a consequence of the above postulates, the knowledge operator, defined (as in the previous section) as the Galois dual of epistemic appearance K a P := {s ∈ S : s(a) ⊆ P }, has the following property: We can also define conditional versions of general belief, common true belief, knowledge, general knowledge, common knowledge, by putting: Eb P Q := a∈A B P a Q, 11 In one way they are equivalent by putting , and in the opposite way by putting: s P →at iff t ∈ s P a .
Cb P Q := n≥0 (Eb P ) n Q = Q ∩ Eb P Q ∩ Eb P (Eb P )Q ∩ ..., K P a Q := K a (P → Q), Ek Q := a∈A K P a Q, Ck P Q := n≥0 (Ek P ) n Q

Theorem 4.1 A CDM is equivalent to a semantic AGM theory over a KB-model.
Proof. Given an AGM theory over a KB-model, we define s P a := s a * a P , and check this satisfies the clauses of a CDM. For the converse, start with a CDM, and put T a := {s P a : s ∈ S, P ⊆ S}. Define a revision operator T * a Q for our theories T = s P a ∈ T a , by cases: if we have P ∩ s(a) = ∅ (i.e. if s P a = ∅), then we put s P a * a Q := ∅ ; if we have P ∩ s(a) = ∅, but P ∩ Q ∩ s(a) = ∅, then put s P a * a Q := s Q a ; else, put s P a * a Q := s P ∩Q a = s P a ∩ Q = s Q a ∩ P . It is easy to check the KB conditions. 2 Examples of CDM's: Any KB-model is a CDM; indeed, we can trivially convert a KB-model into a CDM, by putting: s P a = s a ∩ P , whenever s a ∩ P = ∅, and s P a = s(a) ∩ P otherwise. Of course, this is only one way to organize a KB-model as a CDM, a very special case corresponding to the most trivial belief revision policy, encoded in the principle: "when your beliefs are contradicted by new facts, give them all up and stick with what you know". A more general example is given by: Plausibility Models: An epistemic plausibility frame is a structure (S, ∼ a , ≤ a ) a∈A , consisting of a set S endowed with a family of equivalence relations ∼ a and a family of "well-preorders" ≤ a , one for each agent a. Here, a "well-preorder" is just a preorder ≤ on S such that every subset has minimal elements; i.e. for every set T ⊆ S there exists t ∈ T such that t ≤ t for all t ∈ T . An epistemic plausibility frame together with a valuation gives an epistemic plausibility model. Plausibility frames for only one agent and without the epistemic relations have been used as models for AGM belief revision in [12,22] etc. A more concrete example of plausibility frames was given by W. Spohn in [24], in terms of ordinal preference maps assigning ordinals d(s) ("the degree of plausibility" of s) to each state s ∈ S. In our epistemic multi-agent context, this would give us structures consisting of a multi-agent knowledge frame (S, ∼ a ) a∈A , together with an ordinal plausibility map d a : S → Ord (where Ord is the family of all ordinals). Any epistemic plausibility model gives rise to a CDM, in a canonical way, by putting s P a := Min ≤a {t ∈ P : t ∼ a s} where Min ≤a T = {t ∈ T : t ≤ a t for all t ∈ T } is the set of minimal elements in T . We call this the canonical CDM associated to the given plausibility model. The converse is given by the following: . It is easy to check that this is an epistemic plausibility model, whose canonical CDM is S itself. 2 So our setting in terms of CDM's is equivalent to a more standard one in terms of plausibility models. Nevertheless, the proof of the above theorem shows the correspondence is not one-to-one 12 : the same CDM corresponds canonically to many plausibility models. In its turn, the same plausibility model corresponds to many Spohn-type models (in terms of plausibility degrees). In this paper, we take the conditional doxastic structure as fundamental, since we are interested in a logic of conditional beliefs. This means that, for our purposes, not only the actual assignment d a of ordinal degrees of plausibility, but even much of the induced structure of the plausibility relations ≤ a , is irrelevant: they contain superfluous features. The important thing are the corresponding conditional doxastic maps. Conditional Doxastic Logic (CDL). We now change BKL to a version in which belief operators are conditionalized. The syntax of CDL is given by: while the semantics is given by the obvious compositional clauses for the interpretation map • S : CDL → P(S) in a CDM S. In this logic, the knowledge modality can be defined as an abbreviation, putting K a φ := B ¬φ a ⊥ (where ⊥ = p ∧ ¬p is an inconsistent sentence), or equivalently K a φ := B ¬φ a φ. 13 It is easy to see that this agrees semantically with the previous definition of the semantic knowledge operator (as the Galois dual of epistemic appearance): K a φ S = K a φ S . We also define K θ a ϕ := K a (θ → ϕ), Eb θ ϕ := a∈A B θ a ϕ, Ek θ ϕ := a∈A K θ a ϕ.

Theorem 4.3
A sound and complete proof system for CDL is obtained as follows: first, include all the axioms and rules of classical propositional logic; second, include Necessitation Rules for all modalities: from ϕ infer B ψ a ϕ, Ckϕ and Cb ψ ϕ ; third, include the following axioms: Hypotheses are (hypothetically) accepted: B ϕ a ϕ Minimality of revision: Fixed-Point Axioms: Related to our topic are the standard philosophical problems of using conditionals in belief revision models (see for instance [11,15,20]). In this context, it is interesting to see how our conditional belief operators, understood as conditionals, can avoid Gardenfors' triviality result [11], which has been used to argue that standard AGM theory is incompatible with a conditional-based view of belief revision. This result was based on the assumption that any such conditional should satisfy the so-called Ramsey test [19]. Following [20], the Ramsey test can be stated in syntactic terms as saying that (R) "if P then Q" ∈ T iff Q ∈ T * P If we interpret the conditional "if P then Q" as our conditional belief B P a Q, interpret the revision operator as the operator * a defined above (in the proof of the theorem on the equivalence between CDM's and AGM theories over KB models), and interpret "theories" T to mean elements of T a in a CDM (as defined in the abovementioned proof, i.e. theories of the form T = s R a , for some proposition R), then we obtain the following semantic version of the Ramsey test: It is easy to check this is false: given our CDM postulates, the (R * )-test fails under this interpretation. To see this, observe that the left-hand side of (R * ?) is equivalent to ∀t ∈ s R a : t P a ⊆ Q. But, by our postulates, t ∈ s R a implies t P a = s P a = s a * a P . So, whenever s R a = ∅, the left-hand side of (R * ?) is simply equivalent to s a * a P ⊆ Q, which is in general not equivalent to the right-hand side s R a * a P ⊆ Q. So we see that the Ramsey test could only succeed if we had s a = s R a in general, i.e. if conditional beliefs would collapse to unconditional ones: this is in a way our own semantic version of Gardenfors' triviality result. On the other hand, observe that (R * ?) does hold in unconditional contexts, that is for R = S (i.e. for theories of the form T = s a ): s a ⊆ B P a Q iff s a * a P = s P a ⊆ Q. The deep flaw underlying the Ramsey test is that it treats hypothetical beliefs about beliefs in the same way as hypothetical beliefs about facts; the test would succeed only if, when making a hypothesis, agents would revise their beliefs about their own beliefs in the same way they revise their factual beliefs. But this is inconsistent with the restrictions posed by introspective knowledge to belief revision: introspective agents know their own beliefs, and so cannot accept hypotheses that go against this knowledge. A hypothetical belief system (e.g. the theory s R a in the above counterexample) may include different ontic statements than the unconditional belief system (s a ); but it includes precisely the same doxastic/epistemic statements B P a Q as this unconditional belief system. Due to introspection, beliefs about beliefs cannot be revised, not in the sense of ("static") belief revision that we have here. 14 Only a "dynamic" kind of belief revision (that aims to represent the revised beliefs of the agent about the situation after the revision) would satisfy some (suitably modified) Ramsey test.

Dynamic Belief Revision: Public Announcements
The belief revision encoded in the conditional doxastic models above is of a static, purely hypothetical, nature. Indeed, the revision operators cannot alter models in any way: all the possibilities are already there, so both the unconditional and the revised, conditional beliefs refer to the same world and the same moment in time. 15 In contrast, a belief update is a dynamic form of belief revision, meant to capture the actual change of beliefs induced by learning (or by other forms of epistemic/doxastic actions). As already noticed before [13,6,5], the original model does not usually include enough states to capture all the epistemic possibilities that arise in this way. So, contrary to the previous section, we now allow for belief revisions that change the original CDM. In this section we focus on public announcements, which change epistemic (and conditional doxastic) models in a minimal way: they can only shrink the model by "relativization" to a given sentence.
Given a model (CDM) S, denote by s Q a , . the appearance maps and valuation in S. For any S-proposition P ⊆ S, we define the relativized CDM P!(S) by taking: (i) the set of states of P!(S) is the set P , (ii) (s Q a ) P!(S) := s Q a , for every s ∈ P and Q ⊆ P , (iii) p P!(S) := p ∩ P .
As an immediate consequence, we get that unconditional beliefs after the update come from prior conditional beliefs: (s a ) P!(S) = (s P a ) P!(S) = s P a . We interpret the action P ! as a transition relation from any current state s ∈ S satisfying P to the state s ∈ P!(S). The syntax of our public announcement logic is obtained by simply adding constructs involving dynamic modalities < ϕ! > ϕ to the syntax of CDL. For the semantics we include the following extra clause: To obtain a sound and complete proof system, we add reduction axioms for public announcements to the axioms of CDL: 14 Remember that B P a Q means "if a would learn P , then he would come to believe that Q had been the case (before the learning)". Suppose you happen to believe ¬P , and somebody asks you: "If I was to tell you that P was the case, would that change your mind about the fact that you currently believe ¬P ?". Clearly, the correct answer is: "No, it wouldn't. It would indeed change my belief about P , but not my belief about the fact that now I believe ¬P ". 15 Indeed, the postulate (*2) (and the corresponding clause (4) in the definition of CD-frames) can only hold if a revision with so-called Moore sentences (e.g. ϕ ∧ ¬Kaϕ) is understood to be only hypothetically possible. The agent a's actual beliefs after learning such a sentence cannot possibly include the sentence itself.
where p's denote atomic sentences.

Private Announcements to subgroups
In this section we deal with the specific action of "privately learning a fact" or, more generally, a "private announcement P ! A to a subgroup of agents". The intuition is that the announcement is broadcasted to the agents of a group A, while the outsiders B ∈ A do not suspect this is happening. For simplicity, we consider here the case in which it is common knowledge that nothing else can happen: this particular announcement (of this particular sentence P to the group A) is the only message that may be broadcasted at this time; the only alternative is no message being sent, i.e. the silent action τ A P in which "nothing happens" (but in which the outsiders don't know this, so they think it is possible that the message P was in fact broadcasted to group A). Given a CDM S and an S-proposition P ⊆ S, we define the a new, updated CDM under private announcements P! A (S) as follows: for each of the old states s ∈ S we take two distinct new copies P ! A (s) (meant to denote the state after P was announced to the group A) and τ A P (s) (meant to denote the corresponding state in which nothing really happened, but the outsiders b ∈ A consider possible that P was announced to group A). Then the new model S is obtained by putting: (i) the new set of states of P! A (S) is the set S = P ! A (P ) ∪ τ A P (S) (ii) for all a ∈ A: P ! A (s) Q a := P ! A ( s where we used the notations σ(Q) := {σ(s) : s ∈ Q} and σ −1 (Q ) := {s ∈ S : σ(s) ∈ Q } for any of the two "actions" σ ∈ {P ! A , τ A P }, and for all sets Q ⊆ S, Q ⊆ S . We explain the clauses for conditional belief update. For clause 2: the insiders know in any case which action σ happened (be it P ! A or τ A P ), so if after that action they are given some new information Q they apply the following algorithm. They first reconsider their beliefs about the past states, in the view of the new information: they might have to revise these beliefs with the fact that, after this specific action happens, Q becomes true; so they revise their beliefs about the past state with σ −1 (Q); then they run back to present, by applying action σ to the states allowed by these past beliefs: this gives their current belief about the state of the world after the action σ. In clause 3, the outsiders apply essentially the same algorithm, but (not knowing which action really happens) they keep the default belief that what they see, that is action τ A P (i.e. "nothing"), is what is happening; so they apply the above algorithm only to action σ = τ A P ; unless this is contradicted by the new information Q, i.e. unless it is already known beforehand that Q cannot become true after τ A P ; in which case, they "revise their belief about the current action": they realize that P ! A is happening, so they apply the above algorithm to σ = P ! A .
For our syntax, we replace the public announcement modalities above < ϕ! > with dynamic modalities < ϕ! A > and < τ A ϕ > corresponding to the two types of action above. 16 The semantics is given by the standard PDL clause: < σ > ψ S := {s ∈ S : σ(s) exists and σ(s) ∈ ψ S }. To get a complete proof system, we replace the reduction axiom for conditional beliefs with the axioms: for all insiders a ∈ A and all outsiders b ∈ B. With these modifications, and by eliminating the axioms and rules referring to common knowledge and common belief, we obtain a sound and complete proof system for the logic of private announcements (without common knowledge/belief ). 17 And finally, here is the promised "dynamic analogue" of the Ramsey test (which is valid, unlike its static counterpart):

Back to Mary.
Having introduced these models, we return to the example presented in the introduction. So given Eve (e), Adam (a) and Mary (m), we denote the states in the initial model S by x = (x e , x a , x m ), with x e , x a , x m ∈ {0, 1} where 0 =clean and 1 =dirty. The epistemic uncertainty relation is clear: agents see each other but not themselves, so x(i) = {y ∈ S : y j = x j for all j = i}. We can convert this into a KB-model by e.g. assuming that agents start by being "cautious", i.e. believing only what they know. This sets x i = x(i). For conditional beliefs, we can use e.g. the "most trivial" belief revision policy (introduced in section 4): s P i = s i ∩ P , whenever s i ∩ P = ∅, and s P i = s(i) ∩ P otherwise. 18 Now, the real state of the world is w = (1, 1, 0). Mary's initial belief and knowledge is w m = w(m) = {(1, 1, 1), (1, 1, 0)}. After father's announcement, the state (0, 0, 0) is eliminated. Eve's peek in the mirror can be modeled as a private announcement γ = 1 e ! e to herself (where the atomic sentence 1 e indicates that Eve's forehead is dirty), and the alternative (no peeking) is denoted by τ := τ e 1 e . After that, in the resulting model S , Mary's knowledge is γ(w)(m) = {τ (1, 1, 1), τ(1, 1, 0), γ(1, 1, 1), γ(1, 1, 0)}, while her belief is γ(w) m = {τ (1, 1, 1), τ(1, 1, 0)}. But after Eve's public announcement (K e 1 e )!, the model shrinks to the set S := K e 1 e S = {γ(1, x a , x m ) : x a , x m ∈ {0, 1}}. Mary's unconditional beliefs after the public announcement are obtained using her prior conditional beliefs (γ(w) m ) S = γ(w) S m . To evaluate the last term we need to use the second case of clause 3 in the definition of private announcements (since we have w m ∩ τ −1 (S ) = ∅ ): (γ(w) m ) S = γ S m = γ( w γ −1 (S ) m ) = γ( w(m) ∩ γ −1 (S ) ) = γ( w(m) ) = {γ (1, 1, 1), γ(1, 1, 0)}. This is a non-empty set of possible states: so Mary is still sane! Moreover, all her possible states are outputs of the action γ: she knows that γ has happened. In other words: Mary discovers that cheating (γ) has taken place!

Conclusion
We have presented here a new, qualitative semantic implementation of the AGM belief revision theory, in terms of conditional doxastic models. Based on this, we proposed a revised semantics for public and private announcements, incorporating belief revision into the notion of update. This "Merciful Logic" solves problems such as the ones posed by the above cheating version of the Muddy Children Puzzle, preventing agents from going mad when their beliefs are invalidated.
The semantical structures used in this paper have an algebraic counterpart. In [7], a first attempt has been made to work out an algebraic setting for multiagent belief revision. In unpublished work [8], we generalize the present setting to allow other types of actions. More precisely, all epistemic action models in [6,4,5] can be conditionalized. The updated CDM's are actually the result of taking the "update product" (in a sense that refines the concept in [5]) of the initial conditional doxastic state model with a conditional doxastic action model. But the definition of the general update is rather complex and technical, and would require a lot of preparation and justification. To build a case for it, we chose for simplicity (and due to lack of space) to concentrate here on two very special cases, of great intuitive appeal. But the general picture can already be glimpsed from our example: looking back at Mary, Adam and Eve, it is obvious that when Mary revises her beliefs as part of the update with action (K e 1 e )!, she actually deduces that the cheating action γ = 1 e ! e has happened (instead of τ ); so she revises not only her static beliefs about propositions, but also her beliefs about actions.