Rational belief revision has been characterized by numerous postulates, starting with the AGM axioms for propositional revision. The perspective on belief revision has been broadened significantly by Darwiche and Pearl who proposed a framework for iterated revision of epistemic states, extending the AGM framework. In view of representation results for AGM, most postulates for iterated AGM revision naturally correpond to conditions on how specific total preorders are modified by specific propositions. In this paper, we propose strategic principles for iterated revision that establish links among revisions from diferent priors by diferent (propositional or conditional) inputs. We start with reinterpreting a strategic principle of Chandler and Booth that expresses an independence of irrelevant alternatives (IIA principle) in the framework of Spohn's ranking functions. We combine this ranking-based principle with Kern-Isberner's principle of conditional preservation (PCP principle), yielding strategic principles significantly extending both IIA and PCP principles. Moreover, we elaborate the consequences of these postulates for strategic c-revisions, presenting classes of revision operators for ranking functions that comply with these postulates.
AGM theory [1] that proposes postulates for revising a deductively closed set of propositions by a new proposition. As the authors show in [2], the crucial epistemic structure on which AGM belief revision relies can be characterized by total preorders over possible worlds which are faithful to the respective set of beliefs and can be constructed from the outcomes of the revision operator. In the paper [3], this insight was used as a starting point to come up with postulates for iterated revision (DP postulates) that establish links between successive AGM revision operations. Since AGM revision is guided by total preorders, this amounts to propose postulates for the revision of total preorders to ensure coherence over any sequence of revision operations. Spohn’s ranking functions [4] are often used as a convenient implementation of total preorders that also provide gradual information about beliefs. Such a ranking function assigns a natural number to each layer of a total preorder, starting with 0 for the lowermost layer, and provides a basic arithmetics that usually alleviates presentation of revision results a lot.
representation of epistemic states in the context of belief revision, fully complying with AGM and DP theories: On the one hand, they implement a total preorder and hence the basic structure on which
probabilities [5] which provide the leading framework for reasoning and revision under uncertainty. In particular, ranking functions provide features like conditionalization and arithmetics which allow for an in-depth analysis of changes. Hence, ranking functions combine features of two leading paradigms for reasoning with (changed) beliefs. This makes them perfect candidates for developing strategic principles of belief revision, where strategic principles are meant to reveal basic characteristics of revision operators across diferent inputs, i.e., the underlying revision strategy with which an operator approaches arbitrary revision scenarios.
The results of [2] may count as a first strategic insight into AGM revision by relating each belief set to a total preorder via faithful assignments and perform AGM revision via that total preorder. In general, such revision strategies can be revealed only by postulates that relate revisions based on diferent priors to one another. The revision operator for ranking functions in [3] implicitly encodes a revision strategy that complies with the proposed postulates. Strategic c-revisions [6] provide an example for making revision strategies for ranking functions explicit by imposing general principles on the parameters of c-revisions [7]. A more recent example for strategies regarding the revision of total preorders has been proposed in [8]. Those authors present a characterization of so-called elementary revision operators that is mainly based on a principle mimicking the Independence of Irrelevant Alternatives (IIA) from social choice theory. Their postulate (IIA)1 relates revisions from two diferent total preorders by two diferent propositions to one another. Interestingly, the IIA principle also plays a role for the principles for ensuring homogeneity in iterated belief revision which have been proposed in the paper [9].
[6]. First, we present a more expressive IIA-principle for the revision of ranking functions and compare this with the principle of conditional preservation (PCP) that is characteristic for c-revisions. At first sight, these principles seem to be quite diferent. However, a closer analysis shows that for special cases, the PCP-principle covers the IIA-principle while the IIA-principle is more broadly applicable.
ifrst plainly applying the IIA-principle to strategic c-revisions. This results in quite strict and inflexible strategies for c-revisions. In the next step, we integrate information from the prior ranking functions more explicitly in the IIA-principle and present a strategic postulate that extends the PCP-principle by making use of basic ideas of IIA. We characterize strategic c-revisions that comply with this novel postulate. Moreover, we lift these results to revising ranking functions by single conditionals.
Section 4. In particular, we present an adapted IIA-principle for ranking functions, and compare this principle to the PCP-principle. Section 5 combines the basic ideas of IIA- and PCP-principles. Here we present a novel strategic postulate that extends the IIA-principle from [8] signficantly and makes it better compatible with the PCP-principle. In Section 6 we show that this novel postulate can be lifted to be applicable to the revision of ranking functions by single conditionals. We conclude in Section 7 and point out future work.
Let ℒ be a finitely generated propositional language over an alphabet Σ with atoms , , , . . . and with formulas , , , . . ., equipped with the standard connectives ∧, ∨, ¬. For conciseness of notation, we will omit the logical -connector, writing instead of ∧ , and overlining formulas will indicate negation, i.e., means ¬. Logical equivalence is denoted by ≡ . ⊤ denotes an arbitrary propositional tautology, and ⊥ denotes an arbitrary contradiction. The set of all propositional interpretations resp. possible worlds over Σ is denoted by Ω. |= means that the propositional formula ∈ ℒ holds in the possible world ∈ Ω; then is called a model of , and the set of all models of is denoted by Mod (). For propositions , ∈ ℒ, |= holds if () ⊆ (), as usual. By slight abuse of notation, we will use both for the model and the corresponding conjunction of all positive or negated atoms, easing notation a lot. Since |= means the same for both readings of , no confusion will arise. We also consider conditionals (|) ∈ (ℒ|ℒ) which express statements like “If then plausibly ”. A conditional belief base Δ is a finite set of conditionals. For the sake of technical conciseness, we presuppose for each conditional (|) dealt with in this paper that , ̸≡ ⊥ hold. 1We adapt their notation here a bit; originally, this postulate is denoted by (IIA*⪯ )
Total preorders (TPOs) ⪯
on Ω are transitive and reflexive total relations. They stand for plausibility orderings on the set of possible worlds. In the framework of (iterated) AGM revision, Ψ = (Ω, ⪯ Ψ) is a suitable representation of an epistemic state such that ⪯ Ψ provides a semantic base for an AGM revision operator [2]. For iterated revision, TPOs need to be revised according to suitable guidelines, which is a main topic of iterated belief revision. As usual, 1 ≺ Ψ 2 if 1 ⪯ Ψ 2, but not 2 ⪯ Ψ 1, and 1 ≈ Ψ 2 if both 1 ⪯ Ψ 2 and 2 ⪯ Ψ 1. The most plausible worlds are located in the lowermost layer of ⪯ Ψ, denoted by min⪯ Ψ (Ω). More generally, if Ω˜ ⊆
Ω is a subset of possible worlds, min⪯ Ψ (Ω˜ ) denotes the set of minimal worlds in Ω˜ according to ⪯ Ψ. A TPO ⪯ Ψ is lifted to a relation between propositions in the usual way: ⪯ Ψ if there is |= such that ⪯ Ψ ′ for all ′ |= ; equivalently, whenever Mod (), Mod () are both not empty, if min⪯ Ψ (Mod ()) ⪯ Ψ min⪯ Ψ (Mod ()). A conditional (|) is accepted in Ψ, denoted by Ψ |= (|), if ≺ Ψ . Note that is plausibly believed in Ψ if the conditional (|⊤) is accepted by Ψ. This allows us to subsume plausible beliefs in terms of conditional beliefs, which supports a more coherent view on reasoning and revision. Moreover, the following notations prove to be helpful for an epistemic state Ψ = (Ω, ⪯ Ψ), and , ′ ∈ Ω and ∈ ℒ : Ψ(, ′) = = () = ︂{ ︂{ ⎨ ⎧ 1 , if ≺ Ψ ′,
0 , if ≈ Ψ ′, ⎩ − 1, if ′ ≺ Ψ .
if |= , if ̸|= .
1 if |= , 0 if ̸|= (|)() = (|) = ⎨ ⎧ 1 if |= ,
0 if |= , ⎩ if ̸|= . ⎩ ⎨ ⎧ if |= , if |= , if ̸|= .
Furthermore, we use the Boolean indicator function for propositions from ℒ, defined by
For conditionals, we make use of the three-valued indicator function [10]
for any ∈ ℒ and ∈ Ω. Note that for any two worlds , ′, we have = ′ if () = (′).
(
Ordinal Conditional Functions (OCF, also called ranking functions) : Ω → N ∪ {∞} with − 1(0) ̸= ∅ were first introduced by Spohn [ 4] and implement TPOs by ranks in the ordinals, here natural numbers or ∞2. These ranks express degrees of implausibility, or surprise. For a formula , we have () := min{ () | |= }. Hence, due to − 1(0) ̸= ∅, at least one of (), () must be 0. A proposition is believed in , denoted by |
= , if |= for all such that () = 0; this is equivalent to saying that () > 0; the set of all believed propositions in is denoted by Bel ( ). Conditionals are accepted
possible worlds Ω˜ ⊆ in the epistemic state represented by , written as | = (|), if () < (). For a subset of Ω, min (Ω˜ ) denotes the set of minimal worlds in Ω˜ according to their ranks in .
As stated above, the starting point and perspective of this paper is given by the following well-known cornerstones characterizing AGM-based iterated revisions: (A) AGM theory is based on belief sets, i.e., 0, + ∞ = ∞, − ∞ = −∞ , −∞
< − ≤ < ∞ for all natural numbers . 2Regarding ∞, we stipulate the following calculation rules by considering suitable limiting processes: ∞+∞ = ∞, ∞−∞ = deductively closed sets; (B) there are eight AGM postulates (six in the Katsuno-Mendelzon version); (C) to have all eight AGM postulates for revising deductively closed sets, one needs total preorders over possible worlds, and such total preorders are enough for guaranteeing all postulates [2]; (D)
the Katsuno-Mendelzon theorem, featuring total preorders and also ranking functions.
up total preorders means giving up at least one of the AGM postulates, and usually, there are good reasons for doing so. For instance, Hansson has started a whole new line of research studying revision of belief bases where (A) cannot be ensured, with very valuable insights [11]. Basically, each one of the
there are many works systematically investigating what happens if only parts of the postulates can be satisfied (in particular, see [ 13]). The paper [14] presents a generic, model-theoretic characterization of belief revision operators in general Tarskian logics following the AGM paradigm.
strengthen it by using ranking functions in order to exploit the full power of iterated AGM revision.
seminal paper [3] laid the foundation for research on iterated revision by proposing postulates for the revision of total preorders. As a proof of concept for their axiomatic framework, they presented the following revision operator for ranking functions by propositions :
* () = ︂{ (()) +− 1(),, iiff ||== (
simple intuitive schema for revision by making use of the arithmetics of ranking functions.
so-called c-revisions were designed to handle revision of ranking functions by sets of propositions or
conditionals. c-Revisions generalize the schema (
4.1. The Basic Principles
state Ψ = (Ω, ⪯ Ψ) represented by a total preorder ⪯ Ψ and a propositional formula ∈ ℒ and returning a revised epistemic state Ψ ∙ . For characterizing such operators, the following axiom expressing an
(IIA) If , ′ ∈/ min⪯ Ψ (Mod ()) ∪ min⪯ Θ (Mod ()) then: if Ψ(, ′) = Θ(, ′), and () − (′) = () − (′), then Ψ∙ (, ′) = Θ∙ (, ′).
contexts as a formal guide to focus on relevant parts of a problem. In the form stated above, (IIA) makes a connection between (seemingly unrelated) revision scenarios Ψ ∙ and Θ ∙ , requiring the relative plausibility between two worlds , ′ in the revision result to only be afected by their prior relative plausibility and the new information (but not by any other worlds in Ψ resp. Θ).
Since each OCF induces a total preorder ⪯ on the possible worlds, a plain adaptation of this postulate to OCFs would be straightforward. However, a strengthening of (IIA) for OCFs can be obtained by making use of their arithmetics. Instead of just comparing two possible worlds according to their ranks, we can compute the diference between their ranks and compare these diferences among diferent ranking functions. Hence we propose the following IIA-postulate for revising ranking functions 1, 2 by formulas resp. , yielding revisions 1 * and 2 * : (IIA ) If , ′ ∈/ min 1 (Mod ()) ∪ min 2 (Mod ()) then: if 1() − 1(′) = 2() − 2(′) and () − (′) = () − (′), then 1 * () − 1 * (′) = 2 * () − 2 * (′).
diferences” () − (′) = () − (′). In our reinterpretation of the IIA principle for ranking functions, relevance is expressed by the model diferences and the rank diferences, resp., being equal.
Let us investigate the precondition () − (′) = () − (′) of this postulate in more detail because the distinction among the arising possible cases will be crucial for this paper. For each ∈ ℒ, we have () − (′) ∈ {− 1, 0, 1}, depending on whether and ′ are models of or not. When also another ∈ ℒ has to be taken into regard, we have to investigate each of the three options and check when equality holds. The results of this investigation are summarized in the following lemma. Lemma 1. For all , ∈ ℒ, and for all , ′ ∈ Ω, () − (′) = () − (′) holds in exactly two (non-exclusive) cases: (I) () = () and (′) = (′), or (II) () = (′) and () = (′).
sitions or conditionals was proposed, aiming at preserving conditional relationships among possible
worlds (expressed by diferences) as far as possible. Hence this principle was named Principle of
Conditional Preservation, PCP. In its most simple form, when is revised by a proposition , this principle
reads as follows:
(PCP1) Let , ′ ∈ Ω such that () = (′). Then * () − () = * (′) − (′).
Note that both (IIA ) and (PCP1) rely on considering diferences which is only possible by making use
of the arithmetics of ranking functions. Since equality of diferences is considered to be a basic form
of an analogy [19], they both implement analogy principles in revision. For example, (PCP1) claims
that if , ′ are analoguous with respect to in that they are both models or non-models of , then
* () is to () as * (′) is to (′). A more general analogy also holds for the general case
* Δ. Revisions of ranking functions by single propositions satisfying the (PCP1) principle are called
c-revisions. A c-revision * has the form
* () = − () + () +
︂{ if ̸|= ,
0 if |= ,
(
> () − (). (
Definition 1 (Selection strategy , strategic c-revision * for propositions). A selection strategy for
c-revisions of ranking functions by propositions is a function : (, ) ↦→ , assigning to each
pair of an OCF and a (consistent) proposition a non-negative integer (or ∞) that solves (
For example, the DP revision operator in (
by , and 2 by . Note that a priori, 1 |= and 2 |= . The revisions will be done by c-revisions.
According to (
minimal -model for 2 is . These models have to be excluded from our considerations. We choose = and ′ = . Then we find 1() − 1(′) = 2 − 5 = − 3 = 3 − 6 = 2() − 2(′), and () − (′) = 1 − 0 = 1 = 1 − 0 = () − (′), as required. However, 1 * () − 1 * (′) = 1 − 6 = − 5, which is diferent from 2 * () − 2 * (′) = 1 − 7 = − 6. Hence (IIA ) is violated.
4.2. Comparing the IIA and PCP principles When comparing (IIA ) and (PCP1) with one another, we first notice some mismatches between their settings which are due to their diferent perspectives. While (IIA ) aims at relating the revision of diferent ranking functions by arbitrary propositions to one another, (PCP1) originates from the more general PCP-principle, which deals with most complex revisions of ranking functions by sets of propositions or conditionals, but without making connections between the revisions of diferent prior ranking functions. Consequently, (IIA ) is more general than (PCP1) regarding two aspects. First, (IIA ) compares two posterior ranking functions that are based on diferent prior ranking functions and revised by diferent propositions while (PCP1) just compares a posterior ranking function to its prior ranking function. Second, the precondition () = () and (′) = (′) leaves more freedom for comparing also revisions on models of resp. with models of ¬ resp. ¬. This is not possible with (PCP1) that crucially requires the two worlds under consideration to be both models or non-models of the same proposition. On the other hand, these two worlds cannot be minimal models for (IIA ) whereas no such restriction exists for (PCP1).
It is particularly this last point which reveals a crucial diference between the approaches in [ 8] and [7]. It must be emphasized that (PCP1) deliberately links all models of resp. ¬ to the handling of their minimal models. This means that (PCP1) does not distinguish between minimal models and non-minimal models. Hence, if models of resp. ¬ have to be shifted downwards resp. upwards because exactly the minimal models of must have rank 0 after revision according to AGM, this shifting should also apply to the other models of resp. ¬ by the same amount. In this way, the shifting of possible worlds by c-revisions are mainly motivated by AGM and considerations of analogies.
more basic (IIA)) is to explicitly allow diferent revision strategies for the minimal models and the non-minimal models. The basic glue efective in elementary revision operators is the possibility to relate the strategies of handling models vs. handling non-models to each other. This definitely goes beyond (PCP1).
intersection of their scopes. This allows for gaining fruitful insights for integrating ideas from (IIA ) into (PCP1), and also the other way round. The following proposition establishes a basic link between the two postulates.
Proposition 2. Let 1, 2 be ranking functions, , ∈ ℒ be propositions, and * a revision operator. For any two possible worlds , ′ ∈ Ω such that () = (′), if (PCP1) is fulfilled then also (IIA ) is fulfilled.
Proof. Let 1, 2 be ranking functions, and , ∈ ℒ be propositions. We consider the revisions 1 * and 2 * . Let , ′ ∈ Ω be such that () = (′). To comply with the prerequisites of (IIA ), we assume , ′ ∈/ min 1 (Mod ()) ∪ min 2 (Mod ()), () − (′) = () − (′), and 1() − 1(′) = 2() − 2(′) to hold. We have to show that (PCP1) then implies that 1 * () − 1 * (′) = 2 * () − 2 * (′).
Since () = (′) and () − (′) = () − (′), we also have () = (′). Hence (PCP1) can be applied to both revisions 1 * and 2 * , yielding 1() − 1(′) = 1 * () − 1 * (′) and 2() − 2(′) = 2 * () − 2 * (′). Now, making use of the precondition 1() − 1(′) = 2() − 2(′) we obtain 1 * () − 1 * (′) = 2 * () − 2 * (′), i.e., (IIA ) holds.
is stronger than (IIA ) because it also allows these worlds to be minimal worlds. However, if one of the worlds is a model and the other one a non-model of , (PCP1) cannot say anything about the relationship of the two worlds after revision. In the next section, we make use of basic ideas underlying (IIA ) to extend (PCP1) regarding the relationship of two arbitrary worlds after revision.
strategic c-revisions in Section 5.1. As we will see, this imposes quite strong absolute restrictions to the impact factors of c-revisions. Therefore, we modify (IIA ) in Section 5.2 in two steps to make its main statement explicitly dependent on prior information. 5.1. Absolute IIA Principles for c-Revisions
after Proposition 2 by considering two possible worlds , ′ ∈ Ω such that () ̸= (′). Lemma 3. Let 1, 2 be ranking functions, and , ∈ ℒ. Let * be a strategic c-revision operator with a selection strategy . Let , ′ ∈ Ω be such that 1() − 1(′) = 2() − 2(′) and () = () = 1, (′) = (′) = 0. Then 1 * () − 1 * (′) = 2 * () − 2 * (′) if and only if ( 1, ) = ( 2, ).
Proof. Let 1 * , 2 * be two strategic c-revisions of the form (
prior. Note that the prerequisite 1() − 1(′) = 2() − 2(′) is trivially fulfilled if 1 = 2. This simplifies the proof above a bit, but yields basically the same result.
Corollary 4. Let be a ranking function, and let , ∈ ℒ. Let * be a strategic c-revision operator with selection strategy . Let , ′ ∈ Ω be such that () = () = 1, (′) = (′) = 0. Then * () − * (′) = * () − * (′) if and only if (, ) = (, ).
arbitrary propositions, even if we fix the prior ranking function. Note that the impact factor in (
Motivated by these considerations, we also propose a restricted version of the strong (IIA ) postulate that only considers revisions from the same prior, i.e., keeping 1 = 2 fixed and allowing variations only over the involved propositions. To align our notation with that of the paper [8], we denote this postulate by (IIAI ), where the additional “I” refers to the propositional input of the revision which can be varied while the prior is fixed. (IIAI ) If , ′ ∈/ min 1 (Mod ()) ∪ min 2 (Mod ()) then: if () − (′) = () − (′), then * () − * (′) = * () − * (′).
characterizes strategic c-revisions satisfying (IIAI ) resp. (IIA ) via their selection strategies. Theorem 5.
(
Proof. Let , ∈ ℒ, and let , ′ be possible worlds. Note that (strategic) c-revisions do not make
diferences between minimal and non-minimal models of propositions, so the precondition “ , ′ ∈/
min 1 (Mod ()) ∪ min 2 (Mod ())” is not relevant here. Furthermore, from Proposition 2 we know
that (IIA ) and hence (IIAI ) is fulfilled by any c-revision when () = (′). Hence in the
following, we only need to consider the case () ̸= (′) combined with the prerequisite () −
(′) = () − (′). This means that we are in case (I) of Lemma 1, i.e., we must have () =
() and (′) = (′). W.l.o.g., let () = () = 1, (′) = (′) = 0. For (
(
in Example 1, as we explain in more detail in the next example.
Example 2 (Example 1 cont’d). For the revisions 1 * and 2 * as shown in Fig. 1, we chose the impact factors 1 = 2 and 3 = 3 in Example 1. To fully comply with (IIA ), we would have to choose ∞ in both cases, according to Theorem 5. Even if we just aim at satisfying (IIAI ), we must choose impact factors which must be greater than the largest rank occurring in the respective ranking functions. This means, the impact factors must satisfy 1 > 5 and 2 > 6 to guarantee that (IIAI ) is satisfied.
of lexicographic revision [20] if the prior ranking function is fixed, and kind of a conditionalization enforcing all models violating the new information to have infinite rank in the general case.
operator * ℓ for OCFs was introduced as ( * ℓ )() = () − () + ( * ′ℓ )() = () − () + ⎩0 if |= .
This revision is a strategic c-revision in which we assign (, ) = 1 + max|= () depending on
and (see Equation (
∈Ω ⎩0 if |= . is a strategic c-revision that assigns (, ) = 1 + max∈Ω () to every and every . Note that this assignment is independent of , i.e., * ′ℓ presents a strategy for realizing lexicographic revision via a strategic c-revision whose selection strategy assigns to all propositions (with fixed ) the same value, complying with (IIAI ). ⎧ ⎨1 + max ()} |={ if ̸|= , 5.2. Relative IIA Principles
does not take prior information into account explicitly. It is only implicitly that it presupposes 1() − 1(′) = 2() − 2(′) when postulating 1 * () − 1 * (′) = 2 * () − 2 * (′) for the posterior ranking functions. To the contrary, (PCP1) explicitly includes the prior ranks when postulating * () − () = * (′) − (′).
account, we generalize (IIA ) slightly by weakening its precondition 1() − 1(′) = 2() − 2(′) suitably, presenting now the Extended (IIA ) postulate.
Proposition 6. Any revision operator that satisfies (EIIA ) also satisfies (IIA ).
As a further feature, (PCP1) applies to all models of the new information, not just to the non-minimal ones. However, the precondition , ′ ∈/ min 1 (Mod ()) ∪ min 2 (Mod ()) of (EIIA ) still excludes the minimal models of and . In fact, the position of these models after revision is clear from the AGM paradigm – they must have the posterior rank 0. So, (IIA ) aims at controlling the revision of the other worlds. For those worlds, 1() resp. 2() are not relevant. However, if we want to also include the minimal worlds of and when setting up a general revision strategy guided by the AGM paradigm, we have to take the prior ranks into account as well. We continue this idea of extending (IIA ) further towards a more general relativization so that also the prior ranks 1(), 1() resp. 2(), 2() are taken into account. More precisely, we are aiming at an IIA-like postulate that deals with all worlds at the same time while only using the information whether they are models or non-models of the new information and their relative rank compared to resp. . To this end, we relate the ranks occurring in (EIIA ) to the ranks of the minimal worlds of and resp. and . This leads to the novel principle of Equality of Relative Impact (ERI) as a general strategy for revisions of ranking functions by propositions: (ERI) If () − (′) = () − (′), then 1 * () − 1 * (′) − [( 1() − 1()) − ( 1(′) − 1(′ ))] = 2 * () − 2 * (′) − [( 2() − 2()) − ( 2(′) − 2(′ ))].
This postulate takes up basic ideas of (IIA ) of maintainig distances resp. analogies for arbitrary revisions, but it is applicable to all models. Hence it has to take into account the diferences to the minimal models of , resp. , suitably. On the other hand, (ERI) significantly extends (PCP1). In case of () = (′) (and hence () = (′)), we have = ′ (and also = ′ ). In this case, (PCP1) implies that both sides of the equation in (ERI) evaluate to 0 and hence are equal. This means that (PCP1) implies (ERI) when , ′ are both models or non-models of resp. . However, in the general case, (ERI) is much more expressive by relating two diferent revisions involving diferent ranking functions and diferent propositions to each other. In this way, the novel (ERI) postulate combines crucial ideas of both IIA- and PCP-principles and allows for expressing revision strategies accross diferent prior ranking functions and diferent new propositions.
In the following, we elaborate on the consequences of (ERI) for c-revisions. The results from Lemma
3 and Corollary 4 together with the constraint (
(, ) = () − () + , i.e., (, ) − ( () − ()) is constant for all and all .
() − (). With this property of selection strategies, we are able to characterize strategic c-revisions that satisfy (ERI).
Theorem 7. Strategic c-revisions satisfy (ERI) if their selection strategies satisfy (ERIF ).
is that (IIA ) aims at fixing the absolute impact factor , while (ERI) fixes the relative impact factor − ( ()− ()), allowing for taking prior information into account. The property (ERIF ) implements this for the corresponding selection strategies. We reconsider Example 1 again regarding whether the revisions 1 * and 2 * from Fig. 1 comply with (ERI).
the selection strategies in Example 1 satisfy (ERIF ). There, we chose ( 1, ) = 2 and ( 2, ) = 3, and find immediately ( 1, ) − ( 1() − 1()) = 2 − 1 = 1 = 3 − 2 = ( 2, ) − ( 2() − 2()), hence (ERI) is satisfied in this case (please see Fig. 1). Note that this is only a local check. Only if the relative impact factor is chosen to be 1 also for all other revisions, we can confirm that this strategic c-revision satisfies (ERI).
propose for revising a ranking function by a conditional (|) in the next section. 6. A Strategic Principle for Conditional Revision of Ranking Functions As briefly explained in Section 4.1, the PCP-principle is a very general and far-reaching principle for revising ranking functions also by (sets of) conditionals. In the following, by generalizing the ideas from the previous sections, we develop a novel ERI-postulate called (CERI) for revising a ranking function by a single conditional (|). Regarding (PCP), this means we consider the case * Δ with Δ = {(|)}, where , ∈ ℒ. For sake of technical convenience, we assume (|) to be non-contradictory, i.e., ̸≡ ⊥ , and leave the elaboration of the general case for future work. Moreover, since Δ consists of just one conditional, we simply write * (|) and omit set brackets in general. (PCP) [7] yields the following postulate for this case: (PCP1) Let , ′ ∈ Ω such that (|)() = (|)(′). Then
* (|)() − () = * (|)(′) − (′) The precondition (|)() = (|)(′) of this postulate means that both worlds are either verifying or falsifying the conditional, or the conditional is applicable to neither of them. (PCP1) establishes a similar analogy principle for conditional revision as (PCP1) does in the propositional case. Again, crevisions are revisions (basically) characterized by (PCP1). c-Revisions * (|) have the following form (see [7]): where is a non-negative integer or ∞ satisfying
> () − (). (
After this brief introduction to conditional revision of ranking functions by c-revisions, we now
propose the general principle of Equality of Relative Impact for revising ranking functions 1, 2 by
single conditionals (|), (|).
(CERI) Let , ′ ∈ Ω be such that {(|)(), (|)(), (|)(′), (|)(′)} ⊆ {
(|)() − (|)(′) = (|)() − (|)(′) then
0, 1}. If
1 * (|)() − 1 * (|)(′) − [( 1() − 1((|))) − ( 1(′) − 1((|)′ ))]
= 2 * (|)() − 2 * (|)(′) − [( 2() − 2((|))) − ( 2(′) − 2((|)′ ))]
Note that we exclude the case that anyone of (|)(), (|)(), (|)(′), (|)(′) is from
the scope of the postulate (CERI) since the negation of the premise is explicitly and deliberately
excluded from the scope of conditionals (see (
By identifying propositions with conditionals (|⊤), it is obvious that (CERI) lifts (ERI) to the case
of revising by conditionals. To formalize a corresponding lifting of (ERIF ) for selection strategies, we
need to make use of an extended definition of selection strategies for c-revisions that apply to revisions
of ranking functions by (single) conditionals (please see [6] for more details),
* (|)() = − ( ∨ ) + () +
(
We are now ready to set up the property (CERIF ) for selection strategies, ensuring an Equality of Relative Impact Factor for conditional revisions. (CERIF ) There is ≥ 1 such that for all ranking functions and for all conditionals (|),
(, (|)) = () − () + , i.e., (, (|)) − ( () − ()) is constant for all and all (|).
Theorem 8. Strategic c-revisions satisfy (CERI) if their selection strategies satisfy (CERIF ).
Proof. Let 1, 2 be ranking functions, (|), (|) conditionals over ℒ, , ′ ∈ Ω such that
{(|)(), (|)(), (|)(′), (|)(′)} ⊆ { 0, 1}. Furthermore, let (|)() − (|)(′) =
(|)() − (|)(′). We first observe that since {(|)(), (|)(), (|)(′), (|)(′)} ⊆
{0, 1}, we have a situation that is analogous to that in Lemma 1. Hence we obtain that (|)() −
(|)(′) = (|)() − (|)(′) exactly in two cases: (I) (|)() = (|)() and (|)(′) =
(|)(′), or (II) (|)() = (|)(′) and (|)() = (|)(′). We set *1 = 1 * (|) and
*2 = 2 * (|) with the same selection strategy . From (
We first consider case (II) of (|)() − (|)(′) = (|)() − (|)(′), i.e., (|)() = (|)(′) and (|)() = (|)(′). Moreover, we have (|) = (|)′ and (|) = (|)′ . From (PCP1), we obtain *1() − *1(′) − [( 1() − 1((|))) − ( 1(′) − 1((|)′ ))] = *1() − 1() − ( *1(′) − 1(′)) + 1((|)) − 1((|)′ ) = 0.
In the same way, we obtain *2() − *2(′) − [( 2() − 2((|))) − ( 2(′) − 2((|)′ ))] = 0, hence the left-hand side and right-hand side of (CERI) coincide trivially. So, (PCP1) ensures (CERI) in this case, same as for propositional revision.
Let us now consider case (I), i.e., (|)() ̸= (|)(′) and hence also (|)() ̸= (|)(′). Since (|)(), (|)(′) are presupposed to be diferent from , we have (|)(), (|)(′) ∈ {0, 1}. W.l.o.g. we assume (|)() = 1 and (|)(′) = 0; the other case is dealt with in a symmetric way. Then we also have (|)() = 1 and (|)(′) = 0. Therefore, |= , , ′ |= , , and (|) = , (|)′ = , (|) = , (|)′ = . The left-hand side of (CERI) is then computed as follows: *1() − *1(′) − [( 1() − 1()) − ( 1(′) − 1())] = − 1( ∨ ) + 1() + 1( ∨ ) − 1(′) − 1 − 1() + 1()) + 1(′) − 1() = − 1 + 1() − 1() = − ( 1 − ( 1()) − 1())) = − 1.
Analogously, for the right-hand side of (CERI), we obtain − 2. Therefore, (CERI) holds in general if 1 = 2, which is claimed by (CERIF ).
By identifying a proposition with the conditional (|⊤), a proof of Theorem 7 can be obtained immediately from the proof of Theorem 8.
We illustrate conditional revision strategies complying with (CERI) by an example. with ( 1, (|)) = 1 > 1() − 1() = 2 − 1 = 1; and ︂{ 2 if |= , 2 * (|)() = 2() + 0 if |= ∨ , with ( 2, (|)) = 2 > 2() − 2() = 4 − 3 = 1. According to (CERIF ), we choose the same relative impact factor = 2 for both revisions, i.e., 1 = 3 and 2 = 3. This yields the numbers in Fig. 2.
Let us now verify (CERI) for = and ′ = . For these possible worlds, we have (|)() = (|)() = 1, (|)(′) = (|)(′) = 0, and hence (|) = , (|)′ = , (|) = , (|)′ = . We obtain 1 * (|)() − 1 * (|)(′) − [( 1() − 1()) − ( 1(′) − 1())] = − 2 = − , as could have been expected from the proof of Theorem 8. Similarly, we obtain the same result for 2 * (|). This verifies (CERI) for , ′.
to dealing with revision by conditionals with analogous results.
In this paper, we proposed strategic postulates for revising ranking functions by single propositions and conditionals, respectively. More precisely, with the postulates (ERI) and (CERI), we presented postulates that relate revisions of diferent prior ranking functions by diferent (propositional or conditional) input formulas. By complying with these postulates, generic revision strategies can be elaborated not relying on given ranking functions and formulas. In particular, we showed how the integration of information from prior ranking functions, as the PCP-principle [7] does, can make the basic idea of the IIA-principle from [8] much more broadly applicable. Our novel propositional postulates allow for a straightforward generalization to the case of revising ranking functions by conditionals. This possibility of a homogeneous extension towards handling more complex information also underlines the strategic quality of the novel postulates.
presenting also a proof of concept of our approach. As part of our future work, we plan to combine (ERI) and (CERI). or their characterizations for selection strategies, respectively, with other postulates for strategic c-revisions. Moreover, transferring the novel postulates to the problem of revising total preorders might also lead to new insights into iterated belief revision in general.