Trust plays a role in the process of belief revision. When information is reported by another agent, it should only be believed if the reporting agent is trusted as an authority over some relevant domain. In practice, an agent will be trusted on a particular topic if they have provided accurate information on that topic in the past. In this paper, we demonstrate how an agent can construct a model of knowledge-based trust based on the accuracy of past reports. We then show how this model of trust can be used in conjunction with Ordinal Conditional Functions to define two approaches to trust-influenced belief revision. In the ifrst approach, strength of trust and strength of belief are assumed to be incomparable as they are on diferent scales. In the second approach, they are aggregated in a natural manner. We then describe a software tool for modelling and reasoning about trust and belief change. Our software allows a trust graph to be updated incrementally by looking at the accuracy of past reports. After constructing a trust graph, the software can then compute the result of AGM-style belief revision using two diferent approaches to incorporating trust.
that topic in the past.
In the rest of the paper, we proceed as follows. In Belief revision is concerned with the manner in which an the next section, we give a motivating example that will agent incorporates new information that may be incon- be used throughout the paper. We then review formal sistent with their current beliefs. In general, the belief preliminaries related to belief revision and trust. We revision literature assumes that new information is more then introduce trust graphs, our formal model of trust. reliable than the initial beliefs; in this case, new informa- We define a simple approach for building a trust graph tion must always be believed following belief revision. from past revisions, and prove some basic results. We However, in many practical situations this is not a rea- then demonstrate how trust rankings can influence belief sonable assumption. In practice, we need to take into revision in two diferent ways. First, we consider the account the extent to which the source of the new infor- naive case, where the strength of trust is independent mation is trusted. In this paper, we demonstrate how an of the strength of belief. Second, we consider the more agent can actually build trust in a source, based on past complex case, where strength of trust is aggregated with reports.1 strength of belief.
Suppose that an agent believes to be true, and they Finally, we describe and implemented software tool are being told by an agent that is not true. In this kind that automates this entire process. The software preof situation, we will use ranking functions to represent sented here is a useful addition to the relatively small both the initial strength of belief in as well as the level collection existing belief revision solvers, because it exof trust in . Significantly, however, the trust in is not tends the class of practical problems that we can model uniform over all formulas. Each information source is and solve. To the best of our knowledge, the software pretrusted to diferent degrees on diferent topics. The extent sented in this paper is the first implemented system that to which is trusted on a particular topic is determined incrementally builds a model of trust that is specifically by how frequently they have made accurate reports on intended to inform the process of belief revision. communicate about the status of the lights in each room. that the agent considers it more likely that 1 is the actual For simplicity, we say that is true when the light is on state, as opposed to 2. Note that defines a belief state in room and we say is true when the light is on in ( ) as follows: room .
We focus on the beliefs of Absent, who initially thinks that the light in room is on and the light in room is of. Now suppose that asserts the light is of in and the light is on in room .
( ) = { | () is minimal }.
plain the mistakes in the reports; they need some mecha- the knowledge required to be trusted on particular stateWe assume an underlying set V of propositional variables. A formula is a propositional combination of ele- the light is on in room , and one that includes all states If Present is completely trusted, this is not a problem; the report simply leads Absent to believe they were incorrect about the lights.
But suppose that Present has given incorrect reports in the past. We can collect these reports, and check to see when they have been correct and when they have been incorrect. For example, suppose that Present is always correct about the light status in room , whereas they are often incorrect about the light status in room . We might draw the conclusion that they are normally physically in the room , and that they are too lazy to walk to a another room to check the lights.
Formally, Absent does not need a plausible story to exnism for modelling trust over diferent propositions. By looking at the accuracy of reports on diferent topics, they build a model of trust that allows information reported from Present to be incorporated appropriately. In this paper, we develop formal machinery that is suitable for capturing all facets of this seemingly simple example. 2.2. Belief Revision ments of V, using the usual connectives →, ∧, ∨, ¬. We will assume that V is finite in this paper, though that need not be the case in general. A state is a propositional interpretation over V, which assigns boolean values to all variables. We will normally specify a state by giving the set of variables that are true. A belief state is a set of states, informally representing the set of states that an agent considers possible. We let || denote the set of states where the formula is true.
The dominant approach to belief revision is the AGM approach. A revision operator is a function * that maps a belief state and a formula to a new belief state * . An AGM revision operator is a revision operator that satisfies the so-called AGM postulates. We refer the reader to [2] for a complete introduction to the AGM theory of belief revision.
Although we are concerned with AGM revision at times, in this paper we actually define the beliefs of an agent in terms of Ordinal Conditional Functions (OCFs) [3], which are also called ranking functions. An OCF is a function that maps every state to an ordinal ().
Informally, if (1) < (2), this is understood to mean The operator on belief states specified in this manner deifnes an AGM belief revision operator, for any underlying OCF. 2.3. Trust The notion of trust plays an important role in many applications, including security [4, 5] and multi-agent systems [6, 7]. In this paper, we are concerned primarily with knowledge-based trust. That is, we are concerned with the extent to which one agent trusts another to have ments. This is distinct from trust related to honesty or deception.
We refer occasionally to trust-senstive belief revision operators [8]. Trust-sensitive belief revision operators are defined with respect to a trust-partition over states.
The equivalence classes of a trust partition Π
consist of states that can not be distinguished by a particular reporting agent. In our motivating example, we might define a trust partition for
Present that consists of two equivalence classes: one that includes all states where where the light is of in room
. In this case, Present is informally trusted to be able to tell if the light in room is on or of. However, Present is not trusted to be able to tell if the light in room is on or of.
A trust-sensitive revision operator * Π is defined with respect to a given AGM revision operator * and a trust partition Π . The operator * Π operates in two steps when an agent is given a report . First, we find the set Π( ) of all states that are related by Π to a model of . Then we perform regular AGM revision with this expanded set of states as input. Hence, the model of trust is essentially used to pre-process the formula for revision, by expanding it to ignore distinctions that we do not trust the reporter to be able to make.
We can also define trust in terms of a distance function between states. The notion of distance required is generally an ultrametric.
Definition 1.
An ultrametric is a binary function over a set , such that for all , , ∈ : 2 2
2 A trust ranking is intended to capture the degree to which an agent is trusted to distinguish between states in a graph. If (1, 2) is large, this means the agent can be trusted to distinguish the states 1 and 2. However, if the distance is small, they can not be trusted to draw this distinction.
We now turn to our main problem: building a notion of trust from data. We assume throughout this paper a ifxed, finite vocabulary V. All states, belief states, and formulas will be defined with respect to this underlying vocabulary.
Definition 3. Let be the set of states over V. A trust graph over is a pair ⟨, ⟩, where : × → N.
Hence, a trust graph is just a complete weighted graph along with a distance between states. Informally, a trust graph represents the trust held in another agent. The weight on the edge between two states 1 and 2 is an indication of how strongly the agent is trusted to directly distinguish between those states.
Example 1. Consider the motivating example, in the case where Absent trusts Present more strongly to check if the light in room is on as opposed to room . This could be captured by the trust graph in Figure 1, by having a higher weight on edges that connect states that difer on the value of . Note that the minimax distance can easily be calculated from this graph.
• (, ) ≥ 0. • (, ) = 0 if and only if = . • (, ) = (, ). • (, ) ≤ max{(, ), (, )}.
We let Φ , possibly with subscripts, range over report If we remove condition 2, then is a pseudo-ultrametric. histories. A report history Φ represents all of the claims The following definition of a trust ranking is given in [ 9]. that an agent has truthfully or falsely claimed in the past.
Definition 2. For any propositional vocabulary, a trust reported in the past in a situation where was shown ranking is a pseudo-ultrametric over the set of all states. to be true. On the other hand, (, 0) ∈ Φ means that has been reported in a situation where it was false.
The edge weights represent how strongly a reporting agent is trusted to distinguish between a pair of states.
If the weight is high, we interpret this to mean that the agent is strongly trusted to distinguish between the states.
If the weight is low, then the reporting agent is not trusted to distinguish the states.
In order to build a notion of trust in an agent, we need to have a history of the past reports that agent has provided. Our basic approach is to assume that we start with a set of statements that a reporting agent has made in the past, along with an indication of whether the reports were correct or not.
Definition 4. A report is a pair (, ), where is a formula and ∈ {0, 1}. A report history is a multi-set of reports.
Suppose we start with a trust graph in which the reporting agent is essentially trusted to be able to distinguish all states, with a default confidence level. For each true report in the history, we strengthen our trust in the reporting agent’s ability to distinguish certain states. For each false report, we weaken our trust.
Definition 5. For any > 0, the initial trust graph = ⟨, ⟩ where is the set of states, and is defined such that (, ) = 0 if = and (, ) = otherwise. The idea of the initial trust graph is that the reporting agent is trusted to distinguish between all states equally well.
We are now interested in giving a procedure that takes a report history, and returns a trust graph; this is presented in Algorithm 1. The algorithm looks at each report in the history , and it increases the weight on edges where there have been true reports and decreases the weight on edges where there have been false reports. Proposition 1. Given a report history , the weighted graph returned by Algorithm 1 is a trust graph. This result relies on the fact that only returns nonnegative values; this is guaranteed by the choice of for the initial trust graph.
Example 2. We return to our running example. Suppose that we have no initial assumptions about the trust held Algorithm 1 Construct_from()
Input , a report history. ← size of . = ⟨, ⟩ is the initial trust graph for . while ̸= ∅ do
Get some (, ) ∈ if = 0 then (1, 2) ← (1, 2) − 1 for all 1, 2 such that 1 |= and 2 ̸|= else (1, 2) ← (1, 2) + 1 for all 1, 2 such that 1 |= and 2 ̸|= end if = − (, ). end while
Return ⟨, ⟩. in Present, and that the report history consists of the following reports:
⟨, 1⟩, ⟨, 1⟩, ⟨, 0⟩, ⟨ ∧ , 1⟩ Since our report history has size 4, the initital trust graph would look like Figure 1, except that all edge weights would be 4. After the first report, the edge weights would be increased on the following edges:
({, }, ∅), ({, }, {}), ({}, ∅), ({}, {}). The same thing would happen after the second report. On the third report, we would subtract one from the following edges:
({, }, ∅), ({, }, {}), ({}, ∅), ({}, {}). Finally, the fourth report would add one to the following edges:
({, }, ∅), ({, }, {}), ({, }, {}). The final trust graph is given in Figure 2. Based on this graph, Present is least trusted to distinguish the states {} and ∅. This is because the positive reports were all related to the truth of , and the only false report was a report about the trust of . Hence, the graph is intuitively plausible.
We have defined an approach to building trust graphs from reports. We remark that the edge weights will not be used directly when it comes to belief revision. For belief revision, what we need is a single trust ranking that is derived from the trust graph. However, constructing the graph allows us to define the ranking function as sort of a consequence of the reports. In this section, we show the construction satisfies some desirable properties.
First, we define the trust ranking associated with a trust graph. Definition 6. For any trust graph = ⟨, ⟩, let denote the minimax distance between states.
The distance captures an overall trust ranking that can be used to inform belief revision. Informally, even if an agent is not trusted to distinguish two states directly, they may be trusted to distinguish them based on a path in the graph. The important feature of such a path is the minimax weight. The following is a basic result about the notion of distance defined by a trust graph. Proposition 2. For any trust graph = ⟨, ⟩, the function is a pseudo-ultrametric on .
Recall from Section 2 that a pseudo-ultrametric over states can be used to define a ranking that is suitable for reasoning about trust. We remark that, in fact, every ultrametric over a finite set is actually equivalent up to isomorphism to an ultrametric defined by the minimax distance over some weighted graph. This means that every trust ranking can be defined by a trust graph.
The next result shows that there is nothing particularly special about the trust graphs constructed by our algorithm.
Proposition 3. Every weighted graph over is the trust graph obtained from some report history .
This can be proven by a simple construction where each report only modifies a single edge weight.
In the next results, we adopt some simplifiying notation. If is a report history and is a report, we let · denote the multiset obtained by adding to . Also, if is a report history, we let () denote the trust graph obtained from and we let denote the distance defined by ().
As stated, Algorithm 1 can only construct a trust graph starting from scratch. However, the following proposition states that we can iteratively modify a trust graph as we get new reports.
Proposition 4. Let be a report history and let be a report. Then (· ) is identical to the trust graph obtained by modifying () as follows: , if is a positive report. , if is a negative report.
with the new edge weights. • Decrement weights between states that disagree on • Defining a new minimax distance in accordance Hence, rather than viewing trust graphs as something created with no a priori knowledge, we can think of trust graphs as a simple model of trust together with an operation that tweeks the weights to respond to a new report.
One desirable feature of our construction is that a report of (, 0) should make the reporting agent less trustworthy with regards to reports about the trust of . The next proposition shows that this is indeed the case. Proposition 5. Let be a report history, let 1 and 2 be states such that 1 |= and 2 ̸|= . Then
(1, 2) ≥ · (,0)(1, 2).
We have a similar result for positive reports.
Proposition 6. Let be a report history, let 1 and 2 be states such that 1 |= and 2 ̸|= . Then
(1, 2) ≤ · (,1)(1, 2).
Taken together, these results indicate that negative (resp. positive) reports of make the reporting agent less (resp. more) trusted with respect to . We remark that the inequalities in the previous theorems would be strict if we were considering actual edge weights; but they are not strict for , since there may be multiple paths between states.
We have seen that trust graphs define a distance over states that represents a general notion of trust that is implicit in the graph. Significantly, trust graphs can be constructed in a straightforward way by looking at past reports; the implicitly defined trust ranking is based on the accuracy of these reports. In the next section, we consider how the notion of trust defined by a trust graph can be used to construct diferent approaches to revision.
Consider again our example involving reports about the sent might not actually trust the reports from Present, and we gave an approach to construct a trust graph.
Informally, when talking about trust, we might make assertions of the following form: 1. Present is not trusted to know which room they
are in. • Increment weights between states that disagree on lights in a building. We previously pointed out that Ab- From the theory of metric spaces, we have the following.
These kind of assertions give us a hint about how belief revision might occur. For example, in the first case,
Absent would interpret a report to mean that exactly one of the rooms is lit.
Note, however, that a trust graph does not simply give a binary notion of trust; it defines a distance function that indicates strength of trust in various distinctions. Similarly, the beliefs of an agent might be held with diferent levels of strength. So, even if we have a trust graph, there are still problems with incorporating reports related to comparing strength of belief with strength of trust.
In our example, if Absent just left the building, they might believe very strongly that the light in room must be of. They might believe this so strongly that they disregard Present’s report entirely. But disregarding reports is not the only option. It might be the case that the exact strength of Absent’s beliefs needs to be considered. Suppose Absent believes the light in room is of with a medium degree of strength. In that case, a report from a weakly trusted agent will not change their beliefs, whereas a report from a strongly trusted agent would be more convincing. Moreover, Absent also needs to have a strength ranking over possible alternatives. Hence, this is not simply a binary comparison between strength of degree and strength of trust. In order to model interaction between belief and trust, we need a precise formal account that permits a comparison of the two. We also need to account for the way that Present develops a reputation, either for laziness or inaccuracy. defined by a trust graph. revision operators * .
In the remainder of this paper, we assume that the beliefs of an agent are represented by an OCF. We show how a trust graph allows us to capture an approach to belief revision that takes trust into account. In fact, the approach in this section depends only on a pseudo-ultrametric
For any pseudo-ultrametric , we define a family of such that ( ) * is equal to: Definition 7.
Let be an OCF and let be a pseudoultrametric over . For each , the operator * is defined min{ | there exists such that (, ) ≤ and |= } (, ) ≤ } is a partition of .
Proposition 7. For any pseudo-ultrametric over a set , if ∈
N then the collection of sets = { | The next result relates these revision operators to trustsensitive revision operators. A parallel result is proved in [9], although the result here is stated in terms of OCFs rather than AGM revision.
Proposition 8. Let be an OCF and let be a trust graph. For any formula and any :
( ) * = ( ) * Π where Π is the partition defined by ( , ) and * Π is the trust-senstive revision operator associated with Π . Hence and define a set of trust-sensitive revision operators. The parameter specifies how close two states must be to be considered indistinguishable in the partition.
We refer to the operators * as naive trust-sensitive revision operators in this paper. These operators are naive in the sense that they do not allow us to take into account the relative magnitudes of the values in and the distances given by . In other words, the scales of and are not compared; it doesn’t matter if the initial strength of belief is high or low. This makes sense in applications where the magnitudes in and are seen as independent.
We have supposed that Present reports ¬ ∧ . So, what should Absent believe? It depends on the threshold . If we set = 3, then by Proposition 6, * 3 is the trustsensitive revision operator defined by the partition with cells {{}, {}} and {{, }, ∅}. Since {} and {} are in the same cell, it follows that revision by is equivalent to revision by ∨ . Hence:
( ) * 3 = {{}}.
This is a belief state containing just one state; so Absent believes that the most plausible state is the unique state where only the light in room is on. Hence, if Present reports that the light in room is on, it will not change the beliefs of at all.
For naive operators, it does not matter how strongly Absent believes the light in room is on. It only matters whether or not the reporting agent can distinguish between particular states.
In the previous section, we considered the case where Example 3. We refer back to our motivating example. strength of belief and strength of trust are incomparable; Suppose that the initial beliefs of Absent are given by the magnitudes of the values are not on the same scale. In such that: this case, we can not meaningfully combine the numeric values assigned by with the numeric distances given by ({}) = 0, a trust graph; we essentially have two orderings that have ({}) = 1, to be merged in some way. This is the general setting of ({, }) = 1, AGM revision, and trust-sensitive revision.
(∅) = 2 However, there is an alternative way to define revision that actually takes the numeric ranks into account. First, we define a new OCF, given some initial beliefs and a trust distance function.
Hence the initial belief set for Absent is {}. Now suppose that Present passes a message that asserts ¬ ∧ ; in other words, the light is of in while it is on in . If this information was given to Absent as infallible sensory data, then the result could be determined easily with regular AGM revision. But this is not sensory data; this is a report, and trust can play a role in how it is incorporated.
To make this concrete, suppose that Absent thinks that Present is generally lazy and unaware of the room that they are in. It is unlikely therefore, that Present would run quickly from one room to another to verify the status of the light in both. So perhaps the trust graph constructed from past reports defines the distance function from {} as follows: ({}, {}) ({}, {}) ({}, {, }) ({}, ∅) = = = = 1 0 10 5
Definition 8. Let be an OCF and let be a pseudoultrametric. For any ∈ :
() = () · min{(, ) | |= }.
hood of along with a measure indicating how easily can be distinguished from a model of . Essentially, this definition uses to construct a ranking function over states centered on ||. This ranking is aggregated with , by adding the two ranking functions together.
Given this definition, we can define a new revision operator.
Definition 9. Let be an OCF and let be a pseudoultrametric. For any formula , define ∘ such that ( ) ∘ = { | () is minimal}.
This distance function does indeed encode the fact that Present is not strongly trusted to distinguish {} and {}; this is because they do not always know where they are.
This new definition lets the initial strength of belief be traded of with perceived expertise. We return to our example. Example 4. Consider the light-reporting example again, with the initial belief state and the distance function specified in Example 3. Now suppose again that Present reports = ¬ ∧ , i.e. that only the light in room is on. We calculate () for all states in the following table.
In order to perform belief revision using T-BEL , we first need to initialize a trust graph. This is done through the panel in Figure 3. The user simply enters a propositional vocabulary as a comma delimited sequence of strings.
Optionally, one can specify an initial trust value; this is the weight that will be assigned to all edges in the trust () ({}, ) () graph. If it is not specified, it will default to 1. {} 0 1 1 The panel in Figure 4 is used for visualizing and ma{} 1 0 1 nipulating the trust graph. After the trust graph has been {, } 1 10 11 generated, it is displayed on the left side as a matrix that ∅ 2 5 7 gives the weight between every pair of states. The values in this matrix can be edited manually, but this is not
Since the first two rows both have minimal values, it the preferred way to change the values. The main goal follows that of T-BEL is to allow trust to be built incrementally by adding reports. This is done through the report entry ( ) ∘ *¬ ∧ = {{}, {}}. section in Figure 4. Reports are entered as formulas in a Following revision, Absent believes exactly one light is on. simple variant of propositional logic, using the keyboardfriendly symbols & (conjunction), | (disjunction) and − (negation). The reports are tagged with 1 (positive) and 0 (negative). By default, when the Add Reports button is pressed, the matrix on the left updates the values in accordance with the following update rules:
This example demonstrates how the strength of belief and the strength of trust can interact. The given result occurs because the strength of belief in {} is identical to the strength of trust in the report of {}. Increasing or decreasing either measure of strength will cause the result to be diferent. Note also that this approach gives a full OCF as a result, so we have a ranking of alternative states as well. panels for diferent actions: initializing a trust graph, manipulating the trust graph, visualizing the trust graph, and performing revision. The only constraint is that the vocabularly needs to be provided to initialize the trust graph. After the initial trust graph is constructed, a user can jump between diferent panels. For example, one could add new information about past reports at any time, even after revision has been performed.
In the following sections, we describe the basic usage of the software.
Update Rule 1. For each pair of states 1, 2 such that 1 |= and 2 ̸|= decrease the value (1, 2) to (1, 2) − 1.
Update Rule 2. For each pair of states 1, 2 such that 1 |= and 2 ̸|= , increase the value (1, 2) to (1, 2) + 1.
These update rules correspond to the construction of a trust graph in Algorithm 1. However, we remark that T-BEL is not restricted to these updates. If the user would like to specify diferent update rules, this can be done by providing a text file specifying new update rules.
There is one remaining feature to mention in this panel: the Distance Checker. We will see in the next section that we actually do not use the values in the trust matrix directly; we use the minimax distance generated from these values. As such, we provide the user with a simple mechanism for checking minimax distance for testing and experimentation.
We describe T-BEL , a Java application for modeling the dynamics trust and belief. The core functionality of T-BEL is as follows. It allows a user to create a trust graph that captures the distinctions an information source is trusted to make. It allows a user to enter a series of reports, which might be correct or incorrect. These reports trigger an update to the trust graph. Finally, the user can calculate the result of belief revision, in a manner that accounts for the influence of trust.
Note that the steps listed above need not be done sequentially. The interface for the software provides several
As noted previously, epistemic states are represented in T-BEL using ranking functions. The software provides two diferent ways to specify an epistemic state.
The first way to specify an epistemic state is by explicitly specifying a total pre-order over all states. This is done by creating an external text file that lists a “level” for all states starting from 0. For example, if we had two variables and , then one example input file could be specified as follows: T-BEL implements both naive revision and general revision; the user chooses the mechanism to be used in the menu in Figure 3. 2 If Naive Revision is selected, then the user needs to 0:00 enter a threshold value. Following Proposition 8, this 1:10 threshold value defines a trust-sensitive revision operator. This operator is used to calculate the result of belief The first line indicates that there are 2 variables. The revision when the Naive option is selected. The result of second line says that the state where and are both revision is displayed as a formula, capturing the minimal false is the most plausible, so it is the only state in level 0. states in the new ranking. We note that the software The next line specifies the states in level 1. Any states not can be used to perform more than one revision when the listed are put in level 2. A ranking over states specified Hamming distance has been specified for the ranking. in this manner gives us enough information to perform However, for file-based rankings, iterated revision is not belief revision. possible.
Manually specifying a complete ranking in this manner We can also specify that we want to use general recan be problematic, because it is time consuming and it is vision in the dropdown menu in Figure 3. In this case, easy to make mistakes. As such, we also give the user the if is the original ranking function, is the minimax ability to experiment with revision simply by entering distance and is the formula for revision, then we can a belief state as a set of formulas through an input box define a new function: in the main interface. For example, we could enter the beliefs by giving this list of formulas: () = () + min{(, ) | |= }. distance from the set of satisfying assignments to create a full ranking. In other words, the default approach defines a ranking that corresponds to Dalal’s revision operator [10]. However, T-BEL also provides a flexible mechanism for reading alternative rankings from a file input.
A&B
A|-B To generate a ranking function from such a list, T-BEL ifnds all satisfying assignments. In the example given, the only satisfying assignment occurs when and are both true. By default, T-BEL then uses the Hamming By normalizing this function, we define a new ranking function that represents the beliefs following revision. The result of belief revision is displayed as a formula. However, general revision can be iterated because the full ranking is maintained after each revision.
as well as past reports of ( ∨ , 1) and (, 1). Assume further that we would like to start with the belief state ( ∧ ) and then revise by ( ∧ ¬) ∨ (¬ ∧ ). Using T-BEL , then can solve this problem through the following steps: 1. Enter the vocabulary , and a default value of 5. 2. Enter reports (|, 1) and (, 1) then click Add
Reports. 3. Select Naive revision with threshold 3.
)|(− &).
5. Click Revise.
The default value in step 1 should be set so that it is at least as high as the number of reports. However, beyond that constraint, it will not impact the results. After step 2, the values in the matrix representing the trust graph will be as follows:
The question of run time is a challenging one to address for any implemented belief revision system, due to the well known compexity of revision [11]. The problem is even worse when we add trust graphs, which become very large as the vocabulary size increases.
The present implementation has made many imple- 6.2. Conclusion mentation choices in order to optimize performance.
For example, we represent a trust map internally as a hashmap of hashmaps; the lookup time is very fast. Another place where we focus on eficiency is in the translation from formulas to belief states, where we use a DPLL solver to find satisfying assignments. However, the run time for T-BEL still becomes slow as the vocabulary size increases. It is a useful prototype for reasoning about small examples, and demonstrating the utility of trust graphs. In future work, we will look to improve run time by integrating a competition level ALLSAT solver for the hard calculations [12].
This work fits in the general tradition of formalisms that address notions of trust and credibility for belief revision. There are alternative approaches, based on non-prioritized and credibility-limited revision as well [13, 14, 15]. The notion of trust has been explored in the setting of Dynamic Epistemic Logic (DEL), by adding an explicit measure of trust to formulas [16]. Finally, since we are primarily concerned with with trust based on expertise, the formalism presented here is also related to recent work on truth discovery [17].
But fundamentally, this work is really about building trust in a source based on the knowledge demonstrated in past reports; our goal is to develop a formal model of knowledge-based trust. To the best of our knowledge, this problem has not been explored previously in the context of formal belief change operators. However, it has been explored in some practical settings, such as the formulation of search engine results [18].
The software introduced here can be seen as an extension of the GenB system [19]. GenB is a general solver for revision with a limited capacity to capture trust; TBEL is significantly more sophisticated when it comes to representing and reasoning about the dynamics of trust and belief.
In this paper, we have addressed the problem of building trust from past reports. We demonstrated that, in the context of OCFs, trust can be interpreted in two ways. ceedings of the 21st International Joint Conference First, if the scale used for the the strength of belief is on Artificial Intelligence (IJCAI), 2009, pp. 272–277. deemed to be independent of the distance metric, then [8] R. Booth, A. Hunter, Trust as a precursor to belief we can use a trust ranking to define a family of naive revision, J. Artif. Intell. Res. 61 (2018) 699–722. revision operators for trust-sensitive revision. On the [9] A. Hunter, R. Booth, Trust-sensitive belief revision, other hand, if strength of trust and strength of belief are in: Q. Yang, M. J. Wooldridge (Eds.), Proceedings of considered to be comparable on the same scale, then we the Twenty-Fourth International Joint Conference have shown how the two can be aggregated to define a on Artificial Intelligence, IJCAI 2015, Buenos Aires, new approach to trust-influenced belief revision. Argentina, July 25-31, 2015, AAAI Press, 2015, pp.
We have also described a tool for solving belief change 3062–3068. problems influenced by trust. The focus is on building [10] M. Dalal, Investigations into a theory of knowledge trust from reports, and then performing belief revision. base revision, in: Proceedings of the National ConOur software provides a simple interface that can be used ference on Artificial Intelligence (AAAI), 1988, pp. to build a trust graph iteratively, and then this graph is 475–479. used to adjust the behaviour of a formal belief change [11] T. Eiter, G. Gottlob, On the complexity of proposioperator to account for trust. We suggest that this tool tional knowledge base revision, updates and counis an important step towards demonstrating the utility terfactuals, Artificial Intelligence 57 (1992) 227–270. of belief change operators for solving practical problems [12] T. Toda, T. Soh, Implementing eficient all soluwith partially trusted information sources. tions sat solvers, ACM Journal of Experimental
There are many directions for future research. Beyond Algorithmics 21 (2016) 1–44. expanding the formal theory, we are primarily interested [13] S. O. Hansson, E. L. Fermé, J. Cantwell, M. A. in practical applications of this work. In future work, we Falappa, Credibility limited revision, J. Symb. Log. intend to improve run time performance, apply the tool 66 (2001) 1581–1596. to concrete problems in the evaluation of web resources, [14] R. Booth, E. Fermé, S. Konieczny, R. P. Pérez, and connect our approach to related work on learning Credibility-limited revision operators in proposiwith respect to trust. tional logic, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, References Italy, June 10-14, 2012, 2012. [15] G. Bonanno, Credible information, allowable in[1] A. Hunter, Building trust for belief revision, in: Pro- formation and belief revision - extended abstract, ceedings of the Pacific Rim Conference on Artificial in: L. S. Moss (Ed.), Proceedings Seventeenth ConIntelligence (PRICAI), 2021, pp. 543–555. ference on Theoretical Aspects of Rationality and [2] C. E. Alchourrón, P. Gärdenfors, D. Makinson, On Knowledge, TARK 2019, Toulouse, France, 17-19 the logic of theory change: Partial meet functions July 2019, volume 297 of EPTCS, 2019, pp. 82–90. for contraction and revision, Journal of Symbolic [16] F. Liu, E. Lorini, Reasoning about belief, evidence Logic 50 (1985) 510–530. and trust in a multi-agent setting, in: PRIMA 2017: [3] W. Spohn, Ordinal conditional functions. A dy- Principles and Practice of Multi-Agent Systems namic theory of epistemic states, in: W. Harper, 20th International Conference, Nice, France, OcB. Skyrms (Eds.), Causation in Decision, Belief tober 30 - November 3, 2017, Proceedings, volume Change, and Statistics, vol. II, Kluwer Academic
Publishers, 1988, pp. 105–134. 120061271,popf.L7e1ct–u8r9e.Notes in Computer Science, Springer, [4] M. Carbone, M. Nielsen, V. Sassone, A formal model [17] J. Singleton, R. Booth, An axiomatic approach to for trust in dynamic networks, in: International truth discovery, in: Proceedings of the International Conference on Software Engineering and Formal Conference on Autonomous Agents and Multiagent Methods, 2003, pp. 54–61. Systems (AAMAS), 2020, pp. 2011–2013. [5] K. Krukow, M. Nielsen, Trust structures, Inter- [18] X. Dong, E. Gabrilovich, K. Murphy, V. Dang, national Journal of Information Security 6 (2007) W. Horn, C. Lugaresi, S. Sun, W. Zhang, Knowledge153–181. based trust: Estimating the trustworthiness of web [6] T. D. Huynh, N. R. Jennings, N. R. Shadbolt, An in- sources, Proceedings of the VLDB Endowment 8 tegrated trust and reputation model for open multi- (2015). agent systems, Autonomous Agents and Multi- [19] A. Hunter, E. Tsang, GenB: A general solver Agent Systems 13 (2006) 119–154. for AGM revision, in: Proceedings of the Euro[7] A. Salehi-Abari, T. White, Towards con-resistant pean Conference on Logics in Artificial Intelligence trust models for distributed agent systems, in: Pro- (JELIA), 2016, pp. 564–569.