# parallel_belief_revision_via_order_aggregation__79b5bc70.pdf Parallel Belief Revision via Order Aggregation Jake Chandler1 , Richard Booth2 1La Trobe University 2Cardiff University jacob.chandler@latrobe.edu.au, boothr2@cardiff.ac.uk Despite efforts to better understand the constraints that operate on single-step parallel (aka package , multiple ) revision, little work has been carried out on how to extend the model to the iterated case. A recent paper by Delgrande & Jin outlines a range of relevant rationality postulates. While many of these are plausible, they lack an underlying unifying explanation. We draw on recent work on iterated parallel contraction to offer a method for extending serial iterated belief revision operators to handle parallel change. Based on a family of order aggregators known as Team Queue aggregators, it provides a principled way to recover the independently plausible properties that can be found in the literature, without yielding the more dubious ones. 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 Team Queue 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 Team Queue 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. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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: (LI) [Ψ A] = Cn([Ψ A] {A}) 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: (HI) [Ψ A] = [Ψ] [Ψ A] 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 (C2 ) If x, y [[ A]] then x Ψ A y iff x Ψ y (C3 ) If x [[A]], y [[ A]] and x Ψ y then x Ψ A y (C4 ) 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 : (Ind b) If A [Ψ B], then A [(Ψ A) B] 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 Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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: (GR b) [(Ψ A) A] = [Ψ A] 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 V S will represent A1 . . . An, W 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 V S of the members of S: (Conj ) [Ψ S] = [Ψ {V 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 (LI ) [Ψ S] = Cn([Ψ c S] S) then satisfies (K1 ), (K2 ), (K3 ), (K4 ), (K7 ), and (K8 ), as well as the following weakening of (K6 ): (K6 ) If, A1 S1, A2 S2 s.t. Cn(A1) = Cn(A2), and vice versa, then [Ψ S1] = [Ψ S2] 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: (Di Pc) There exist Ψ and consistent S L, s.t. W S [Ψ c S] Indeed, by this principle, even if S is itself consistent, it may fail to be consistent with [Ψ c S], since we could still have W 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: (HI ) [Ψ c S] = [Ψ] [Ψ S] Indeed, the fact that it may be the case that W 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 W S / [Ψ S] and so, by (HI ), W S / [Ψ c S]. 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 V S, As Delgrande & Jin ([Delgrande and Jin, 2012]) have noted, this is not so in the iterated Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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 ] = [(Ψ {V 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 (SC2 b ) If S1 S2 is inconsistent, then [(Ψ S1) S2] = [Ψ S2] (SC2 ) If x, y / [[V S]] then x Ψ S y iff x Ψ y 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 ): (C1 ) If x, y [[V S]], then x Ψ S y iff x Ψ y (C3 ) If x [[V S]], y / [[V S]] and x Ψ y, then x Ψ S y (C4 ) If x [[V S]], y / [[V 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]: (C1 b ) If S1 Cn(S2), then [(Ψ S1) S2] =[Ψ S2] (C3 b ) If S1 [Ψ S2], then S1 [(Ψ S1) S2] (C4 b ) If S1 [Ψ S2] is consistent, then so is S1 [(Ψ S1) S2] 1The 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: (C2 ) If x, y [[V S]], then x Ψ S y iff x Ψ y 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: (C2 b ) If S1 Cn(S2), then [(Ψ S1) S2] =[Ψ S2] 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] (PC4 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: (PC3 ) If (S |y) (S |x) and x Ψ y then x Ψ S y (PC4 ) If (S |y) (S |x) and x Ψ y then x Ψ S y 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 [[V S]] or x, y [[V S]]. So, to summarise, we have: Proposition 2. Let be a parallel revision operator that satisfies (PC3 ) and (PC4 ). Then satisfies (C1 ) (C4 ). Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) 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: (S b ) [Ψ (S1 S2)] = [(Ψ (S1 S2)) (S1 S2)] (S min) min( Ψ, [[V(S1 S2)]]) = min( Ψ (S1 S2), [[V(S1 S2)]]) This mildly strengthens the parallel version of the principle (GR ), mentioned in relation to Example 1 (set S1 = ): (GR b ) [(Ψ S) S] = [Ψ S] (GR min) min( Ψ S, [[V S]]) = min( Ψ, [[V S]]) (GR ) is itself a special case of (C2 b ). 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: (Ind b ) If S1 [Ψ S2] is consistent, then S1 [(Ψ S1) S2] (Ind ) If x [[V S]], y / [[V S]] and x Ψ y, then x Ψ S y Finally, they propose: (P b ) If S1 S2 is consistent, then S1 [(Ψ (S1 S2)) S2] (P min) If S1 S2 is consistent, then min( Ψ (S1 S2), [[V S2]]) [[S1]]2 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 Team Queue aggregation method presented there, which generalises the approach in [Booth and Chandler, 2019], and (ii) its application to iterated parallel contraction. 4 Team Queue Aggregation and Iterated Parallel Contraction Where I is an index set, a Team Queue 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, T k = Clrat(T i[ i]>). In the same paper, the authors make use of Team Queue 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] (C3 b ) If A [Ψ B] then A [(Ψ A) B] (C4 b ) A [Ψ B] then A [(Ψ A) B] and semantically by: (C1 ) If x, y [[ A]] then x Ψ A y iff x Ψ y (C2 ) If x, y [[A]] then x Ψ A y iff x Ψ y (C3 ) If x [[ A]], y [[A]] and x Ψ y then x Ψ A y (C4 ) If x [[ A]], y [[A]] and x Ψ y then x Ψ A y They endorse the following principle: (Aggc ) Ψc{A1,...,An}= { Ψ A1, . . . , Ψ An} and offer the following definition Definition 4. c is a Team Queue (resp. Synchronous Team Queue) 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 Team Queue aggregator (resp. Synchronous Team Queue aggregator STQ), such that, for all Ψ and S L, Ψc S is defined from the Ψ Ai by (Aggc ), using (resp. STQ). If we impose the constraint that a P(1) = {1, . . . , n} on the construction of , as is the case in relation to STQ, then Team Queue 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}] = T 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: (C1c ) If x, y [[V S]] then x Ψc S y iff x Ψ y (C2c ) If x, y [[V S]] then x Ψc S y iff x Ψ y (C3c ) If x [[V S]], y / [[V S]] and x Ψ y then x Ψc S y (C4c ) If x [[V S]], y / [[V S]] and x Ψ y then x Ψc S y Syntactic counterparts for these are provided as follows: (C1c b ) If S1 Cn(S2), then [(Ψ c S1) S2] = [Ψ S2] (C2c b ) If S1 Cn(S2), then [(Ψ c S1) S2] = [Ψ S2] (C3c b ) If S1 [Ψ S2], then S1 [(Ψ c S1) S2] (C4c b ) If S1 [Ψ S2] is consistent, then S1 [(Ψ c S1) S2] is consistent Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) Figure 2: Model of Example 1, using the TQ approach. The correct result is obtained here: A, B / [Ψ] and A [(Ψ {A, B}) { B}], since min( Ψ {A,B}, [[ B]]) = {z} {z, w} = [[A]]. 5 Parallel Revision via Team Queue 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) [[V 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 V 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: (Agg ) Ψ S= { Ψ A1, . . . , Ψ An} V S This leads us to the following definition: Definition 5. is a Team Queue (TQ; resp. Synchronous Team Queue) 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 Team Queue aggregator (resp. Synchronous Team Queue 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) TQ parallel 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. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25) References [Alchourr on et al., 1985] Carlos E Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2):510 530, 1985. [Booth and Chandler, 2017] Richard Booth and Jake Chandler. The irreducibility of iterated to single revision. Journal of Philosophical Logic, 46(4):405 418, 2017. [Booth and Chandler, 2019] Richard Booth and Jake Chandler. From iterated revision to iterated contraction: Extending the Harper Identity. Artificial Intelligence, 277:103171, 2019. [Booth and Chandler, 2020] Richard Booth and Jake Chandler. On strengthening the logic of iterated belief revision: Proper ordinal interval operators. Artificial Intelligence, 285:103289, 2020. [Booth and Meyer, 2006] Richard Booth and Thomas Meyer. Admissible and restrained revision. Journal of Artificial Intelligence Research, 26(1):127 151, 2006. [Boutilier, 1996] Craig Boutilier. Iterated revision and minimal change of conditional beliefs. Journal of Philosophical Logic, 25(3):263 305, 1996. [Chandler and Booth, 2019] Jake Chandler and Richard Booth. Elementary iterated revision and the Levi Identity. In Patrick Blackburn, Emiliano Lorini, and Meiyun Guo, editors, Logic, Rationality, and Interaction - 7th International Workshop, LORI 2019, Chongqing, China, October 18-21, 2019, Proceedings, volume 11813 of Lecture Notes in Computer Science, pages 15 28. Springer, 2019. [Chandler and Booth, 2025] Jake Chandler and Richard Booth. Parallel belief contraction via order aggregation. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25), Montreal, Canada, 2025. International Joint Conferences on Artificial Intelligence Organization. [Chandler, 2017] Jake Chandler. Review of Wolfgang Spohn s The Laws of Belief: Ranking Theory and its Philosophical Applications, Oxford: Oxford University Press, 2012. Dialectica, 71(1):141 146, 2017. [Chopra et al., 2008] Samir Chopra, Aditya Ghose, Thomas Meyer, and Ka-Shu Wong. Iterated belief change and the Recovery axiom. Journal of Philosophical Logic, 37(5):501 520, 2008. [Darwiche and Pearl, 1997] Adnan Darwiche and Judea Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89(1):1 29, 1997. [Delgrande and Jin, 2012] James Delgrande and Yi Jin. Parallel belief revision: Revising by sets of formulas. Artificial Intelligence, 176(1):2223 2245, 2012. [Fuhrmann, 1988] Andr e Fuhrmann. Relevant logics, modal logics and theory change. Ph D thesis, Research School of Social Sciences, ANU, 1988. [Harper, 1976] William L Harper. Rational conceptual change. In PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, pages 462 494, 1976. [Jin and Thielscher, 2007] Yi Jin and Michael Thielscher. Iterated belief revision, revised. Artificial Intelligence, 171(1):1 18, 2007. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3):263 294, 1991. [Konieczny and Pino P erez, 2000] S ebastien Konieczny and Ram on Pino P erez. A framework for iterated revision. Journal of Applied Non-Classical Logics, 10(3-4):339 367, 2000. [Lehmann and Magidor, 1992] Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail? Artificial intelligence, 55(1):1 60, 1992. [Levi, 1977] Isaac Levi. Subjunctives, dispositions and chances. Synthese, 34(4):423 455, 1977. [Lindstr om, 2022] Sten Lindstr om. A semantic approach to nonmonotonic reasoning: Inference operations and choice. Theoria, 88(3):494 528, 2022. [Makinson and G ardenfors, 1991] David Makinson and Peter G ardenfors. Relations between the logic of theory change and nonmonotonic logic. In Andr e Fuhrmann and Michael Morreau, editors, The Logic of Theory Change, pages 183 205, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. [Nayak et al., 2003] Abhaya C Nayak, Maurice Pagnucco, and Pavlos Peppas. Dynamic belief revision operators. Artificial Intelligence, 146(2):193 228, 2003. [Nayak et al., 2005] Abhaya C. Nayak, Randy Goebel, Mehmet A. Orgun, and Tam Pham. Iterated belief change and the Levi Identity. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics, 7.-12. August 2005, 2005. [Peppas, 2004] Pavlos Peppas. The Limit Assumption and Multiple Revision. Journal of Logic and Computation, 14(3):355 371, 2004. [Spohn, 1988] Wolfgang Spohn. Ordinal conditional functions. a dynamic theory of epistemic states. In W. L. Harper and B. Skyrms, editors, Causation in Decision, Belief Change, and Statistics, vol. II. Kluwer Academic Publishers, 1988. [Spohn, 2010] Wolfgang Spohn. Multiple contraction revisited. EPSA Epistemology and Methodology of Science: Launch of the European Philosophy of Science Association, pages 279 288, 2010. [Zhang, 2004] Dongmo Zhang. Properties of iterated multiple belief revision. In Vladimir Lifschitz and Ilkka Niemel a, editors, Logic Programming and Nonmonotonic Reasoning, pages 314 325, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)