Trust contraction¶
Problem statement¶
Suppose we trust an agent on a set of propositions \(T\), and come to learn that \(\phi \in T\) is false. We wish to give up trust in \(\phi\) and produce a new trust set \(T - \phi\). How should this be done?
Framework¶
Let \(S\) be a finite and non-empty set of states. A proposition is a subset \(U \subseteq S\). A trust set will be a set of propositions, which intuitively represent those on which we trust the agent in question. The interpretation of trust is the following: we trust the agent on \(U \subseteq S\) if we would revise our beliefs by \(U\) upon receiving information \(U\). That is, we accept information \(U\) at face value (e.g. do not weaken it due to perceived lack of expertise of the agent concerning \(U\)). Note that this does not imply we would believe \(U\) after revision. 1
Under this interpretation, the tautology \(S\) and contradiction \(\emptyset\) should be trusted. 2 We also require a trust set to respect logical operations of negation and disjunction.
Definition 1
A trust set is a family of subsets \(T \subseteq 2^S\) such that
\(S \in T\)
If \(U \in T\) then \(S \setminus U \in T\)
If \(U, V \in T\) then \(U \cup V \in T\)
Let \(\T\) denote the set of trust sets.
\(T\) is also closed under conjunction (intersection) by De Morgan’s laws. Note that a trust set is just a σ-algebra on \(S\).
The objects of our study are contraction functions, which modify trust sets when given a proposition.
Definition 2
A contraction function is a function \(-\) mapping any trust set \(T\) and any proposition \(U \in 2^S \setminus \{\emptyset, S\}\) to a new trust set \(T - U\).
Note that we exclude the pathological cases of removing trust in a tautology or contradiction, which as per Definition 1 must always be trusted.
Trust sets and partitions¶
The finiteness of \(S\) means there is a link between trust sets (i.e σ-algebras over \(S\)) and partitions of \(S\).
Notation. For a set \(X\), let \(X^\cup\) denote the set of all unions of \(X\), i.e. \(X^\cup = \{\bigcup X' \mid X' \subseteq X\}\).
Proposition 1
The mapping \(\Pi \mapsto \Pi^\cup\) is a bijection from the set of partitions of \(S\) into the set of trust sets \(\T\).
Proof.
First we show this map is well-defined, i.e. that \(\Pi^\cup\) is indeed a trust set for any partition \(\Pi\). We take the three properties from Definition 1 in turn.
By definition of a partition we have \(\bigcup \Pi = S\). Since \(\bigcup \Pi \in \Pi^\cup\), \(S \in \Pi^\cup\).
Let \(U \in \Pi^\cup\), i.e. \(U = \bigcup \Pi'\) for some \(\Pi' \subseteq \Pi\). Since sets in \(\Pi\) are disjoint,
\[S \setminus U = \left(\bigcup \Pi \right) \setminus \left(\bigcup \Pi' \right) = \bigcup\left( \Pi \setminus \Pi' \right) \in \Pi^\cup\]Let \(U, V \in \Pi^\cup\). Clearly \(U \cup V \in \Pi^\cup\) too.
Next we show injectivity, i.e. \(\Pi^\cup = (\Pi')^\cup\) implies \(\Pi = \Pi'\) for any two partition \(\Pi, \Pi'\). Indeed, suppose \(\Pi^\cup = (\Pi')^\cup\) and let \(U \in \Pi\). Then \(U \in \Pi^\cup = (\Pi')^\cup\), so there are \(U'_1,\ldots,U'_n \in \Pi'\) such that \(U = U'_1 \cup \cdots \cup U'_n\). In turn, each \(U'_i\) lies in \((\Pi')^\cup = \Pi^\cup\), so there are \(V_{i1},\ldots,V_{im_i} \in \Pi\) such that \(U'_{ij} = V_{i1} \cup \cdots \cup V_{im_i}\). This means
so \(V_{ij} \subseteq U\) for each \(i, j\). But both \(V_{ij}\) and \(U\) are non-empty sets in the partition \(\Pi\); since distinct sets in a partition are disjoint, we must have \(V_{ij} = U\) for all \(i, j\). In particular, \(U'_1 = V_{11} \cup \cdots \cup V_{1m_1} = U \cup \cdots \cup U = U\), so \(U \in \Pi'\).
This shows that \(\Pi \subseteq \Pi'\). By symmetry, \(\Pi' \subseteq \Pi\) also, so \(\Pi = \Pi'\).
To complete the proof we show surjectivity. Let \(T\) be an arbitrary trust set. We must find a partition \(\Pi\) such that \(T = \Pi^\cup\). Set
i.e. \(U \in \Pi\) iff \(U \in T\), \(U \ne \emptyset\) and \(V \not\subset U\) for any other \(V \in T \setminus \{\emptyset\}\). Note that \(\Pi\) is non-empty since \({T \setminus \{\emptyset\} \ne \emptyset}\) (e.g. \(S \in T \setminus \{\emptyset\}\)) and \(T\) is finite.
First we show that \(T = \Pi^\cup\). Clearly \(\Pi \subseteq T\), and since \(T\) is closed under unions, \(\Pi^\cup \subseteq T\) (as a special case, the empty union \(\emptyset = \bigcup \emptyset\) is in \(T\) since \(S \in T\) implies \(\emptyset = S \setminus S \in T\)). For the reverse inclusion, let \(U \in T\). Set
We will show \(Q = U\). Clearly \(Q \subseteq U\). Suppose – for contradiction – that \(Q \subset U\). Then since both \(Q\) and \(U\) are in \(T\) and \(T\) is closed under complements and intersections, \(U \setminus Q = U \cap (S \setminus Q) \in T \setminus \{\emptyset\}\). We use the following claim.
Claim: there is \(V \in \Pi\) with \(V \subseteq U \setminus Q\).
Proof of claim. If \(U \setminus Q \in \Pi\) then simply take \(V = U \setminus Q\). If not, \(U \setminus Q\) is a non-empty set in \(T\) which is not minimal, so there exists some \(V_1 \in T \setminus \{\emptyset\}\) with \(V_1 \subset U \setminus Q\). If \(V_1 \in \Pi\), then take \(V = V_1\). If not then we may repeat this argument: there is \(V_2 \in T \setminus \{\emptyset\}\) with \(V_2 \subset V_1 \subset U \setminus Q\), and so on. Since \(T\) is finite, this must end after finitely steps with some \(V_n \in \Pi\). Indeed, if not then there are infinitely many distinct sets \(V_1 \supset V_2 \supset V_3 \supset \cdots\), which cannot be the case when \(T\) is finite. Taking \(V = V_n \subset \cdots \subset V_1 \subset U \setminus Q\), the claim is proved.
Now we have \(V \subseteq U \setminus Q\) and \(V \in \Pi\). In particular \(V \subseteq U\), so by definition of \(Q\), \(V \subseteq Q\). But this means \(V \subseteq (U \setminus Q) \cap Q = \emptyset\), i.e. \(V = \emptyset\). But this contradicts \(V \in \Pi\). Our original assumption that \(Q \subset U\) is therefore false. Together with \(Q \subseteq U\) this shows \(Q = U\). Finally, since \(U\) was an arbitrary element of \(T\) and \(Q \in \Pi^\cup\), this shows \(T \subseteq \Pi^\cup\) and hence \(T = \Pi^\cup\).
It only remains to show that \(\Pi\) is a partition of \(S\). It is clear that \(\Pi\) covers \(S\), since \(S \in T = \Pi^\cup\) implies \(S \subseteq \bigcup \Pi\) on the one hand, but \(\Pi \subseteq 2^S\) implies \(\bigcup \Pi \subseteq S\) on the other. Hence \(\bigcup \Pi = S\).
To show that distinct sets in \(\Pi\) are disjoint, let \(U, V \in \Pi\), \(U \ne V\). Since \(\Pi \subseteq T\) and \(T\) is closed under intersection, \({U \cap V \in T}\). Clearly \(U \cap V \subseteq U\), and in fact \(U \cap V \subset U\), since \(U \cap V = U\) would imply \(U \subset V\) which contradicts \(V \in \Pi\). Now if \(U \cap V\) were non-empty, we would have \(U \cap V \in T \setminus \{\emptyset\}\) and \(U \cap V \subset U\), but this contradicts \(U \in \Pi\). Hence \(U \cap V = \emptyset\), i.e. \(U\) and \(V\) are disjoint. This shows that \(\Pi\) is indeed a partition and completes the proof.
This results shows that any partition of \(S\) induces a trust set by taking the closure under unions. Conversely, any trust set is uniquely formed from a partition in this way, where the cells of the partition represent the strongest propositions on which the agent is trusted. We will write \(T_\Pi\) for \(\Pi^\cup\) to emphasise that \(\Pi^\cup\) is a trust set.
The connection between trust sets and partitions also respects partition refinement.
Proposition 2
\(\Pi\) refines \(\Pi'\) if and only if \(T_{\Pi} \supseteq T_{\Pi'}\).
Proof.
We use the following definition: \(\Pi\) refines \(\Pi'\) if and only if for every \(U \in \Pi\) there is \(V \in \Pi'\) with \(U \subseteq V\).
“if”: Suppose \(T_{\Pi} \supseteq T_{\Pi'}\). Take \(U \in \Pi\). Then \(U\) is non-empty, so there is some \(x \in U\). Since \(\Pi'\) is a partition, there is a unique \(V \in \Pi'\) with \(x \in V\). Note that \(V \in \Pi' \subseteq T_{\Pi'} \subseteq T_{\Pi}\), so \(V\) can be written as \(V = U_1 \cup \cdots \cup U_n\) for some \(U_1,\ldots,U_n \in \Pi\). So we have \(x \in V = U_1 \cup \cdots \cup U_n\). But \(U\) is the unique set in \(\Pi\) containing \(x\), which means \(U_i = U\) for some \(i\). Hence \(U = U_i \subseteq U_1 \cup \cdots \cup U_n = V\). Since \(U\) was an arbitrary set in \(\Pi\), this shows that \(\Pi\) refines \(\Pi'\).
“only if”: Suppose \(\Pi\) refines \(\Pi'\). We will show \(\Pi' \subseteq T_{\Pi}\), which implies \(T_{\Pi'} \subseteq T_{\Pi}\). To that end, let \(V \in \Pi'\). For each \(x \in V\), there is a unique set \(U_x \in \Pi\) with \(x \in U_x\). Thus \(V \subseteq \bigcup_{x \in V}{U_x}\).
By refinement, for each \(U_x\) there is \(V_x \in \Pi'\) such that \(U_x \subseteq V_x\). In particular, \(x \in V_x\). But \(V\) is the unique set in \(\Pi'\) containing \(x\), so we must have \(V_x = V\) for all \(x \in V\). In particular, \(U_x \subseteq V\). This shows that \(\bigcup_{x \in V}{U_x} \subseteq V\), and consequently \(\bigcup_{x \in V}{U_x} = V\). Clearly the union lies in \(T_{\Pi}\). Since \(V\) was an arbitrary member of \(\Pi'\), this shows that \(\Pi' \subseteq T_\Pi\) and the result follows.
Proposition 3
\(T_\Pi \cap T_{\Pi'} = T_{\Pi \vee \Pi'}\)
Proof.
Recall that, by definition, \(\Pi \vee \Pi'\) is the least upper bound of \(\{\Pi, \Pi'\}\) in the lattice of partitions, i.e. the finest partition coarser than both \(\Pi\) and \(\Pi'\).
First note that since both \(T_\Pi\) and \(T_\Pi'\) are trust sets, \(T_\Pi \cap T_{\Pi'}\) is also. By Proposition 1, there is \(\Pi^*\) such that \(T_{\Pi^*} = T_\Pi \cap T_{\Pi'}\). Since both \(T_{\Pi^*} \subseteq T_\Pi\) and \(T_{\Pi^*} \subseteq T_{\Pi'}\), we have by Proposition 2 that both \(\Pi\) and \(\Pi'\) refine \(\Pi^*\), i.e. \(\Pi^*\) is an upper bound for \(\{\Pi, \Pi'\}\) in the lattice of partitions. Suppose \(\hat{\Pi}\) is also an upper bound. Then, applying Proposition 2 in the other direction, we have \(T_{\hat{\Pi}} \subseteq T_\Pi\) and \(T_{\hat{\Pi}} \subseteq T_{\Pi'}\). Hence \(T_{\hat{\Pi}} \subseteq T_{\Pi} \cap T_{\Pi'} = T_{\Pi^*}\), i.e. \(\Pi^*\) refines \(\hat{\Pi}\). Hence \(\Pi^* = \Pi \vee \Pi'\).
Hierarchical contraction functions¶
We introduce a class of contraction functions inspired by gradually coarsening partitions (see also Multi-agent Trust Expansion). In light of the above results, coarsening partitions of \(S\) can be equivalently represented by decreasing trust sets.
Definition 3
\(-\) is a hierarchical contraction function if there is a function \(\sigma: \T \to \T^{\N_0}\) such that
\(\sigma_T(0) = T\)
\(\sigma_T(n+1) \subseteq \sigma_T(n)\)
\(\sigma_T(n) = \{\emptyset, S\}\) for some \(n \in \N\)
For all \(U \in 2^S \setminus \{\emptyset, S\}\) we have \(T - U = \sigma_T(n)\) for \(n = \min\{k \in \N_0 \mid U \notin \sigma_T(k)\}\)
That is, the function \(\sigma\) assigns to each initial trust set \(T\) an decreasing sequence \(T = \sigma_T(0) \supseteq \sigma_T(1) \supseteq \sigma_T(2) \supseteq \cdots\) which eventually becomes the minimal trust set \(\{\emptyset,S\}\). Contraction by \(U\) is performed by simply finding the minimal index at which \(U\) is no longer trusted. Note that condition (3) ensures that (4) is well-defined (i.e. there actually is some \(k\) with \(U \notin \sigma_T(k)\)).
Some postulates and a representation result¶
Consider the following postulates for trust contraction.
(P1) \(U \notin T - U\)
(P2) \(T - U \subseteq T\)
(P3) if \(U \notin T\), then \(T \subseteq T - U\)
(P4) if \(U \in T - V\), then \(T - U \subseteq T - V\)
(P5) if \(U \in T\) and \(U \not\in T - V\), then \(T - V \subseteq T - U\)
These will be shown to characterise the hierarchical contraction functions.
The first three postulates seem uncontroversial. (P1) ensures that contraction was a success. (P2) says that the agent is not trusted on any new matters after contraction. (P3) says that trust does not decrease if \(U\) was not trusted in the first place.
(P4) and (P5) are less intuitive. (P4) says that if \(U\) is sufficiently well-trusted that it remains after contracting \(V\), contracting \(U\) is at least as severe as contracting \(V\). (P5) says that if \(U\) is removed from \(T\) as a “side-effect” of contracting \(V\), then contraction by \(U\) cannot be more severe than contraction by \(V\).
Note that (P2) and (P3) imply \(T - U = T\) whenever \(U \notin T\). Consequently, (P2), (P3) and (P5) imply the following stronger version of (P5):
(P5’) if \(U \notin T - V\) then \(T - V \subseteq T - U\)
More interestingly, these postulates imply that all “contracts” of \(T\) are nested with respect to set inclusion.
Lemma 1
(P2), (P3), (P4) and (P5) together imply the following property:
(P6) Either \(T - U \subseteq T - V\) or \(T - V \subseteq T - U\)
Proof. Let \(T \in \T\) and \(U, V \in 2^S \setminus \{\emptyset, S\}\). If \(U \in T - V\), then \(T - U \subseteq T - V\) by (P4). Otherwise \(U \notin T - V\), and \(T - V \subseteq T - U\) by (P5’).
This allows us to prove the representation result.
Theorem 1
A contraction function \(-\) satisfies (P1) through to (P5) if and only if it hierarchical.
Proof.
“if”: Let \(-\) be a hierarchical contraction function with associated function \(\sigma\). (P1) follows from property (4) in Definition 3. (P2) follows from properties (1), (2) and (4): we have \(T - U = \sigma_T(n) \subseteq \sigma_T(0) = T\). (P3) follows from properties (1) and (4): we have \(T - U = \sigma_T(0) = T\) whenever \(U \notin T\).
For (P4), suppose \(U \in T - V = \sigma_T(n_V)\). Then by property (2), \(U \in \sigma_T(k)\) for all \(k \le n_V\). Hence \(n_U > n_V\), and property (2) again gives \(T - U = \sigma_T(n_U) \subseteq \sigma_T(n_V) = T - V\).
For (P5), suppose \(U \in T\) and \(U \notin T - V = \sigma_T(n_V)\). Since \(n_U = \min\{k \in \N_0 \mid U \notin \sigma_T(k)\}\), \(n_V\) lies in a set whose minimum is \(n_U\). Hence \(n_U \le n_V\). Property (2) therefore gives \(T - V = \sigma_T(n_V) \subseteq \sigma_T(n_U) = T - U\).
“only if”: Let \(-\) be a contraction function satisfying the stated postulates. Let \(T\) be any trust set, and write
By Lemma 1, (P6) holds for \(-\). Consequently, \(\mathcal{Q}\) is totally ordered by set inclusion, and we can write \(\mathcal{Q} = \{T_1,\ldots,T_m\}\) such that \(T_1 \supseteq \cdots \supseteq T_m\). Define \(\sigma\) by
We show each of the properties from Definition 3 in turn. Property (1) holds by definition.
Property (2) holds by case analysis. If \(n=0\) then \(\sigma_T(n+1) = \sigma_T(1) = T - U\) for some \(U\), and (P2) gives \(\sigma_T(n+1) = T - U \subseteq T = \sigma_T(n)\). If \(1 \le n < m\) then \(\sigma_T(n+1) = T_{n+1} \subseteq T_n = \sigma_T(n)\) by our enumeration of \(\mathcal{Q}\). Finally, if \(n \ge m\) then \(\sigma_T(n+1) = \{\emptyset, S\}\) which is the minimal trust set, so clearly \(\sigma_T(n+1) \subseteq \sigma_T(n)\).
Property (3) also holds by definition: we have \(\sigma_T(m+1) = \{\emptyset, S\}\).
We come to property (4). Let \(U \in 2^S \setminus \{\emptyset, S\}\). Write \(K = \{k \in \N_0 \mid U \notin \sigma_T(k)\}\). We must show that \({T - U = \sigma_T(\min K)}\). There are two cases.
Case 1: (\(U \notin T\)). We have \(\sigma_T(0) = T\) which does not contain \(U\), so \(0 \in K\) and thus \(\min K = 0\). On the other hand, (P2) and (P3) imply \(T - U = T\). Hence \(T - U = T = \sigma_T(0) = \sigma_T(\min K)\) as required.
Case 2: (\(U \in T\)). Note that \(T - U \in \mathcal{Q}\), so \(T - U\) appears at least once in the sequence \(\sigma_T\). Write \(n = \min\{k \in \N_0 \mid \sigma_T(k) = T - U\} \le m\), so that \(T - U = \sigma_T(n)\) but \(T - U \ne \sigma_T(k)\) for any \(k < n\). We are done if we can show \(n = \min K\).
First note that (P1) gives \(U \notin T - U = \sigma_T(n)\), so \(n \in K\). Suppose for contradiction that \(n\) is not minimal in \(K\), i.e there is some \(k \in K\) with \(k < n\). By definition of \(n\), we have \(\sigma_T(k) \ne \sigma_T(n)\).
Note that \(k\) cannot be \(0\), since by assumption \(U \in T = \sigma_T(0)\) and thus \(0 \notin K\). Hence \({1 \le k < n \le m}\), so \(\sigma_T(k) \in \mathcal{Q}\), i.e. there is some \(V \in 2^S \setminus \{\emptyset, S\}\) with \(\sigma_T(k) = T - V\). Now, \(k \in K\) means \({U \notin T - V}\). Applying (P5), we get \(T - V \subseteq T - U\). That is, \(\sigma_T(k) \subseteq \sigma_T(n)\). But \(k < n\) implies \(\sigma_T(k) \supseteq \sigma_T(n)\) by property (2) for \(\sigma\), which we showed above. Hence \(\sigma_T(k) = \sigma_T(n)\), but this contradicts \(\sigma_T(k) \ne \sigma_T(n)\). Finally, this shows that \(n = \min K\), and we are done.
- 1
Whether we would believe \(U\) or not depends on our prior beliefs, and doesn’t seem relevant to the question of trusting the agent.
- 2
It may seem counterintuitve to trust the agent on a contradiction. But the alternative, i.e. not trusting the agent on \(\emptyset\), means we would not revise by \(\emptyset\) upon receipt of \(\emptyset\). But that amounts to changing an inconsistent report into a consistent one before revision, which seems irrational. Moreover, if we want to trust the agent on the tautology \(S\) and for trust to be closed under negation, we are forced to trust \(\emptyset\).