Trust and Belief Revision¶
Introduction¶
Aim is to investigate belief revision methods which output a belief set and a measure of trust in the incoming information source.
Here trust is in relation to expertise: on what sentences do we trust the source has the expertise to give a truthful report? We are not considering trust as reliability in a probabilistic sense, or as a relation between agents
Expertise is represented as a partition over the set of possible states, following [BH18]. States \(x\) and \(y\) are in the same partition cell if the source cannot distinguish between \(x\) and \(y\).
To get an idea of which states the source can distinguish, we need access to historical reports at times when the true state was known. Plan is to proceed in three stages:
For a single source, look at revision methods which take a sequence of historical reports and output a partition.
Extend the framework to allow “current” reports at an unknown state, in addition to historical reports. Revision methods will now output a belief set about the current state in addition to a partition.
Extend to the multi-source setting.
Preliminaries¶
Let \(X\) be an at most countable set of states and \(\O \subseteq 2^X \setminus \{\emptyset\}\) be a collection of observable propositions in \(X\) which is closed under finite intersections.
The set of all partitions of \(X\) is denoted by \(\P\). For \(\pi \in \P\) and \(x \in X\), the unique cell in \(\pi\) containing \(x\) is denoted by \(\pi[x]\). For a set \(A \subseteq X\), we write \(\pi[A] = \bigcup_{x \in A}{\pi[x]}\). Partition refinement is denoted by \(\preceq\), so that \(\pi_1 \preceq \pi_2\) iff \(\pi_1\) refines \(\pi_2\). \((\P, {\preceq})\) is then a lattice.
A proposition \(U \in \O\) is sound for a partition \(\pi \in \P\) and a state \(x\) iff \(x \in \pi[U]\). 1 Write \(\|x, U\| = \{\pi \in \P : U \text{ is sound for } (x, \pi)\}\). We may alternatively say that \((x, U)\) is sound for \(\pi\) etc.
For any set \(A\), we write \(A^* = \bigcup_{n \in \N_0}A^n\) for the set of all finite sequences in \(A\), including the empty sequence (denoted by \(\emptyset\)). For \(\mu, \delta \in A^*\) and \(a \in A\), \(\mu \append a\) denotes the concatenation of \(\mu\) and \(a\), and \(\mu \concat \delta\) denotes the concatenation of the two sequence \(\mu\) and \(\delta\). By \(\set(\mu)\) we denote the contents of a sequence \(\mu\) as a set, i.e. \(\set(\langle(x_1,U_1),\ldots,(x_n,U_n)\rangle) = \{(x_1,U_1),\ldots,(x_n,U_n)\}\).
Trust Sets¶
(TODO: this section should come before mention of partitions)
A trust set \(T\) is a collection of subsets \(T \subseteq 2^X\) which represent the propositions on which we trust an agent. As in the Trust contraction document, trusting an agent on \(A \subseteq X\) means that we would revise beliefs by \(A\) upon receiving \(A\) (i.e. not weaken \(A\) due to any perceived lack in expertise of the agent).
Definition 1
A proposition \(U \in \O\) is sound for a trust set \(T\) and state \(x\) if for every \(A \in T\), \(U \subseteq A\) implies \(x \in A\).
Soundness of \(U\) with respect to \(T\) and \(x\) says that \(U\) is “true” within the expertise of the agent, as given by \(T\). That is, for all logically weaker propositions \(A\) on which the agent is trusted, \(A\) is true at \(x\).
Consider the following properties for a trust set \(T\).
(T1) \(\emptyset, X \in T\)
(T2) If \(A, B \in T\) then \(A \cup B \in T\)
(T1) simply says that the agent is trusted on tautologies and contradictions. (T2) says that the agent is trusted on finite disjunctions if they are trusted on each of the disjuncts. Given both of these properties, the set \(\{A^C \mid A \in T\}\) forms a basis for a topology on \(X\). Let \({\cl_T: 2^X \to 2^X}\) denote the closure operator in this topology. We have the following.
Proposition 1
Suppose \(T\) satisfies (T1) and (T2). Then \(U\) is sound for \(T\) and \(x \in X\) if and only if \(x \in \cl_T{U}\).
Proof.
Note that since \(T\) is closed under finite unions, the set of complements \(\{A^C \mid A \in T\}\) is closed under finite intersections and does indeed form a basis. The open sets in the induced topology on \(X\) are unions of the basis sets. In particular, for each \(A \in T\), \(A^C\) is open and therefore \(A\) is closed.
“if”: Suppose \(x \in \cl_T{U} = \bigcap\{A \subseteq X \mid A \supseteq U, A \text{ closed}\}\). Take any \(A \in T\) with \(U \subseteq A\). Then \(A\) is closed, so \(\cl_T{U} \subseteq A\). Hence \(x \in \cl_T{U}\) implies \(x \in A\). This shows that \(U\) is sound for \(T\) and \(x\).
“only if”: Suppose \(U\) is sound for \(T\) and \(x\). Let \(B\) be any closed set with \(U \subseteq B\). Then \(B^C\) is open, so \(B^C = \bigcup_{i \in I}{A^C_i}\) for some index set \(I\) and sets \(A_i \in T\). Hence \(B = \bigcap_{i \in I}{A_i} \subseteq A_j\) for any \(j \in I\). Since \(A_j \in T\), and \(U \subseteq B \subseteq A_j\), soundness implies \(x \in A_j\). Since \(j\) was arbitrary, \(x \in \bigcap_{i \in I}{A_i} = B\). We have shown that any closed set containing \(U\) also contains \(x\). Hence \(x \in \cl_T{U}\).
Intuitively, this result says that \(U\) is sound for \(T\) and \(x\) if \(x\) is “close” to \(U\), with the notion of closeness coming from \(T\).
Consider some additional properties for \(T\).
(T2’) \(T\) is closed under countable unions
(T3) If \(A \in T\) then \(A^C \in T\)
(T4) There is no sequence \(\langle A_n \rangle_{n \in \N}\), \(A_n \in T\), such that \(A_{n+1} \subset A_n\) for all \(n\)
(T2’) strengthens (T2) to allow infinite (but countable) unions. Note that while \(X\) is countable, \(T\) need not be (e.g. \(T = 2^X\)). Clearly (T2) and (T2’) coincide when \(X\) is finite. (T3) says that trust is symmetric with respect to negations. (T4) is a condition akin to well-foundedness. It says trust has to stop somewhere: there is no infinite chain of stronger and stronger statements on which the agent is trusted.
Proposition 2
If \(T\) satisfies (T1), (T2), (T3) and (T4), there is a partition \(\pi\) of \(X\) such that every \(A \in T\) is a countable union of sets in \(\pi\)
If \(T\) additionally satisfies (T2’), every countable union of sets in \(\pi\) is in \(T\).
Proof.
Set
\[\begin{aligned} \pi &= \min(T \setminus \{\emptyset\}, {\subseteq}) \\ &= \{A \in T \setminus \{\emptyset\} \mid \forall B \in T \setminus \{\emptyset\}: B \not\subset A\} \end{aligned}\]First we show \(\pi\) forms a partition of \(X\). Let \(A, B \in \pi\), \(A \ne B\). By definition of \(\pi\), \(A \not\subseteq B\). Since \(A, B \in T\), (T2) and (T3) give \(A \cap B \in T\). Clearly \(A \cap B \subseteq A\), and in fact \(A \not\subseteq B\) implies \(A \cap B \subset A\). Since \(A \in \pi\), we have \(A \cap B \not\in T \setminus \{\emptyset\}\). But \(A \cap B \in T\), so we must have \(A \cap B = \emptyset\).
Next we show \(\pi\) covers \(X\). Suppose otherwise, and that there is some \(x \notin \bigcup\pi\). Set \(A_0 = X\). By (T1), \(A_0 \in T \setminus \{\emptyset\}\), and clearly \(x \in A_0\). Since \(x \notin \bigcup\pi\), \(A_0 \notin \pi\), and thus there is \(B \in T\) with \(\emptyset \subset B \subset A_0\). Set
\[A_1 = \begin{cases} B,& x \in B \\ A_0 \cap B^c,& x \notin B \end{cases}\]In either case we have \(x \in A_1\), \(A_1 \in T\) (applying (T2) and (T3) in the case \(x \notin B\)) and \(A_1 \subset A_0\) (this is immediate if \(x \in B\); otherwise \(B \ne \emptyset\) ensures the strict inclusion). We can repeat this procedure: since \(A_1\) is a non-empty set in \(T\) containing \(x\) and \(x \notin \bigcup\pi\), \(A_1 \notin \pi\). Hence there is \(B' \in T\) with \(\emptyset \subset B' \subset A_1\). Defining \(A_2\) in terms of \(B'\) as above, we get \(x \in A_2\), \(A_2 \in T\) and \(A_2 \subset A_1\). By induction, there is a sequence \(\langle A_n \rangle_{n \in \N}\) of sets in \(T\) with \(A_{n+1} \subset A_n\) for each \(n\), which directly contradicts (T4).
So \(\pi\) is indeed a partition. It only remains to show that every \(A \in T\) is a countable union of sets in \(\pi\). Let \(A \in T\). We claim that \(A = \bigcup_{x \in A}{\pi[x]}\), where \(\pi[x]\) is the unique set in \(\pi\) containing \(x\). Since \(X\) is countable, \(A\) is countable (or finite) and this is therefore a countable union.
The left to right inclusion is clear, since each \(x\) lies in \(\pi[x]\). For the reverse inclusion, we show that \(\pi[x] \subseteq A\) for each \(x \in A\). Since both \(A, \pi[x] \in T\), we have \(\pi[x] \cap A^C \in T\). Since \(x \in \pi[x] \cap A\), we also have \({\pi[x] \cap A^C \subset \pi[x]}\). But \(\pi[x] \in \pi\), so any strict subset of \(\pi[x]\) in \(T\) must be empty. Hence \(\pi[x] \cap A^C = \emptyset\), i.e. \(\pi[x] \subseteq A\). This completes the proof.
Suppose \(T\) satisfies (T2’). Since \(\pi \subseteq T\), it is clear by (T2’) that any countable union of sets in \(\pi\) lies in \(T\) also.
For a trust set \(T\) satisfying (T1), (T2’), (T3) and (T4), write \(\pi_T\) for the partition from Proposition 2. Then \(T\) is precisely the set of countable unions from \(\pi_T\). It can be shown that \(\pi_T\) is unique. We have the following
Proposition 3
\(\pi_T\) refines \(\pi_{T'}\) if and only if \(T \supseteq T'\).
Proof.
For brevity, let \(\pi\) and \(\pi'\) denote \(\pi_T\) and \(\pi_{T'}\) respectively. We use the following definition of refinement: \(\pi\) refines \(\pi'\) iff every set in \(\pi'\) is a union of sets in \(\pi\).
“if”: Suppose \(T \supseteq T'\). Let \(A \in \pi'\). Then \(A\) is a union of sets in \(\pi'\), so \(A \in T' \subseteq T\). Hence \(A \in T\), i.e. \(A\) is a union of cells in \(\pi\). This shows that \(\pi\) refines \(\pi'\).
“only if”: Suppose \(\pi\) refines \(\pi'\). Let \(A \in T'\). Then \(A\) is a union of sets in \(\pi'\), so there is \(U \subseteq X\) such that \(A = \bigcup_{x \in U}{\pi'[x]}\). But each \(\pi'[x]\) can be written as a union of sets in \(\pi\), i.e. \(\pi'[x] = \bigcup_{y \in U_x}{\pi[y]}\) for some \(U_x \subseteq X\). Hence \(A = \bigcup_{x \in U}\bigcup_{y \in U_x}\pi[x]\), i.e. \(A\) is a union of sets in \(\pi\). Hence \(A \in T\).
Proposition 4
If \(X\) is finite, \(\pi_{T \cap T'} = \pi_T \vee \pi_{T'}\)
Proof.
Recall that, by definition, \(\pi_T \vee \pi_{T'}\) is the least upper bound of \(\{\pi_T, \pi_{T'}\}\) in the lattice of partitions, i.e. the finest partition coarser than both \(\pi_T\) and \(\pi_{T'}\).
It is clear that \(T \cap T'\) satisfies the relevant properties, so \(\pi_{T \cap T'}\) is well-defined. Since \(T \cap T' \subseteq T\) and \(T \cap T' \subseteq T'\), we have by Proposition 3 that both \(\pi_T\) and \(\pi_{T'}\) are refinements of \(\pi_{T \cap T'}\), i.e. \(\pi_{T \cap T'}\) is an upper bound for \(\{\pi_T, \pi_{T'}\}\). Now let \(\hat{\pi}\) be any upper bound for \(\{\pi_T, \pi_{T'}\}\). Since \(X\) is finite, the set of all unions of \(\hat\pi\) forms a trust set \(\hat{T}\) satisfying (T1), (T2’), (T3) and (T4), and we have that both \(\pi_T, \pi_{T'}\) are refinements of \(\hat\pi = \pi_{\hat{T}}\). Applying Proposition 3 in the other direction, we get that \(T, T' \supseteq \hat{T}\), i.e. \(\hat{T} \subseteq T \cap T'\). Hence \(\pi_{T \cap T'}\) refines \(\hat\pi\). This shows that \(\pi_{T \cap T'}\) is the least upper bound of \(\{\pi_T, \pi_{T'}\}\), i.e. \({\pi_T \vee \pi_{T'} = \pi_{T \cap T'}}\).
General revision¶
In subsequent sections we will look at revision operators which map a sequence of inputs to some outputs (e.g. a partition, or a partition together with a belief set). In this section we present a general characterisation of such operators based on a total preorder; this characterisation will be applied in concrete settings later on.
Definition 2
A revision domain is a tuple \(\D = (A, B, \|\cdot\|)\), where \(A\) and \(B\) are finite sets, and \(\|\cdot\|: A \to 2^B\) is a mapping such that \(\bigcap_{a \in A}{\|a\|} \ne \emptyset\).
A (set-valued) revision operator in \(\D\) is a mapping \(M: A^* \to 2^B\).
For a domain \(\D = (A, B, \|\cdot\|)\) and \(\mu \in A^*\) we write \(\|\mu\| = \bigcap_{a \in \mu}{\|a\|}\). Note that \(\|\mu\| \ne \emptyset\) for all \(\mu\). Consider the following properties for an operator \(M: A^* \to 2^B\):
(M1) \(M(\mu) \subseteq \|\mu\|\)
(M2) \(M(\mu) \ne \emptyset\)
(M3) If \(\|\mu\| = \|\mu'\|\) then \(M(\mu) = M(\mu')\)
(M4) \(M(\mu) \cap \|a\| \subseteq M(\mu \append a)\)
(M5) If \(M(\mu) \cap \|a\| \ne \emptyset\) then \(M(\mu \append a) \subseteq M(\mu) \cap \|a\|\)
(M6) If \(\mu_0,\ldots,\mu_n\) are such that \(\|\mu_i\| \cap M(\mu_{i+1}) \ne \emptyset\) for all \(0 \le i < n\) and \(\|\mu_n\| \cap M(\mu_0) \ne \emptyset\), then \(M(\mu_n) \cap \|\mu_0\| \ne \emptyset\).
First we show that these properties imply \(M\) is defined via a (partial) preorder.
Lemma 1
If \(M\) satisfies (M1) - (M6), there is a preorder \(\le_0\) over \(B\) such that, for all \(\mu\),
\(M(\mu) = \min(\|\mu\|, {\le_0})\)
If \(b \in M(\mu)\) and \(b' \in \|\mu\|\), then \(b \le_0 b'\) 2
Proof.
First recall that, by definition, for a preorder \(\le_0\) we have that
where \(<_0\) is the strict part of \(\le_0\).
Now, suppose \(M: A^* \to 2^B\) satisfies (M1) - (M6). For \(b, b' \in B\), write
Note that \(s(b)\) is finite since \(A\) is finite by assumption. For \(b, b' \in B\), let \(\delta(b, b') \in A^*\) be an arbitrary enumeration of \(s(b) \cap s(b')\). Note that \(b, b' \in \|\delta(b, b')\|\). By (M3), the choice of enumeration does not affect the output of \(M\), so we may write \(M(\delta(b, b'))\) without ambiguity.
Define a relation \(\R\) by
Note that \(\R\) is reflexive. Let \(\le_0\) denote the transitive closure of \(\R\). Then \(\le_0\) is transitive and reflexive, so is a preorder.
Now, let \(\mu \in A^*\) be a sequence. We show both inclusions of (1) separately; (2) will be shown as part of the “\(\subseteq\)” inclusion.
\(\subseteq\): Let \(b \in M(\mu)\). By (M1), \(b \in \|\mu\|\). We need to show that \(b\) is minimal in \(\|\mu\|\), i.e. that \(b' {\not<_0} b\) for all \(b' \in \|\mu\|\). Fix any \(b' \in \|\mu\|\). Since both \(b, b' \in \|\mu\|\), we have \(\set(\mu) \subseteq s(b)\) and \(\set(\mu) \subseteq s(b')\). Hence
Let \(\epsilon \in A^*\) be any enumeration of \(\set(\delta(b, b')) \setminus \set(\mu)\). Then
so
By (M3), we have \(M(\delta(b, b')) = M(\mu \concat \epsilon)\). Note that \(b \in M(\mu) \cap \|\epsilon\|\). In particular, \(M(\mu) \cap \|\epsilon\| \ne \emptyset\). Repeated applications of (M4) and (M5) therefore give that \(M(\mu \concat \epsilon) = M(\mu) \cap \|\epsilon\|\), and consequently
This shows that \(b \R b'\), and therefore \(b \le_0 b'\). This proves (2) and also implies \(b' {\not<_0} b\). Hence \(b \in \min(\|\mu\|, {\le_0})\), and the “\(\subseteq\)” inclusion of part (1) is proved.
\(\supseteq\): Let \(b \in \min(\|\mu\|, {\le_0})\). By (M2), there is some \(b' \in M(\mu)\). If \(b = b'\) then we are done, so assume \(b \ne b'\). Since \(b \in \|\mu\|\), by property (2) – proved in the left-to-right inclusion above – we have \(b' \le_0 b\). Note also that \(b' \in \|\mu\|\) by (M1), so \(b' {\not<_0} b\) by minimality of \(b\) in \(\|\mu\|\). Consequently we must have \(b \le_0 b'\) also. By definition of \(\le_0\) as the transitive closure of \(\R\), there is some \(n \ge 0\) and \(b_0, \ldots, b_n \in B\) such that \(b_0 = b\), \(b_n = b'\) and \(b_i \R b_{i+1}\) for all \(0 \le i < n\). Assume without loss of generality that all the \(b_i\) are distinct.
For \(0 \le i < n\), set
and set
Note that \(b_i \R b_{i+1}\) and \(b_i \ne b_{i+1}\) imply \(b_i \in M(\mu_i)\) for all \(0 \le i < n\). In fact, we have \(b_n \in M(\mu_n)\) also, since \(b' \le_0 b\) implies \(b_n = b' \in M(\delta(b, b')) = M(\mu_n)\). Consequently, for all \(0 \le i < n\),
Moreover, \(b_0 \in M(\mu_0)\) and \(b_0 \in \|\mu_n\|\), so \(\|\mu_n\| \cap M(\mu_0) \ne \emptyset\). On the one hand, applying (M4) and (M5)* we get
On the other, combining \((*)\) and \(\|\mu_n\| \cap M(\mu_0) \ne \emptyset\) we may apply (M6) to get \(M(\mu_n) \cap \|\mu_0\| \ne \emptyset\). Now using (M3), (M4) and (M5), we obtain
In particular, \(b_0 \in M(\mu_n)\). Recalling that \(b_0 = b\) and \(\mu_n = \delta(b_0, b_n) = \delta(b, b')\), we see that \(b \in M(\delta(b, b'))\) and \(b \R b'\).
To conclude, note that by an identical argument to the one used above, the fact that both \(b, b' \in \|\mu\|\) implies there is \(\epsilon \in A^*\) such that \(b, b' \in \|\epsilon\|\) and \(\|\delta(b, b')\| = \|\mu \concat \epsilon\|\). Since \(b' \in M(\mu) \cap \|\epsilon\| \ne \emptyset\), we have by (M3), (M4) and (M5) that
i.e. \(b \in M(\mu)\), as required.
Next we show that any partial preorder can be extended to a total preorder which preserves strict inequalities. 3
Lemma 2
Let \(\sqsubseteq\) be a (possibly partial) preorder over a set \(Z\). Then there is a total preorder \(\sqsubseteq^*\) over \(Z\) such that \(x \sqsubseteq y\) implies \(x \sqsubseteq^* y\) and \(x \sqsubset y\) implies \(x \sqsubset^* y\).
Proof.
Write \(x \sim y\) iff \(x \sqsubseteq y\) and \(y \sqsubseteq x\). Then since \(\sqsubseteq\) is reflexive and transitive, \(\sim\) is an equivalence relation. Define a partial order \(\preccurlyeq\) over the equivalence classes of \(\sim\) by \([x] \preccurlyeq [y]\) iff \(x \sqsubseteq y\). It is straightforward to check that \(\preccurlyeq\) is well-defined and is indeed a partial order. By the Szpilrajn extension theorem, \(\preccurlyeq\) can be extended to a total order \(\preccurlyeq^*\) over the equivalence classes of \(\sim\) such that \([x] \preccurlyeq [y]\) implies \([x] \preccurlyeq^* [y]\).
Define \(\sqsubseteq^*\) by \(x \sqsubseteq^* y\) iff \([x] \preccurlyeq^* [y]\). Totality and transitivity of \(\sqsubseteq^*\) follow from totality and transitivity of \(\preccurlyeq^*\). Hence \(\sqsubseteq^*\) is a total preorder. We show that \(\sqsubseteq^*\) extends \(\sqsubseteq\). Suppose \(x \sqsubseteq y\). Then \([x] \preccurlyeq [y]\); since \(\preccurlyeq^*\) extends \(\preccurlyeq\), this gives \([x] \preccurlyeq^* [y]\) and \(x \sqsubseteq^* y\). Now suppose \(x \sqsubset y\). Then \([x] \preccurlyeq [y]\) and \([x] \ne [y]\). Thus \([x] \preccurlyeq^* [y]\) but \([y] \not\preccurlyeq^* [x]\) (otherwise antisymmetry of \(\preccurlyeq^*\) would give \([x] = [y]\)). Hence \(x \sqsubset^* y\).
We can now prove the representation result for \(M\) derived from a total preorder.
Theorem 1
\(M: A^* \to 2^B\) satisfies (M1) - (M6) if and only if there is a total preorder \(\le\) over \(B\) such that for all \(\mu\),
Proof.
“if”: Let \(\le\) be a total preorder over \(B\) and set \(M(\mu) = \min(\|\mu\|, {\le})\).
(M1) is clear by definition. (M2) holds since \(B\) is finite and \(\|\mu\| \ne \emptyset\) for all \(\mu\), so \(\|\mu\|\) has at least one minimal element. (M3) also holds by definition.
For (M4), suppose \(b \in M(\mu) \cap \|a\|\). Then \(b \in \|\mu\|\) and \(b \in \|a\|\), so \(b \in \|\mu \append a\|\). Let \(b' \in \|\mu \append a\|\). Then in particular, \(b' \in \|\mu\|\). Since \(b\) is minimal in \(\|\mu\|\), we have \(b' \not< b\). Hence \(b\) is minimal in \(\|\mu \append a\|\), so \(b \in M(\mu \append a)\), i.e. \(M(\mu) \cap \|a\| \subseteq M(\mu \append a)\) as required for (M4).
For (M5), suppose there is some \(\hat{b} \in M(\mu) \cap \|a\|\). Let \(b \in M(\mu \append a)\). Then \(b \in \|\mu \append a\| = \|\mu\| \cap \|a\|\), so \(b \in \|a\|\). We need to show that \(b \in M(\mu)\). To that end, let \(b' \in \|\mu\|\). Since \(\hat{b} \in M(\mu)\), we have \(b' \not<\hat{b}\); since \(\le\) is total, this means \(\hat{b} \le b'\). Note also that \(\hat{b} \in \|\mu \append a\|\), so \(b \in M(\mu \append a)\) implies \(\hat{b} \not< b\) and hence \(b \le \hat{b}\). By transitivity of \(\le\) we have \(b \le b'\), and consequently \(b' \not< b\). This shows that \(b\) is minimal in \(\|\mu\|\), i.e. \(b \in M(\mu) \cap \|a\|\). Hence \(M(\mu \append a) \subseteq M(\mu) \cap \|a\|\) as required.
Finally, let \(\mu_0,\ldots,\mu_n\) be as in the statement of (M6). For \(0 \le i < n\), take \(b_i \in \|\mu_i\| \cap M(\mu_{i+1})\). Take \(b_n \in \|\mu_n\| \cap M(\mu_0)\).
For any \(i\), we have \(b_i \in \|\mu_i\|\). For \(i < n\), we also have \(b_i \in M(\mu_{i+1})\). Consequently \(b_i\) is minimal in \(\|\mu_{i+1}\|\), so \(b_i \le b_{i+1}\). By transitivity, \(b_0 \le b_n\). But since \(b_0 \in \|\mu_0\|\) and \(b_n \in M(\mu_0)\), we also have \(b_n \le b_0\). Hence the chain \(b_0 \le \cdots \le b_n\) flattens, and we have \(b_i \sim b_j\) for all \(i, j\).
In particular, \(b_n \le b_{n-1}\). Since \(b_{n-1} \in M(\mu_n)\), this implies \(b_n \in M(\mu_n)\). Since \(b_n \in M(\mu_0) \subseteq \|\mu_0\|\) too, we get \(b_n \in M(\mu_n) \cap \|\mu_0\| \ne \emptyset\). Hence (M6) is satisfied.
“only if”: Suppose \(M\) satisfies (M1) - (M6). By Lemma 1 part (1), there is a preorder \(\le_0\) such that \(M(\mu) = \min(\|\mu\|, {\le_0})\) for any \(\mu\). Apply Lemma 2 to \(\le_0\) to obtain a total preorder \(\le\) over \(B\) such that \(b \le_0 b'\) implies \(b \le b'\) and \(b <_0 b'\) implies \(b < b'\). We conclude the proof by showing that \(\min(\|\mu\|, {\le}) = \min(\|\mu\|, {\le_0})\) for any sequence \(\mu\).
Indeed, fix \(\mu\) and let \(b \in \min(\|\mu\|, {\le})\). Let \(b' \in \|\mu\|\). Then \(b' \not< b\). Since \(<\) extends \(<_0\), we must have \(b' \not<_0 b\). This shows that \(b \in \min(\|\mu\|, {\le_0})\).
Conversely, let \(b \in \min(\|\mu\|, {\le_0})\) and \(b' \in \|\mu\|\). Then \(b \in M(\mu)\). By part (2) of Lemma 1, \(b \le_0 b'\). Since \(\le\) extends \(\le_0\), we get \(b \le b'\) and consequently \(b' \not< b\). This shows that \(b \in \min(\|\mu\|, {\le})\). Hence \(M(\mu) = \min(\|\mu\|, {\le_0}) = \min(\|\mu\|, {\le})\), and we are done.
Note that the proof of Theorem 1 has followed the general lines of Theorems 4.8 and 4.9 of Delgrande et. al. in [DPW18]. Indeed, our problem is almost an instantiation of their general logical framework, except for a few important differences:
Comparing our problem to their framework, elements of \(B\) are the semantic models of formulas \(\mu \in A^*\) (i.e. \(b \vDash \mu\) iff \(b \in \|\mu\|\)). This means that our revision operators output sets of models rather than sets of formulas. This difference allows us to avoid requiring the extra condition of regularity on the total preorders in the representation result, as Delgrande et. al. do.
Their framework assumes a property they call (Expr), which we do not assume here here. Translated to our problem, (Expr) says that for every distinct \(b, b' \in B\), there is some \(\mu \in A^*\) such that \(b \in \|\mu\|\) but \(b' \notin \|\mu\|\). This fails when instantiating our framework with \(A = X \times \O\), \(B\) as the set of partitions over \(X\), and \(\|\cdot\|\) given by soundness as described in the preliminaries. The above property fails, for example, if \(\pi\) refines \(\pi'\); then every \(\mu\) sound for \(\pi\) is also sound for \(\pi'\).
The proof of the step going from a preorder to a total preorder (in Lemma 2 and the “only if” part of Theorem 1) is greatly simplified here: we choose an arbitrary extension of the constructed (partital) preorder \(\le_0\), whereas Delgrade et. al. take great care to construct this extension explicitly.
Theorem 1 can be extended to characterise \(M\) based on a total order with one additional postulate.
(M-total) \(|M(\mu)| = 1\)
Notation. For a total order \(\le\) on \(B\) and \(B' \subseteq B\), we write \(\Min(B', {\le}) \in B'\) for the unique minimal element in \(B'\). For consistency with notation for total preorders (since any total order is in particular a total preorder), we write \(\min(B', {\le}) \subseteq B'\) for the (singleton) set of minimal elements.
Corollary 1
\(M: A^* \to 2^B\) satisfies (M1) - (M6) and (M-total) if and only if there is a total order \(\le\) over \(B\) such that for all \(\mu\),
Proof.
“if”: Suppose \(M(\mu) = \min(\|\mu\|, {\le})\) for some total order \(\le\). Since any (finite) subset of \(B\) has a unique minimum under a total order, we have (M-total). (M1) - (M6) follow by Theorem 1, since \(\le\) is also a total preorder.
“only if”: Suppose \(M\) satisfies (M1) - (M6) and (M-total). By Theorem 1, there is a total preorder \(\le_0\) such that \(M(\mu) = \min(\|\mu\|, {\le_0})\) for any \(\mu\). Let \(\sqsubseteq\) be an arbitrary tie-breaking total order over \(B\). Let \(\le\) be the lexicographic order corresponding to \(\le_0\) and \(\sqsubseteq\), i.e.
where \(\sim_0\) denotes the equivalence relation corresponding to \(\le_0\). Then \(\le\) is a total order.
Let \(\mu\) be any sequence. By (M-total), \(\|\mu\|\) has a unique minimum with respect to \(\le_0\), say \(b\). Let \(b' \in \|\mu\|\). Then either \(b = b'\) or \(b <_0 b'\). In either case we have \(b \le b'\). Hence \(b\) is minimal in \(\|\mu\|\) with respect to \(\le\) also. Consequently
and we are done.
Revising a partition¶
In this section we consider operators which receive finite sequences of pairs \((x, U) \in X \times \O\), and output a partition.
Definition 3
A partition revision operator is a mapping \(F: (X \times \O)^* \to \P\). We write \(\pi_F(\mu)\) for \(F(\mu)\).
Intuitively, each \((x, U)\) in the input sequence \(\mu\) represents a source claiming \(U\) was true at the state \(x\). We additionally assume there is some “actual” partition \(\pi\) for which every report in \(\mu\) is sound. Based on this intuition, the following postulates might be desirable for a revision operator \(F\).
(P1) \(\pi_F(\mu) \in \|x, U\|\) for each \((x, U) \in \mu\)
(P2) If \(\pi_F(\mu) \in \|x, U\|\), then \(\pi_F(\mu\append(x,U)) = \pi_F(\mu)\)
(P3) \(\pi_F(\mu \append (x, U)) \preceq \pi_F(\mu) \join \{U_x, U_x^c\}\), where \(U_x = U \cup \{x\}\)
(P4) For any permutation \(\mu'\) of \(\mu\), \(\pi_F(\mu) = \pi_F(\mu')\)
(P5) Write \(\pi = \pi_F(\mu)\) and \(\pi' = \pi_F(\mu \append (x, U))\). If \(U \subseteq \pi[y]\) for some \(y\), then \(\pi'[x] \subseteq \pi[x] \cup \pi[y]\)
(P1) says that each report in \(\mu\) is sound for \(\pi_F\). This is analogous to Success in the AGM postulates. (P2) is analogous to Vacuity: if \(\pi_F\) is already sound for \((x, U)\) after receiving input \(\mu\), then \(\pi_F\) does not change upon receiving \((x, U)\). (P3) says that the partition after receiving \((x, U)\) is at least as refined as the “trivial” partition obtained by taking the join of the previous partition and \(\{U_x, U_x^c\}\), which is in a way the “simplest” partition in \(\|x, U\|\). 4 (P4) expresses commutativity. (P5) is getting a bit complicated, but says that if \(U\) was already wholly contained in a partition cell before receiving \((x, U)\), then the revised cell of \(x\) does not include any state outside this cell or the original cell containing \(x\).
Example 1. As a baseline operator following the idea in (P3), set
Then \(F\) satisfies (P1), (P3) and (P4), and fails (P2). 5
Example 2. Let \(\kappa: \P \to \N_0 \cup \{\infty\}\) be a ranking function over partitions. Write \(p(\mu)\) for the most plausible partitions sound for each report in \(\mu\), i.e.
Define an operator by setting \(\pi_F(\mu) = \bigjoin p(\mu)\). Then \(F\) satisfies (P1) by definition of the conditioning and the fact that each \(\|x, U\|\) is upwards closed with respect to \(\preceq\). \(F\) also satisfies (P4).
Order-based operators¶
Let us say an operator \(F\) is tpo-based if there is a total preorder \(\le\) over \(\P\) such that
where \(\|\mu\| = \bigcap_{(x, U) \in \mu}\|x, U\|\). Note that Example 2 falls into this class.
When the set of states \(X\) is finite, we can instantiate the general sequential revision framework of the previous section by taking revision domain \(\D_{\text{part}} = (X \times \O, \P, \|\cdot\|)\), where \(\|\cdot\|\) is the soundness notion as laid out in the preliminaries. The only condition required in Definition 2 is \(\bigcap_{a \in A}\|a\| \ne \emptyset\); this holds here since the coarsest partition \(\{X\}\) lies in \(\|x, U\|\) for all \((x, U) \in X \times \O\).
Via the (M1) - (M6) properties for this particular instantiation, we obtain a characterisation of tpo-based partition revision operators as a consequence of Theorem 1.
Corollary 2
Suppose \(X\) is finite. Then an operator \(F\) is tpo-based if and only there is is a function \(M: (X \times \O)^* \to 2^\P\) satisfying (M1) - (M6) such that
for all \(\mu\).
Corollary 2 is not completely satisfactory, as it characterises tpo-based operators in terms of postulates which do not actually refer to the operator itself, but an unspecified function \(M\) such that \(\pi_F(\mu) = \bigjoin M(\mu)\). In the case where \(M(\mu)\) is a singleton set, however, we obtain a characterisation of total-order-based operators in terms of explicit postulates for the operator \(F\).
Proposition 5
Suppose \(X\) is finite. Consider the following properties: 6
\(\pi_F(\mu) \in \|\mu\|\)
\(\|\mu\| = \|\mu'\|\) implies \(\pi_F(\mu) = \pi_F(\mu')\)
\(\pi_F(\mu) \in \|x, U\|\) implies \(\pi_F(\mu \append (x, U)) = \pi_F(\mu)\)
If \(\mu_0,\ldots,\mu_n\) are such that \(\pi_F(\mu_{i+1}) \in \|\mu_i\|\) for all \(0 \le i < n\) and \(\pi_F(\mu_0) \in \|\mu_n\|\), then \(\pi_F(\mu_n) \in \|\mu_0\|\)
Then \(F\) satisfies (1) - (4) if and only if there is a total order \(\le\) over \(\P\) such that
Proof.
“if”: Suppose there is a total order \(\le\) such that \(\pi_F(\mu) = \Min(\|\mu\|, {\le})\) for all \(\mu\). Set \(M(\mu) = \{\pi_F(\mu)\}\). Then
By Corollary 1, \(M\) satisfies (M1) - (M6). It is then easy to see that property (1) for \(F\) follows from (M1), (2) from (M3), (3) from (M4) and (M5), and (4) from (M6).
“only if”: Suppose \(F\) satisfies (1) - (4). Again, set \(M(\mu) = \{\pi_F(\mu)\}\). Clearly \(M\) satisfies (M-total). Moreover, \(M\) satisfies (M1) by property (1), (M2) by construction, (M3) by (2), (M4) and (M5) by (3), and (M6) by (4). By Corollary 1, there is a total order \(\le\) over \(\P\) such that \(M(\mu) = \min(\|\mu\|, {\le})\), i.e. \(\pi_F(\mu) = \Min(\|\mu\|, {\le})\).
The following example shows a tpo-based operator not based on any total order, since it violates property (3) above.
Example 3. Suppose \(X = \{1,2,3,4\}\). Write
Let \(\le\) be the tpo whose minimal rank is \(\{\pi_1, \pi_2\}\), and whose second minimal rank is \({\P \setminus \{\pi_1, \pi_2\}}\). Consider
Then every partition is sound for \(\mu\), so \(\|\mu\| = \P\), and thus
Now note that \(\pi_1 \in \|x, U\|\) but \(\pi_2 \notin \|x, U\|\). By construction of \(\le\), we have \(\min(\|x, U\|, {\le}) = \{\pi_1\}\). Hence
However, since \(\pi_F(\mu)\) is the trivial partition \(\{X\}\), we have \(\pi_F(\mu) \in \|x, U\|\). Since \(\pi_F(\mu\append(x,U)) \ne \pi_F(\mu)\), the tpo-based operator \(F\) violates property (3) in the statement of Proposition 5.
Another simple possibility for obtaining sufficient conditions for tpo-based operators is to set
(where \(\preceq\) denotes the refinement partial order on partitions) and rephrase the (M1) - (M6) properties in terms of \(F\). If \(\pi_F(\mu) \in \|\mu\|\), then we have \(\bigjoin M(\mu) = \pi_F(\mu)\). (M1) and (M2) hold by definition, and (M3) holds if property (2) from Proposition 5 does. However, one can show that (M4) is equivalent to the following condition:
This condition fails for \(\le\), \(\mu\) and \((x, U)\) from Example 3, e.g. by taking \(\pi = \{X\}\), so any postulates resulting from this choice of \(M\) will not be sound for all tpo-based operators.
Handling new information¶
We extend the framework to handle “new” information – assumed to come from the same unknown state – in addition to historical reports at which the actual state was known. Operators in this setting maintain a both trust partition and a belief set.
Let \(\unknown\) be a constant symbol representing the current unknown state. Write \(X^\unknown = X \cup \{\unknown\}\). We denote sequences over \(X^\unknown \times \O\) by \(\sigma\), \(\sigma'\) etc to distinguish between sequences \(\mu\) over \(X \times \O\).
Notation. For \(\sigma \in (X^\unknown \times \O)^*\) and \(x \in X\), write \(\mu_{\sigma,x}\) for the sequence in \((X \times \O)^*\) obtained by replacing all occurrences of \(\unknown\) with \(x\). Write
i.e. \((x, \pi) \in \|\sigma\|\) iff \(\pi \in \|y, U\|\) for all \((y, U) \in \sigma\) with \(y \ne \unknown\), and \(\pi \in \|x, U\|\) for all \((\unknown, U) \in \sigma\).
Definition 4
A partition and belief revision operator is a mapping \(G: (X^\unknown \times \O)^* \to 2^X \times \P\). Write \(G(\sigma) = (B_G^\sigma, \pi_G^\sigma)\).
TODO: fix inconsistencies with \(\pi_G^\sigma\) vs \(\pi_G(\mu)\) etc.
Note that any such \(G\) defines a partition revision operator by discarding the belief set \(B_G(\sigma)\). Accordingly, rationality postulates for partition operators also apply to partition and belief operators. We might want to consider additional postulates to constrain the belief set, and the relation between the belief set and partition.
First, we state some basic soundness and consistency postulates.
(B1) \(B_G^\sigma \subseteq \pi_G^\sigma[U]\) for all \((\unknown, U) \in \sigma\)
(B2) \(\pi_G^\sigma \in \|x, U\|\) for all \((x, U) \in \sigma\), \(x \ne \unknown\)
(B3) \(B_G^\sigma \ne \emptyset\)
(B1) is a weak form of Success. It says that after weakening the reports about the unknown state by the estimated partition \(\pi_G^\sigma\), all these reports are believed. (B2) is carried over from the partition-only operator case (it is the same as (P1)). (B3) says that the output belief set is always consistent. This is plausible even if the input reports are inconsistent, since for any sequence of \(U \ne \emptyset\) there is always some partition and state \(x\) for which the sequence is sound (e.g. the coarsest partition \(\{X\}\)).
Proposition 6
Consider the following property
We have
(B1) \(\wedge\) (B2) \(\implies (*)\)
If (B3) holds, then (B1) \(\wedge\) (B2) \(\iff (*)\)
Proof.
(B1) implies \(\pi_G^\sigma \in \|x, U\|\) for all \(x \in B_G^\sigma\) and \((\unknown, U) \in \sigma\), and (B2) says that \(\pi_G^\sigma \in \|y, U\|\) for all \((y, U) \in \sigma\). From this it is clear that \(\pi_G^\sigma \in \|\mu_{\sigma,x}\|\) for any \(x \in B_G^\sigma\), i.e. \((x, \pi_G^\sigma) \in \|\sigma\|\).
Suppose (B3) and \((*)\) hold. For (B1), take any \(x \in B_G^\sigma\) and \((\unknown, U) \in \sigma\). By \((*)\) we have \((x, \pi_G^\sigma) \in \|\sigma\|\), i.e. \(\pi_G^\sigma \in \|\mu_{\sigma,x}\|\). Since \((\unknown, U) \in \sigma\), we have \((x, U) \in \mu_{\sigma,x}\). Hence \(\pi_G^\sigma \in \|\mu_{\sigma,x}\| \subseteq \|x, U\|\), i.e. \(\pi_G^\sigma\) is sound for \((x, U)\), so \(x \in \pi_G^\sigma[U]\). This shows (B1).
For (B2), let \((x, U) \in \sigma\), \(x \ne \unknown\). Let \(y\) be any element of \(B_G^\sigma\); by (B3) \(B_G^\sigma\) is non-empty. Then by \((*)\) we have \(\pi_G^\sigma \in \|\mu_{\sigma,y}\|\). But \((x, U) \in \sigma\) implies \((x, U) \in \mu_{\sigma,y}\), so \(\pi_G^\sigma \in \|x, U\|\) as required.
Example 4. Extending Example 2, let \(\kappa: X \times \P \to \N_0 \cup \{\infty\}\) be a ranking function over pairs \((x, \pi)\). Write
For a set \(S \subseteq X \times \P\), write \(S \restrict X\) and \(S \restrict \P\) for the projections onto \(X\) and \(\P\) respectively. Define an operator \(G\) by setting
Example 5. Let \(D\) be a function \(X \times \P \times \O \to \N_0 \cup \{\infty\}\). For a sequence \(\sigma\), write
Set
and, as in Example 4, set
Note that if \(\kappa(x, \pi) < \infty\) for all \((x, \pi)\), \(G_\kappa\) from Example 4 is a special case of \(G_D\): set
Then for \(\sigma\) of length \(n\) and \((x, \pi) \in \|\sigma\|\) we have \(D(x, \pi, \sigma) = n\kappa(x, \pi) < \infty\), and \(D(x, \pi, \sigma) = \infty\) for \((x, \pi) \notin \|\sigma\|\). This implies \(\argmin_{x,\pi}\kappa(x,\pi \mid \|\sigma\|) = \argmin_{x,\pi}D(x,\pi,\sigma)\).
Proposition 7
Suppose \(X\) is finite and \(D\) from Example 5 is such that
Then \(G_D\) satisfies (B1), (B2) and (B3).
Proof.
Since \(X\) is finite, \(X \times \P\) is also finite and the \(\argmin\) in the definition of \(G_D\) is non-empty. Hence \(G_D\) satisfies (B3). For (B1) and (B2), we show property \((*)\) from Proposition 6 and conclude by part (2) of that result.
Note that for any \(x, \pi\) and \(\sigma\),
Since \(\|\sigma\| \ne \emptyset\) for any \(\sigma\), 7 there are \(x, \pi\) such that \(D(x, \pi, \sigma) < \infty\). This implies \(\min_{x,\pi}D(x,\pi,\sigma) < \infty\), and consequently \(p(\sigma) \subseteq \|\sigma\|\).
Now, to show \((*)\), let \(x \in B_G^\sigma = p(\sigma) \restrict X\). Then there is \(\pi\) such that \((x, \pi) \in p(\sigma)\). Since \(p(\sigma) \subseteq \|\sigma\|\), we have \((x, \pi) \in \|\sigma\|\), i.e. \(\pi \in \|\mu_{\sigma,x}\|\). Note that \(\pi \in p(\sigma) \restrict \P\) implies \(\pi \preceq \pi_G^\sigma\). Since \(\|\mu\|\) is upwards-closed wrt partition refinement for any sequence \(\mu\), we have \(\pi_G^\sigma \in \|\mu_{\sigma,x}\|\), i.e. \((x, \pi_G^\sigma) \in \|\sigma\|\). This shows \((*)\), and by Proposition 6 we are done.
The following postulates express different ideas about how belief should evolve over time.
(A1) There is an AGM operator \(\star\) such that
\[B_G^{\sigma \append (\unknown, U)} = B_G^\sigma \star \pi_G^{\sigma \append (\unknown, U)}[U]\](A2) There is an AGM operator \(\star\) such that
\[B_G^{\sigma} = B_G^\emptyset \star \bigcap_{(\unknown, U) \in \sigma}{ \pi_G^\sigma[U] }\]
Both postulates refer to a kind of selective revision, where the input proposition is weakened before revision with an AGM operator. (A1) says that revision is iterative: the beliefs after receiving \((\unknown, U)\) are obtained by revising the previous beliefs \(B_G^\sigma\) by the weakened version of \(U\) according to the latest partition estimate.
There is a potential problem with this iterative approach: what if the new report causes a change in the partitions which requires previous reports \((\unknown, V)\) be be re-evaluated? Indeed, consider \(X = \{1,2,3\}\) and \(\sigma = \langle (\unknown, \{1, 2\}), (\unknown, \{2, 3\}) \rangle\). It seems reasonable for \(G\) to output the unit partition and belief set \(\{2\}\) on input \(\sigma\). Now consider a report \((\unknown, \{1,3\})\). The reports in \(\sigma' = \sigma \append (\unknown, \{1, 3\})\) are no longer jointly consistent, so the unit partition cannot be sound, and so the partition must be coarsened. In this case (A1) says we should revise the previous belief set \(\{2\}\) by \(\pi_G^{\sigma'}[\{1, 3\}]\). But the earlier belief in state 2 only came about because the unit partition was assumed on input \(\sigma\). Knowing that the partition must change for the cell containing 1 or 3, we may wish to re-evaluate the reports \(\{1,2\}\) and \(\{2,3\}\), rather than simply revising by the latest report.
To work around this, (A2) says beliefs should be revised “from scratch” at each step. The downside is that this requires one to keep a history of all previous reports.
Revisiting order-based operators¶
We introduce two classes of operators induced by some kind of ordering over alternatives. The first generalises tpo-based operators for partition-only operators (and is a rephrasing of Example 4). Say an operator \(G\) is tpo-based if there is a total preorder \(\le\) over \(X \times \P\) such that for all \(\sigma\),
An alternative approach is to take an order over partitions only, determine \(\pi_G^\sigma\) using this order, and define the belief set in terms of \(\pi_G^\sigma\) and the current reports in \(\sigma\). Say that \(G\) is a partition-first operator if there is a total order \(\sqsubseteq\) over \(\P\) such that
Note that we specify a total order here and take the unique minimum, instead of taking a total preorder and taking the join of the minimal partitions. This is because the expression for \(B_G^\sigma\) is less well-motivated when multiple partitions are identified as most plausible for \(\sigma\). Indeed, suppose \(X = \{1,2,3,4\}\), the only current report in \(\sigma\) is \((\unknown, \{1\})\), and the most plausible partitions are \(\pi_1 = 1, 2 \mid 3, 4\) and \(\pi_2 = 1, 3 \mid 2, 4\). Then expanding the current report \(\{1\}\) in \(\pi_1\) we get \(B_1 = \{1,2\}\), and doing the same for \(\pi_2\) gives \(B_2 = \{1,3\}\). A reasonable output for \(B_G^\sigma\) is their union \(\{1,2,3\}\), since \(\pi_1\) and \(\pi_2\) are equally plausible. However, the join \(\pi_3 = \pi_1 \join \pi_2\) is the coarsest partition \(1, 2, 3, 4\), and we have \(\pi_3[\{1\}] = \{1,2,3,4\}\). Thus, taking \(B_G^\sigma = \bigcap_{(\unknown, U) \in \sigma}{\pi_G^\sigma[U]}\) yields a weaker belief set containing the extra state \(4\).
We obtain a representation result for partition-first (and a subclass of tpo-based operators) using the following postulates.
(B4) If \(\|\sigma\| = \|\sigma'\|\) then \(G(\sigma) = G(\sigma')\)
(B5) If \(\pi_G^\sigma \in \|\sigma \concat \delta\| \restrict \P\) then \(\pi_G^{\sigma \concat \delta} = \pi_G^\sigma\)
(B6) If \((x, \pi_G^\sigma) \in \|\sigma\|\) then \(x \in B_G^\sigma\)
(B7) For all \(\sigma\) there is \(\delta\) such that \(\pi_G^\delta = \pi_G^\sigma\) and \(B_G^\delta \supseteq B_G^\emptyset\)
(B8) Suppose \(\sigma_0, \ldots, \sigma_n\) are such that there are \(x_0,\ldots,x_n\) with \(x_i \in B_G^{\sigma_i}\) for all \(i\), \((x_{i+1}, \pi_G^{\sigma_{i+1}}) \in \|\sigma_i\|\) for \(0 \le i < n\) and \((x_0, \pi_G^{\sigma_0}) \in \|\sigma_n\|\). Then there is \(y \in B_G^{\sigma_n}\) such that \((y, \pi_G^{\sigma_n}) \in \|\sigma_0\|\)
(B4) is a simple extensionality-like property. (B5) says that if \(\pi\) was selected on input \(\sigma\) and is a candidate partition for \(\sigma \concat \delta\) (for some state), then \(\pi\) is also selected on input \(\sigma \concat \delta\). Note that (B5) is already suggestive of a partition-first approach, since we constrain the partition output for \(\sigma \concat \delta\) without reference to the belief set or the \(X\) components of \(\|\sigma \concat \delta\|\).
(B6) says that if \(x\) is a sound possibility for the current state represented by \(\unknown\) when the partition is \(\pi_G^\sigma\), then \(x\) is considered plausible by \(G\). Note that together with (B1) and (B2), this implies \(B_G^\sigma = \bigcap_{(\unknown, U) \in \sigma}\pi_G^\sigma[U]\). So (B6) is also already suggestive of a partition-first approach. The arguments given above against this expression as a definition for \(B_G^\sigma\) also apply to (B6) (if (B1) and (B1) are accepted as fundamental), so that (B6) is not necessarily a universally desirable postulate.
(B7) says that it is possible to “reset” the belief output of \(G\) (so that the beliefs are weaker than the initial belief set) while keeping the partition output the same. In fact, the following modification of (B7) – which is stronger than (B7) in the presence of (B3) – may also be intuitively reasonable:
(B7*) For all \(\sigma\) and \(x \in B_G^\sigma\) we have \(\pi_G^{\mu_{\sigma,x}} = \pi_G^\sigma\) and \(B_G^{\mu_{\sigma,x}} = B_G^\emptyset\)
Clearly (B7*) and (B3) imply (B7): take any \(x \in B_G^\sigma\) and take \(\delta = \mu_{\sigma,x}\). The intuition behind (B7*) is as follows. Suppose \(x\) is a plausible candidate for the current state according to \(G\) on input \(\sigma\). Then suppose at a later time we learn that \(x\) was indeed the current state represented by \(\unknown\) in \(\sigma\), but the current state has now changed. This new information together with \(\sigma\) is represented by \(\mu_{\sigma,x}\): the historical reports in \(\sigma\) remain, all \((\unknown, U) \in \sigma\) are replaced by \((x, U)\), and, since there is no information about the new current state, there are no \((\unknown, U)\) elements in \(\mu_{\sigma,x}\). (B7*) then says that the new information does not change \(G\)’s estimate of the partition (i.e. \(\pi_G^{\mu_{\sigma,x}} = \pi_G^\sigma\)), and there are no beliefs about the new current state (i.e. \(B_G^{\mu_{\sigma,x}} = B_G^\emptyset\)). This is intuitively reasonable if \(\pi_G^\sigma\) is interpreted as the most plausible partition on input \(\sigma\). As with (B6), the desirability of (B7*) is less certain if \(\pi_G^\sigma\) is an aggregation of equiplausible partition (for instance, their join).
Finally, (B8) is an adaptation of (M6) – which is in turn an adaptation of the (Acyc) postulate of Delgrande et. al. [DPW18] – which is necessary to capture transitivity.
Theorem 2
Suppose \(X\) is finite and let \(G\) be an operator. Then the following are equivalent.
\(G\) satisfies (B1) - (B8)
\(G\) is a tpo-based operator for some total preorder \(\le\) over \(X \times \P\) such that
\[(x, \pi) \sim (x', \pi') \iff \pi = \pi' \tag{\dag}\]\(G\) is a partition-first operator
Proof.
(1) \(\implies\) (2): Suppose \(G\) satisfies (B1) - (B8). Take a revision domain \(\D = (A, B, \|\cdot\|)\) where \(A = X^\unknown \times \O\), \(B = X \times \P\) and \(\|z, U\| = \|\langle (z, U) \rangle\|\) according to the notion of soundness for the length-one \(\sigma\) sequence \(\langle (z, U) \rangle\). Note that for any \(\sigma, \sigma'\) we have \(\|\sigma \concat \sigma'\| = \|\sigma\| \cap \|\sigma'\|\), so the notion of soundness for sequences in the general revision framework (i.e. \(\|\sigma\| := \bigcap_{(z, U) \in \sigma}\|z, U\|\)) aligns with our usual notion for \(\|\sigma\|\).
Set
We will show that \(M\) satisfies (M1) - (M6).
(M1) is equivalent to \((x, \pi_G^\sigma) \in \|\sigma\|\) for all \(x \in B_G^\sigma\), i.e. property \((*)\) from Proposition 6. Since \(G\) has (B1) and (B2), we get (M1) for \(M\) by Proposition 6.
(M2) holds by (B3)
(M3) holds by (B4)
For (M4), suppose \((x, \pi) \in M(\sigma) \cap \|\delta\|\), where \(\delta\) is a length-one sequence \(\langle z, U \rangle\). Then \(x \in B_G^\sigma\), \(\pi = \pi_G^\sigma\) and \((x, \pi) \in \|\delta\|\). By (M1), we have \((x, \pi) \in \|\sigma\|\) too, so \((x, \pi) \in \|\sigma\| \cap \|\delta\| = \|\sigma \concat \delta\|\). Hence \(\pi \in \|\sigma \concat \delta\| \restrict \P\). Since \(\pi = \pi_G^\sigma\), applying (B5) we get \(\pi_G^{\sigma \concat \delta} = \pi_G^\sigma = \pi\).
On the other hand, from \((x, \pi_G^{\sigma \concat \delta}) = (x, \pi) \in \|\sigma \concat \delta\|\) we may apply (B6) to get \(x \in B_G^{\sigma \concat \delta}\). Consequently \((x, \pi) \in B_G^{\sigma \concat \delta} \times \{\pi_G^{\sigma \concat \delta}\} = M(\sigma \concat \delta)\). Hence \(M(\sigma) \cap \|\delta\| \subseteq M(\sigma \concat \delta)\), and (M4) holds.
For (M5), let \(\sigma, \delta\) be as above and suppose \(M(\sigma) \cap \|\delta\| \ne \emptyset\). By the same argument as above, we have \(\pi_G^{\sigma \concat \delta} = \pi_G^\sigma\). Let \((x, \pi) \in M(\sigma \concat \delta)\). Then \(\pi = \pi_G^{\sigma \concat \delta} = \pi_G^\sigma\). We need to show \((x, \pi) \in M(\sigma) \cap \|\delta\|\). By (M1), \((x, \pi) \in \|\sigma \concat \delta\| \subseteq \|\delta\|\). Also, \((x, \pi_G^\sigma) = (x, \pi) \in \|\sigma\|\) gives \(x \in B_G^\sigma\) by (B6). Hence \((x, \pi) \in B_G^\sigma \times \{\pi_G^\sigma\} = M(\sigma)\). This shows \(M(\sigma \concat \delta) \subseteq M(\sigma) \cap \|\delta\|\) and (M5) holds.
Finally we show (M6). Suppose \(\sigma_0, \ldots, \sigma_n\) are such that \(\|\sigma_i\| \cap M(\sigma_{i+1}) \ne \emptyset\) for all \(0 \le i < n\) and \(\|\sigma_n\| \cap M(\sigma_0) \ne \emptyset\). Then by definition of \(M\) there are \(x_0,\ldots,x_n\) such that \(x_i \in B_G^{\sigma_i}\) for all \(i\) and
\((x_{i+1}, \pi_G^{\sigma_{i+1}}) \in \|\sigma_i\|\) for \(0 \le i < n\)
\((x_0, \pi_G^{\sigma_0}) \in \|\sigma_n\|\)
Applying (B8) directly we see there is \(y \in B_G^{\sigma_n}\) such that \((y, \pi_G^{\sigma_n}) \in \|\sigma_0\|\). Clearly \((y, \pi_G^{\sigma_n}) \in M(\sigma_n) \cap \|\sigma_0\|\), so \(M(\sigma_n) \cap \|\sigma_0\| \ne \emptyset\), and (M6) holds.
By Theorem 1, there is a total preorder \(\le_0\) over \(X \times \P\) such that for all \(\sigma\),
This means that
and
i.e. \(G\) is tpo-based. We modify \(\le_0\) to satisfy \((\dag)\) while preserving the minimal elements of each \(\|\sigma\|\) in two stages.
First, write
Construct \(\le_1\) from \(\le_0\) by conditioning on \(Q\): move all elements not in \(Q\) to the top of the ranking, where they will rank equally:
Note that \(\le_1\) is a total preorder since \(\le_0\) is.
Claim: For any \(\sigma\), \(\min(\|\sigma\|, {\le_1}) = \min(\|\sigma\|, {\le_0})\).
Proof: \(\subseteq\): Let \((x, \pi) \in \min(\|\sigma\|, {\le_1})\). Let \((x', \pi') \in \min(\|\sigma\|, {\le_0})\). Then \((x', \pi') \in Q\) by definition of \(Q\). Also, \((x, \pi) \le_1 (x', \pi')\) by minimality of \((x, \pi)\) with respect to \(\le_1\), so we must have \((x, \pi) \in Q\) and \((x, \pi) \le_0 (x', \pi')\). Since \((x, \pi)\) \(\le_0\)-precedes everything in \(\min(\|\sigma\|, {\le_0})\) it also \(\le_0\)-precedes everything in \(\|\sigma\|\), and we have \((x, \pi) \in \min(\|\sigma\|, {\le_0})\).
\(\supseteq\): Let \((x, \pi) \in \min(\|\sigma\|, {\le_0})\) and \((x', \pi') \in \|\sigma\|\). If \((x', \pi') \notin Q\) then clearly \((x, \pi) \le_1 (x', \pi')\). Otherwise we have both \((x, \pi), (x', \pi') \in Q\) and \((x, \pi) \le_0 (x', \pi')\), since \((x, \pi)\) is \(\le_0\)-minimal. Thus \((x, \pi) \le_1 (x', \pi')\) in this case too, and therefore \((x, \pi) \in \min(\|\sigma\|, {\le_1})\).
Next, let \(\sqsubseteq\) be any tie-breaking total order over \(\P\). Let \(\le\) be the lexicographic ordering of \(X \times \P\) where sort first by \(\le_1\) and then by \(\sqsubseteq\) applied to the partition component:
Again, \(\le\) is a total preorder since \(\le_1\) is a tpo and \(\sqsubseteq\) is a total order.
Claim: For any \(\sigma\), \(\min(\|\sigma\|, {\le}) = \min(\|\sigma\|, {\le_1})\).
Proof: \(\subseteq\): This inclusion is clear since \((x, \pi) \le (x', \pi')\) implies \((x, \pi) \le_1 (x', \pi')\).
\(\supseteq\): Let \((x, \pi) \in \min(\|\sigma\|, {\le_1})\) and \((x', \pi') \in \|\sigma\|\). Then \((x, \pi) \le_1 (x', \pi')\). If this comparison is strict, then clearly \((x, \pi) \le (x', \pi')\). So suppose instead that \((x, \pi) \sim_1 (x', \pi')\). Then \((x', \pi') \in \min(\|\sigma\|, {\le_1})\) also.
Recall from above that \(\min(\|\sigma\|, {\le_1}) = \min(\|\sigma\|, {\le_0}) = M(\sigma) = B_G^\sigma \times \{\pi_G^\sigma\}\). We see that \((x, \pi), (x', \pi') \in \min(\|\sigma\|, {\le_1})\) implies \(\pi = \pi' = \pi_G^\sigma\), so \(\pi \sqsubseteq \pi'\) by reflexivity of \(\sqsubseteq\). This shows that \((x, \pi) \le (x', \pi')\).
As a consequence of these claims, \(M(\sigma) = \min(\|\sigma\|, {\le})\), so the operator \(G\) is also the tpo-operator corresponding to \(\le\). It only remains to show that \(\le\) satisfies \((\dag)\).
\(\implies\): Suppose \((x, \pi) \sim (x', \pi')\). Then from the definition of \(\le\) we have \(\pi \sqsubseteq \pi'\) and \(\pi' \sqsubseteq \pi\). By antisymmetry of \(\sqsubseteq\), we get \(\pi = \pi'\).
\(\impliedby\): Take \(\pi \in \P\) and \(x, x' \in X\). First suppose there is some \(\sigma\) such that \(\pi = \pi_G^\sigma\). By (B7) there is \(\delta\) such that \(\pi_G^\delta = \pi_G^\sigma = \pi\) and \(B_G^\delta \supseteq B_G^\emptyset\). Note that \(\|\emptyset\| = X \times \P\). In particular, \((x, \pi_G^\emptyset), (x', \pi_G^\emptyset) \in \|\emptyset\|\). By (B6) we have \(x, x' \in B_G^\emptyset \subseteq B_G^\delta\). That is, both \((x, \pi)\) and \((x', \pi)\) lie in \(B_G^\delta \times \{\pi_G^\delta\} = M(\delta) = \min(\|\delta\|, {\le})\). This shows \((x, \pi) \sim (x', \pi)\), as required.
For the remaining case, suppose there is no \(\sigma\) such that \(\pi = \pi_G^\sigma\). Then \(\pi \notin M(\sigma) \restrict \P\) for any \(\sigma\), and \((x, \pi), (x', \pi) \notin Q\). Thus \((x, \pi) \sim_1 (x', \pi)\). Clearly \(\pi \sqsubseteq \pi\) holds by reflexivity of \(\sqsubseteq\). By the definition of \(\le\) we see that \((x, \pi) \sim (x', \pi)\), as required.
(2) \(\implies\) (3): Suppose \(G\) is a tpo-based operator corresponding to some tpo \(\le\) over \(X \times \P\) satisfying \((\dag)\). Let \(x_0\) be an arbitrary member of \(X\). Define a relation \(\sqsubseteq\) on \(\P\) by
Then \(\sqsubseteq\) is transitive, total and reflexive since \(\le\) is. Moreover, \(\sqsubseteq\) is antisymmetric by \((\dag)\). Therefore \(\sqsubseteq\) is a total order.
For any \(\sigma\), write \(\pi_{\Min}^\sigma\) for \(\Min(\|\sigma\| \restrict \P, {\sqsubseteq})\). Then we have the following
Claim: \((x, \pi) \in \min(\|\sigma\|, {\le})\) if and only if \(\pi = \pi_{\Min}^\sigma\) and \(x \in \bigcap_{(\unknown, U) \in \sigma}\pi[U]\).
Proof: “if”: Suppose \(x, \pi\) are as stated. First we show \((x, \pi) \in \|\sigma\|\). Since \(\pi \in \|\sigma\| \restrict \P\), there is some \(\hat{x}\) with \((\hat{x}, \pi) \in \|\sigma\|\) and therefore \(\pi \in \mu_{\sigma,\hat{x}}\). If \((y, U) \in \sigma\) with \(y \ne \unknown\), then \((y, U) \in \mu_{\sigma,\hat{x}}\) too and clearly \(\pi \in \|y, U\|\). For \((\unknown, U) \in \sigma\) we have \(x \in \pi[U]\) by assumption, so \(\pi \in \|x, U\|\). This shows that \(\pi \in \|\mu_{\sigma,x}\|\), i.e. \((x, \pi) \in \|\sigma\|\).
To show minimality, take any \((x', \pi') \in \|\sigma\|\). Since \(\pi\) is \(\sqsubseteq\)-minimal in \(\|\sigma\| \restrict \P\), we have \(\pi \sqsubseteq \pi'\), i.e. \((x_0, \pi) \le (x_0, \pi')\). But by \((\dag)\), \((x_0, \pi) \sim (x, \pi)\) and \((x_0, \pi') \sim (x', \pi')\). Hence \((x, \pi) \le (x', \pi')\). This shows that \((x, \pi) \in \min(\|\sigma\|, {\le})\).
“only if”: Let \((x, \pi) \in \min(\|\sigma\|, {\le})\). Then
\[\pi \in \|\mu_{\sigma,x}\| \subseteq \bigcap_{(\unknown, U) \in \sigma}\|x, U\|\]i.e. \(x \in \pi[U]\) for all \((\unknown, U) \in \sigma\), as required. To show \(\pi\) is \(\sqsubseteq\)-minimal, let \(\pi' \in \|\sigma\| \restrict \P\). Then there is \(x'\) such that \((x', \pi') \in \|\sigma\|\), so \((x, \pi) \le (x', \pi')\). By \((\dag)\) again, we have \((x_0, \pi) \le (x_0, \pi')\), i.e. \(\pi \sqsubseteq \pi'\).
It follows from the claim that
for any \(\sigma\). Recalling that \(G\) is the tpo-based operator corresponding to \(\le\), we get
i.e. \(G\) is the partition-first operator corresponding to \(\sqsubseteq\), as required.
(3) \(\implies\) (1): Suppose \(G\) is the partition-first operator corresponding to a total order \(\sqsubseteq\) on \(\P\). The following will be used throughout the proof. [TODO: something similar was shown as part of the claim in the (2) \(\implies\) (3) direction above. Can this be extracted to a lemma to avoid writing the same proof twice?]
Claim: \(x \in B_G^\sigma\) if and only if \((x, \pi_G^\sigma) \in \|\sigma\|\).
Proof: “if”: \((x, \pi_G^\sigma) \in \|\sigma\|\) implies \(\pi_G^\sigma \in \|\mu_{\sigma,x}\|\), so \(\pi_G^\sigma \in \|x, U\|\) for all \((\unknown, U) \in \sigma\) and hence \(x \in \bigcap_{(\unknown, U) \in \sigma}\pi_G^\sigma[U] = B_G^\sigma\).
“only if”: Note that \(\pi_G^\sigma \in \|\sigma\| \restrict \P\) by definition of \(G\), so \(\pi \in \|y, U\|\) for all \((y, U) \in \sigma\), \(y \ne \unknown\). But \(x \in B_G^\sigma = \bigcap_{(\unknown, U) \in \sigma}\pi_G^\sigma[U]\) implies \(\pi_G^\sigma \in \|x, U\|\) for all \((\unknown, U) \in \sigma\) too. This implies \(\pi_G^\sigma \in \|\mu_{\sigma,x}\|\), i.e. \((x, \pi_G^\sigma) \in \|\sigma\|\).
It remains to show that \(G\) satisfies (B1) - (B8).
We show (B1) - (B3) together. Since \(\pi_G^\sigma \in \|\sigma\| \restrict \P\), there is some \(x\) such that \((x, \pi_G^\sigma) \in \|\sigma\|\). By the “if” direction of the claim above, \(x \in B_G^\sigma\), and (B3) holds. Moreover, property \((*)\) from Proposition 6 holds by the “only if” direction of the claim. Hence, by Proposition 6 part (2), \(G\) satisfies (B1) and (B2).
For (B4), suppose \(\|\sigma\| = \|\sigma'\|\). Then \(\|\sigma\| \restrict \P = \|\sigma'\| \restrict \P\), so \(\pi_G^{\sigma} = \pi_G^{\sigma'}\). By the claim,
\[\begin{aligned} x \in B_G^\sigma &\iff (x, \pi_G^{\sigma}) \in \|\sigma\| \\ &\iff (x, \pi_G^{\sigma'}) \in \|\sigma'\| \\ &\iff x \in B_G^{\sigma'} \end{aligned}\]i.e. \(B_G^\sigma = B_G^{\sigma'}\). Hence \(G\) satisfies (B4).
For (B5), suppose \(\pi_G^\sigma \in \|\sigma \concat \delta\| \restrict \P\). By definition, \(\pi_G^\sigma\) is \(\sqsubseteq\)-minimal in \(\|\sigma\| \restrict \P\). Since
\[\|\sigma\concat\delta\|\restrict\P =(\|\sigma\| \cap \|\delta\|) \restrict \P \subseteq \|\sigma\| \restrict \P \]it follows that \(\pi_G^\sigma\) is \(\sqsubseteq\)-minimal in \(\|\sigma \concat \delta\| \restrict \P\) also. Hence \(\pi_G^{\sigma\concat\delta} = \pi_G^\sigma\), and (B5) holds.
(B6) is just the “if” direction of the claim above
For (B7) we show (B7*); this implies (B7) since we have already shown (B3) holds. Fix some \(\sigma\) and take \(x \in B_G^\sigma\). Write \(\delta = \mu_{\sigma,x}\). Note that since \(\delta\) contains no elements of the form \((\unknown, U)\), we have \((y, \pi) \in \|\delta\|\) iff \((y', \pi) \in \|\delta\|\), for all \(y, y' \in X\) and \(\pi \in \P\).
Now since \(x \in B_G^\sigma\) implies \((x, \pi_G^\sigma) \in \|\sigma\|\), we have \((y, \pi_G^\sigma) \in \|\delta\|\) for all \(y \in X\), and \(\pi_G^\sigma \in \|\delta\| \restrict \P\). Take any \(\pi \in \|\delta\| \restrict \P\). From the definition of \(\delta\) it is easy to see that \((x, \pi) \in \|\sigma\|\), so \(\pi \in \|\sigma\| \restrict \P\). Since \(\pi_G^\sigma\) is minimal, we have \(\pi_G^\sigma \sqsubseteq \pi\). This shows that \(\pi_G^\sigma\) is also minimal in \(\|\delta\| \restrict \P\), i.e. \(\pi_G^\delta = \pi_G^\sigma\).
For the belief set, since neither \(\delta\) nor the empty sequence \(\emptyset\) contain any current reports \((\unknown, U)\), we clearly have
\[B_G^\delta = \bigcap_{(\unknown, U) \in \delta}\pi_G^\delta[U] = \bigcap\emptyset = B_G^\emptyset\]and (B7*) holds.
Finally, let \(\sigma_0, \ldots, \sigma_n\) and \(x_0,\ldots,x_n\) be as in the statement of (B8). Then for \(0 \le i < n\) we have \(\pi_G^{\sigma_{i+1}} \in \|\sigma_i\| \restrict \P\). Since \(\pi_G^{\sigma_i} = \Min(\|\sigma_i\| \restrict \P, {\sqsubseteq})\), we have \(\pi_G^{\sigma_i} \sqsubseteq \pi_G^{\sigma_{i+1}}\). By transitivity, \(\pi_G^{\sigma_0} \sqsubseteq \pi_G^{\sigma_n}\). On the other hand, we have \((x_0, \pi_G^{\sigma_0}) \in \|\sigma_n\|\) in the antecedent of (B8), so \(\pi_G^{\sigma_0} \in \|\sigma_n\| \restrict \P\). Hence \(\pi_G^{\sigma_n} \sqsubseteq \pi_G^{\sigma_0}\). By the antisymmetry of \(\sqsubseteq\), we have \(\pi_G^{\sigma_0} = \pi_G^{\sigma_n}\). Taking \(y = x_0\) and noting that \(x_0 \in B_G^{\sigma_0}\) by assumption, we have
\[(y, \pi_G^{\sigma_n}) = (x_0, \pi_G^{\sigma_0}) \in \|\sigma_0\|\]as required for (B8).
Remark. If \(G\) only satisfies (B1) - (B6) and (B8), then \(G\) is a tpo-based operator according to some total preorder \(\le\) satisfying the “\(\implies\)” direction of \((\dag)\), and we have \(|\min(\|\sigma\|, {\le}) \restrict \P| = 1\).
Old ideas
(B~1) If \(U\) is a union of cells of \(\pi_G(\sigma)\), then \(B_G(\sigma \append (\unknown, U)) \subseteq U\)
(B~2) For all \(\sigma\) and \(U\) there is \(V\) such that \(U \subseteq V\) and \(B_G(\sigma \append (\unknown, U)) \subseteq V\)
(B~3) \(\pi_G(\sigma) \preceq \pi_G(\sigma\append(\unknown, U))\)
(B~4) There is an AGM operator 8 \(\star\) and a function \(f(\cdot\ ; B, \pi): 2^X \to 2^X\) for each \(B \subseteq X\), \(\pi \in \P\) such that
\[B_G(\sigma \append (\unknown, U)) = B_G(\sigma) \star f(U; B_G(\sigma), \pi_G(\sigma))\](B~5) \(\pi_G(\sigma) \in \|x, U\|\) for all \((\unknown, U) \in \sigma\) and \(x \in B_G(\sigma)\)
(B~6) If \(\pi_G(\sigma)\) is the unit partition and \(B_G(\sigma) \cap U \ne \emptyset\), then \(B_G(\sigma \append (\unknown, U)) = B_G(\sigma) \cap U\)
(B~1) is the Success postulate for belief in the case where the incoming report is trusted. (B~2) is Proxy Success (see e.g. [BH18]). (B~3) says that trust in the source does not increase on receipt of uncertain information. 9 (B~4) says that the belief part of \(G\) is a selective revision operator, in that it uses an AGM operator to revise by a transformed input \(f(U)\), where the transformation function \(f\) depends only on the current belief set and partition. (B~5) is similar to (P1): it says that all current reports are sound for \(\pi\) and any plausible state (i.e. any state in the belief set). (B~6) says that if the source is fully trusted after input \(\sigma\), beliefs are updated simply by intersection for any new information consistent with current beliefs.
Multiple sources¶
Let \(S\) be a finite set of sources.
TODO: change \(\mu\) to some other letter to distinguish between partition revision sequences, as with \(\sigma\) above?
Definition 5
A multi-source partition and belief revision operator is a mapping \({H : (S \times X^\unknown \times \O)^* \to 2^X \times \P^S}\). We write \((B_H(\mu), \vec{\pi}_H(\mu))\) for the components of \(H(\mu)\), and \(\pi_H^s(\mu)\) for the partition corresponding to each source \(s\) in \(\vec{\pi}_H(\mu)\).
Again, postulates from the previous cases apply to multi-source operators with slight modifications. New postulates may be introduced to govern the interaction between beliefs and claims from different sources. For example:
(S1) If \(\pi_H^s(\mu) \preceq \pi_H^t(\mu)\) and \(B_H(\mu \append (t, \unknown, U)) \subseteq U\), then \(B_H(\mu \append (s, \unknown, U)) \subseteq U)\)
(S2) If \(\pi_H^s(\mu) \preceq \pi_H^t(\mu)\) then \(B_H(\mu \append (s, \unknown, U)) \subseteq B_H(\mu \append (t, \unknown, U))\)
(S3) If \(\pi_H^s(\mu)[x] \subseteq \pi_H^t(\mu)[x]\) and \(x \in U\), then \(\pi_H^s(\mu')[x] \subseteq \pi_H^t(\mu')[x]\), where \(\mu' = \mu \append (s, x, U)\)
(S4) \(\bigcap_{(s, \unknown, U) \in \mu}{\pi_H^s(\mu)[U]} \ne \emptyset\)
(S1) says that if \(s\) is broadly more trusted than \(t\) (i.e. has a finer partition), then any report which would be believed when coming from \(t\) would also be believed when coming from \(s\). (S2) is a strengthening of this idea: if \(s\) is more trusted than \(t\), then any report from \(s\) is more informative than the same report from \(t\). (S3) says that if \(s\) is more trusted than \(t\) at the state \(x\), learning that \(s\) made a correct statement at \(x\) previously does not change this. (S4) is a strong condition; it requires consistency of the expansions of the “current” reports from all sources, taken with respect to the latest estimate of the partitions.
- 1
This definition can be movitated by the trust set idea: \(U\) is sound if for every \(V\) in the trust set, \(U \vdash V\) implies \(x \vDash V\). If trust sets are unions of partitions cells, then this definition is equivalent.
- 2
This does not follow from \(M(\mu) = \min(\|\mu\|, {\le_0})\), since \(\le_0\) is not necessarily total.
- 3
According to the Wikipedia article on the Szpilrajn extension theorem, this result was shown by Arrow (presumably Kenneth Arrow?) and Hansson (presumably Sven Ove Hansson?). Since it is quite straightforward I did not attempt to find their proofs in the literature.
- 4
Excluding the trivial partition \(\{X\}\).
- 5
For (P2) failure consider \(X = \{a,b,c,d\}\) and \(\mu = \langle(a, \{b,c\}), (a, \{b,d\})\rangle\).
- 6
Note that (1) is equivalent to (P1) above, and (3) is (P2).
- 7
E.g. for \(\pi = \{X\}\) the coarsest partition, we have \((x, \pi) \in \|\sigma\|\) for any \(x \in X\).
- 8
Following [KSH97], an AGM operator in this context is a mapping \(\star: 2^X \times 2^X \to 2^X\) satisfying: i) \(B \star U \subseteq U\); ii) if \(U \ne \emptyset\) then \(B \star U \ne \emptyset\); iii) if \(B \cap U \ne \emptyset\) then \(B \star U = B \cap U\); iv) if \((B \star U) \cap V \ne \emptyset\) then \(B \star (U \cap V) = (B \star U) \cap V\).
- 9
This does not rule out the possibility of trust decreasing, however. E.g. suppose \(\mu\) contains \((\unknown, U)\) and we receive a new report of \((\unknown, U^c)\). It does not seem unreasonable that the partition should be coarsened in this case.