=Paper=
{{Paper
|id=Vol-2680/paper5
|storemode=property
|title=On the Joint Revision of Belief and Trust
|pdfUrl=https://ceur-ws.org/Vol-2680/paper5.pdf
|volume=Vol-2680
|authors=Ammar Yasser,Haythem Ismail
|dblpUrl=https://dblp.org/rec/conf/ki/AmmarI20
}}
==On the Joint Revision of Belief and Trust==
https://ceur-ws.org/Vol-2680/paper5.pdf
Proceedings of the 6th Workshop on Formal and Cognitive Reasoning
On the Joint Revision of Belief and Trust
Ammar Yasser1 and Haythem O. Ismail2,1
1
German University in Cairo, Egypt
2
Cairo University, Egypt
{ammar.abbas,haythem.ismail}@guc.edu.eg
Abstract. Trust plays a vital role when it comes to beliefs. Deciding what to
believe and what not to believe depends, to a large extent, on trust. When an in-
formation source we trust conveys a piece of information, we are more likely to
believe it. On the contrary, we are more reluctant to believe information com-
municated by information sources we do not trust. In general, trust guides us
while revising our beliefs. Despite the existence of great bodies of literature on
trust and belief revision separately, a formal treatment for their intertwined rela-
tionship is lacking. Hence, in this paper, we argue that trust revision and belief
revision are inseparable processes. To provide a formal treatment for the joint
revision of beliefs and trust, we address issues concerning the formalization of
trust in information sources and provide AGM-style postulates for the rational
joint revision of the two attitudes which we refer to as information revision.
Keywords: Belief Revision · Trust Revision · Information Revision.
1 Introduction
Trust acts, even if we are not aware, as an information filter. We are willing to believe
in information communicated by sources we trust, cautious about information from
sources we do not trust, and suspicious about information from sources we mistrust.
Trust and mistrust are constantly revised; we gain more trust in information sources the
more they prove themselves to be reliable, and our trust in them erodes as they mislead
us one time after the other. Such attitudes allow us to be resilient, selective and astute. If
exhibited by logic-based agents, these same attitudes would make them less susceptible
to holding false beliefs and, hence, less prone to excessive belief revision. Moreover, by
revising trust, these agents will not forever be naively trusting nor cynically mistrusting.
Trust has been thoroughly investigated within multi-agent systems [3,9,20,19,29,22,
for instance], psychology [32,8,15, for instance], and philosophy [17,14,27, for in-
stance]. Crucially, it was also investigated in the logic-based artificial intelligence (AI)
literature by several authors [4,6,24,22,16,23]. Nevertheless, we believe that there are
several issues that are left unaddressed by the logical approaches. Intuitively, trust is
intimately related to misleading, on one hand, and belief revision, on the other. While
several logical treatments of misleading are to be found in the literature [31,7,30,18, for
instance], the relation of misleading to trust erosion is often not attended to or delegated
to future work. On the other hand, the extensive literature on belief revision [1,11, for
example], while occasionally addressing trust-based revision of beliefs [26,28,2] does
Copyright c 2020 for this paper by its authors. Use permitted under
Creative Commons License Attribution 4.0 International (CC BY 4.0).
55
On the Joint Revision of Belief and Trust
not have much to say about the revision of trust (but see [24,26] for minimal discus-
sions) and, as far as we know, any systematic study of jointly revising belief and trust.
The goal of this paper is, hence, twofold: (i) to motivate why belief and trust revision are
intertwined and should be carried out together, and (ii) to propose AGM-style postulates
for the joint revision of trust and belief.
The paper is structured as follows. Section 2 describes what we mean by trust, in-
formation and information sources. It also highlights the intuitions behind joint trust
and belief revision. In Section 3, we present information states, a generic structure rep-
resenting information and investigating its properties. Section 4 presents a powerful
notion of relevance which information structures give rise to. Finally, in Section 5, the
formal inter-dependency of belief and trust is explored, culminating in AGM-style pos-
tulates for joint belief-trust revision.3
2 Trust and Belief
It is often noted that trust is not a dyadic relation, between the trusted and the trustee,
but is a triadic relation involving an object of trust [27]. You trust your doctor with your
health, your mechanic with your car, your parents to unconditionally believe you, and
your mathematics professor to tell you only true statements of mathematics. Our inves-
tigation of the coupling of belief and trust lets us focus only on trust in sources of infor-
mation. Trust in information sources comes in different forms. Among Demolombe’s
[5,25] different types of trust in information sources, we focus on trust in sincerity and
competence since they are the two types relevant to belief revision and realistic in-
formation sources.4 A sincere information source is one which (if capable of forming
beliefs) only conveys what it believes; a competent source is one which only conveys
what is true. In this paper, we consider trust in the reliability of information sources,
where a source is reliable if it is both sincere and competent.5 Note that we do not take
information sources to only be cognitive agents. For example, a sensor (or perception,
in general) is a possible source of information. For information sources which are not
cognitive agents, reliability reduces to competence.
Rational agents constantly receive information, and are faced with the question of
whether to believe or not to believe. The question is rather simple when the new in-
formation is consistent with the agent’s beliefs, since no obvious risk lies in deciding
either way. Things become more interesting if the new information is inconsistent with
what the agent believes; if the agent decides to accept the new information, it is faced
with the problem of deciding on which of its old beliefs to give up in order to maintain
consistency. Principles for rationally doing this are the focus of the vast literature on
belief revision [1,12, for example].
It is natural to postulate that deciding whether to believe and how to revise our
beliefs–the process of belief revision–are influenced by how much we trust the source
3
For a more detailed discussion, the reader is kindly guided towards [33].
4
Trust in completeness, for example, is unrealistic since it requires that the source informs about
P whenever P is true.
5
As suggested by [18], it is perhaps possible that breach of sincerity and competence should
have different effects on belief revision; for simplicity, we do not consider this here though.
56
On the Joint Revision of Belief and Trust
of the new piece of information. (Also see [26,28,2].) In particular, in case of a conflict
with old beliefs, how much we trust in the source’s reliability and how much evidence
we have accumulated for competing beliefs seem to be the obvious candidates for guid-
ing us in deciding what to do. Thus, rational belief revision depends on trust.
But things are more complex. For example, suppose that information source σ1 ,
whom we trust very much, conveys φ to us. φ is inconsistent with our beliefs but,
because we trust σ1 , we decide to believe in φ and give away ψ which, together with
other beliefs, implies ¬φ. In this case, we say that φ is a refutation of ψ. So far, this is
just belief revision, albeit one which is based on trust. But, by stopping believing in ψ,
we may find it rational to revise, and decrease, our trust in σ2 who earlier conveyed ψ
to us. Moreover, suppose that φ, together with other beliefs, implies our old belief ξ.
We say that φ is a confirmation of ξ. This confirmation may trigger us to revise, and
increase, our trust in σ3 who is the source of ξ. Thus, trust revision depends on belief
revision. In fact, belief revision may be the sole factor that triggers rational trust revision
in information sources.
We need not stop there though. For, by reducing our trust in σ2 ’s reliability, we
are perhaps obliged to stop believing (or reduce our degree of belief in) ψ 0 which was
conveyed by σ2 . It is crucial to note that ψ 0 may be totally consistent with φ and we,
nevertheless, give it away. While we find such scenario quite plausible, classical belief
revision, with its upholding of the principle of minimal change, would deem it irrational.
Likewise, by increasing our trust in σ3 we may start believing (or raise our degree of
belief) in ξ 0 which was earlier conveyed by σ3 . This second round of belief revision
can start a second round of trust revision. It is clear that we may keep on doing this for
several rounds (perhaps indefinitely) if we are really fanatic about information and its
sources. Hence, we contend that belief revision and trust revision are so entangled that
they need to be combined into one process of joint belief-trust revision or, as we shall
henceforth refer to it, information revision.
3 Information States
In this section, we introduce formal structures for representing information in a way
that would facilitate information revision.
Definition 1. An information grading structure G is a quadruple (Db , Dt , ≺b , ≺t ),
where Db and Dt are non-empty, countable sets; and ≺b and ≺t are, respectively, total
orders over Db and Dt .
Db and Dt contain the degrees of belief and trust, respectively. They are not nec-
essarily finite, disjoint, different or identical.6 Moreover, to be able to distinguish the
strength by which an agent believes a proposition or trusts a source, the two sets are
ordered; here, we assume them to be totally ordered.
Definition 2. An information structure I is a quadruple (L, C, S, G), where
6
Db and Dt are usually the same; however, a qualitative account of trust and belief might have
different sets for grading the two attitudes.
57
On the Joint Revision of Belief and Trust
1. L is a logical language with a Tarskian consequence operator Cn,
2. C is a finite cover of L whose members are referred to as topics,
3. S is a non-empty finite set of information sources, and
4. G is an information grading structure.
Information structures comprise our general assumptions about information. S is
the set of possible information sources. Possible pieces of information are statements
of the language L, with each piece being about one or more, but finitely many, topics as
indicated by the L-cover C. L is only required to have a Tarskian consequence operator
[13]. A topic represents the scope of trust. That is, an agent trusts an information source
on particular topics. Moreover, a topic is a set of statements which may be closed under
all connectives, some connectives or none at all. Topics could also be disjoint or over-
lapping. Choosing topics to be not necessarily closed under logical connectives allows
us to accommodate interesting cases. For example, A may have, for the same source, a
different trust value when conveying φ to when it conveys ¬φ.
Definition 3. Let I = (L, C, S, (Db , Dt , ≺b , ≺t )) be an information structure. An in-
formation state K over I is a triple (B, T , H), where
1. B : L ,→ Db is a partial function referred to as the belief base,
2. T : S × C ,→ Dt is a partial function referred to as the trust base, and
3. H ⊆ L × S, the history, is a finite set of pairs (φ, σ) where, for every T ∈ C, if
φ ∈ T then (σ, T, dt ) ∈ T , for some dt ∈ Dt .
Trust in information sources is recorded in T (K).7 This is a generalization to ac-
commodate logics with an explicit account of trust in the object language [6,23, for
instance] as well as those without [22,21, for example]. H(K) acts as a formal device
for recording conveyance instances. Hence, a tuple of the form (φ, σ) in the history de-
notes that formula φ was acquired through source σ. As with T (K), we do not require
L to have an explicit account for conveying.
With this setup, having trust on single propositions, as is most commonly the case
in the literature [5,23, for instance], reduces to restricting all topics to be singletons. On
the other hand, we may account for absolute trust in sources by having a single topic to
which all propositions belong.
To put together all the pieces forming an information state, consider the following
example.
Example 1. Let an information grading structure G = ({b1 , b2 , b3 }, {t1 , t2 , t3 },
{(b1 ≺b b2 ), (b1 ≺b b3 ), (b2 ≺b b3 )}, {(t1 ≺t t2 ), (t1 ≺t t3 ), (t2 ≺t t3 )}). Hence,
a belief associated with b3 is the most preferred while a belief assigned b1 is the least
preferred. Similarly, a source associated with t3 is the most trusted while a source that
has a trust degree of t1 is the least trusted. Given G, we define information structure
I = (LV , C, {σ1 , σ2 }, G) where language LV is a propositional language with the set
V = {P, Q, S} of propositional variables and C = {TP , TQ , TS } where TP is the
7
It is worthy of mentioning that we use B(K), T (K), and H(K) to denote the belief base, trust
base, and history of a particular information state K. More importantly, we do not use such
notation to denote an invocation of a function with K as an argument.
58
On the Joint Revision of Belief and Trust
set of formulas containing P as a sub-formula, likewise for TQ and TS with Q and S
respectively . Finally, information state K = (B, T , H) where
– B = {(P, b2 ), (Q, b3 ), (Q → P, b3 )}
– T = {(σ1 , TP , t2 ), (σ1 , TS , t1 ), (σ2 , TQ , t3 ), (σ2 , TS , t2 )}
– H = {(P, σ1 ), (Q, σ2 ), (Q → P, σ2 ), (S, σ1 )}
This example shows how information is represented in an information state. Trust
attribution for information sources with different topics is recorded. Based on that, we
have P ,Q, and Q → P that are believed with varying degrees of belief.8 Moreover, it is
important to note that S was conveyed by σ1 but was not believed. There could be many
reasons for not believing a conveyed proposition, one of them could be that source σ1
has the weakest degree of trust on the topic containing S.
So far, we defined what information states are. We now define the following abbre-
viations of which we will later make use.
– σ(H(K)) = {φ | (φ, σ) ∈ H(K)}
– SK = {σ | (φ, σ) ∈ H(K)}
– F or(B(K)) = {φ | (φ, db ) ∈ B(K)}
– ΦK = {φ | φ ∈ F or(B(K)) or (φ, σ) ∈ H(K) f or any σ}
Information revision is the process of revising an information state K with the con-
veyance of a formula φ by a source σ yielding a revised information state. Every infor-
mation revision operator is associated with a conveyance inclusion filter F ⊆ L × S
which determines the conveyance instances that make it into H(K). Hence, a generic
revision operator is denoted by nF , where F is the associated filter. Revising K with a
conveyance of φ by σ is denoted by K nF (φ, σ). We require all revision operators nF
to have the same effect on the history:
H(K) ∪ {(φ, σ)} (φ, σ) ∈ F
H(K nF (φ, σ)) =
H(K) otherwise
There are three major filter types. A filter F is non-forgetful if F = L × S; it is
forgetful if ∅ 6= F ⊂ S × L; and it is memory-less if F = ∅. Having filters beside
the non-forgetful one is to simulate realistic scenarios where an agent does not always
remember every piece of information that was conveyed to it. Henceforth, the subscript
F will be dropped from nF whenever this does not result in ambiguity.
Definition 4. Let φ ∈ L and σ ∈ S.
1. φ is more entrenched in state K2 over state K1 , denoted K1 ≺φ K2 , if (i) φ ∈ /
Cn(F or(B(K1 ))) and φ ∈ Cn(F or(B(K2 ))); or (ii) (φ, b1 ) ∈ B(K1 ), (φ, b2 ) ∈
B(K2 ), and b1 ≺b b2 . If K1 ⊀φ K2 and K2 ⊀φ K1 , we write K1 ≡φ K2 .
8
For this simple example, the mapping between trust degrees and belief degrees was straight
forward. However, as we will see later, addressing the relationship between trust degrees and
belief degrees is a complex matter.
59
On the Joint Revision of Belief and Trust
2. σ is more trusted on topic T in state K2 over state K1 , denoted K1 ≺σ,T K2 ,
if (σ, T, t1 ) ∈ T (K1 ), (σ, T, t2 ) ∈ T (K2 ), and t1 ≺t t2 . If K1 ⊀σ,T K2 and
K2 ⊀σ,T K1 , we write K1 ≡σ,T K2 .
Intuitively, a belief changes after revision if it is added to or removed from the
belief base, or if its associated grade changes. Similarly, trust in a source regarding a
topic changes after revision if the associated trust grade changes.
4 Relevant Change
As proposed earlier, the degrees of trust in sources depend on the degrees of belief in
formulas conveyed by these sources and vice versa. To model such dependence, we
need to keep track of which formulas and which sources are “relevant” to each other.
First, we recall a piece of terminology due to [11]: Γ ⊂ L is a φ-kernel if Γ |= φ and,
for every ∆ ⊂ Γ , ∆ 6|= φ.
Definition 5. Let K be an information state. The support graph G(K) = (SK ∪ ΦK , E)
is such that (u, v) ∈ E if and only if
1. u ∈ SK , v ∈ ΦK , and v ∈ u(H(K));
2. u ∈ ΦK , v ∈ ΦK , u 6= v, and u ∈ Γ ⊆ ΦK where Γ is a v-kernel; or
3. u ∈ ΦK , v ∈ SK , and (v, u) ∈ E.
A node u supports a node v if there is a simple path from u to v.
Figure 1 shows an example of the support graph for the information state presented
in Example 1. Source σ1 conveyed both P and S, thus, according to clause 1 in Defini-
tion 5, there is an edge from σ1 to both P and S. Moreover, there is an edge from both
P and S to σ1 given the third clause in Definition 5. Similarly, there are edges from σ2
to both Q and Q → P as well as from Q and Q → P to σ2 . Finally, {Q → P, Q}
is a P -kernel. Hence, we have an edge from Q to P and from Q → P to P given the
second clause in the definition of the support graph.
The support graph allows us to trace back and propagate changes in trust and belief
to relevant beliefs and information sources along support paths. Instances of support
may be classified according to the type of relata.
Observation 1. Let K be an information state.
1. φ ∈ ΦK supports ψ ∈ ΦK if and only if φ 6= ψ and (i) φ ∈ Γ ⊆ ΦK where Γ is a
ψ-kernel or (ii) φ supports some σ ∈ SK which supports ψ.
2. φ ∈ ΦK supports σ ∈ SK if and only if ψ ∈ σ(H(K)) and φ ∈ Γ ⊆ ΦK where Γ
is a ψ-kernel or φ supports some σ 0 ∈ SK which supports σ.
3. σ ∈ SK supports φ ∈ ΦK if and only if ψ ∈ σ(H(K)) and ψ ∈ Γ ⊆ ΦK where Γ
is a φ-kernel or σ supports some σ 0 ∈ SK which supports φ.
4. σ ∈ SK supports σ 0 ∈ SK if and only if σ 6= σ 0 σ supports some φ ∈ ΦK which
supports σ 0 .
60
On the Joint Revision of Belief and Trust
Fig. 1: The support graph where σ2 conveyed Q and Q → P that both logically imply P which
was conveyed alongside S by σ1 .
Thus, given the first three clauses, the support relation from a formula to a formula,
a formula to a source, or a source to formula may be established in two ways: (i) either
purely logically via a path of only formulas or (ii) with the aid of a trust link via an
intermediate source. A source can only support a source, however, by supporting a
formula which supports that other source. Note that self-support is avoided by requiring
support paths to be simple.
The support graph provides the basis for constructing an operator of rational in-
formation revision. Traditionally, belief revision is concerned with minimal change
[10,12]. In this paper, we model minimality using relevance. However, our notion of
relevance is not restricted to logical relevance as with classical belief revision; it also
accounts for source relevance. When an information state K is revised with formula φ
conveyed by source σ, we would want to confine changes in belief and trust to formulas
and sources relevant to φ, ¬φ, and σ.
Definition 6. Let K be an information state and u and v be nodes in G(K). u is v-
relevant if u supports v or v supports u. Further, if φ, ψ ∈ L with Γφ ⊆ ΦK a φ-kernel
and Γψ ⊆ ΦK a ψ-kernel where u is v-relevant for some u ∈ Γφ and v ∈ Γψ , then φ is
ψ-relevant.
Observation 2. If K is an information state where u is v-relevant then (i) v is u-
relevant; (ii) if v ∈ σ(H(K)) and u 6= σ, then u is σ-relevant; and (iii) if v ∈ SK ,
φ ∈ v(H(K)), and u 6= φ, then, u is φ-relevant.
Hence, relevance is a symmetric relation. Crucially, if σ conveys φ, then the for-
mulas and sources relevant to φ (other than σ) are exactly the formulas and sources
relevant to σ (other than φ). For this reason, when revising with a conveyance of φ by
σ it suffices to consider only φ-relevant (and ¬φ-relevant) formulas and sources.
61
On the Joint Revision of Belief and Trust
5 Information Revision
5.1 Intuitions
Table 1 shows the possible reasonable effects on B(K) as agent A revises its information
state K with (φ, σ); Kn is shorthand for K n (φ, σ) while “neither” means that neither
φ nor ¬φ is in Cn(F or(B(K))).
# K Kn φ ¬φ Notes
B1 neither (φ, b) ∈ B(Kn ) K ≺φ Kn K ≡¬φ Kn -
B2 neither neither K ≡φ Kn K ≡¬φ Kn -
B3 (φ, b1 ) ∈ B(K) (φ, b2 ) ∈ B(Kn ) K ≺φ Kn K ≡¬φ Kn b1 ≺b b2
B4 (φ, b1 ) ∈ B(K) (φ, b1 ) ∈ B(Kn ) K ≡φ Kn K ≡¬φ Kn -
B5 (¬φ, b1 ) ∈ B(K) (φ, b2 ) ∈ B(Kn ) K ≺φ Kn Kn ≺¬φ K -
B6 (¬φ, b1 ) ∈ B(K) neither K ≡φ Kn Kn ≺¬φ K -
B7 (¬φ, b1 ) ∈ B(K) (¬φ, b2 ) ∈ B(Kn ) K ≡φ Kn Kn ≺¬φ K b2 ≺b b1
B8 (¬φ, b1 ) ∈ B(K) (¬φ, b1 ) ∈ B(Kn ) K ≡φ Kn K ≡¬φ Kn -
B9 B(K) |= {(¬φ, b1 ), (φ, b2 )} (φ, b3 ) ∈ B(Kn ) K ≺φ Kn Kn ≺¬φ K b2 ≺b b3
B10 B(K) |= {(¬φ, b1 ), (φ, b2 )} (φ, b2 ) ∈ B(Kn ) K ≡φ Kn Kn ≺¬φ K -
B11 B(K) |= {(¬φ, b1 ), (φ, b2 )} (φ, b3 ) ∈ B(Kn ) Kn ≺φ K Kn ≺¬φ K b3 ≺b b2
B12 B(K) |= {(¬φ, b1 ), (φ, b2 )} neither Kn ≺φ K Kn ≺¬φ K -
B13 B(K) |= {(¬φ, b1 ), (φ, b2 )} (¬φ, b1 ) ∈ B(Kn ) Kn ≺φ K K ≡¬φ Kn -
B14 B(K) |= {(¬φ, b1 ), (φ, b2 )} (¬φ, b3 ) ∈ B(Kn ) Kn ≺φ K Kn ≺¬φ K b3 ≺b b1
Table 1: The admissible scenarios of belief revision.
In Cases B1 and B2 , A initially believes neither φ nor ¬φ. After revision, B1 shows
the case where A believes φ as it has no evidence for the contrary. However, another
possible scenario would be that portrayed in Case B2 where A decides that the weight
of evidence for and against φ is comparable and hence φ can not be accepted.
In the next two cases, A already believes φ and revision with φ confirms what is
already believed. Thus, φ could become more entrenched as now σ also supports φ
(Case B3 ) or φ’s degree may remain unchanged (Case B4 ) which could occur when φ
is believed with the maximum degree of belief, if there is such a degree, or when φ has
only been ever conveyed by σ, who are now only confirming itself. In this latter case,
A might choose not to increase the degree of belief in φ.
A believes ¬φ before revision in Cases B5−8 . Thus, revising with the conflicting
piece of information φ could yield the following outcomes: (i) A stops believing ¬φ
and starts believing φ (Case B5 ), which could occur if, for example, σ is a highly
trusted source; (ii) A decides that there is not enough evidence to believe either φ or ¬φ
(Case B6 ); (iii) A decides not to completely give up ¬φ but there is enough evidence
to make A doubt ¬φ making it less entrenched (Case B7 ); or (iv) A decides not to
change its beliefs, even when provided with φ (Case B8 ). One scenario where this is
possible is when the source is not trusted and so A decides not to consider this instance
of conveyance.
62
On the Joint Revision of Belief and Trust
In general, revision may be applied to an inconsistent belief base. In such cases,
what matters is retaining consistency. This is accompanied by rejecting φ, ¬φ, or ac-
tually both. Depending on the weight of evidence and trust in σ this may result in φ’s
becoming more entrenched (Case B9 ) or not (Case B10 ). It may also happen that φ
becomes less entrenched (Case B11 ), for example when some supporters of φ are also
¬φ-relevant. Although revision may prefer ¬φ over φ (Case B13 and Case B14 ) this
should not make ¬φ more entrenched, since revision with φ provides no positive ev-
idence for its negation. Case B12 shows A contracting both φ and ¬φ upon deciding
that evidence for (and against) each one is comparable.
Other cases, we believe, should be forbidden for a rational operation of information
revision. These cases are presented in Table 2. In Case B15 , A is neutral. However,
when provided with evidence for φ, surprisingly, A starts believing ¬φ. Cases B16−18
are ones where A already believes φ and, on revising with φ, the following occurred: (i)
φ becomes less entrenched (Case B16 ); (ii) A stops believing in φ (Case B17 ); (iii) an
extreme case where A receives a confirmation for the already believed φ, and ¬φ ends
up being believed (Case B18 ).9 Cases B19 and B20 show a scenario where ¬φ becomes
more entrenched. These cases are forbidden since revising with φ provides no support
for ¬φ.
# K Kn φ ¬φ Notes
B15 neither (¬φ, b) ∈ B(Kn ) Kn ≡φ K K ≺¬φ Kn -
B16 (φ, b1 ) ∈ B(K) (φ, b2 ) ∈ B(Kn ) Kn ≺φ K K ≡¬φ Kn b2 ≺b b1
B17 (φ, b) ∈ B(K) neither Kn ≺φ K K ≡¬φ Kn -
B18 (φ, b1 ) ∈ B(K) (¬φ, b2 ) ∈ B(Kn ) Kn ≺φ K K ≺¬φ Kn -
B19 (¬φ, b1 ) ∈ B(K) (¬φ, b2 ) ∈ B(Kn ) K ≡φ Kn K ≺¬φ Kn b1 ≺b b2
B20 B(K) |= {(¬φ, b1 ), (φ, b2 )} (¬φ, b3 ) ∈ B(Kn ) Kn ≺φ K K ≺¬φ Kn b1 ≺b b3
Table 2: The forbidden scenarios of belief revision.
Similar to our treatment of belief revision, in Table 3, we present the possible sce-
narios for trust change. The cases in Table 3 are based on the admissible cases of belief
change presented in Table 1. In Table 3, Kn is also a shorthand for K n (φ, σ), θ is
any φ-relevant and not ¬φ-relevant source, and η is any ¬φ-relevant and not φ-relevant
source where σ 6= θ 6= η.
If φ becomes more entrenched, then some new support was provided for φ. Hence,
θ (or σ) might become more trusted (in light of the new support) or remain unchanged
as the new evidence could be not enough to change trust. Regardless, σ and θ should
not be less trusted. Also, if ¬φ becomes less entrenched as a result of revising with φ, it
means that φ affected the revision even if it was not accepted. Thus σ and θ should not
become less trusted. In both cases, there is no reason to for η to be more trusted. The
foregoing is captured in Case T1 . If φ is rejected (φ ∈
/ F or(B(Kn ))) and at the same
9
These extreme reactions to revising with φ may perhaps be justified by complete mistrust in
σ. We do not address mistrust in this paper, though.
63
On the Joint Revision of Belief and Trust
# Condition Belief Revision Cases σ θ η
T1 K ≺φ Kn or Kn ≺¬φ K B1 , B3 , B5−7 , B9 , B10 Kn ⊀σ,T K Kn ⊀θ,T K K ⊀η,T Kn
T2 φ rejected and Kn ⊀¬φ K B2 ,B8 ,B13 K ⊀σ,T Kn K ⊀θ,T Kn K ≡η,T Kn
T3 K ≡φ Kn and K ≡¬φ Kn B4 K ≡σ,T Kn K ≡θ,T Kn K ≡η,T Kn
T4 Kn ≺φ K and Kn ≺¬φ K B11 ,B12 ,B14 K ⊀σ,T Kn K ⊀θ,T Kn K ⊀η,T Kn
Table 3: The admissible scenarios of trust revision.
time ¬φ does not get affected, then σ and θ should not become more trusted while
trust in η should stay the same as no new support was provided for/against it (Case
T2 ).10 If there is no change in the entrenchment of φ and ¬φ, then there is no reason to
change trust in any of σ, θ, or η (Case T3 ). Finally, Case T4 shows that if both φ and ¬φ
become less entrenched, then there is no reason for σ, θ, or η to become more trusted.
The forbidden cases of trust revision constitute all scenarios that contradict any of the
aforementioned admissible cases.
Note that, in none of the cases in Table 3, do we require that trust should change
in certain ways, only that it should not. We believe it be unwise to postulate sufficient
conditions for trust change in a generic information revision operation. For example,
one might be tempted to say that, if after revision with φ, ¬φ is no longer believed, then
trust in any source supporting ¬φ should decrease. Things are not that straightforward,
though.
Example 2. Agent A’s belief base is {(S → P, b1 ), (Q → ¬S, b2 )}. Source Jordan,
conveys P then conveys Q. Since A has no evidence against either, it believes both. Now,
source N our, who is more trusted than Jordan, conveys S. Consequently, A starts
believing S despite having evidence against it. To maintain consistency, A also stops
believing Q (because it supports ¬S). What should happen to A’s trust in Jordan?
We might, at first glance, think that trust in Jordan should decrease as he conveyed Q
which is no longer believed. However, one could also argue that trust in Jordan should
increase because he conveyed P , which is now being confirmed by N our.
This example shows that setting general rules for how trust must change is almost
impossible, as it depends on several factors. Whether A ends up trusting Jordan less,
more, or without change appears to depend on how the particular revision operators ma-
nipulates grades. The situation becomes more complex if the new conveyance by N our
supports several formulas supporting Jordan and refutes several formulas supported
by him. In this case, how trust in Jordan changes (or not) would also depend on how
the effects of all these support relations are aggregated. We contend that such issues
should not, and cannot, be settled by general constraints on information revision.
This non-determinism about how trust changes extends to similar non-determinism
about how belief changes. According to Observation 1, a formula φ may support another
formula ψ by transitivity through an intermediate source σ. Given that, in general, the
10
In Case B2 where A is neutral and φ is rejected after revision, a particular operator might
actually choose to decrease trust in σ. An example of this is when σ informs A about φ and A
is sure that there is no way for anyone to know either φ or ¬φ (Schrödinger’s cat).
64
On the Joint Revision of Belief and Trust
effect of revising with φ on σ is non-deterministic, then so is its effect on ψ. Hence,
the postulates to follow only provide necessary conditions for different ways belief and
trust may change; the general principle being that the scope of change on revising with
φ is limited to formulas and sources which are φ- and ¬φ-relevant. Postulating sufficient
conditions is, we believe, ill-advised.
5.2 Postulates
In the sequel, where φ is a formula and σ is a source, a σ-independent φ-kernel is,
intuitively, a φ-kernel that would still exist if σ did not exit. More precisely, for every
ψ ∈ Γ , ψ is supported by some σ 00 6= σ, or ψ has no source. Of course, all formulas
are conveyed by sources. However, given a forgetful filter, record of sources for some
formulas may be missing from the history.
We believe a rational information revision operator n should observe the following
postulates on revising an information state K with (φ, σ) and φ ∈ T where T is a topic.
The postulates are a formalization of the intuitions outlined earlier.
(n1 : Consistency) Cn(F or(B(Kn(φ, σ)))) 6= L.
(n2 : Resilience) If Cn({φ}) = L, then K ⊀σ,T Kn(φ, σ).
(n3 : Supported Entrenchment) Kn(φ, σ) ≺φ K only if Cn(F or(B(K))) = L.
(n4 : Opposed Entrenchment) K ⊀¬φ Kn(φ, σ).
(n5 : Positive Relevance) If K ≺σ0 ,T Kn(φ, σ) and φ ∈ F or(B(Kn(φ, σ))), then
1. σ 0 6= σ is supported by φ; or
2. σ 0 = σ and there is Γ ⊆ F or(B(K)) where Γ is a σ-independent φ-kernel.
(n6 : Negative Relevance) If Kn(φ, σ) ≺σ0 ,T K, then
1. φ ∈ F or(B(Kn(φ, σ))) and σ 0 is ¬φ-relevant; or
2. σ 0 = σ, but, there is Γ ⊆ F or(B(K n (φ, σ))) where Γ is a ¬φ-kernel.
(n7 : Belief Confirmation) If K ≺ψ Kn(φ, σ), then, ψ 6= φ is supported by φ.
(n8 : Belief Refutation) If Kn(φ, σ) ≺ψ K, then
1. ψ is ¬φ-relevant and φ ∈ Cn(F or(B(Kn(φ, σ)))) or Kn(φ, σ) ≺¬φ K; or
2. ψ is φ-relevant and φ ∈ / Cn(F or(B(Kn(φ, σ)))) or Kn(φ, σ) ≺φ K.
A revised information state is consistent even if the revising formula is itself contra-
dictory (n1 ). If φ is inconsistent, σ should not become more trusted11 (n2 ). Following
Tables 1 and 2, φ cannot become less entrenched unless the belief base is inconsistent
(n3 ). ¬φ, even if the belief base is inconsistent, should never become more entrenched
(n4 ). If σ 0 is more trusted after revision, then (i) φ succeeds and (ii) either σ 0 is different
from σ and supported by φ or σ 0 is σ and there is independent believed evidence for φ
(n5 ). If σ 0 is less trusted after revision, then it must be either that φ succeeds and σ 0
(possibly identical to σ) is relevant to ¬φ, or that σ 0 is σ and there is believed evidence
for ¬φ that leads to rejecting φ (n6 ). ψ is more entrenched after revision only if it is
supported by φ (n7 ). ψ is less entrenched after revision only if it is relevant to φ or ¬φ
(or both) and the one it is relevant to is not favored by the revision (n8 ).
Given the definition of information states, support graphs, and the postulates out-
lined earlier, the following observations hold.
11
A specific operator might choose to actually decrease trust in a source that conveys contradic-
tions as this is a proof of its unreliability.
65
On the Joint Revision of Belief and Trust
Observation 3. If φ ∈ Cn(F or(B(K))) 6= L, then φ ∈ Cn(F or(B(K n (φ, σ)))).
Observation 4. If ¬φ ∈
/ Cn(F or(B(K))), then ¬φ ∈
/ Cn(F or(B(K n (φ, σ)))).
Observation 5. If (ψ, b1 ) ∈ B(K), (ψ, b2 ) ∈ B(K n (φ, σ)) where b1 6= b2 , then ψ is
either φ-relevant or ¬φ-relevant.
Observation 6. If (σ 0 , T, t1 ) ∈ T (K), (σ 0 , T, t2 ) ∈ T (Kn(φ, σ)) and t1 6= t2 , then σ 0
is φ-relevant or ¬φ-relevant.
Observation 7. If φ ∈/ F or(B(K n (φ, σ))), then there is no σ 0 ∈ SK such that
K ≺σ0 ,T K n (φ, σ).
Observation 8. If Cn(F or(B(K))) 6= L, then an operator that observes n4 and n5
allows for only cases in Table 1 to occur.
6 Conclusion and Future Work
It is our conviction that belief and trust revision are intertwined processes that should not
be separated. Hence, in this paper, we argued why that is the case and provided a model
for performing the joint belief-trust (information) revision with minimal assumptions on
the modeling language. Then, we introduced the notion of information states that allows
for the representation of information in a way that facilitates the revision process. We
also introduced the support graph which is a formal structure that allows us to identify
relevance relations between not only formulas, but also, information sources. Finally,
we proposed the postulates that we believe any rational information revision operator
should observe. Future work could go in one or more of the following directions:
1. We intend to define a representation theorem for the postulates we provided.
2. We intend to further investigate conveyance and information acquisition to further
allow agents to trust/mistrust their own perception(s).
3. Lastly, we would like to add desires, intentions, and other mental attitudes to create
a unified revision theory for all mental attitudes.
References
1. Alchourrón, C.E., Gärdenfors, P., Makinson, D.: On the logic of theory change: Partial meet
contraction and revision functions. The journal of symbolic logic 50(2), 510–530 (1985)
2. Booth, R., Hunter, A.: Trust as a precursor to belief revision. Journal of Artificial Intelligence
Research 61, 699–722 (2018)
3. Castelfranchi, C., Falcone, R.: Principles of trust for MAS: Cognitive anatomy, social impor-
tance, and quantification. In: Proceedings International Conference on Multi Agent Systems.
pp. 72–79. IEEE (1998)
4. Demolombe, R.: To trust information sources: a proposal for a modal logical framework. In:
Castelfranchi, C., Tan, Y.H. (eds.) Trust and Deception in Virtual Societies, pp. 111–124.
Springer Netherlands, Dordrecht (2001)
66
On the Joint Revision of Belief and Trust
5. Demolombe, R.: Reasoning about trust: A formal logical framework. In: Jensen, C., Poslad,
S., Dimitrakos, T. (eds.) Trust Management. pp. 291–303. Springer Berlin Heidelberg,
Berlin, Heidelberg (2004)
6. Demolombe, R., Liau, C.J.: A logic of graded trust and belief fusion. In: Proceedings of the
4th workshop on deception, fraud and trust in agent societies. pp. 13–25 (2001)
7. van Ditmarsch, H.: Dynamics of lying. Synthese 191(5), 745–777 (2014)
8. Elangovan, A., Auer-Rizzi, W., Szabo, E.: Why don’t I trust you now? An attributional ap-
proach to erosion of trust. Journal of Managerial Psychology 22(1), 4–24 (2007)
9. Falcone, R., Castelfranchi, C.: Social trust: A cognitive approach. In: Trust and Deception in
Virtual Societies, pp. 55–90. Springer Netherlands (2001)
10. Gärdenfors, P., Makinson, D.: Revisions of knowledge systems using epistemic entrench-
ment. In: Proceedings of the 2nd conference on Theoretical aspects of reasoning about
knowledge. pp. 83–95. Morgan Kaufmann Publishers Inc. (1988)
11. Hansson, S.O.: Kernel contraction. The Journal of Symbolic Logic 59(3), 845–859 (1994)
12. Hansson, S.O.: A survey of non-prioritized belief revision. Erkenntnis 50(2-3), 413–427
(1999)
13. Hansson, S.O.: A textbook of belief dynamics - theory change and database updating, Ap-
plied logic series, vol. 11. Kluwer (1999)
14. Hardwig, J.: The role of trust in knowledge. The Journal of Philosophy 88(12), 693–708
(1991)
15. Haselhuhn, M.P., Schweitzer, M.E., Wood, A.M.: How implicit beliefs influence trust recov-
ery. Psychological Science 21(5), 645–648 (2010)
16. Herzig, A., Lorini, E., Hübner, J.F., Vercouter, L.: A logic of trust and reputation. Logic
Journal of the IGPL 18(1), 214–244 (2010)
17. Holton, R.: Deciding to trust, coming to believe. Australasian Journal of Philosophy 72(1),
63–76 (1994)
18. Ismail, H., Attia, P.: Towards a logical analysis of misleading and trust erosion. In: Gordon,
A.S., Miller, R., Turán, G. (eds.) Proceedings of the Thirteenth International Symposium
on Commonsense Reasoning, COMMONSENSE 2017, London, UK, November 6-8, 2017.
vol. 2052. CEUR-WS.org (2017)
19. Jones, A.J.: On the concept of trust. Decision Support Systems 33(3), 225–232 (2002)
20. Jones, A.J., Firozabadi, B.S.: On the characterisation of a trusting agent—aspects of a formal
approach. In: Castelfranchi, C., Tan, Y.H. (eds.) Trust and Deception in Virtual Societies, pp.
157–168. Springer Netherlands, Dordrecht (2001)
21. Jøsang, A., Ivanovska, M., Muller, T.: Trust revision for conflicting sources. In: The 18th
International Conference on Information Fusion (Fusion 2015). pp. 550–557. IEEE (2015)
22. Katz, Y., Golbeck, J.: Social network-based trust in prioritized default logic. In: Proceedings
of the Twenty-First National Conference on Artificial Intelligence (AAAI 2006). pp. 1345–
1350 (2006)
23. Leturc, C., Bonnet, G.: A normal modal logic for trust in the sincerity. In: Proceedings of the
17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 175–
183. International Foundation for Autonomous Agents and Multiagent Systems (2018)
24. Liau, C.J.: Belief, information acquisition, and trust in multi-agent systems—a modal logic
formulation. Artificial Intelligence 149(1), 31–60 (2003)
25. Lorini, E., Demolombe, R.: From binary trust to graded trust in information sources: A
logical perspective. In: International Workshop on Trust in Agent Societies. pp. 205–225.
Springer (2008)
26. Lorini, E., Jiang, G., Perrussel, L.: Trust-based belief change. In: T. Schaub, G. Friedrich,
B.O. (ed.) Proceedings of the 21st European Conference on Artificial Intelligence (ECAI
2014). Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 549–554. IOS Press,
Amsterdam (2014)
67
On the Joint Revision of Belief and Trust
27. McLeod, C.: Trust. In: Zalta, E.N. (ed.) The Stanford Encyclopedia of Philosophy. Meta-
physics Research Lab, Stanford University, fall 2015 edn. (2015)
28. Rodenhäuser, L.B.: A matter of trust: Dynamic attitudes in epistemic logic. Universiteit van
Amsterdam [Host] (2014)
29. Sabater, J., Sierra, C.: Review on computational trust and reputation models. Artificial Intel-
ligence Review 24(1), 33–60 (Sep 2005)
30. Sakama, C.: A formal account of deception. In: 2015 AAAI Fall Symposia, Arlington, Vir-
ginia, USA, November 12-14, 2015. pp. 34–41. AAAI Press (2015)
31. Sakama, C., Caminada, M., Herzig, A.: A logical account of lying. In: European Workshop
on Logics in Artificial Intelligence. pp. 286–299. Springer (2010)
32. Simpson, J.A.: Psychological foundations of trust. Current Directions in Psychological Sci-
ence 16(5), 264–268 (2007)
33. Yasser, A., Ismail, H.O.: Information revision: The joint revision of belief and trust. In: Varz-
inczak, I.J., Martinez, M.V. (eds.) Proceedings of the 18th International Workshop on Non-
Monotonic Reasoning (NMR2020) (2020), forthcoming
68