Parallel Belief Contraction via
Order Aggregation

The field of belief revision studies the formal rationality constraints that govern the impact of the removal or addition of particular beliefs on an agent’s broader world view. The incorporation of new beliefs is modelled by an operation of “revision”, while the removal of beliefs is modelled 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 alchourron1985logic 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 alchourron1985logic , serial partial meet base contraction Hansson1992aa and serial kernel contraction KCH .

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 DelgrandeJames2012PbrR , which focuses on revision, and SpohnPC , 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 darwiche1997logic for iterated serial revision and the postulates of Chopra et al chopra2008iterated for iterated serial contraction, as well as various strengthenings thereof.

Regarding single-step parallel change, single-step parallel revision has been plausibly claimed to reduce to single-step serial revision (see DelgrandeJames2012PbrR ). 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 https://doi.org/10.1111/j.1755-2567.1989.tb00725.x , FurHanSMC and DBLP:journals/jphil/ReisF12 ), with an interesting special case studied in DBLP:journals/jphil/FermeR12 , DBLP:journals/rsl/FermeR13 and DBLP:journals/amai/ReisPF16 ; there also exists an extension to the parallel case of serial kernel contraction (see DBLP:journals/sLogica/FermeSS03 ). 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 $n$-ary case of a binary order aggregation method–“TeamQueue” aggregation–proposed in another context by Booth & Chandler DBLP:journals/ai/BoothC19 . 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 single-step 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 Furhmann & Hansson’s, 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. In order to improve readability, proofs of propositions and theorems have been relegated to the appendix.

In the standard model of belief change, the beliefs of an agent are represented by a belief state $\Psi$. The latter determines a belief set $[\Psi]$, a deductively closed set of sentences, drawn from a propositional, truth-functional, finitely-generated language $L$. The set of classical logical consequences of $S\subseteq L$ will be denoted by $\mathrm{Cn}(S)$. When $S$ is simply the singleton set $\{C\}$, we write $\mathrm{Cn}(C)$. The set of $2^{n}$ 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 $\ast$ and contraction $\div$, 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.

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 non-empty finite indexed set $S=\{A_{1},\ldots,A_{n}\}$ of sentences in $L$ (with set of indices $I=\{1,\ldots,n\}$). We shall denote parallel contraction by and assume that it subsumes $\div$ as the special case in which the input is a singleton set, setting $[\Psi\odiv\{A\}]=[\Psi\div A]$. We use $\bigwedge S$ to denote $A_{1}\wedge\ldots\wedge A_{n}$ and $\neg S$ to denote $\{\neg A\mid A\in 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 HANSSONS.O1993RtLI ): 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 $\bigvee S$ of the members of $S$, so that, for example, $\Psi\odiv\{A,B\}=\Psi\div A\vee B$). Certainly, due to the logical closure of belief sets, removing $A\vee B$ would involve removing both $A$ and $B$, as contraction by $\{A,B\}$ requires. However, as pointed out, for instance, in FurHanSMC , 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\vee B$. From this observation, it follows that we cannot generally identify the belief sets $[\Psi\odiv\{A,B\}]$ and $[\Psi\div A\vee B]$ and hence a fortiori, that we cannot generally identify the belief states $\Psi\odiv\{A,B\}$ and $\Psi\div A\vee B$. Furthermore, more generally, as Fuhrmann notes in Fuhrmann1996-FUHAEO , 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 SpohnPC , as it follows from his more general approach to iterated parallel contraction.

Beyond this rationale, we note that $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$ has several further attractive properties. First of all, if one assumes the basic AGM postulates for serial contraction, i.e. $(\mathrm{K}{1}^{\scriptscriptstyle\div})$ to $(\mathrm{K}{6}^{\scriptscriptstyle\div})$, it yields a parallel contraction operator that satisfies plausible generalisations of these:

It is worth noting that $(\mathrm{K}{6})$ differs from the following alternative generalisation of $(\mathrm{K}{6}^{\scriptscriptstyle\div})$: If $\mathrm{Cn}(S_{1})=\mathrm{Cn}(S_{2})$, then $[\Psi\odiv S_{1}]=[\Psi\odiv S_{2}]$. Indeed, as Fuhrmann & Hansson (FurHanSMC, , pp. 52) point out, the latter is actually inconsistent with the conjunction of $(\mathrm{K}{3})$ and $(\mathrm{K}{4})$. To see why, where $p$ and $q$ are atomic sentences, let $[\Psi]=\mathrm{Cn}(p)$. Then we have $[\Psi\odiv\{p\wedge q\}]=[\Psi]$, by $(\mathrm{K}{3})$, since $p\wedge q\notin[\Psi]$, but $[\Psi\odiv\{p\wedge q,p\}]\neq[\Psi]$, by $(\mathrm{K}{4})$, even though $\mathrm{Cn}(\{p\wedge q\})=\mathrm{Cn}(\{p\wedge 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 $(\mathrm{K}{1}^{\scriptscriptstyle\div})$-$(\mathrm{K}{8}^{\scriptscriptstyle\div})$:

Although Fuhrmann & Hansson propose the above two principles as “very tentative generalisations” of $(\mathrm{K}{7}^{\scriptscriptstyle\div})$ and $(\mathrm{K}{8}^{\scriptscriptstyle\div})$, 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 $(\mathrm{K}{7}^{\scriptscriptstyle\div})$ and $(\mathrm{K}{8}^{\scriptscriptstyle\div})$. The following are obvious suggestions:

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, SpohnPC is the only existing proposal regarding how this issue should be handled. However, although Spohn’s suggestion has the desirable feature of entailing $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, it relies heavily on his ranking theoretic formalism, the foundations of which still require a careful assessment ChandlerSpohn .

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 $[\Psi]$ and $[\Psi\ast\neg A]$). In the iterated case, we faced the task of aggregating a number of conditional belief sets ($[\Psi]_{>}$ and $[\Psi\ast\neg A]_{>}$) or, equivalently, TPOs ($\preccurlyeq_{\Psi}$ and $\preccurlyeq_{\Psi\ast\neg 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.

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 DBLP:journals/ai/BoothC19 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,\ldots,n\}$, a tuple $\mathbf{P}=\langle\preccurlyeq_{i}\rangle_{i\in I}$ of TPOs over $W$ known as “profiles” and an aggregation function $\oplus$ 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,\ldots,n^{j}\}$ and $\mathbf{P}^{j}=\langle\preccurlyeq^{j}_{i}\rangle_{i\in I^{j}}$. When the identity of $\mathbf{P}$ is clear from context, we shall write $\oplus$ to denote $\oplus(\mathbf{P})$ and $x\preccurlyeq_{\oplus}y$ to denote $\langle x,y\rangle\in\oplus$, or simply $x\preccurlyeq_{\oplus}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${}^{\scriptscriptstyle\div}_{\scriptscriptstyle>}$)) clashed with the AGM postulates. This result is in fact related to a more general observation, made in lehmann1992does , 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 $[\preccurlyeq_{\oplus}]_{>}$ be rational or $\preccurlyeq_{\oplus}$ be a TPO:

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

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

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) Furhmann 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 DBLP:journals/ai/BoothC20 or ranking functions (see Spohn2009-SPOASO 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.

Looking 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 only significant work being 10.1007/978-3-540-24609-1_27 and DelgrandeJames2012PbrR (resinamultiplesurvey survey work on the single-step case).

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 would need generalisation 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.

See 1

Regarding $(\mathrm{K}{2})$: Assume $C\in[\Psi\odiv S]$. We need to show that $C\in[\Psi]$. By $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, $C\in\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]$. By $(\mathrm{K}{2}^{\scriptscriptstyle\div})$, we then recover $C\in[\Psi]$.

Regarding $(\mathrm{K}{3})$: Assume $S\cap[\Psi]=\varnothing$. By $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, we simply need to show that $\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]=[\Psi]$. From $S\cap[\Psi]=\varnothing$, we have, for all $i$ such that $1\leq i\leq n$, $A_{i}\notin[\Psi]$. By $(\mathrm{K}{3}^{\scriptscriptstyle\div})$, it then follows that, for all $i$ such that $1\leq i\leq n$, $[\Psi\div A_{i}]=[\Psi]$. Hence $\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]=[\Psi]$, as required.

Regarding $(\mathrm{K}{4})$: Assume that $A_{i}\in S-\mathrm{Cn}(\varnothing)$. By $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, we need to show that $A_{i}\notin\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]$. This immediately follows from $(\mathrm{K}{4}^{\scriptscriptstyle\div})$, which ensures that $A_{i}\notin[\Psi\div A_{i}]$.

Regarding $(\mathrm{K}{5})$: Assume $S\subseteq[\Psi]$. By $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, we need to show that $[\Psi]\subseteq\mathrm{Cn}(\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]\cup\{S\})$. By $(\mathrm{K}{5}^{\scriptscriptstyle\div})$, we have, for all $i$ such that $1\leq i\leq n$, $[\Psi]\subseteq\mathrm{Cn}([\Psi\div A_{i}]\cup\{A_{i}\})$. Let $B\in L$ be such that $[\Psi]=\mathrm{Cn}(B)$ (by the finiteness of $L$, we know that such $B$ exists). By the Deduction Theorem for $\mathrm{Cn}$, for all $i$ such that $1\leq i\leq n$, we have $A_{i}\rightarrow B\in[\Psi\div A_{i}]$. By $(\mathrm{K}{1}^{\scriptscriptstyle\div})$, for all $i$ such that $1\leq i\leq n$, we then have $\bigwedge S\rightarrow B\in[\Psi\div A_{i}]$ and hence $\bigwedge S\rightarrow B\in\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]$. It then follows from this that $B\in\mathrm{Cn}(\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]\cup\{S\})$ and hence that $[\Psi]\subseteq\mathrm{Cn}(\bigcap_{1\leq i\leq n}[\Psi\div A_{i}]\cup\{S\})$, as required.

Regarding $(\mathrm{K}{6})$: Assume that $\forall A^{1}\in S^{1}$, $\exists A^{2}\in S^{2}$ such that $\mathrm{Cn}(A^{1})=\mathrm{Cn}(A^{2})$, and vice versa. By $(\mathrm{Int}_{\scriptscriptstyle\mathrm{b}})$, we need to show that $\bigcap_{1\leq i\leq n}[\Psi\div A^{1}_{i}]=\bigcap_{1\leq i\leq m}[\Psi\div A^{2}_{i}]$. By $(\mathrm{K}{6}^{\scriptscriptstyle\div})$, we know that, $\forall A^{1}\in S^{1}$, $\exists A^{2}\in S^{2}$ such that $[\Psi\div A^{1}]=[\Psi\div A^{2}]$. From this, it follows that $\bigcap_{1\leq i\leq n}[\Psi\div A^{1}_{i}]\supseteq\bigcap_{1\leq i\leq m}[\Psi\div A^{2}_{i}]$. But by the same postulate, we also know that $\forall A^{2}\in S^{2}$, $\exists A^{1}\in S^{1}$ such that $[\Psi\div A^{2}]=[\Psi\div A^{1}]$. The converse inclusion then holds and we recover the required result.