Parallel Belief Contraction via Order Aggregation

1 Introduction

The field of belief revision studies the rationality constraints that govern the impact of the addition or removal of particular beliefs on an agent's broader world view. The addition of new beliefs is modelled by an operation of "revision" and the removal of beliefs by an operation of "contraction".

Initial work in this area was restricted to studying the repercussions of (i) a single episode of change (single-step change), involving the removal or addition of (ii) a single item of information (serial change). In this narrow context, the AGM postulates presented in [Alchourr´on et al., 1985] are widely accepted to provide adequate constraints on both contraction and revision, although belief change operations whose characteristic axioms fall considerably short of full AGM have also been studied extensively, including serial partial meet contraction [Alchourr´on et al., 1985], serial partial meet base contraction [Hansson, 1992] and serial kernel contraction [Hansson, 1994].

The focus was later broadened. Two new aspects were considered: (iii) the behaviour of beliefs under successive changes (iterated change), and (iv) their response to the simultaneous removal or addition of multiple items of information (parallel change). With the exceptions of [Delgrande and Jin, 2012], which focuses on revision, and [Spohn, 2010], which tackles contraction, these generalisations have largely been carried out separately, with research focusing either on iterated serial change or on single-step parallel change.

Work on iterated serial change notably saw the introduction of the postulates of Darwiche & Pearl [1997] for iterated serial revision, the postulates of Chopra et al [2008] for iterated serial contraction, and various strengthenings thereof.

Regarding single-step parallel change, single-step parallel revision has been plausibly claimed to reduce to singlestep serial revision (see [Delgrande and Jin, 2012]). Work on single-step parallel change has therefore focussed on the less obvious case of contraction. For reasons that are not entirely clear, however, the emphasis here has been on extending to the parallel case serial contraction operations that do not satisfy full AGM. We find proposals for partial meet parallel contraction (see [?], [Fuhrmann and Hansson, 1994] and [Reis and Ferm´e, 2012]), with an interesting special case studied in [Ferm´e and Reis, 2012], [Ferm´e and Reis, 2013] and [Reis et al., 2016]; there also exists an extension to the parallel case of serial kernel contraction (see [Ferm´e et al., 2003]). In contrast, little attention has been paid to extending fully AGM-compliant operations.

This article aims to fill a substantial gap by extending fully AGM-compliant serial contraction not only to the single-step parallel case but to the iterated parallel case as well. It achieves this goal by employing a generalisation to the nary case of a binary order aggregation method-"TeamQueue" aggregation-proposed in another context by Booth & Chandler [2019]. An axiomatic characterisation of this generalisation is provided, which will be of interest independently of the question of parallel change.

The plan of the paper is as follows. In Section 2, we recapitulate basic notions of serial belief contraction, both singlestep and iterated. Section 3 turns to the parallel case, restricting attention to single-step parallel contraction due to the absence of relevant work on the iterated case. There, we show that a particularly plausible approach to this issue, the "intersective" approach, validates a number of plausible principles due to Fuhrmann & Hansson, as well as two further ones that we introduce here. This is an important result, since, collectively, these principles generalise to the parallel case the AGM postulates for serial contraction. In Section 4, we outline and discuss the n-ary generalisation of TeamQueue aggregation, covering its construction, semantic and syntactic characterisations, noteworthy properties, and connection to Lehmann & Magidor's concept of rational closure. Section 5 then puts n-ary TeamQueue aggregation to work in the construction of iterated parallel contraction operators, generalising the intersective approach to the iterated case. Section 6 concludes with open questions and suggestions for future research, including the potential broader applications of TeamQueue aggregation. Due to space limitations, proofs are provided in a longer version of the paper, which can be accessed online at https://arxiv.org/abs/2501.13295.

2 Serial Belief Contraction

In the standard model of belief change, the beliefs of an agent are represented by a belief state Ψ. The latter determines a belief set [Ψ], a deductively closed set of sentences, drawn from a propositional, truth-functional, finitely-generated language L. The set of classical logical consequences of S ⊆ L will be denoted by Cn(S). When S is simply the singleton set {C}, we write Cn(C). The set of 2n propositional worlds or valuations will be denoted by W, and the set of models of a given sentence A by [[A]].

The core of this model includes two "serial" belief change operations, revision ∗ and contraction ÷, both mapping a pair consisting of a state and a single input sentence onto a state. Revision models the incorporation of the input into the agent's beliefs, while contraction models its removal. While earlier discussions of the model focussed on single-step serial belief change, i.e. the change brought about by a single episode of revision or contraction by a single sentence, attention shifted to iterated serial change, involving a succession of episodes of serial revision or contraction.

2.1 Single-Step Serial Change

In the case of single-step serial belief change, it is widely accepted that the AGM postulates, introduced in [Alchourr´on et al., 1985], provide an adequately strong set of rationality constraints. In relation to contraction, these are:

The first six principles are known as the "basic" AGM postulates. The last two are known as the "supplementary" ones. Analogous principles regulate single-step serial revision. We call a serial contraction operator that satisfies (K1÷)-(K8÷) an AGM contraction operator.

A principle known as the Harper identity [Harper, 1976] allows us to define single-step serial contraction in terms of single-step serial revision.

The motivation for this principle is straightforward. The idea is that, in contracting by A, we are opening our minds to the possibility that A is false. So we must retract anything that would be no longer endorsed, had one come to believe that this possibility is an actuality. This, however, is the only modification to our prior beliefs that we should make, as we should retract nothing further and introduce nothing new.

A representation theorem connects contraction operators compliant with the full set of AGM postulates to total preorders (TPOs), i.e. reflexive, complete and transitive binary relations, over sets of propositional worlds. More specifically each Ψ can be associated with a TPO ≼Ψ over W, such that min(≼Ψ÷A, W) = min(≼Ψ, W) ∪min(≼Ψ, [[¬A]]) (see [Caridroit et al., 2017]).

The information conveyed by the TPOs associated with belief states can be equivalently captured by conditional belief sets [Ψ]> := {A > B | B ∈ [Ψ∗A]} or again nonmonotonic consequence relations |∼Ψ= {⟨A, B⟩ | A > B ∈ [Ψ]>}. The AGM postulates ensure that such belief sets or consequence relations are "rational" (in the sense of [Lehmann and Magidor, 1992]) and "consistency preserving" (see [Makinson and G¨ardenfors, 1991]).

These results mean that the various principles that we shall be discussing can typically be presented in several equivalent alternative formats, where we will use subscripts to distinguish between these, with the non-subscripted version of the name generically referring to the principle regardless of presentation. The names of principles framed in terms of TPOs will be subscripted with ≼. It will sometimes be useful to present principles in terms of minimal sets, denoting the ≼- minimal subset of S ⊆ W, that is {x ∈ S | ∀y ∈ S, x ≼ y}, by min(≼, S). We will use the subscript min to indicate presentation in this format. Similarly, a principle cast in terms of conditional belief sets will be subscripted with >. Where required for disambiguation, the names of principles presented in terms of belief sets will include the subscript b. Superscripts will be used to indicate the particular operation, such as ∗ or ÷, whose behaviour a given postulate constrains.

2.2 Iterated Serial Contraction

When it comes to sequences of serial contraction, the basic postulates of Chopra et al [2008] remain largely uncontroversial. While these have been supplemented in various ways, few additions have been uncontested and we shall not be discussing them here. In the case of contraction, supplementary postulates have yielded moderate, priority (see [Nayak et al., 2007]), and restrained (introduced in [Chandler and Booth, 2023]) contraction operators. But these operations are alike in identifying, for the purposes of belief change, belief states with TPOs, a view criticised in [Booth and Chandler, 2017].

The postulates of Chopra et al can be presented either "syntactically" in terms of belief sets or "semantically" in terms of TPOs. Syntactically, they are given by:

• (C3÷b ) If ¬A ∈ [Ψ ∗ B] then ¬A ∈ [(Ψ ÷ A) ∗ B]
• (C4÷b ) If A ̸∈ [Ψ ∗ B] then A ̸∈ [(Ψ ÷ A) ∗ B] and semantically by:

The question of how to extend the Harper Identity to the iterated case was considered in [Booth and Chandler, 2019]. We briefly recapitulate this contribution here, since it is relevant to what follows. In that paper, it was first noted that the naive suggestion of simply recasting (HI) in terms of conditional belief sets.

(equivalently, in terms of non-conditional belief sets: [(Ψ÷ A) ∗ B] = [Ψ ∗ B] ∩ [(Ψ ∗ ¬A) ∗ B]) is a non-starter: on pains of placing undue restrictions on the space of permissible conditional belief sets, the left-to-right inclusion in the naive suggestion was shown to be jointly inconsistent with several of the AGM postulates for serial revision and contraction.

A proposal was then made, involving a binary TPO aggregation function ⊕, mapping pairs of input TPOs onto a single aggregate output TPO:

A family of binary aggregators, the "TeamQueue" (TQ) family, was argued to be appropriate for this job, with one specific member of this family, the "Synchronous TQ" function ⊕STQ, being singled out as particularly promising. It was shown that, when ⊕ is taken to be a TQ aggregation function, (iHI÷≼) allows for the derivation of several important principles, including (HI), which comes out as a special case of (iHI÷≼), as well as (C1÷b ) to (C4÷b ) above, which are derivable from the corresponding Darwiche-Pearl postulates for iterated serial revision.

Taking ⊕ to specifically correspond to ⊕STQ was argued to yield further desirable theoretical results. In particular, it delivers an appealing syntactic version of (iHI÷≼) based on the rational closure Clrat(Γ) of a set of conditionals Γ, or equivalently of a non-monotonic consequence relation (see [Lehmann and Magidor, 1992]):

In other words, the conditional belief set obtained after contraction by A corresponds to the rational closure of the intersection of the prior conditional belief set with the conditional belief set obtained after revision by ¬A. This principle is attractive, due to the fact that Clrat(Γ) has been argued to correspond to the most conservative way of extending a consequence relation (equivalently: conditional belief set) to a rational consequence relation (equivalently: conditional belief set). (iHI), therefore, parsimoniously fixes the issue noted above in relation to (NiHI), which sometimes resulted in a non-rational conditional belief set. We return to TQ aggregation below, in Section 4.

3 Background on Parallel Belief Contraction

While the "serial" model takes single sentences as inputs for contraction or revision, it has been suggested that this imposes unrealistic limitations on the kind of change that can be modelled. The problem of so-called "parallel" (aka "package" or "multiple") contraction is to compute the impact, on an agent's beliefs, of the simultaneous removal of a nonempty finite indexed set S = {A1, . . . ,An} of sentences in L (with set of indices I = {1, . . . , n}). We shall denote parallel contraction by c and assume that it subsumes ÷ as the special case in which the input is a singleton set, setting [Ψ c {A}] = [Ψ ÷ A]. We use ∧ S to denote A1 ∧ . . . ∧ An and ¬S to denote {¬A | A ∈ S}.

Considerations of parsimony motivate defining parallel contraction in terms of serial contraction. Regarding the single-step case, a number of the more straightforward proposals have been noted to be problematic.

First, we have the identification of parallel contraction by a set S with a sequence of serial contractions by the members of S. This runs into problems due to a failure of commutativity (see [Hansson, 1993]): different orders of operations can yield different outcomes, and no principled way seems to exist to privilege one order over another.

Second, there is the identification of parallel contraction by S with a single serial contraction by some truth functional combination of the members of S (such as the disjunction ∨ S of the members of S, so that, for example, Ψ c {A,B} = Ψ ÷ A ∨ B). Certainly, due to the logical closure of belief sets, removing A∨B would involve removing both A and B, as contraction by {A, B} requires. However, as pointed out, for instance, in [Fuhrmann and Hansson, 1994], this would be too drastic an operation: clearly, one can simultaneously retract one's commitments both to A and to B without thereby retracting one's commitment to A∨B. From this observation, it follows that we cannot generally identify the belief sets [Ψ c {A,B}] and [Ψ ÷ A ∨ B] and hence a fortiori, that we cannot generally identify the belief states Ψ c {A, B} and Ψ ÷ A ∨ B. Furthermore, more generally, as Fuhrmann [1997] notes, there is no truth-functional combination of A and B that would do the job either.

A more promising solution is the "intersective" approach, which identifies the belief set obtained by parallel contraction by S with the intersection of the belief sets obtained by serial contraction by the members of S. This proposal has been endorsed by Spohn [2010], as it follows from his more general approach to iterated parallel contraction.

This suggestion owes its plausibility to the same kind of considerations as the formally related Harper Identity did (see Subsection 2.1). In contracting by a set of sentences, the thought goes, we ought not believe anything that any of the individual contractions would preclude us from believing. But this is the only modification to our prior beliefs that we should make. In particular, we should retract nothing further and introduce nothing new.

Beyond this rationale, we note that (Intcb ) has several further attractive properties. First of all, if one assumes the basic AGM postulates for serial contraction, i.e. (K1÷) to (K6÷), it yields a parallel contraction operator that satisfies plausible generalisations of these:

Theorem 1. Let c be a parallel contraction operator such that, for some serial contraction operator ÷ that satisfies (K1÷)-(K6÷), c and ÷ jointly satisfy (Intcb ). Then c satisfies:

• (K1c) Cn([ΨcS]) ⊆ [ΨcS]
• (K2c) [Ψ c S] ⊆ [Ψ]
• (K3c) If S ∩ [Ψ] = ∅, then [Ψ c S] = [Ψ]
• (K4c) ∀A ∈ S, if A /∈ Cn(∅), then A /∈ [Ψc S]
• (K5c) If S ⊆ [Ψ], then [Ψ] ⊆ Cn([Ψ c S] ∪ {S})
• (K6c) If, ∀A1 ∈ S1, ∃A2 ∈ S2 s.t. Cn(A1) = Cn(A2), and vice versa, then [ΨcS1] = [ΨcS2]

These postulates were all endorsed by Fuhrmann & Hansson [1994] as plausible generalisations of their serial counterparts, with the exception of (K4c). Their own generalisation of (K4÷) is indeed slightly weaker, although the difference only pertains to the handling of certain limiting cases.

It is worth noting that (K6c) differs from the following alternative generalisation of (K6÷): If Cn(S1) = Cn(S2), then [ΨcS1] = [ΨcS2]. Indeed, as Fuhrmann &Hansson [1994, p. 52] point out, the latter is actually inconsistent with the conjunction of (K3c) and (K4c). To see why, where p and q are atomic sentences, let [Ψ] = Cn(p). Then we have [Ψ c {p ∧ q}] = [Ψ], by (K3c), since p ∧ q /∈ [Ψ], but [Ψc{p∧q, p}] ̸= [Ψ], by (K4c), even though Cn({p∧q}) = Cn({p ∧ q, p}).

Fuhrmann & Hansson propose a pair of postulates constraining the relation between contractions by sets standing in a subset relation to one another. The first of these is satisfied by the intersective approach, while the second is not, even assuming (K1÷)-(K8÷):

Proposition 1. (a) Let c be a parallel contraction operator such that, for some serial contraction operator ÷, c and ÷ jointly satisfy (Intcb ). Then c satisfies:

(b) There exist a parallel contraction operator c and a serial contraction operator ÷ that jointly satisfy (Intcb ) but are such that the following principle fails:

This is exactly as things should be, since, while the first postulate is plausible, the second seems quite dubious:

Example 1. I initially believe that Alfred and Barry are both guilty (A,B ∈ [Ψ]) but would entirely suspend judgment on the situation if I gave up on that belief (so that I would endorse no non-tautological combination of A and B in [Ψc{A∧B}]). If I gave up my belief that Barry is guilty, I would no longer believe that Alfred is guilty (A /∈ [Ψc{B}]). However, while, in that situation, I would still believe that, if Barry is guilty, then Alfred is so too (B → A ∈ [Ψc {B}]), I would no longer believe this if I simultaneously gave up on both the belief that Barry is guilty and the belief that Alfred is (B → A /∈ [Ψ c {A, B}]).

If we take S1 and S2 to be respectively given by {A} and {B}, this perfectly rationally acceptable situation runs contrary to the prescription made in the second postulate.

Although Fuhrmann & Hansson propose the above two principles as "very tentative generalisations" of (K7÷) and (K8÷), respectively, these cannot really be "generalisations" in any obvious sense of the term, since the corresponding AGM postulates do not seem to be recoverable as special cases. This then raises the question of whether there exist any promising candidates for generalisations of (K7÷) and (K8÷). The following are obvious suggestions:

Again, the intersective approach delivers here:

Theorem 2. Let c be a parallel contraction operator such that, for some serial contraction operator ÷, c and ÷ jointly satisfy (Intcb ). Then, (i) if ÷ satisfies (K7÷), then c satisfies (K7c) and, (ii) if ÷ satisfies (K8÷), then c satisfies (K8c).

Despite its considerable appeal, (Intcb ) has been explicitly rejected by Fuhrmann & Hansson [1994, pp. 51-57] due to its entailing the following monotonicity principle: If S1 ⊆ S2, then [Ψc S2] ⊆ [Ψc S1]. This principle is not satisfied by their preferred constructive approach, which is governed by a remarkably weak set of principles that falls strictly short of (K1c)-(K8c). However, as Spohn [2010] has noted, in the absence of a convincing, independent story as to why parallel contraction should be be governed by principles no stronger than the ones they endorse, this remains insufficient ground for criticism.

So much for single-step parallel contraction. What about the iterated case? Surprisingly, next to no work has been carried out on this issue. Indeed, to the best of our knowledge, [Spohn, 2010] is the only existing proposal regarding how this issue should be handled. However, although Spohn's suggestion has the desirable feature of entailing (Intcb ), it relies heavily on his ranking theoretic formalism, the foundations of which still require a careful assessment [Chandler, 2017].

In what follows, we shall propose a more straightforward way of extending the intersective approach to the iterated case. Our key insight is that the situation here is analogous to the one faced in relation to extending the Harper Identity. In that situation, in the single-step case, we also had a proposal involving an intersection of belief sets (the sets [Ψ] and [Ψ∗¬A]). In the iterated case, we faced the task of aggregating a number of conditional belief sets ([Ψ]> and [Ψ∗¬A]>) or, equivalently, TPOs (≼Ψ and ≼Ψ∗¬A). The TPO aggregation procedure used in that context, however, was only characterised for pairs of TPOs. In the present context, we will need to aggregate arbitrarily large finite sets of TPOs.

4 TeamQueue Aggregation

In this section, we offer generalisations to the n-ary case of the construction and characterisation results of the family of binary aggregators studied in [Booth and Chandler, 2019] and two of their noteworthy special cases.

The formal framework involves the following: a finite set of alternatives W, a finite non-empty set of indices I = {1, . . . , n}, a tuple P = ⟨≼i⟩i∈I of TPOs over W known as "profiles" and an aggregation function ⊕ mapping all possible profiles onto single TPOs over W. When we shall need to refer to multiple profiles and their constituent relations, we shall use superscripted roman numerals, writing I j = {1, . . . , nj } and Pj = ⟨≼ji ⟩i∈I j . When the identity of P is clear from context, we shall write ⊕ to denote ⊕(P) and x ≼⊕ y to denote ⟨x, y⟩ ∈ ⊕, or simply x ≼⊕ y.

As was mentioned above, TQ aggregation was originally introduced after observing the fact that a particular identity involving the intersection of two conditional belief sets (namely (NiHI÷>)) clashed with the AGM postulates. This result is in fact related to a more general observation, made in [Lehmann and Magidor, 1992], that the intersection of two sets of rational conditionals needn't itself be rational. In other words, the following naive principles of "Conditional Intersection" make poor suggestions, if we require that [≼⊕]> be rational or ≼⊕ be a TPO:

The following example makes the point:

Example 2. Let W = {x, y, z, w} and ≼1 and ≼2 be respectively given by: x ≺1 {w, z} ≺1 y and z ≺2 y ≺2 x ≺2 w.

(CI⊕min ) has the consequence that ≼⊕ isn't a TPO. Indeed, min(≼1,W) ∪ min(≼2,W) = {x, z}. So by (CI⊕min ), we have z ≼⊕ x and x ≺⊕ w. On the assumption that ≼⊕ is a TPO, this gives us z ≺⊕ w. However, from the fact that min(≼1, {w, z}) ∪ min(≼2, {w, z}) = {w, z}, we have, by (CI⊕min ), w ≼⊕ z. Contradiction.

Similarly, (CI⊕>) has the consequence that [≼⊕]> isn't rational. First, from the fact that (x∨w) > ¬w ∈ [≼1]> ∩ [≼2 ]>, by (CI⊕>), we have: (i) (x ∨ w) > ¬w ∈ [≼⊕]>. Second, from the fact that (x ∨ z) > ¬z /∈ [≼2]>, by (CI⊕>) it follows that :(ii) (x ∨ z) > ¬z /∈ [≼⊕]>. Finally, from (w ∨ z) > ¬w /∈ [≼1]>, by the same principle again: (iii) (w∨z) > ¬w /∈ [≼⊕]>. However, taken together, (i)-(iii) directly violate a principle that is valid for rational conditionals (see [Lehmann and Magidor, 1992, Lem. 17]).

4.1 Construction

The n-ary version of the aggregation method is constructively defined in a very similar way to that in which the original binary case was. The definition makes use of the representation of a TPO ≼ by means of an ordered partition ⟨S1, S2, . . . Smi ⟩ of W, defined inductively as follows: S1 = min(≼,W) and, for i ≥ 2, Si = min(≼, ⋂j<i Sc j ), where Sc is the complement of S. This representation grounds the notion of the absolute rank r(x) of an alternative x, with respect to ≼. The absolute rank of an alternative is given by its position in the ordered partition, so that r(x) is such that x ∈ Sr(x) (in cases in which the TPO is indexed, as in ≼i, we write ri(x)). With this in mind, we can offer:

Definition 1. ⊕ is a TeamQueue (TQ) aggregator iff, for each profile P with index set I, there exists a sequence ⟨aP(i)⟩i∈N such that ∅ ̸= aP(i) ⊆ I 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.

The procedure takes the input TPOs and processes them step by step to form a new TPO. At the first step, it removes the minimal elements of one or more of the input TPOs (which TPOs these are depends on the specifics of the procedure, i.e. on the value(s) in aP(i) for the relevant step i) and places them in the minimal rank of the output TPO, before deleting any copies of these elements that might remain in the input TPOs. At each step, it then repeats the process using the remainders of the input TPOs, until all input TPOs have been processed entirely. 1

Of particular interest is the member of the TQ aggregator family that processes the TPOs "synchronously", so that, at each step, the minimal elements of all TPOs are included in the relevant output rank:

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

Another noteworthy TQ aggregator is the "MinRank" aggregator, whose binary version is briefly discussed in footnote 11 of [Booth and Chandler, 2019] and shown there to be distinct from ⊕STQ:

Definition 3. The MinRank aggregator ⊕min is the aggregator s.t. x ≼⊕ y iff argmini∈I ri(x) ≤ argmini∈I ri(y).

While ⊕min assigns to x the minimal rank it received among the inputs, ⊕STQ assigns to x the minimal rank it can receive within the constraints imposed by TQ aggregation. The following example illustrates the way in which these aggregators can yield different outputs:

Example 3. Let P = ⟨≼1, . . . , ≼4⟩, where: {w} ≺1 {z} ≺1 {x, y}, {w} ≺2 {y} ≺2 {x, z}, {z} ≺3 {w} ≺3 {x, y}, and {z} ≺4 {y} ≺3 {x,w}. We have ⊕STQ given by {w, z} ≺⊕STQ {x, y} but ⊕min is given by {w, z} ≺⊕min {y} ≺⊕min {x}. See Figure 1.

4.2 Characterisation

The family of n-ary TQ aggregators can be characterised in terms of minimal sets as follows:

Theorem 3. ⊕ is a TQ aggregator iff it satisfies the following "factoring" property:

1 In [Booth and Chandler, 2019], which simply discussed the binary case, the additional requirement that aP(1) = {1, 2} was imposed. We do not require the n-ary generalisation of this requirement (i.e. aP(1) = {1, . . . , n}).

This is a weakening of the principle (CI⊕min ) discussed above, which we have seen cannot hold in full.

The characterisation can also be given in terms of a property requiring that no element of W can improve its relative position with respect to all input orderings:

Proposition 2. (F⊕min ) is equivalent to

(F⊕≼) Assume that x1 to xn are s.t. xi ≼i y. Then there exists j ∈ I s.t.

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

Theorem 4. ⊕STQ is the only aggregator that satisfies both (F⊕≼) and the following 'Parity' constraint:

This principle can also be framed in terms of minimal sets:

Proposition 3. (PAR⊕≼) is equivalent to:

The possibility of characterising ⊕min in similar terms remains an open question.

4.3 Further Properties

Like its binary special case, n-ary TQ aggregation satisfies several Pareto-style properties. In particular, we note that:

Proposition 4. (F⊕≼) entails the following two properties:

(SPU+⊕≼) Assume that, for all i ∈ I, xi ≺i y. Then there exists j ∈ I s.t. xj ≺⊕ y

(WPU+⊕≼) Assume that, for all i ∈ I, xi ≼i y. Then there exists j ∈ I s.t. xj ≼⊕ y These properties (SPU+⊕≼) and (WPU+⊕≼) can be equivalently be framed in terms of minimal sets, as follows:

Proposition 5. (SPU+⊕≼) and (WPU+⊕≼) are respectively equivalent to:

(SPU+⊕≼) and (WPU+⊕≼) generalise the well-known Social Choice properties of Weak Pareto and Pareto Weak Preference, which can be respectively given as:

(SPU⊕≼) and (WPU⊕≼) can also be formulated in terms of upper and lower bounds on the output relation ≼⊕, jointly corresponding to ⋂i∈I ≼i ⊆ ≼⊕ ⊆ ⋃i∈I ≼i.

4.4 The Connection to Rational Closure

As mentioned above, in Section 2.2, a connection was drawn in [Booth and Chandler, 2019] between the binary special case of ⊕STQ and the concept of the rational closure of a set of conditionals. It was shown, as a corollary of a key theorem, that the conditional belief set corresponding to the TPO obtained by aggregation of two input TPOs is given by the rational closure of the conditional belief sets corresponding to these input TPOs (see their Theorem 3 and Corollary 1). Here we can report that this theorem and its corollary generalise straightforwardly to the n-ary case. Indeed, we first recall the following definition:

Definition 4. Let ⊒ be a binary relation on the set of TPOs over W s.t. ⟨S1, S2, . . . , Sm⟩ ⊒⟨T1, T2, . . . , Tm⟩ iff either (i) Si = Ti for all i = 1, . . . ,m, or (ii) Si ⊃ Ti for the first i s.t. Si ̸= Ti.

The relation ⊒ intuitively partially orders TPOs by what one could call comparative "flatness". So, for instance, where ≼1 and ≼2 are respectively given by {x, y} ≺1 {z,w} and {x, y} ≺2 z ≺2 w and so ≼1 is intuitively "flatter" than ≼2, we have ≼1 ⊒≼2. We can then show the following:

To appreciate the significance of this result, we firstly need to understand how (SPU+⊕≼) translates into the language of conditionals. Recall that this property was shown to be equivalent to a property that we called (UB⊕C ). This second property can be presented in terms of sets of conditionals as stating that the intersection of the sets of conditionals corresponding to the inputs is included in the set of conditionals corresponding to the output:

Theorem 5, then, tells us that ⊕STQ returns the flattest TPO whose corresponding conditional belief set contains the intersection of the conditional belief sets corresponding to the input TPOs. Secondly, we know from Booth & Paris [1998] that the rational closure of a set of conditionals corresponds to the flattest TPO that satisfies it. Finally, putting the above two observations together then leaves us with the following immediate corollary:

5 Parallel Contraction via TeamQueue Aggregation

An obvious suggestion is to define iterated parallel contraction in terms of iterated contraction, using TQ aggregation, as follows:

If we require that aP(1) = {1, . . . , n} when constructing ⊕, as is the case in relation to ⊕STQ, then this yields (Intcb )- 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 Sas its special case for single-step contraction. By Theorem 1 and Theorem 2, we then also recover (K1c)-(K8c).

We can then use the above principle to define the class of TQ parallel contraction operators:

Definition 5. c is a TQ parallel contraction operator if and only if there exists an AGM contraction operator ÷, s.t. c and ÷ jointly satisfy (Aggc≼ ), where ⊕ is a aggregator.

More specific concepts, such as, for example, that of an STQ parallel contraction operator, can be defined in the same manner. As an immediate corollary of Theorem 3, we then also have the following characterisation result:

Corollary 2. c is a TQ parallel contraction operator if and only if it satisfies

The various results of sections 4.2 and 4.3 also have straightforward corollaries, starting with the following immediate joint consequence of Propositions 4 and 5:

Corollary 3. If c is a TQ parallel contraction operator then it satisfies

Importantly, TQ parallel contraction operators satisfy some rather compelling analogues of (C1÷≼)-(C4÷≼):

Proposition 6. Let c be a parallel contraction operator such that, for some AGM contraction operator ÷ and aggregator ⊕, c, ÷ and ⊕ jointly satisfy (Aggc≼ ). Then, if ÷ satisfies (C1÷≼)-(C4÷≼), then c satisfies:

As a corollary of Theorem 4 we can provide a result, pertaining to STQ parallel contraction, framed in terms of the concept of "strong belief", discussed in [Battigalli and Siniscalchi, 2002; Stalnaker, 1996]:

Definition 6. A is strongly believed (s-believed) in Ψ iff (i) A ∈ [Ψ], and (ii) A ∈ [Ψ ∗ B] for all sentences B s.t. A ∧ B is consistent.

This result is the following:

Corollary 4. c is an STQ parallel contraction operator iff it is a parallel contraction operator that also satisfies:

Last but not least, Corollary 1 translates into the following, connecting STQ iterated parallel contraction with rational closure:

Corollary 5. c is an STQ parallel contraction operator iff the following equality holds: [Ψ c {A1, . . . ,An}]> = Clrat(⋂i [Ψ ÷ Ai]>)

6 Concluding Comments

In this paper, we have proposed an original approach to the neglected issue of parallel belief contraction, based on the generalisation of a largely unexplored family of methods for TPO aggregation. The method generalises to the iterated case the "intersective" approach to single-step parallel contraction, which we have demonstrated can derive (i) Fuhrmann and Hansson's parallel versions of the basic AGM postulates for serial contraction and (ii) a pair of new plausible generalisations of the relevant supplementary postulates.

While explicitly regulating two-step parallel change, the approach allows handling indefinitely many parallel contractions when used with serial contraction operators that identify epistemic states with TPOs, such as moderate or priority contraction operators. For models using richer structures than TPOs, such as ordinal intervals [Booth and Chandler, 2020] or ranking functions (see [Spohn, 2009] for an overview, though note that Spohn's proposal does not involve aggregation), a parallel suggestion would require a suitable adaptation of the aggregation method.

Beyond contraction, it would be valuable to investigate whether the TQ approach could be applied to iterated parallel revision. This topic remains under-explored, with the exception of [Zhang, 2004] and [Delgrande and Jin, 2012] (see [Resina and Wassermann, 2020] on the single-step case). An initial step in this direction is [Chandler and Booth, 2025].

Finally, there may be applications of TQ aggregation beyond belief revision, as the aggregation of orderings appears in multiple areas. One might consider whether TQ aggregation could show promise in preference or judgment aggregation, as a method for aggregating conditional judgments, preference aggregation, or judgments regarding comparative magnitudes. However, TQ aggregation as presented here might need generalising for such tasks, as it is currently insensitive to TPO duplication in the profile, meaning profiles with identical members yield the same output. While this property suits parallel iterated belief change, it may not suit these other domains.

Acknowledgments

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