Parallel Belief Revision via Order Aggregation

1 Introduction

The traditional operations of belief revision theory-revision and contraction-were initially designed to take single sentences as inputs, offering a model of "serial" change, in which beliefs were incorporated into or excised from an agent's worldview one at a time. In more recent years, these operators have been generalised to handle entire sets of sentences as inputs, yielding a model that can accommodate "parallel" change, where multiple beliefs are simultaneously processed.

Until recently, existing work in this direction had focused almost exclusively on single-step change, i.e. studying the effects of a single episode of change on an agent's set of beliefs. With only a few exceptions, no research had been carried out on the more general issue of iterated change, i.e. studying the effects of a sequence of changes. In relation to iterated parallel contraction, these exceptions include the work of Spohn [2010], who offers a treatment in terms of his ranking-theoretic construction, and a recent paper by Chandler & Booth [2025] in which they propose an axiomatically characterised construction based on a generalisation of their "TeamQueue" method of order aggregation [2019]. Regarding iterated parallel revision, the only discussions that we are aware of are those of Zhang [2004] and Delgrande & Jin [2012]. Zhang introduces generalisations to the parallel case of a number of well-known principles for iterated serial revision. Delgrande & Jin critique Zhang's postulates, finding fault in one key principle, and offer several new ones of their own. As we shall see, however, at least one of the axioms that Delgrande & Jin propose is not compelling, and those that are have yet to be underpinned by a convincing construction.

We take cue from the TeamQueue approach to iterated parallel contraction to offer a similar constructive approach to the case of revision. We find that this approach precisely allows us to derive those principles of Delgrande & Jin that are plausible, while failing to allow us to derive those that are not.

The remainder of the paper proceeds as follows. Section 2 briefly recapitulates existing work on serial belief revision, while Section 3 does the same for parallel revision, focusing on Delgrande & Jin's contribution. Section 4 provides a succinct summary of Chandler & Booth's aggregation-based proposal for parallel contraction. Section 5 offers a somewhat similar aggregation-based solution to our problem of interest. Finally, Section 6 summarises the discussion and makes several suggestions for future research. Due to space limitations, proofs are provided in a longer version of the paper, which can be accessed online at https://arxiv.org/abs/2505.13914.

2 Background on Serial Belief Revision

In what follows, the state of mind of an agent will be represented by an abstract belief state Ψ, which we do not assume to have any particular internal structure. This state gives rise to a belief set [Ψ] which contains all and only those sentences that the agent takes to be true when in state Ψ. Belief sets are deductively closed and drawn from a propositional, truth-functional, finitely-generated language L. We denote by Cn(S) the set of classical logical consequences of S ⊆ L. Where A ∈ L, we write Cn(A) instead of Cn({A}). The set of propositional worlds or valuations will be denoted by W, and the set of models of a given sentence A by [[A]].

The standard "serial" model consists of two belief change operations, serial revision ∗ and contraction ÷. These take a state and a single input sentence and return a new state. Revision captures how an agent incorporates the input into their beliefs, while contraction captures the way in which they remove it from them. The model originally dealt with singlestep serial change-the change induced by a single application of revision or contraction by a single sentence-but later research turned to iterated serial change-the change induced by a sequence of applications of serial revision or contraction.

The AGM postulates for revision [Alchourr´on et al., 1985] provide rationality constraints on single-step serial revision:

• (K1∗ ) Cn([Ψ ∗ A]) ⊆ [Ψ ∗ A]
• (K2∗ ) A ∈ [Ψ ∗ A]
• (K3∗ ) [Ψ ∗ A] ⊆ Cn([Ψ] ∪ {A})
• (K4∗ ) If ¬A /∈ [Ψ], then Cn([Ψ] ∪ {A}) ⊆ [Ψ ∗ A]
• (K5∗ ) If A is consistent, then so too is [Ψ ∗ A]
• (K6∗ ) If Cn(A) = Cn(B), then [Ψ ∗ A] = [Ψ ∗ B]
• (K7∗ ) [Ψ ∗ A∧B] ⊆ Cn([Ψ ∗ A] ∪ {B})
• (K8∗ ) If ¬B /∈ [Ψ ∗ A], then Cn([Ψ ∗ A] ∪ {B}) ⊆ [Ψ ∗ A ∧ B]

They are derivable from an analogous set of postulates for contraction by means of an equality known as the Levi Identity [Levi, 1977], given by:

This principle is justified as follows: The simplest way to modify [Ψ] to include A would be to take the closure of the union of [Ψ] and {A}, i.e. Cn([Ψ] ∪ {A}). Doing this, however, would lead to a violation of (K5∗ ), since [Ψ] and A needn't be jointly consistent, even when A is. To ensure consistency without jettisoning more beliefs than required, we therefore consider the union of [Ψ÷¬A] and {A} instead.

The Harper Identity [Harper, 1976] takes us in the other direction, from single-step serial revision to contraction:

It has been shown that the single-step behaviour of a serial revision operator ∗ that satisfies the above postulates can be represented by associating with each state Ψ a reflexive, complete and transitive binary relation (aka total preorder or TPO) ≼Ψ over W, such that [[[Ψ]]] = min(≼Ψ,W) and min(≼Ψ∗A,W) = min(≼Ψ, [[A]]) [Katsuno and Mendelzon, 1991]. We use x ∼Ψ y when x ≼Ψ y and y ≼Ψ x, and x ≺Ψ y when x ≼Ψ y but y ̸≼Ψ x. Equivalence classes of worlds, i.e. sets of worlds closed under ∼Ψ, are sometimes represented using curly brackets, so that we write "x ≺ {y, z}" instead of "x ≺ y and y ∼ z". We take the AGM postulates, and hence the TPO representability of single-step change, for granted. We call an operator that satisfies the AGM postulates an "AGM operator".

This single-step behaviour can also be captured by (i) enriching the language with a conditional connective >, associating each state Ψ with a conditional belief set [Ψ]> = {A > B | B ∈ [Ψ ∗ A]} or (ii) associating Ψ with a nonmonotonic consequence relation |∼Ψ= {⟨A,B⟩ | A > B ∈ [Ψ]>}. In (ii), the AGM postulates ensure that |∼Ψ is "rational" [Lehmann and Magidor, 1992] and "consistency preserving" [Makinson and G¨ardenfors, 1991]. By abuse of notation, since any TPO ≼ determines a unique conditional belief set, we will denote the latter by [≼]>.

Many of the principles that follow can be presented in multiple equivalent ways. When this occurs, we use subscripts to distinguish between these formulations, dropping the subscript to refer to the principle beyond specific presentation. A principle framed in terms of TPOs is denoted using a subscript "≼". Occasionally, we may also want to express principles via minimal sets, symbolizing the ≼-minimal subset of S ⊆ W, defined as {x ∈ S | ∀y ∈ S, x ≼ y}, by min(≼, S). The subscript "min" denotes presentation in this style. When appropriate, the names of principles presented in terms of belief sets will include the subscript "b". Additionally, we use superscripts to remind the reader of the nature of the operation constrained by the relevant principle, so that, for example, some principles will carry the superscripts "∗" or "÷".

In [Darwiche and Pearl, 1997], Darwiche & Pearl proposed a set of postulates (henceforth the "DP postulates") governing sequences of serial revisions. These can be presented either "syntactically" in terms of belief sets or "semantically" in terms of TPOs. In syntactic terms, we have:

• (C1∗b ) If A ∈ Cn(B) then [(Ψ ∗ A) ∗ B] = [Ψ ∗ B]
• (C2∗b ) If ¬A ∈ Cn(B) then [(Ψ ∗ A) ∗ B] = [Ψ ∗ B]
• (C3∗b ) If A ∈ [Ψ ∗ B] then A ∈ [(Ψ ∗ A) ∗ B]
• (C4∗b ) If ¬A ̸∈ [Ψ ∗ B] then ¬A ̸∈ [(Ψ ∗ A) ∗ B] Semantically, they are given by:
• (C1∗≼) If x, y ∈ [[A]] then x ≼Ψ∗A y iff x ≼Ψ y

• (C3∗≼) If x ∈ [[A]], y ∈ [[¬A]] and x ≺Ψ y then x ≺Ψ∗A y

We shall call an operator that satisfies the DP postulates a "DP operator".

Beyond these, [Booth and Meyer, 2006] introduced a strengthening of both (C3∗b ) and (C4∗b ) which they called "(P)" and which later appeared in [Jin and Thielscher, 2007] under the name of "Independence":

Its semantic counterpart is given by:

(Ind∗≼) If x ∈ [[A]], y ∈ [[¬A]] and x ≼Ψ y, then x ≺Ψ∗A y In semantic terms, the previous postulates only constrain the relation between the prior TPO and the TPO resulting from revision by a given sentence. In [Booth and Chandler, 2020] two further postulates, (β1∗≼) and (β2∗≼), were introduced to constrain the relation between different posterior TPOs resulting from revisions by different sentences.

Constructive proposals premised on the idea that belief states can be identified with TPOs have also been tabled (though see [Booth and Chandler, 2017] for criticism). These include most notably the operations of lexicographic (∗L), restrained (∗R) and natural (∗N) revision (see, respectively, [Nayak et al., 2003], [Booth and Meyer, 2006] and [Boutilier, 1996]). They all satisfy the DP postulates, as well as (β1∗≼) and (β2∗≼). Lexicographic and restrained revision additionally satisfy (Ind∗b ). Natural revision does not.

Although (C1∗b ), (C3∗b ) and (C4∗b ) are fairly uncontroversial, (C2∗b ) has received criticism, which is relevant to the discussion of parallel revision that follows. Here is an alleged counterexample, due to Konieczny & Pino P´erez [2000].

Example 1 (Konieczny & Pino P´erez [Konieczny and Pino P´erez, 2000]). Consider a circuit containing an adder and a multiplier. We initially have no information about the condition of either component. We then come to believe of each that they are working. We then change our mind again and believe that the multiplier is not working after all. After this second change of mind, the thought goes, it should not be the case that we also lose our belief that the adder is working.

Let A and B respectively stand for the claims that the adder is in order and that the multiplier is. Let Ψ be the initial belief state. If the initial change in view is to be modelled as a revision by a single sentence, it would appear that we move from Ψ to state Ψ∗A∧B and then (Ψ∗A∧B) ∗ ¬B. Since ¬(A ∧ B) ∈ Cn(¬B) and A /∈ [Ψ], the alleged intuition that A ∈ [(Ψ ∗ A ∧ B) ∗ ¬B] would mean that Example 1 contradicts (C2∗b ).

Chopra et al, who take this kind of example to mean that (C2∗b ) is not acceptable, recommend replacing (C2∗b ) with:

We return to Example 1 in the next section.

3 Background on Parallel Belief Revision

The limitations of the serial model have been highlighted in several previous discussions, particularly its inability to fully encompass the spectrum of potential alterations in belief. It has been suggested that this model should be expanded to include the concepts of parallel revision and contraction, which involve the simultaneous addition or removal of a finite set S = {A1, . . . ,An} of sentences in L (with set of indices I = {1, . . . , n}).

We will use ⊛ and c to represent parallel revision and contraction, respectively, and assume that when the input is a singleton, the single-step effects of these operations can be expressed in terms of those of their serial equivalents, with [Ψ ⊛ {A}] = [Ψ ∗ A] and [Ψ c {A}] = [Ψ ÷ A]. The symbol ∧ S will represent A1 ∧ . . . ∧An, ∨ S will represent A1 ∨ . . . ∨ An, and ¬S will represent {¬A | A ∈ S}.

3.1 Single-Step Parallel Revision

For single-step parallel revision, a plausible proposal, which we endorse here, is to simply identify the belief set obtained by parallel revision by S with the belief set obtained by serial revision by the conjunction ∧ S of the members of S:

Given the AGM postulates for serial revision, this suggestion is equivalent to a set of postulates for single-step parallel revision given in [Peppas, 2004], where they are credited, with minor differences, to a preliminary version of [Lindstr¨om, 2022], published in 1991:

• (K1⊛) Cn([Ψ⊛S]) ⊆ [Ψ⊛S]
• (K2⊛) S ⊆ [Ψ⊛S]
• (K3⊛) [Ψ⊛S] ⊆ Cn([Ψ] ∪S)
• (K4⊛) If [Ψ] ∪S is consistent, then Cn([Ψ] ∪S) ⊆ [Ψ ⊛ S]
• (K5⊛) If S is consistent, then so is [Ψ⊛S]
• (K6⊛) If Cn(S1) = Cn(S2), then [Ψ⊛S1] = [Ψ⊛S2]
• (K7⊛) [Ψ⊛ (S1 ∪S2)] ⊆ Cn([Ψ⊛S1] ∪S2)
• (K8⊛) If [Ψ⊛S1] ∪S2 is consistent, then Cn([Ψ ⊛ S1] ∪ S2) ⊆ [Ψ ⊛ (S1 ∪ S2)]

Indeed, as is noted by Peppas [Peppas, 2004] and later Delgrande & Jin [Delgrande and Jin, 2012], who all endorse (Conj⊛), the latter is an immediate consequence of (K6⊛). Similarly, assuming (Conj⊛), (K1⊛) to (K8⊛) are obviously recoverable from the AGM postulates.

We noted in Section 2 that, in the single-step situation, a correspondence exists between the AGM postulates for serial revision and contraction, via the Levi and Harper Identities. Since a similar set of postulates to (K1⊛)-(K8⊛), labelled (K1c)-(K8c) in [Chandler and Booth, 2025], extends the AGM postulates for serial contraction to the parallel case, it is natural to ask whether a two-way correspondence can be established here too. The picture, however, is much less satisfactory here: in [Fuhrmann, 1988, Thm 19.1], Fuhrmann showed that, if c satisfies (K1c)-(K8c) and [Ψ⊛ S] is defined from [Ψ c ¬S] by the following straightforward generalisation of the Levi Identity

then ⊛ satisfies (K1⊛), (K2⊛), (K3⊛), (K4⊛), (K7⊛), and (K8⊛), as well as the following weakening of (K6⊛):

Importantly, Fuhrmann notes that (K5⊛) is not recoverable, as it clashes with the following plausible principle of "Disjunctive Persistence", which states that it is possible to perform a parallel contraction by a consistent set of sentences without thereby removing the belief that at least one of the members of that set is true:

Indeed, by this principle, even if S is itself consistent, it may fail to be consistent with [Ψc¬S], since we could still have ∨ ¬S ∈ [Ψc¬S]. This leaves Cn([Ψc¬S]∪S) inconsistent and hence, by (LI◦ ), [Ψ ⊛ S] inconsistent as well. This is prohibited by (K5⊛), which requires [Ψ⊛S] is inconsistent only if S is. This is an important and problematic result, in our view, and we take it to demonstrate the implausibility of this seemingly natural way of extending the Levi Identity to the parallel case.

The fact that one can perform a parallel contraction by a set of sentences without removing the belief that at least one element is true also poses a problem for the most straightforward extension of the Harper Identity, namely:

Indeed, the fact that it may be the case that ∨ S ∈ [Ψc S] this time leads to a conflict with (K2⊛), i.e. the requirement that ¬S ⊆ [Ψ⊛¬S]: from the latter, assuming (K1c), (K5c) and consistency of ¬S, we have ∨ S /∈ [Ψ⊛ ¬S] and so, by (HI◦ ), ∨ S /∈ [ΨcS].

To sum up, we take (Conj⊛) to be the correct way to handle the single-step case, with (LI◦ ) and (HI◦ ) proving to be implausible as generalisations of (LI) and (HI).

3.2 Iterated Parallel Revision

In the single-step case, we can plausibly reduce parallel revision by S to serial revision by ∧ S, As Delgrande & Jin ([Delgrande and Jin, 2012]) have noted, this is not so in the iterated case: while we can identify [Ψ ⊛ {A, B}] and [Ψ ∗ A ∧ B], differences can emerge in subsequent operations, so that there may exist a sentence C, such that [(Ψ ⊛ {A,B}) ∗ C] and [(Ψ∗A∧B) ∗C] are distinct: the equality [(Ψ⊛S)⊛S′ ] = [(Ψ⊛{∧ S})⊛S′ ] may fail. So the beliefs states Ψ⊛{A, B} and Ψ ∗ A ∧ B cannot always be equated.

Interestingly, the example supporting this claim is none other than Example 1 above, which was deployed in criticism of (C2∗b ). Delgrande & Jin argue that the first change in belief in this example (i.e. coming to believe of each of the adder and the multiplier that they are in working order) is not appropriately modelled by revision by a conjunction (so that we move to the state Ψ ∗ A ∧ B) but rather by a revision by the corresponding set of conjuncts (so that we move to the state Ψ⊛ {A,B}). If the former model was appropriate, they claim, we would, after ultimately revising by the proposition that the multiplier is not working, lose our belief that the adder is functioning (following (C2∗b ), which they find appropriate). However, if we properly interpret the situation as parallel revision, they tell us no such consequence follows: intuitively A ∈ [(Ψ ⊛ {A, B}) ⊛ {¬B}].

This is plausible and, indeed, the kind of motivation given for (C2∗b ) does not carry over to the parallel case. As we saw earlier, the intuition there is that the effects of a serial revision should be undone if it is immediately followed by a revision that runs contrary to it. But in the parallel change modelling of Example 1, the second step runs contrary to only a strict subset of the initial parallel operations.

For the above reason, Delgrande & Jin reject a strong parallel version of (C2∗b ), proposed by Zhang in [Zhang, 2004]: 1

since, given this principle, whenever A /∈ [Ψ ⊛ {¬B}], it would follow that A /∈ [(Ψ ⊛ {A,B}) ⊛ {¬B}], since {A,B} ∪ {¬B} is inconsistent, yielding the incorrect result in the parallel revision interpretation of Example 1.

If the reductive proposal that we have seen does not plausibly generalise to the iterated case, how exactly, then, are we to handle iterated parallel revision? Delgrande & Jin endorse the following generalisations of (C1∗≼), (C3∗≼) and (C4∗≼):

• (C3⊛≼) If x ∈ [[∧ S]], y /∈ [[∧ S]] and x ≺Ψ y, then x ≺Ψ⊛S y

They tell us (omitting the proof) that these correspond to the following syntactic principles presented in [Zhang, 2004]:

1 The nomenclature is ours here, with the "S" standing for "strong", for contrast with a weaker version below.

Delgrande & Jin do not endorse any kind of parallel version of (C2∗b ) and indeed do not actually consider the question of whether a more plausible alternative to (SC2⊛b ) could be found. Such a generalisation, however, is not hard to devise:

A corresponding syntactic form can be given too:

Proposition 1. Let ⊛ be a parallel revision operator such that, for some AGM serial revision operator ∗, ⊛ and ∗ jointly satisfy (Conj⊛). Then (C2⊛≼) is equivalent to:

Unlike its stronger counterpart (SC2⊛b ), this principle doesn't get us into trouble in relation to Example 1. Indeed, this principle is perfectly consistent with its being the case that both A /∈ [Ψ ⊛ {¬B}] and A ∈ [(Ψ ⊛ {A, B}) ⊛ {¬B}], since we have {¬A, ¬B} ⊈ Cn({¬B}) and hence the principle doesn't generate the equality [(Ψ ⊛ S1) ⊛ S2] = [Ψ ⊛ S2].

As it turns out, the entire set (C1⊛b )-(C4⊛b ) of parallel versions of of the DP postulates is derivable, from two further -strong but plausible-principles that Delgrande & Jin tentatively endorse. The syntactic versions of the latter are given by:

• (PC3⊛b ) If (i) S2 ̸= ∅ and (ii), for all S ⊆ S1 s.t. S ∪S2 is consistent, we have A ∈ [Ψ ⊛ (S ∪ S2)], then (iii) A ∈ [(Ψ ⊛ S1) ⊛ S2]

While these principles are perhaps a little tricky to interpret, their semantic versions, which are also provided in [Delgrande and Jin, 2012], have a much more immediate appeal. They are formulated using the following useful notation:

Definition 1. Where S ⊆ L, and x ∈ W, (S | x) denotes the subset of S that is true in x (i.e. (S |x) = {A ∈ S |x |= A}). and are given by:

These principles essentially state the following: if x makes true at least those sentences in S that y does, then revision by S doesn't improve the position of y with respect to x. By contrast, (C3⊛≼) and (C4⊛≼) only jointly stipulate that the position of y with respect to x doesn't improve in the special case in which x makes all the sentences in S true and y does not make them all true. So, as Delgrande & Jin remark, (PC3⊛≼) and (PC4⊛≼) entail (C3⊛≼) and (C4⊛≼). But note that principles (C1⊛≼) and (C2⊛≼) are also derivable from (PC3⊛≼) and (PC4⊛≼). Indeed, it obviously follows from the latter that, when (S | y) = (S | x), we have x ≼Ψ y iff x ≼Ψ⊛S y. But clearly (S | y) = (S | x) holds true whenever the antecedents of either (C1⊛≼) or (C2⊛≼) do, i.e. whenever either x, y ∈ [[∧ S]] or x, y ∈ [[∧ ¬S]]. So, to summarise, we have:

Proposition 2. Let ⊛ be a parallel revision operator that satisfies (PC3⊛≼) and (PC4⊛≼). Then ⊛ satisfies (C1⊛≼)-(C4⊛≼).

Notably, the problematic (SC2⊛≼) does not follow from these principles, however. We shall present a construction for which (PC3⊛≼) and (PC4⊛≼) are sound but (SC2⊛≼) is not. (Proposition 4 and Proposition 6 below.)

Besides (PC3⊛≼) and (PC4⊛≼), Delgrande & Jin also endorse this plausible postulate, which we give in terms of both belief sets and minimal sets:

This mildly strengthens the parallel version of the principle (GR∗ ), mentioned in relation to Example 1 (set S1 = ∅):

Beyond these, they also propose two further possibly more controversial properties. First, since they endorse (Ind∗b ) in the serial case, they argue in favour of a corresponding generalisation to the parallel case, which strengthens (C3⊛≼) and (C4⊛≼), in the same way that (Ind∗b ) strengthened (C3∗≼) and (C4∗≼). The formulation of this principle is obvious:

Finally, they propose:

Why endorse this principle? Delgrande & Jin provide two reasons: (1) "[a]s a consequence [of endorsing it], problems associated with the DP Postulate (C2) are sidestepped". In other words, it delivers the right result in relation to cases like Example 1. It ensures that if we revise by a set of sentences S and then by the negation of a subset of these, the non-negated remainder of S survives this second revision (if consistent with its input). (2) "[It] reflects the intuition that, in revising by S and after which some members of S are subsequently disbelieved, then insofar as possible the remaining members of S are still believed".

Neither reason is persuasive. Regarding (1), as we shall see, (P⊛b ) isn't required to correctly handle Example 1. Fig. 2 demonstrates that an alternative approach, which invalidates the principle, also delivers the right result. Regarding (2), the intuition's plausibility hinges on whether "insofar as possible" means (a) "insofar as is possible according to the rules of logic" or (b) "insofar as is possible, according to the agent's prior evidential beliefs". (P⊛b ) would be supported by the intuition on reading (a), but not (b). We claim, however, that the intuition in (2) is compelling on reading (b), not (a).

2 (P⊛b ) and (S⊛b ) are formulated in a different, but logically equivalent, manner in the original text.

Example 2. As in Example 1, except that we are initially (i.e. prior to our sequence of changes in view) convinced that our friend Bill has made sure that the functionalities of the adder and multiplier are positively correlated, so that the adder is working if and only if the multiplier is working too.

A and ¬B are jointly logically consistent. However, it seems rationally permissible that A /∈ [(Ψ⊛{A, B})⊛{¬B}] (contradicting (P⊛b )). This is because A and ¬B stand in opposition in the agent's prior beliefs, with A being initially taken as a reason to doubt ¬B and vice versa.

Delgrande & Jin show their properties are sound for a particular construction. This construction, however, is both by their own admission, "somewhat complicated" and based on the ranking function formalism of Spohn [1988], whose recent axiomatic foundations remain poorly understood [Chandler, 2017].

In this section, we've seen that Delgrande & Jin have convincingly argued against Zhang's strong generalisation of Darwiche & Pearl's second postulate ((SC2⊛b )) and offered a plausible strengthening of his generalisations of the remaining three (his (C1⊛b ), (C3⊛b ) and (C4⊛b )), via (PC3⊛b ) and (PC4⊛b ). They have also introduced a promising postulate (S⊛b ), and an appropriate generalisation of (Ind∗b ) to the parallel case through (Ind⊛b ). On the negative side, their proposal includes the implausible (P⊛b ) and lacks a compelling constructive foundation.

We now propose a constructive approach to carry over constraints from iterated serial to iterated parallel revision. Under mild assumptions, it validates the more plausible principles (e.g. (PC3⊛b ), (PC4⊛b ), and (S⊛b )), while invalidating the less plausible ones (e.g. (SC2⊛b ) and (P⊛b )). It draws from the order aggregation-based approach to iterated parallel contraction of [Chandler and Booth, 2025]. Next, we recapitulate (i) the "TeamQueue" aggregation method presented there, which generalises the approach in [Booth and Chandler, 2019], and (ii) its application to iterated parallel contraction.

4 TeamQueue Aggregation and Iterated Parallel Contraction

Where I is an index set, a TeamQueue aggregator is a function ⊕ taking as inputs tuples P = ⟨≼i⟩i∈I of TPOs over W known as "profiles" and returning single TPOs over W as outputs. When the identity of P is clear from context, we write ⊕P to denote ⊕(P) and x ≼⊕P y to denote ⟨x, y⟩ ∈ ⊕P, or simply x ≼⊕ y. The constructive definition makes use of the representation of a TPO ≼j by means of an ordered partition ⟨T1, T2, . . . Tmj ⟩ of W, defined inductively by setting, for each i ≥ 1, Ti = min(≼j, ⋂k<i T c k ), where T c is the complement of T. This representation grounds the notion of the absolute rank rj (x) of an alternative x, with respect to ≼j . The absolute rank of an alternative is given by its position in the ordered partition, so that rj(x) is such that x ∈ Trj(x). The aggregation method is then defined inductively:

Definition 2. ⊕ is a TeamQueue (TQ) aggregator iff, for each profile P = ⟨≼1, . . . ≼n⟩, there exists a sequence ⟨aP(i)⟩i∈N such that ∅ ̸= aP(i) ⊆ {1, . . . , n} for each i and the ordered partition ⟨T1, T2, . . . , Tm⟩ of indifferences classes corresponding to ≼⊕ is constructed inductively as follows:

where m is minimal s.t. ⋃i≤m Ti = W.

In the initial step, this procedure cuts the minimal elements from one or more of the input TPOs and then pastes them into the lowest rank of the output TPO. Any remaining duplicates of these minimal elements in the input TPOs are also deleted. This operation is reiterated at each subsequent step until all input TPOs have been fully processed.

One noteworthy member of the TQ aggregator family manages the queues in a "synchronous" or again "concurrent" manner. This implies that at every stage, the minimal elements from all TPOs are incorporated into the appropriate output rank. This aggregator is defined as follows:

Definition 3. The Synchronous TeamQueue (STQ) aggregator ⊕STQ is the TeamQueue aggregator for which aP(i) = {1, . . . , n} for all profiles P = ⟨≼1, . . . , ≼n⟩ and all i.

In [Chandler and Booth, 2025], the family of TQ aggregators was shown to be characterisable in terms of the following "factoring" property, which we give both in terms of minimal sets and in terms of binary relations:

A characterisation of ⊕STQ can be achieved by supplementing (F⊕min ) with a principle of "Parity":

It was shown that there exists a close connection between ⊕STQ and the rational closure of a set of conditionals Γ ([Lehmann and Magidor, 1992]), which represents the rational set of conditionals that can be inferred from Γ. More specifically, it was shown that [≼⊕STQ ]> = Clrat(⋂i [≼i]>).

In the same paper, the authors make use of TeamQueue aggregation to define iterated parallel contraction in terms of iterated serial contraction. They assume the AGM postulates for serial contraction, as well as the following analogues for serial contraction of the DP postulates proposed by Chopra et al [2008], given syntactically by:

• (C1÷b ) If ¬A ∈ Cn(B) then [(Ψ÷A) ∗ B] = [Ψ ∗ B]
• (C2÷b ) If A ∈ Cn(B) then [(Ψ÷A) ∗ B] = [Ψ ∗ B]

• (C4÷b ) A ̸∈ [Ψ ∗ B] then A ̸∈ [(Ψ÷A) ∗ B] and semantically by:
• (C1÷≼) If x, y ∈ [[¬A]] then x ≼Ψ÷A y iff x ≼Ψ y

They endorse the following principle:

Definition 4. c is a TeamQueue (resp. Synchronous TeamQueue) parallel contraction operator if and only if it is a parallel contraction operator such that there exists a serial contraction operator ÷ satisfying the AGM postulates and the postulates of Chopra et al and a TeamQueue aggregator ⊕ (resp. Synchronous TeamQueue aggregator ⊕STQ), such that, for all Ψ and S ⊆ L, ≼ΨcS is defined from the ≼Ψ÷Ai by (Aggc≼ ), using ⊕ (resp. ⊕STQ).

If we impose the constraint that aP(1) = {1, . . . , n} on the construction of ⊕, as is the case in relation to ⊕STQ, then TeamQueue parallel contraction yield the "intersective" definition of single-step parallel contraction, the principle according to which the belief set obtained after contraction by a set S is given by the intersection of the belief sets obtained after contractions by each of the members of S ([Ψ c {A1, . . . ,An}] = ⋂1≤i≤n [Ψ ÷ Ai]). This intersective definition was proven in [Chandler and Booth, 2025] to entail a set of appealing generalisations to the parallel case of the AGM postulates for serial contraction.

In [Chandler and Booth, 2025], it was also shown that the TQ approach allows us to recover generalisations to the parallel case of the postulates of Chopra et al. These are:

Syntactic counterparts for these are provided as follows:

5 Parallel Revision via TeamQueue Aggregation

TQ aggregation also offers a promising, though less direct, route to parallel revision. This approach requires two steps:

• (i) Aggregate the TPOs obtained from the revisions by the members of S, yielding ⊕{≼Ψ∗A1 , . . . , ≼Ψ∗An },
• (ii) Transform this TPO to ensure that the "Success" postulate (K2⊛) is satisfied, i.e. that S ⊆ [Ψ⊛S].

This second step is required, since:

Proposition 3. There exists a set of sentences S ⊆ L, an AGM and DP serial belief revision operator ∗ and a state Ψ, s.t. min(⊕{≼Ψ∗A1 , . . . ,≼Ψ∗An },W) ⊈ [[∧ S]].

In the special case in which the single sentence revision operator ∗ is one that identifies belief states with TPOs (such as the natural, lexicographic or again restrained revision operators), the obvious choice of transformation in step (ii) would simply be a serial revision by ∧ S. We could take this revision to use the same serial revision operator as the one used in the first step. Alternatively, we could choose the natural revision operator ∗N, which has some attractive properties and involves the absolute minimal change required to get the job done. Either way, the proposal would schematically be:

Definition 5. ⊛ is a TeamQueue (TQ; resp. Synchronous TeamQueue) parallel revision operator if and only if it is a parallel revision operator such that there exists two AGM and DP revision operators ∗ and ∗′ and a TeamQueue aggregator ⊕ (resp. Synchronous TeamQueue aggregator ⊕STQ), such that, for all Ψ and S ⊆ L, ≼Ψ⊛S is defined from ∗ and ∗′ by (Agg⊛≼ ), using ⊕ (resp. ⊕STQ).

To illustrate how this approach might work, we depict in Fig. 2 a plausible model of Example 1. We note that it gives us the correct intuitive outcome: we find that A,B /∈ [Ψ] and A ∈ [(Ψ ⊛ {A,B}) ⊛ {¬B}], as required. The immediate upshot of this illustration, of course, is:

Proposition 4. (SC2⊛≼) fails for (even Synchronous) TQ parallel revision operators.

What then of the other properties we previously discussed? First, it yields (Conj⊛) as its single-step special case:

Proposition 5. If ⊛ is a TQ parallel revision operator, then it satisfies (Conj⊛).

Second, we recover Delgrande & Jin's plausible strong principles (PC3⊛≼) and (PC4⊛≼):

Proposition 6. If ⊛ is a TQ parallel revision operator, then it satisfies (PC3⊛≼) and (PC4⊛≼).

We've seen that (PC3⊛≼) and (PC4⊛≼) jointly entail (C1⊛≼)- (C4⊛≼). Proposition 6 therefore gives us:

Lemma 1. If ⊛ is a TQ parallel revision operator, then it satisfies (C1⊛≼), (C2⊛≼), (C3⊛≼) and (C4⊛≼).

We can also recover the parallel version of (Ind∗≼), on the assumption that we are proceeding from serial revision operators that satisfy (Ind∗≼):

Proposition 7. Let ⊛ be a TQ parallel revision operator defined from AGM and DP serial revision operators ∗ and ∗′ . Then, if ∗ and ∗′ satisfy (Ind∗≼), then ⊛ satisfies (Ind⊛≼ ).

Finally, another key principle can also be recovered:

Proposition 8. If ⊛ is a TQ parallel revision operator, then it satisfies (S⊛b ).

Regarding the principles that don't hold, we've already seen that (SC2⊛≼) fails. Thankfully, the same applies to (P⊛b ):

Proposition 9. (P⊛b ) fails for (even Synchronous) TQparallel revision operators.

6 Concluding Comments

Order aggregation via the ⊕STQ operator provides a fruitful approach to iterated parallel revision. It yields a principled way to construct revision operators that satisfy the plausible postulates proposed in [Delgrande and Jin, 2012] without validating more questionable ones. Extending a serial revision operator that identifies epistemic states with TPOs (e.g. natural, restrained or lexicographic revision operators) through this approach covers indefinitely many iterations of revision.

For future research, we might first seek to obtain characterisations of noteworthy classes of TQ parallel revision operators based on different classes of serial revision operators, such as those satisfying both AGM and DP postulates. Currently, we only have soundness results. Secondly, as seen in Section 2, even for the single-step parallel case, the obvious generalisations of Harper and Levi identities ((HI◦ ) and (LI◦ )) are not promising. The situation is less clear for the iterated parallel case, as work on iterated versions of (HI) and (LI) for serial change remains fairly recent (see [Nayak et al., 2005], [Chandler and Booth, 2019], and [Booth and Chandler, 2019]). Nevertheless, finding an elegant connection between the respective extensions to the parallel case of AGM postulates for serial revision and contraction remains an interesting challenge, for both single-step and iterated change.

Acknowledgments

Thanks are due to the IJCAI reviewers for their helpful remarks.