--- title: "Belief Revision Operators with Varying Attitudes Towards Initial Beliefs" authors: - "Adrian Haret" - "Stefan Woltran" doi: "10.24963/ijcai.2019/239" url: "https://ijcai.org/proceedings/2019/239" pdf: "https://ijcai.org/proceedings/2019/0239.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "1726-1733" track: "Main track" keywords: - "Knowledge Representation and Reasoning: Reasoning about Knowlege and Belief" - "Knowledge Representation and Reasoning: Belief Change" --- # Belief Revision Operators with Varying Attitudes Towards Initial Beliefs Adrian Haret, Stefan Woltran *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1726-1733. DOI: [10.24963/ijcai.2019/239](https://doi.org/10.24963/ijcai.2019/239) ## Abstract Classical axiomatizations of belief revision include a postulate stating that if new information is consistent with initial beliefs, then revision amounts to simply adding the new information to the original knowledge base. This postulate assumes a conservative attitude towards initial beliefs, in the sense that an agent faced with the need to revise them will seek to preserve initial beliefs as much as possible. In this work we look at operators that can assume different attitudes towards original beliefs. We provide axiomatizations of these operators by varying the aforementioned postulate and obtain representation results that characterize the new types of operators using preorders on possible worlds. We also present concrete examples for each new type of operator, adapting notions from decision theory. ## Full text ## 1 Introduction Belief revision models rational changes of an agent's epistemic state triggered by the availability of new, trusted information. In the standard logical approach, an agent's epistemic state is represented by propositional formulas, while the standards of rationality a revision operator is expected to abide by are encoded as logical axioms [Alchourr´on et al., 1985; G¨ardenfors, 1988; Katsuno and Mendelzon, 1992; Ferm´e and Hansson, 2018]. Notably, the classical set of revision postulates turn out to define a class of operators that can be looked at in two ways: on the one hand as change, guided by logical postulates, of propositional theories in response to new data; and on the other hand as choice functions over possible worlds exploiting plausibility rankings over such interpretations. This correspondence tells us that an agent faced with revision of its initial beliefs acts as if it chooses from a set of feasible possible worlds the ones it considers most plausible. A distinguishing feature of revision operators, as typically axiomatized, is that they can be assumed to adopt a particular attitude towards initial beliefs, enforced through what are called the Inclusion and Vacuity postulates in the AGM formulation [Ferm´e and Hansson, 2018], or through a single postulate equivalent to their conjunction in the KM axiomatization [Katsuno and Mendelzon, 1992]. This attitude articulates the policy by which the agent's prior information behaves with respect to new data: thus, in the KM axiomatization, the postulate in question states that if new information µ is consistent with existing beliefs κ, then the result of revision is simply κ∧µ. In other words, the agent retains its initial beliefs and simply supplements them with the new item of information, if it can do so in a consistent way. This is in line with a view of revision where the information κ with which the agent starts off represents the possible worlds the agent finds most plausible, information not to be given up unless challenged by conflicting new data, and spells out a conservative attitude towards initial beliefs, guided by the desire to preserve them as much as possible. ∗Contact Author In the current work we view such a conservative attitude as one among many that an agent can have towards its initial beliefs. By varying the postulate responsible for enforcing this attitude we are able to axiomatize revision operators that embody a wider range of attitudes towards prior information, and characterize these operators in terms of the types of preorders they induce on the set of possible worlds. To illustrate these principles we provide concrete operators, constructed using two ingredients: a notion of distance between possible worlds and an aggregation function that ranks possible worlds depending on the initial beliefs. We also show, in each case, how these operators fit into the landscape of new postulates introduced. Without the theoretical apparatus of the new postulates, the concrete operators put forward would be merely classified as deviant, since they do not satisfy the traditional blend of Inclusion and Vacuity. But through the present analysis they can be viewed as encoding distinct and characterizable stances an agent can take towards its beliefs. Alternatives to the classical revision postulates have been considered since as far back as the original publications in the field [G¨ardenfors, 1988; Katsuno and Mendelzon, 1991; Herzig and Rifi, 1999]. However, we believe that a systematic analysis of the intuition underlying the KM postulate corresponding to Inclusion and Vacuity, as we perform here, sheds new light on familiar topics. ## 2 Preliminaries We assume a finite set P of propositional atoms, from which the set Prop of propositional formulas is generated using the usual propositional connectives. A propositional knowledge base κ is a finite set of propositional formulas, which we typically identify with the conjunction of its formulas ∧µ∈κ µ. The set of all propositional knowledge bases is 2Prop . The universe U is the set of all possible interpretations (also called possible worlds) for formulas in Prop. The models of a propositional formula µ are the interpretations which satisfy it, and we write [µ] (respectively, [κ]) for the set of models of µ (respectively, for ⋂µ∈κ [µ]). If there is no danger of ambiguity, we write models as words where the letters are the atoms assigned to true, e.g., {{a, b}, {b, c}} is written as {ab, bc}. For µ1, µ2 ∈ Prop, we say that µ1 entails µ2, written µ1 |= µ2, if [µ1] ⊆ [µ2], and that they are equivalent, written µ1 ≡ µ2, if [µ1] = [µ2]. A formula µ (a knowledge base κ) is consistent if [µ] ̸= ∅ ([κ] ̸= ∅), and complete if it has exactly one model. The set of consistent knowledge bases is 2Prop cons . If κ is a propositional knowledge base, then the dual κ of κ is obtained by replacing every literal appearing in κ with its negation. If w is an interpretation, the dual interpretation w is P \w. If W is a set of interpretations, its dual W is defined as {w | w ∈ W}. In Example 1 we obtain that [κ] = [κ]. Though we do not provide a formal proof, we mention here that this holds more generally, i.e., for any κ ∈ 2Prop , it holds that [κ] = [κ]. If M is a set, then Bin(M) is the set of binary relations on M. We write < for the strict part of ≤, i.e., x < x′ if x ≤ x′ and x′ ̸≤ x; moreover, x ≈ x′ if x ≤ x′ and x′ ≤ x. The ≤-minimal elements of Mwith respect to ≤ are defined as min≤M = {x ∈ M | ∄x′ ∈ M such that x′ < x}. An assignment from M1 to M2 is a function α: M1 → Bin(M2). We write ≤κ instead of α(κ) if there is no danger of ambiguity. If W is a set of interpretations, we denote by ϕW a propositional formula such that [ϕW] =W. ## 3 Revision: Axioms and Characterizations A propositional revision operator is a function ◦: 2Prop cons × Prop → Prop. The intention is that κ ◦ µ encodes changes brought to existing held beliefs κ such that new, trusted information µ is accepted. A sensible revision operator is expected to resolve inconsistencies between κ and µ and to satisfy certain rationality criteria, presented below. ## 3.1 Basic Postulates If κ, κ1, κ2 ∈ 2Prop cons and µ, µ1, µ2 ∈ Prop, we first single out a core set of axioms. Note that R2 as we write it does not coincide with the second KM postulate. The second KM postulate shows up in the latter part of this section. - (R1) κ ◦ µ |= µ. - (R2) If µ is consistent, then κ ◦ µ is consistent. - (R3) If κ1 ≡ κ2 and µ1 ≡ µ2, then κ1 ◦ µ1 ≡ κ2 ◦ µ2. - (R4) (κ ◦ µ1) ∧ µ2 |= κ ◦ (µ1 ∧ µ2). - (R5) If (κ◦µ1)∧µ2 is cons., then κ◦(µ1 ∧ µ2) |= (κ◦µ1)∧ µ2. Postulates R1-5 are part of the standard set of KM postulates [Katsuno and Mendelzon, 1992], saying that a revision operator incorporates new information µ (R1), returns a consistent output if µ is consistent (R2), performs its task irrespectively of how beliefs are written down (R3) and satisfies some coherence constraints when the revision formula is varied (R4-5). A revision operator is basic if it satisfies R1-5. Throughout the paper, we work only with basic operators. ## 3.2 Basic Assignments Reflection on postulates R1-5 reveals that an operator ◦ satisfying them chooses among models of µ and, in doing so, behaves as if it has preferences over units of information. Formally, this is cashed out by assigning to each consistent knowledge base κ in 2Prop cons a binary relation ≤κ on interpretations in U: to revise κ by µ, then, becomes equivalent to choosing the best models of µ in ≤κ. And, in the same way that revision operators are expected to satisfy a set of basic properties (postulates R1-5), rankings on U must satisfy a set of properties, to be introduced in the following, that are conducive to rational choice. For an assignment α: 2Prop cons → Bin(U), a revision operator ◦ and κ, κ1, κ2 ∈ 2Prop cons , w1,w2 ∈ U, we first consider the following properties: - (o1) ≤κ is reflexive. - (o2) ≤κ is transitive. - (o3) If κ1 ≡ κ2, then ≤κ1 =≤κ2 . - (o4) ≤κ is total. - (o5) [κ ◦ µ] =min≤κ [µ], for any propositional formula µ. An assignment is basic if it satisfies properties o1-4. Notice that properties o1-2 imply that ≤κ is a preorder on U. Adding property o4 makes ≤κ total, and o3 adds an independence of syntax aspect to the assignment. If, on top of this, ≤κ satisfies o5, we say that the assignment α represents the revision operator ◦ (and that ◦ is represented by α). The overloading of the term 'basic' is intentional: as Theorem 1 shows, properties o1-5 define a class of rankings on interpretations that fully characterize revision operators satisfying axioms R1-5. Theorem 1. A revision operator satisfies postulates R1-5 iff there exists an assignment α: 2Prop cons →U representing it such that, for any κ ∈ 2Prop cons , ≤κ satisfies properties o1-5. Proof. ("⇒") The proof amounts to checking, one by one, that axioms R1-5 are satisfied by operator ◦. The argument is not new, and can be extracted from classical works on the subject [Katsuno and Mendelzon, 1992]. ("⇐") If w1,. . . ,wn are interpretations, we write ϕ1,...,n for a propositional formula such that [ϕ1,...,n] = {w1, . . . , wn}. Assume, now, that we are given a revision operator ◦ that satisfies axioms R1-5. For any base κ and w1,w2 ∈ U, we define the assignment α: 2Prop cons → U by saying that w1≤κw2 if w1 ∈ [κ ◦ ϕ1,2]. We now show that ≤κ, thus defined, satisfies properties o1-5. Property o1 (reflexivity) follows using axioms R1 and R3. For property o2 (transitivity), take w1, w2 and w3 such that w1≤κw2 and w2≤κw3. First we show that w1 ∈ [κ ◦ ϕ1,2,3]. Notice that, by axioms R1 and R2, we have that ∅ ⊂ [κ ◦ ϕ1,2,3] ⊆ [ϕ1,2,3]. We now do a case analysis. Case 1. If w1 ∈ [κ ◦ ϕ1,2,3], the conclusion is immediate. Case 2. If w2 ∈ [κ◦ϕ1,2,3], then (κ◦ϕ1,2,3)∧ϕ1,2 is consistent. Using axioms R4-5 and R3, this implies that (κ ◦ ϕ1,2,3) ∧ ϕ1,2 ≡ κ ◦ (ϕ1,2,3 ∧ ϕ1,2) ≡ κ ◦ ϕ1,2. Since w1 ∈ [κ ◦ ϕ1,2] (because w1≤κw2), we have that w1 ∈ [κ ◦ ϕ1,2,3]. Case 3. If w3 ∈ [κ◦ϕ1,2,3], then (κ◦ϕ1,2,3)∧ϕ2,3 is consistent. Using axioms R4-5 and R3 again, we get that w2 ∈ [κ◦ϕ1,2,3]. Reproducing the reasoning from Case 2, we conclude that w1 ∈ [κ◦ϕ1,2,3]. Once we have that w1 ∈ [κ ◦ ϕ1,2,3], it follows that (κ ◦ ϕ1,2,3) ∧ ϕ1,3 is consistent. So, by axioms R4-5 and R3, we have that: (κ ◦ ϕ1,2,3) ∧ ϕ1,3 ≡ κ ◦ (ϕ1,2,3 ∧ ϕ1,3) ≡ κ ◦ ϕ1,3. Since w1 ∈ [κ ◦ ϕ1,2,3] and w1 ∈ [ϕ1,3], we conclude that w1 ∈ [κ ◦ ϕ1,3]. This implies that w1≤κw3. Property o3 follows from the fact that the definition of ≤κ does not depend in any way on the syntax of κ. Property o4 follows by axioms R1-2. For property o5, we show the double inclusion. ("⊆") Take w1 ∈ [κ ◦ µ], and w2 ∈ [µ]. We get that w1 ∈ [(κ◦µ)∧ϕ1,2] and, by axioms R4 and R3, it follows that w1 ∈ [κ ◦ (µ ∧ ϕ1,2)] and then that w1 ∈ [κ ◦ ϕ1,2]. Thus, w1≤κw2 and hence, w1 ∈ min≤κ [µ]. ("⊇") Take w1 ∈ min≤κ [µ] and suppose that w1 /∈ [κ◦µ]. Since it follows that µ is consistent, we have, by axioms R1-2, that there exists w2 ∈ [κ ◦ µ]. By axiom R5, we have that (κ ◦ µ) ∧ ϕ1,2 |= κ ◦ (µ ∧ϕ1,2). By axiom R3, we have that κ ◦ (µ ∧ ϕ1,2) ≡ κ ◦ ϕ1,2. Since w1 /∈ [κ ◦ µ], it follows that w1 /∈ [κ ◦ ϕ1,2], and hence w2 <κ w1. But we also have that w1 ∈ min≤κ [µ], implying that w1≤κw2, which is a contradiction. Theorem 1 tells us that an agent revising beliefs along the lines of postulates R1-5 behaves as if it ranks interpretations in U in a total preorder ≤κ that depends on initial beliefs κ, and always picks the minimal models of µ according to ≤κ. Such an agent, then, behaves like a rational agent, in the sense of rational choice theory [Sen, 1984; French, 1988], choosing the best elements from a given menu of options: the menu, here, would be the models of µ, i.e., the possible worlds the agent is allowed to believe in light of new information, while the best elements are decided with reference to ≤κ. Thus, a revision operator can be seen as a choice function over sets of interpretations: accordingly, Theorem 1 aligns with standard choice theoretic results [Arrow, 1959; Sen, 1984; Moulin, 1991]. That a similar mathematical formalism underlies both belief revision and rational choice is, by itself, not a new insight, the topic having been studied under various guises [Rott, 2001; Bonanno, 2009]. The main difference is one of interpretation, with ≤κ usually thought of in revision as a plausibility ranking, i.e., the agent's assessment as to which possible worlds are more or less plausible. Example 2. A doctor knows that the patient has been diagnosed with asthma (a), finds out that the patient is suffering from shortness of breath (b) and infers that chest pain (c) is also present: the two often go together in asthma, and such stereotypical examples are more salient in the doctor's mind than less frequent, more exotic examples. In other words, the doctor has initial information κ = a and a plausibility ranking ≤κ over possible worlds (with respect to the alphabet P = {a, b, c}) depicted in Figure 1. The doctor then revises by µ = b and settles on a possible state of affairs that Figure 1: Revision scenario of Example 2, showing the relevant section of the preorder ≤κ on the basis of which the revision result is constructed: only models of µ = b are depicted; the models of κ among this set are highlighted in grey. is most plausible according to their plausibility ranking ≤κ, i.e., [κ◦µ] = min≤κ [µ] = {abc}. Note that the doctor, in this case, takes the situation represented by a ∧ b ∧ c to be more likely than a ∧ b ∧ ¬c. One way of thinking of postulates R1-5 is that they axiomatize total preorders on interpretations. These preorders nominally depend on κ, but nothing in postulates R1-5 touches on how models of κ should influence these preorders. In other words, there is as yet no information about the attitude of an agent towards its initial epistemic state, and postulates R1-5 are consistent with arbitrary attitudes towards κ. How should the models of κ stand in relation to all other interpretations? Example 2 offers a glimpse into one possible answer: the agent starts off with some information κ and differentiates among possible worlds consistent with κ: some of these worlds are more plausible than others, perhaps as a result of being more salient, or because of a systematic bias [Kahneman et al., 1982]. Still, as a whole, models of κ are more plausible than any other interpretations consistent with the new information µ. In other words, the agent is biased towards the possible worlds consistent with κ. Are there, now, other ways of arranging the models of κ in ≤κ, ways that span the space of possible such attitudes? We study this question through the lens of additional axioms. ## 3.3 Attitudes Towards Initial Beliefs If κ, κ′ ∈ 2Prop cons , µ ∈ Prop, consider the following postulates: - (R6) If κ ∧ µ is consistent, then κ ∧ µ |= κ ◦ µ. - (R7) If κ ∧ µ is consistent, then κ ◦ µ |= κ ∧ µ. - (R8) If κ ◦ µ |= κ, then κ ◦ µ ≡ µ. - (R9) If µ ̸|= κ, then (κ ◦ µ) ∧ κ is inconsistent. - (R10) If κ′ is complete and κ′ |= κ◦µ, then κ′ |= (κ ∨ κ′ )◦µ. Each of these postulates encodes a particular type of attitude towards initial beliefs, and they are intended to be thought of in conjunction with the basic set of postulates R1-5. Some clarification is in order. Postulate R6 models an agent that incorporates all information in κ ∧ µ, and possibly extends this to cover more ground. Postulate R7 models an agent that reserves the right to drop information from κ if it so sees fit, even if that information is consistent with µ: we may imagine this is done on the basis of certain preferences over the information encoded by κ, i.e., the agent is partial towards certain parts of κ to the detriment of others. Taken together, postulates R6-7 imply that κ ◦ µ is equivalent to κ ∧ µ, when κ ∧ µ is consistent. This property models an agent who wants to preserve as much of κ as it can, and does not have any bias towards either of the models of κ. Postulate R6 can be equated with the Inclusion postulate in the AGM formulation and R7 corresponds to Vacuity [Ferm´e and Hansson, 2018], while in the KM axiomatization R6 and R7 are packaged together in one postulate (i.e., KM postulate R2) and presented alongside R1-5 as the default set of rational properties for revision [Katsuno and Mendelzon, 1992]. Postulates R8-9 focus on the dual knowledge base κ obtained by replacing every literal in κ with its negated version. If κ is a conjunction of literals, or if it is a complete (i.e., with exactly one model) formula, then κ will be a formula whose models are complements of the models of κ. Example 3. If P = {a, b, c} and κ = {a∧b} is a knowledge base over the alphabet P, then κ = {¬a ∧ ¬b}, and we have that [κ] = {ab, abc}, while [κ] = {∅, c} Thus, if κ is very specific (e.g., is a conjunction of literals), then κ can be thought of as the point of view opposite to that of κ, and situations can be imagined in which it is desirable to put bounds on the revision function in terms of how it treats information encoded by κ. This is the case if the agent has, or is required to have, a definite opinion on every item from an agenda, as is typically the case in Judgment Aggregation [Endriss, 2016]; if κ is a 'vivid' knowledge base [Levesque, 1986]; or, if it encodes something like an agent's preferred bundle from a set of available items. In all these cases κ can be required to be a conjunction of literals or a complete formula. Postulate R8 says that if κ undergoes revision by a formula µ embodying such an adverse perspective, then the agent must adopt µ: in other words, the agent has no room for maneuvering towards a more amenable middle ground. Such a revision policy makes more sense when considered alongside postulate R9, which specifies that if the agent has the option of believing states of affairs not compatible with κ, it should wholeheartedly adopt those as the most plausible stance. Taken together, postulates R8-9 inform the agent to believe states of affairs compatible with κ only if it has no other choice in the matter: the models of κ should be part of a viewpoint one is willing to accept only as a last resort. Postulate R10 is best understood through an example. Example 4. An agent intends to go to an art museum, the beach and a concert, i.e., κ = {a ∧ b ∧ c}, with P = {a, b, c}. The agent then learns that it only has time for one of these activities and chooses the art museum, i.e., κ◦µ ≡ a∧¬b∧¬c. If the agent's initial intentions were less specific, for instance that it would either go to all three places or only to the art museum (i.e., κ = {(a∧b∧c)∨(a∧¬b∧¬c)}), then, faced with the same new information µ, a ∧ ¬b ∧ ¬c should still feature as one of its most preferred options. A clearer view of postulates R6-10 emerges when looking at how they situate the models of κ in a total preorder ≤κ, for κ, κ′ ∈ 2Prop cons , w1,w2,w′ ∈ U: - (o6) If w1 ∈ [κ], then w1≤κw2. - (o7) If w1 ∈ [κ] and w2 /∈ [κ], then w1<κw2. - (o8) If w1 ∈ [κ], then w2≤κw1. Properties o6-10 turn out to characterize axioms R6-10 on the semantic level, as per the following representation result. Theorem 2. If ◦ is a basic revision operator and α: 2Prop cons → U is a basic assignment that represents it, then, for any κ ∈ 2Prop cons and µ ∈ Prop, the following equivalences hold: - (1) ◦ satisfies axiom R6 iff ≤κ satisfies property o6; - (2) ◦ satisfies axiom R7 iff ≤κ satisfies property o7; - (3) ◦ satisfies axiom R8 iff ≤κ satisfies property o8; - (4) ◦ satisfies axiom R9 iff ≤κ satisfies property o9; - (5) ◦ satisfies axiom R10 iff ≤κ satisfies property o10. Proof. Recall that we denote by ϕ1,2 a propositional formula such that [ϕ1,2] = {w1,w2}. For equivalence 1, we show each direction in turn. ("⇒") Take an assignment α satisfying property o6, and the revision operator ◦ represented by it. We assume that κ ∧ µ is consistent, and show that for any w ∈ [κ ∧ µ], it holds that w ∈ [κ ◦ µ] as well. By property o5, this is equivalent to showing that w ∈ min≤κ [µ]. Take w′ ∈ [µ]. Since w ∈ [κ], we can apply property o6 to get that w≤κw′ . Hence w ∈ min≤κ [µ]. ("⇐") Take a basic revision operator ◦ satisfying R6. and the assignment α which represents it. To show that ≤κ satisfies property o6, take two interpretations w1 and w2 such that w1 ∈ [κ]. Then, by axiom R6, we have that κ ∧ ϕ1,2 |= κ ◦ ϕ1,2. By property o5, it holds that [κ ◦ ϕ1,2] = min≤κ [ϕ1,2] and, since w1 ∈ [κ ∧ ϕ1,2], it follows that w1 ∈ min≤κ [ϕ1,2]. Thus, w1≤κw2. Equivalence 2 uses similar reasoning, and equivalences 3 and 4 are analogous to 1 and 2, respectively. For equivalence 5, assume first that axiom R10 holds, and take interpretations w and w′ and a knowledge base κ′ such that w′≤κw and [κ′ ] = {w′ }. To show that w′ ≤κ∨κ′ w, we must show that w′ ∈ [(κ ∨ κ′ ) ◦ ϕw,w′ ], where ϕw,w′ is a formula such that [ϕw,w′ ] = {w,w′ }. This follows immediately by applying axiom R10. Conversely, suppose [κ′ ] = {w′ }, and take w ∈ [κ ◦ µ]. Then, we get that w′≤κw, and we can apply property o10 to derive the conclusion. Theorem 2 is better understood through an illustration of how such preorders treat models of κ. Property o6 says that models of κ are minimal elements in κ, i.e., the agent considers possible worlds satisfying its beliefs among the most plausible possible worlds, though possibly not uniquely so (Figure 2-(a)). Property o7 states that there are no counter-models of κ more plausible than the models of κ, but the models of κ themselves may not be equally plausible (Figure 2-(b)). Properties o8-9 say that models of the dual knowledge base κ are the least plausible interpretations in ≤κ (Figure 2-(c,d)), while property o10 says that if w′ is more plausible than w when the initial beliefs are κ, then w′ would still be more plausible than w if it were part of the initial beliefs (Figure 2-(e)). Together, properties o1-7 define what is more commonly known as a faithful assignment, placing all and only models of κ on the lowest level of ≤κ. This corresponds to an agent that holds its initial beliefs to be the most plausible states of affairs [Katsuno and Mendelzon, 1992]. Consequently, Theorem 1 plus equivalences 1-2 from Theorem 2 make up the classical representation result for belief revision operators [Katsuno and Mendelzon, 1992]. Here we have opted for a more fine-grained approach to the placement of models of κ in ≤κ, which allows a more diverse representation of the different types of attitudes an agent can have towards initial beliefs. Though operators that do not satisfy the classical KM postulate R2 have been considered before [Ryan, 1996; Benferhat et al., 2005], the idea that such deviations correspond to possible epistemic attitudes and can be axiomatized is, to the best of our knowledge, new. Figure 2: Schematic view of prototypical preorders satisfying each of the properties o6-10; models of κ are in the light gray area, models of κ are in the dark gray area. ![Image](https://ijcai.org/proceedings/2019/fulltext/239/image_000000_1bc6ba61f1727c42c35ae9de5915096dfc24a44b21065e72c23977bad3d74010.png) ## 3.4 Indifference to Already Held Beliefs One particular consequence of weakening the KM axiom R2 (axioms R6-7 in the current context) is that the following property is not guaranteed to hold anymore: This property, called here RIDF (for indifference to already held beliefs), says that revising with information the agent already believes does not change the agent's epistemic state. More generally, the KM standard set of postulates implies that revising by any formula µ such that κ |= µ results in κ. It quickly becomes apparent that axiom R6 implies RIDF, 1 but R7 does not. Thus, if an agent is allowed to rank models of κ unequally, then RIDF is not guaranteed to hold. Example 5. If P = {a, b}, take κ = {a ∨ b} and a revision operator that satisfies axiom R7, and which orders interpretations as follows: a ≈κ b <κ ab <κ ∅. We get that [κ ◦ κ] = {a, b}, i.e., κ ◦ κ ≡ (a ↔ ¬b) ̸≡ κ. This points to a more graded view of what it means to believe κ. Thus, an agent might have a certain threshold of plausibility, along the lines of what is known in epistemology as the Lockean thesis [Foley, 1993], according to which it calibrates its beliefs: anything above the threshold counts as part of the belief κ and anything below counts as disbelief. This fits with the idea that an agent might assign different degrees of plausibility to states of affairs consistent with its belief κ: indeed, this is the point of view we endorse here, in contrast to more standard approaches, which consider that an agent assigns equal degrees of plausibility to all items of its belief. Thus, incoming information that confirms an agent's belief might have the effect of reinforcing parts that are given more plausibility at the expense of parts that are given less, and this is the kind of situation we take to be modeled by Example 5. 1 The converse is not true: RIDF enforces only that models of κ are equally plausible, but not where they are placed in ≤κ. What would be worrying would be a revision policy that makes an agent cycle between different viewpoints when confronted repeatedly with the same type of information: we will see that for revision operators satisfying R7 this concern is unwarranted, but we must first introduce some new notation. We write κi for the knowledge base obtained by revising κ by itself an i number of times. Thus, κ0 = κ and κi+1 = κi ◦ κ. Consider now the following property: (RSTB) There is n ≥ 1 such that κm ≡ κn , for every m ≥ n. A revision operator ◦ is stable if it satisfies property RSTB. Stability implies that repeated revision by κ ultimately settles (or stabilizes) on a set of models that does not change through subsequent revisions by κ. The following result proves relevant to the issue of stability. Proposition 3. If a revision operator ◦ satisfies axioms R1 and R7, then κi+1 |= κi . Proof. By axiom R1, we have that κ ◦ κ |= κ, and thus κ1 |= κ0 . Applying axiom R7, we have that (κ ◦ κ) ◦ κ |= (κ ◦ κ) ∧ κ |= κ ◦ κ. Thus, κ2 |= κ1 , and it is straightforward to see how this argument is iterated to get the conclusion. If the operator ◦ also satisfies axiom R2 (which, here, says that if the revision formula is consistent, then the revision result is also consistent), it follows that if κ is consistent, then κi is consistent, for any i ≥ 0. Thus, combining this fact and Proposition 3, we get that repeated revision by κ leads to a chain of ever more specific knowledge bases, i.e., ∅ ⊂ · · · ⊆ [κi+1 ] ⊆ [κi ] ⊆ · · · ⊆ [κ0 ]. Since a knowledge base has a finite number of models, it falls out immediately from this that there must be a point at which further revision by κ does not change anything. Corollary 4. A basic revision operator ◦ satisfying axiom R7 is stable. Unfortunately, axioms R8-9 do not guarantee stability. Since these axioms require only that the agent places the models of κ as the least plausible interpretations, it becomes possible that an agent's plausibility ranking does not hold on to a core set of interpretations through successive revisions by κ. Example 6. If P = {a, b}, take κ = {¬b} and a revision operator satisfying R8-9, which orders interpretations as shown in Figure 3. We have that [κ0 ] = [κ] = {∅, a}, [κ1 ] = [κ◦κ] = {a}, and [κ2 ] = [κ1 ◦κ] = {∅}. By R3, subsequent revisions by κ cycle between {a} and {∅} ([κ3 ] = {a}, [κ4 ] = {∅}), thus never settling on a stable answer. The issue of stability suggests another dimension along which revision operators can be analyzed, with Corollary 4 and Example 6 showing that a revision operator does not satisfy it trivially. Example 6, in particular, shows that there is interplay between ≤κ and ≤κ′ , if κ′ |= κ, which is relevant to the question of whether an operator is stable. This interplay is reminiscent of topics like iterated revision and kinetic consistency [Darwiche and Pearl, 1997; Peppas and Williams, 2016], but pursuing it further would take us too far afield of the aims of the current work. Figure 3: Repeated revision by κ cycles between {a} and {∅}. ![Image](https://ijcai.org/proceedings/2019/fulltext/239/image_000001_dd1a20d5bbc65c63aa21bfd3b5725038ade3bf70232927fc89080740fa01ed2a.png) ## 4 Concrete Operators with Varying Attitudes We now ask: what is a natural way to construct operators with such varying attitudes towards initial information? Our answer builds on ideas found in belief merging [Konieczny et al., 2004; Konieczny and P´erez, 2011], i.e., it defines rankings on interpretations by appeal to two main ingredients. The first is a distance d : U × U → R≥0 between interpretations, defined such that d(w1,w2) = 0 iff w1 = w2 and d(w1,w2) = d(w2,w1). Given w ∈ U and κ ∈ 2Prop cons such that [κ] = {w1, . . . , wn}, the vector of distances from w to κ is d(w, κ) = (d(w, w1), . . . , d(w, wn)). For brevity we will omit commas and simply write d(w, κ) as a string of numbers. We recall two prominent examples of distance: drastic distance dD works by the all-or-nothing rule: dD(w1, w2) = 0 if w1 = w2, and 1 otherwise; Hamming distance dH, counts the number of atoms on which two interpretations differ. The second ingredient is an aggregation function (more precisely, a family of functions) f : Rn → R, for n ∈ N, mapping a distance vector d(w, κ) to a number, and used to compare distance vectors. We write ----→ d(w, κ) and ←---- d(w, κ) for the vectors of distances from w to κ ordered in ascending order and descending order, respectively. The lexicographic order between two vectors is denoted by ≤lex. The minimal and maximal elements of d(w, κ) are min d(w, κ) and max d(w, κ), respectively, and ∑ d(w, κ) = ∑wi∈[κ] d(w, wi). The centrality of w with respect to κ is cen(w, κ) = max d(w, κ) - mind(w, κ). The displacement of w with respect to κ is dis(w, κ) = min d(w, κ) -min d(w∗ , κ), where w∗ is an interpretation such that mind(w∗ , κ) is minimal among all the interpretations w′ for which cen(w′ , κ) = cen(w, κ). Finally, the agreeability index of w with respect to κ is agr(w, κ) = min{mind(w, κ), cen(w, κ) + dis(w, κ)}, while the disagreeability index of w with respect to κ is dagr(w, κ) = n - agr(w, κ), where n = |P|. Given a distance d between interpretations and aggregation function f, we write ≤d, f κ for the ranking generated using d and f, and ◦d, f for the revision operator represented by the assignment generated using d and f, i.e., [κ ◦d, f µ] = min≤d, f κ [µ]. We then define the following types of rankings: Table 1: Table of Hamming distances for κ from Example 7 | | ∅ | a | b | abc | -----→ dH(w, κ) | ←----- dH(w, κ) | min | max | ∑ | |-----|-----|-----|-----|-------|-------------------|-------------------|-------|-------|-----| | ∅ | 0 | 1 | 1 | 3 | (0113) | (3110) | 0 | 3 | 5 | | a | 1 | 0 | 2 | 2 | (0122) | (2210) | 0 | 2 | 5 | | b | 1 | 2 | 0 | 2 | (0122) | (2210) | 0 | 2 | 5 | | c | 1 | 2 | 2 | 2 | (1222) | (2221) | 1 | 2 | 7 | | ab | 2 | 1 | 1 | 1 | (1112) | (2111) | 1 | 2 | 5 | | ac | 2 | 1 | 3 | 1 | (1123) | (3211) | 1 | 3 | 7 | | bc | 2 | 3 | 1 | 1 | (1123) | (3211) | 1 | 3 | 7 | | abc | 3 | 2 | 2 | 0 | (0223) | (3220) | 0 | 3 | 7 | Example 7. If P = {a, b, c}, take κ = {(¬(a ∧ b) ∧ ¬c) ∨ (a ∧ b ∧ c)}, for which we get that [κ] = {∅, a, b, abc}. For the interpretation w = ∅, we get that -----→ dH(w, κ) = (0113), ←----- dH(w, κ) = (3110), min dH(w, κ) = 0, max dH(w, κ) = 3 and ∑ dH(w, κ) = 5. The distances and aggregated distances for each interpretation are depicted in Table 1. Notice how the models of κ are distributed when the interpretations are ranked according to the different aggregation functions used: we have ∅≈H, min κ a, since mindH(∅, κ) = mindH(a, κ) = 0, but ∅<H, lmin κ a, since (0113) ≤lex (0122). Also, we have that c<H, max κ abc, c<H, lmax κ abc and ab<H, sum κ abc, i.e., models of κ are not minimal in ≤H,max κ , ≤H, lmax κ and ≤H, sum κ . In particular, ≤H, max κ makes the models of κ (i.e., abc, bc, ac and ∅) the least plausible interpretations. The agreement and disagreement operators (◦d, agr and ◦d, dagr ) are simpler than they appear: the idea behind ◦d, agr is to allow interpretations other than the models of κ as the minimal elements of the preorder ≤κ. Notice that the score of an interpretation in ≤d, agr κ is 0 if it is either a model of κ, or it is equidistant from every model of κ (i.e., its centrality is 0) and it is the 'closest' interpretation to κ with this property. The disagreement operator ◦d, dagr works in similar fashion, by making models of κ and interpretations minimally equidistant to them the least plausible interpretations in ≤d, dagr κ . Example 8. If P = {a, b, c}, take κ such that [κ] = {a, b, c}, and notice that dH(∅, κ) = (111) and dH(abc, κ) = (222), i.e., they are both equidistant to κ, hence their centrality is 0. However, ∅ is closer to κ than abc (its displacement is 0, compared to abc's displacement of 1), and agr(∅, κ) = 0. Thus, what ≤H, agr κ does is to give a minimal score to models of κ and to the minimally equidistant interpretation ∅. By contrast, ≤H, dagr κ gives a maximal score to the models of κ and to the maximally equidistant interpretation abc. All operators proposed generate a total preorder ≤κ over interpretations, but differ in how they arrange models of κ in ≤κ: this corresponds to the different attitudes an agent can have towards κ prior to any revision. The operator ◦H,min , known as Dalal's operator [Dalal, 1988], considers all models of κ as the most plausible elements in ≤κ and is the only operator for which κ ◦ µ is equivalent to κ ∧ µ when κ ∧ µ is consistent. Similarly, ◦H, lmin also ranks models of κ as more plausible than any other interpretation, but discriminates among models of κ. The operators ≤H, max κ and ≤H, lmax κ push away models of κ, under the assumption that they are the most implausible possible worlds. They difference between them is that ≤H,max κ considers models of κ equally implausible, whereas ≤H, lmax κ uses the more fine-grained lexicographic approach. The operator ◦H, agr makes models of κ the most plausible elements in ≤κ but also allows other interpretations on that position, in particular certain interpretations that are equidistant to κ as per Example 8. The intuition is that an interpretation equally distanced from models of κ is like a compromise point of view, with good chances of being correct if it is close to κ. The operator ◦H, dagr is the dual of ◦H, agr and, finally, operator ◦H, sum evokes utilitarian approaches by choosing interpretations that minimize the sum of the distances to each model of κ. Table 2: Satisfaction of axioms | | R6 | R7 | R8 | R9 | R10 | RIDF | RSTB | |----------|------|------|------|------|-------|--------|--------| | ◦H,min | ✓ | ✓ | × | × | ✓ | ✓ | ✓ | | ◦H, lmin | × | ✓ | × | × | ✓ | × | ✓ | | ◦H, agr | ✓ | × | × | × | ✓ | ✓ | ✓ | | ◦H,max | × | × | ✓ | ✓ | × | × | ✓ | | ◦H, lmax | × | × | × | ✓ | × | × | ✓ | | ◦H, dagr | × | × | ✓ | × | × | ✓ | ✓ | | ◦H, sum | × | × | × | × | ✓ | × | ✓ | | ◦dr | ✓ | ✓ | × | × | ✓ | ✓ | ✓ | | ◦fg | ✓ | × | ✓ | × | ✓ | ✓ | ✓ | Quick reflection shows that operators obtained with drastic distance dD collapse into two main categories. To get a grasp on this fact, consider first the drastic revision operator ◦dr defined, for κ ∈ 2Prop cons and µ ∈ Prop, as κ ◦dr µ = κ ∧ µ, if κ∧µ is consistent, and µ otherwise, and the forgetful revision operator ◦fg defined as κ ◦fg µ = µ. Proposition 5. For any knowledge base κ and formula µ, it holds that κ ◦D,min µ ≡ κ ◦D, lmin µ ≡ κ ◦D, lmax µ ≡ κ ◦D, sum µ ≡ κ ◦dr µ. Moreover, κ ◦D, agr µ ≡ κ ◦fg µ and κ ◦D, max µ ≡ κ ◦D, dagr µ ≡ {κ ◦dr µ, if κ is complete, κ ◦fg µ, otherwise. With Hamming distance the landscape is more diverse, as the different attitudes the operators assume towards models of κ lead to genuinely different revision strategies. Nonetheless, certain relationships between the operators still hold, with lexicographic operators being the most discriminating, in the sense that they pick formulas with fewer models. Proposition 6. For any κ ∈ 2Prop cons and µ ∈ Prop, we have that κ ◦H, lmin µ |= κ ◦H, min µ |= κ ◦H, agr µ and κ ◦H, lmax µ |= κ ◦H, max µ |= κ ◦H, dagr µ. All operators generate total preorders over interpretations, so by Theorem 1 they all satisfy axioms R1-5. Satisfaction with respect to the newly introduced postulates is clarified below. Proposition 7. For d ∈ {D,H} and f ∈ {min, lmin, max, lmax, agr, dagr, sum}, the operators ◦d, f satisfy postulates R6-10, IDF, STB as per Table 2. Proof. It is already known that ≤H,min κ (known as Dalal's operator [Dalal, 1988; Katsuno and Mendelzon, 1991]) satisfies axioms R5-6. Operator ◦H, lmin satisfies R7 (via property o7) because if w1 ∈ [κ] and w2 /∈ [κ], then mindH(w1, κ) = 0, while min dH(w2, κ) > 0; hence ------→ dH(w1, κ) <lex ------→ dH(w2, κ) and w1<H, lmin κ w2. For ◦H, lmin and axiom R6, take [κ] = {a, b, ab} and [µ] = {a, b, ab}. We get that [κ ◦H, lmin µ] = {ab}. The operator ◦H, agr satisfies axiom R6 because it makes all models of κ, and potentially other interpretations as well (which is the reason why it does not satisfy axiom R7), as the equally most plausible interpretations in ≤H, agr κ . Since all these operators place the models of κ on the lowest levels of ≤κ, they all satisfy axiom R10. Postulates R8-9 are not satisfied by ◦H,min , ◦H, lmin and ◦H, agr because these operators do not make models of κ the least plausible interpretations in ≤κ: if κ = a ∨ b, then κ shares models with κ, yet these (along with all other models of a ∨ b) are among the most plausible interpretations in ≤H, min κ , ≤H, lmin κ and ≤H, agr κ . The case for ◦H,max , ◦H, lmax and ◦H, dagr is analogous to the one for ◦H, min , ◦H, lmin and ◦H, agr , as they can be seen as duals of each other. For the operator ◦H, sum, take [κ] = {a, b, c} and [µ] = {∅, a, b, c}. We get that [κ ◦H, sum µ] = {∅}, as ∅ minimizes the sum of the Hamming distances to the models of κ: this is a counter-example to axioms R6-7. For R8-9, take [µ′ ] = {∅, ab, ac, bc}. For ◦H, sum and R10, notice that adding w′ to [κ] creates a new column for w′ in the table of distances, in which the distance corresponding to w′ is 0, i.e., the score assigned to w′ in ≤H, sum κ∨κ′ does not increase with respect to ≤H, sum κ . For the operators defined with dD, we use Proposition 5. In particular, operators ◦D,max and ◦D, dagr satisfy a postulate if and only if both ◦dr and ◦fg satisfy it. Satisfaction of RIDF and RSTB is straightforward, keeping in mind how the various operators arrange the models of κ in the generated preorders. ## 5 Conclusion We have looked at the classical revision axioms from the point of view of what they assume about an agent's attitude towards its initial beliefs, and argued that this attitude is embedded in a specific axiom (the KM postulate corresponding to Inclusion and Vacuity). By varying this axiom we were able to put forward and characterize a wide range of revision operators, and refine previously entangled intuitions in the process. Analysis of the new operators also uncovered the principles of indifference to already held beliefs (RIDF) and stability (RSTB). Further work is needed to link these notions to the other axioms, to map out their interplay and to provide them with semantic characterizations. At the same time, the more fine grained view on the types of attitudes an agent can have towards its initial beliefs raises the question of what these attitudes are good for, i.e., whether they can be used for tasks such as learning [Kelly, 1998; Baltag et al., 2011]. The idea here is to view revision as part of an ongoing process by which the agent continuously refines its representation of the outside world, with the aim of settling on stable, correct information. Such a task, we think, provides a natural benchmark for revision operators, and it has the potential to connect belief revision to other topics of importance to the field of AI. ## Acknowledgments This work has been supported by the Austrian Science Fund (FWF): P30168-N31, W1255-N23, Y698. ## References 1. [Alchourrón et al., 1985] Carlos E. Alchourrón, Peter Gärdenfors, and David Makinson. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. J. Symb. Log., 50(2):510-530, 1985. 2. [Arrow, 1959] Kenneth J. Arrow. Rational choice functions and orderings. Economica, 26(102):121-127, 1959. 3. [Baltag et al., 2011] Alexandru Baltag, Nina Gierasimczuk, and Sonja Smets. Belief revision as a truth-tracking pro- cess. In Proc. of TARK 2011, pages 187-190, 2011. 4. [Benferhat et al., 2005] Salem Benferhat, Sylvain Lagrue, and Odile Papini. Revision of Partially Ordered Informa- tion: Axiomatization, Semantics and Iteration. In Proc. of IJCAI 2005, pages 376-381, 2005. 5. [Bonanno, 2009] Giacomo Bonanno. Rational choice and AGM belief revision. Artif. Intell., 173(12-13):1194-1203, 2009. 6. [Dalal, 1988] Mukesh Dalal. Investigations into a Theory of Knowledge Base Revision. In Proc. of IJCAI 1988, pages 475-479, 1988. 7. [Darwiche and Pearl, 1997] Adnan Darwiche and Judea Pearl. On the Logic of Iterated Belief Revision. Artif. Intell., 89(1-2):1-29, 1997. 8. [Endriss, 2016] Ulle Endriss. Judgment Aggregation. In Fe- lix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computa- tional Social Choice, pages 399-426. Cambridge Univer- sity Press, 2016. 9. [Fermé and Hansson, 2018] Eduardo Fermé and Sven Ove Hansson. Belief Change: Introduction and Overview. Springer, 2018. 10. [Foley, 1993] Richard Foley. Working Without a Net: A Study of Egocentric Epistemology. Oxford University Press, 1993. 11. [French, 1988] Simon French. Decision Theory: An Intro- duction to the Mathematics of Rationality. Ellis Horwood Limited, 1988. 12. [Gärdenfors, 1988] Peter Gärdenfors. Knowledge in Flux: Modelling the Dynamics of Epistemic States. The MIT Press, Cambridge, MA, 1988. 13. [Herzig and Rifi, 1999] Andreas Herzig and Omar Rifi. Propositional Belief Base Update and Minimal Change. Artif. Intell., 115(1):107-138, 1999. 14. [Kahneman et al., 1982] Daniel Kahneman, Paul Slovic, and Amos Tversky. Judgment under uncertainty: Heuristics and biases. Cambridge University Press, 1982. 15. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Al- berto O. Mendelzon. On the Difference between Updating a Knowledge Base and Revising It. In Proc. of KR 1991, pages 387-394, 1991. 16. [Katsuno and Mendelzon, 1992] Hirofumi Katsuno and Al- berto O. Mendelzon. Propositional Knowledge Base Re- vision and Minimal Change. Artif. Intell., 52(3):263-294, 1992. 17. [Kelly, 1998] Kevin T. Kelly. The Learning Power of Belief Revision. In Proc. of TARK 1998, pages 111-124, 1998. 18. [Konieczny and Pérez, 2011] Sébastien Konieczny and Ramón Pino Pérez. Logic Based Merging. J. Philosophi- cal Logic, 40(2):239-270, 2011. 19. [Konieczny et al., 2004] Sébastien Konieczny, Jérôme Lang, and Pierre Marquis. DA 2 merging operators. Artif. Intell., 157(1-2):49-79, 2004. 20. [Levesque, 1986] Hector J Levesque. Making believers out of computers. Artif. Intell., 30(1):81-108, 1986. 21. [Moulin, 1991] Hervé Moulin. Axioms of Cooperative Deci- sion Making. Number 15 in Econometric Society Mono- graphs. Cambridge University Press, 1991. 22. [Peppas and Williams, 2016] Pavlos Peppas and Mary-Anne Williams. Kinetic Consistency and Relevance in Belief Revision. In Proc. of JELIA 2016, pages 401-414, 2016. 23. [Rott, 2001] Hans Rott. Change, choice and inference: A study of belief revision and nonmonotonic reasoning. Number 42 in Oxford Logic Guides. Oxford University Press, 2001. 24. [Ryan, 1996] Mark Ryan. Belief Revision and Ordered The- ory Presentations. In Logic, Action, and Information, pages 129-151, 1996. 25. [Sen, 1984] Amartya K. Sen. Collective Choice and Social Welfare. NY: North-Holland, 2nd edition, 1984.