We consider domains where agents can receive information from observations, and also from reports. When an agent receives a sequence of observations and reports, this can trigger two changes. First, the agent's beliefs should change to incorporate new information received from trusted agents and from observations. Second, the agent's trust in other agents should change, depending on the accuracy of their reports. In this paper, we address this problem incrementally by first considering trust change. We introduce trust states, and we demonstrate how trust states can be explicitly updated by a new class of trust change operators. Trust change postulates are introduced, and a representation result is presented for these operators. We then demonstrate how we can use trust change operators to make implicit updates to trust in other agents, based on the accuracy of the reports provided by other agents. Broadly, agents are more strongly trusted when they provide reports that agree with observation and they are less strongly trusted when they provide reports that conflict with observation. We define combined trust-belief change operators that allow an agent to simultaneously update their trust in other agents while also revising their beliefs. We then introduce a software tool that automates this entire process. In other words, the software allows us to enter a sequence of reports and observations, and it returns both a new belief state and a new trust state. Applications and directions for future work are considered.
Belief revision occurs when an agent receives new information that must be incorporated with some previous beliefs. The most influential approaches to belief revision make the assumption that new information is “better” than the original beliefs. Hence, an agent should believe the new information is true while keeping as much of the initial belief state as consistently possible. However, when the new information comes from an agent that may not be honest, then this is no longer sensible. In these cases, there are actually two diferent concerns related to trust. First, trust impacts the likelihood that we will believe reports from other agents. This problem has been addressed to some extent in the literature. The second concern is related to trust change. Our level of trust in other agents should change, depending on how often their reports agree with our observations. This problem has not been addressed extensively in the context of belief revision operators. In this paper, we introduce a formal approach to modeling the simultaneous dynamics of trust and belief along with a prototype system that calculates the result of belief revision when new information includes observations and reports from other agents.
Our approach is the following. We first introduce trust states, along with a set of postulates for trust change; these postulates specify basic conditions that we expect to hold when we determine that some agent should be more (or less) trusted. We then prove a representation result for operators satisfying these postulates. Next, we introduce new combined change operators, which specify both how beliefs and trust should change when an agent receives a sequence of reports followed by an observation. Finally, we introduce our implemented system for solving problems involving the joint revision of trust and belief.
This paper makes several contributions to the literature on belief change. First, trust change operators have not been explored in detail in the theory of belief change. As such, both the set of trust-change postulates and the representation result are new contributions in the area. Another 22nd International Workshop on Nonmonotonic Reasoning, November 2-4, 2024, Hanoi, Vietnam $ aaron_hunter@bcit.ca (A. Hunter) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). contribution is the introduction of combined change operators for trust and belief. Our approach makes the relationship between belief change and trust change explicit, framed in the context of a classical model of belief revision. Finally, the work here introduces a practical software tool that can opens up the opportunity to reason about practical applications related to reputation systems.1
The theory of belief revision is framed in the context of
propositional logic. We assume an underlying propositional
signature , and we define propositional formulas in the
usual manner using connectives ∧, ∨, →, and ¬. A belief
state is a logically closed set of formulas. The most
inlfuential approach to belief revision is the AGM approach,
where a belief state and a formula are mapped to a
new belief state * [
AGM revision can only be used for single-shot belief
revision. If we want to perform iterated belief revision, then the
dominant approach is the DP approach [
Most approaches to belief revision require that the new
information must be believed; this is formalized by the
socalled success postulate of AGM revision. As noted, this is not
reasonable if information is reported by other agents. Two
diferent approaches to this problem have been explored in
the literature. There has been work on knowledge-based
trust, where we only consider the ’part’ of the information
where the reporting agent has expertise[
We distinguish between knowledge-based trust and
reliability-based trust. Knowledge-based trust is concerned
with the domain expertise of a reporting agent. For example,
a doctor is trusted on medicine; they may not be trusted
on other topics. Knowledge-based trust has been used as a
means for ranking search results on the Internet [
We are concerned with reliability-based trust. An agent
is reliable if their reports agree with known facts or direct
observation. If an agent provides inaccurate reports, they
will not be trusted. This has been addressed in [
Suppose we are investigating a crime scene and we can receive reports from two agents: Juan( ) and Alma(). Juan is considered to be trustworthy, whereas Alma is not.
We are initially unsure if the door was forced open ( ), and we believe that there is no crowbar in the house(¬). So if our initial epistemic state is E, then (E) should be the set of models of ( ∧ ¬) ∨ (¬ ∧ ¬). Now suppose that we receive a report from Alma that the door was forced open and there is a crowbar in the house. Since Alma is not trusted, this report does not initially trigger a belief change. Juan then reports that the door was not forced open and that there is no crowbar in the house. The most plausible states in our new epistemic state E′ are the models of ¬ ∧ ¬. Suppose that we now observe a crowbar is in the living room. What should be believe now, and who should we trust?
It seems like we should decrease our trust Juan, since he has provided incorrect information. We also need to revisit our trust in Alma. She has provided a report that is consistent with our observation, so our trust in her should increase. We might even want to retroactively believe her initial report.
Reasoning about this kind of problem requires a model
that keeps track of beliefs as well as trust in reporting agents.
As information is acquired, we not only need to revise our
beliefs - we also need to increase (resp. decrease) trust in
agents that have provided accurate (resp. inaccurate) reports.
In this paper, we introduce a family of combined trust-belief
change operators for this purpose. We remark that this kind
of reasoning does not only occur in commonsense problems;
it is also the basis for trust in reputation systems [
We introduce a model of trust change that is defined with respect to a set of agents A. Belief change will be added in section 4. We first define trust states, which are ranking functions that capture the trust held in other agents. Definition 1. A trust state is a function : A → Z. We write ( ) = { | () ≤ 0}, and we refer to this as the set of trusted agents.
Informally, if () < (), then is trusted more than . The set ( ) is similar to the set of ”believed” states in an epistemic state, but there is an important diference. Although the agents in ( ) are all trusted, we still can rank them and to determine which agents are most strongly trusted.
We now introduce a simple class of trust change operators. In the following definition, an agent literal is either or -, where ∈ A.
Definition 2. A basic trust change operator is a function ⋆ that maps a trust state and an agent literal to a new trust state ⋆ .
Intuitively, ⋆ is the operation that occurs when has done something that causes them to be more trusted. For example, if an agent provides a report that is consistent with direct observation, then we will increase trust in that agent. On the other hand, ⋆ - captures the situation where an agent becomes less trusted. This would occur, for example, when the agent has provided a report that is inconsistent with direct observation.
We give some desirable properties for basic trust change operators. The following postulates are all implicitly univerally quantified over trust states , ′ and agents , . For clarity, we use square brackets to write [ ⋆ ](), which is the value assigned to by the trust state ⋆ .
R1. [ ⋆ ]() < ().
R2. [ ⋆ ](-) > ().
R3. If ̸= , then () = [ ⋆ ]() and () = [ ⋆ -]().
Postulate 1 says that, when an agent becomes more trusted, the -ranking for decreases. Postulate 2 makes the dual statement for agents that become less trusted. Postulate 3 states that changing the trust level associated with an agent does not afect the trust level of any other agent.
We also introduce two postulates to ensure that ⋆ treats all agents equally. In other words, the magnitude of the trust change is equal for all agents:
R4. () − [ ⋆ ()] = () − [ ⋆ ()].
R5. [ ⋆ -]() − () = [ ⋆ -]() − (). Finally, the change in trust induced by ⋆ is the same for all trust states; the magnitute of trust change is determined by ⋆ and not by the initial trust state:
R6. () − [ ⋆ ()] = ′() − [ ′ ⋆ ()].
R7. [ ⋆ -()] − () = [ ′ ⋆ -()] − ′(). Taken together, these postulates define a class of basic trust change operators.
Definition 3. A basic trust change operator that satisfies postulates 1 − 7 is called a graded trust change operator.
Proposition 1. Let be a graded trust change operator. Then the following conditions hold: (1) If ∈ ( ), then ∈ ( ⋆ ) and (2) If ̸∈ ( ), then ̸∈ ( ⋆ -). Hence, trusted agents remain trusted when we use ⋆ to increase trust. The reverse holds for untrusted agents that lose trust. These properties are immedidate consequences of 1 and 2, respectively.
The following proposition states that an agent can always become trusted after a finite number of trust strengthenings, and they can always become untrusted after a finite number ifnite number of weakenings.
Proposition 2. If is a graded trust change operator and
∈ A, then there is some such that ∈ ( ⋆ ).
Similarly, there is some such that ̸∈ ( ⋆ -).
This property is reminiscent of the key postulate for
belief improvement operators [
We introduce a class of transformations on ranking functions over agents.
Definition 4. Let : A → Z. If ∈ N, then define the ranking functions + (, ) and − (, ) as follows: [ + (, )]() = [ − (, )]() = {︃() + , if =
(), otherwise {︃() − , if =
(), otherwise Hence + (, ) increases the ranking of and − (, ) decreases the ranking.
We can now give a representation result for graded trust change operators.
Proposition 3. The function ⋆ is a graded trust change operator if and only if there exist positive integers , such that ⋆ = {︃ − (, ), if = for some ∈ A
+ (, ), if = - for some ∈ A Proof Suppose ⋆ is a graded trust operator. Let 0 be a trust state, and let 0 be a particular agent. By 1, there is some such that [0 ⋆ 0](0) + = 0(0) . By 4, it follows that [0 ⋆ ]() + = 0() for all agents . By 3, we also know that [0 ⋆ ] = 0() for all ̸= . Moreover, by 6, we know that these equalities are actually true for all trust states . Therefore ⋆ = − (, ); so the result holds for positive literals. By parallel reasoning, we can use propositions 2, 3, 5 and 7 to show that there is some that validates the result for negative literals as well.
To prove the converse, suppose that we have two positive integers , that define ⋆ as in the definition. Then 1 holds because [ ⋆ ]() + = () and > 0. Similarly 2 holds for . Postulate 3 holds from the definition of the + and − operators, which only increment the ranking for one agent at a time.
For any , and any , ′, we have the following equalities: () − [ ⋆ ]() = () − [ ⋆ ]() = = () − [ ⋆ ]() = ′() − [ ′ ⋆ ]() The first equality shows that 4 holds, and the second equality shows that 6 holds. We can prove 5 and 7 holds through similar equalities, using as the middle value. Hence, ⋆ is a graded trust change operator. So graded trust change operators can be fully characterized by two positive integers: the strengthening constant and the weakening constant .
There are some interesting variations that we can give to characterize a larger set of basic trust change operators. The following is one such instance.
Proposition 4. A basic trust change operator ⋆ satisfies postulates 1 − 3 and 6 − 7 if and only if, for each agent there is a pair of positive integers , such that: ⋆ = {︃ − (, ), if = for some ∈ A + (, ), if = - for some ∈ A (1) We call such an operator a non-uniform graded trust operator. This proposition states that, if we omit postulates 4 and 5, then we have a class of operators that is characterized by strengthening and weakening constants that could be distinct for each agent. The proof is similar to Proposition 3.
Additional operators can be defined by modifying postulates 6 and 7. For example, we could model situations where trust is resilient by making trust decreases very small for strongly trusted agents. We leave a full exploration of such variations for future work.
We have defined graded trust change operators for a single agent literal . However, we will generally be interested in sequences of literals = 1, . . . , . We will write ⋆ as a shorthand for ⋆ 1 ⋆ · · · ⋆ . Each literal represents a single data point, indicating evidence that a particular agent should be more (or less) trusted. We adopt the following notation: = |{ | in }| = |{ | - in }| Hence is the number of postive literals in and is the number of negative literals in . The stands for agreement while the stands for conflict .
Proposition 5. Let ⋆ be a graded trust operator, defined by and . Then Definition 5. A multi-agent signature is a pair ⟨A, V⟩ where A is a set of agents, V is a propositional signature. [ ⋆ ]() = () − + .
This result follows directly from Proposition 3, since each increase or decrease is handled independently. So the iterated trust over a sequence of changes is just the aggregate of individual trust change operations. As a result, for any operator ⋆, any sequence , and any agent we can define the following value:
∆( ⋆, , ) = [ ⋆ ]() − ().
Hence, ∆ represents the change in trust for agent given the operator ⋆ and the sequence . The properties of this change value are given below.
Proposition 6. Let ⋆ be a graded trust change operator. Then: 1. If = = 0, then ∆( ⋆, , ) = 0. 2. If = 0 and > 0, then ∆( ⋆, , ) > 0. 3. If = 0 and > 0, then ∆( ⋆, , ) < 0. 4. If = and > then ∆( ⋆, , ) < ∆( ⋆, , ). 5. If = and < then ∆( ⋆, , ) > ∆( ⋆, , ).
Item (1) asserts that trust in does not change if does not occur in . Item (2) says that becomes less trusted if they only occur in conflict literals, while item (3) says the reverse for agents that occur only in agreement literals. Item (4) compares diferent sequences. It says that, if two sequences include the same number of conflict literals, then the one with more agreement literals will have a more positive impact on trust for . Item (5) makes a similar statement for the case where the number of agreement literals is the same.
Proposition 6 summarizes the properties of aggregate trust change. However, since and are not constrained, we can not say anything specific about the aggregate change due to a sequence that includes both confict and agreement. Proposition 7. Let be a trust state, let ∈ A, and let be any sequence of agent literals that contains at least one instance of and at least one instance of -. Then there are graded trust change operators ⋆1, ⋆2 and ⋆3 such that ∆( ⋆1, , ) < 0 = ∆( ⋆2, , ) < ∆( ⋆3, , ). Hence, in the general case, there is no way to determine if ∆( ⋆, , ) is positive or negative. This flexibility allows us to define graded trust change operators that handle agreement and conflict very diferently. For example, a single conflict might increase the trust ranking as much as a million agreements. So if contains both a strengthening and a weakening for , then we can not say anything about whether or not will be trusted unless we know the specific change operator.
We now move to the case involving both trust and belief. So we need a signature that includes both agents and properties of the world.
The important connection between agents and formulas is that agents provide reports, and the content of a report is a propositional formula.
Definition 6. A report is a pair (, ) where ∈ A and is a formula over V. We write = (1, 1), . . . , (, ) for a finite sequence of reports.
The problems that we address involve both reports and observations. We will normally be concerned with sequences of reports followed by an observation. This concept is formalized below.
Definition 7. A history-sensitive observation (hsobservation) is a pair ⟨, ⟩ where is a report history and is a formula.
Defining belief change with respect to hs-observations allows us to consider how the observation informs the extent to which the reports in should be incorporated. In order to represent an agent’s beliefs along with their trust in other agents, we define the following notion of an epistemic trust state.
Definition 8. An epistemic trust state is a pair ⟨E, ⟩ where E is an epistemic state over V and is a trust state over A.
Note that E and are independent, but we will define change operators that impact them both at the same time.
We now define combined change operators for trust and belief. The first step is to show how an hs-observation defines a sequence of trust change operations.
Definition 9. Let ⟨, ⟩ be an hs-observation where = (1, 1), . . . , (, ). For each ≤ , let: = {︃ , if ̸|= -, if |= .
Let (⟨, ⟩) = 1, . . . , .
Hence, (⟨, ⟩) is a sequence of literals. The literal in position is if the formula reported by in position is consistent with . The literal in position is - if the formula reported by in position is inconsistent with . Intuitively, this sequence encodes how our trust in each agent should change given the hs-observation ⟨, ⟩; the agent should be more trusted if they have provided reports consistent with and they should be less trusted if they have provided reports inconsistent with .
We use Definition 9 to overload the ⋆ operator, by allowing it to take an hs-observation as input. Specifically, we adopt the following notation::
⋆ ⟨, ⟩ = ⋆ (⟨, ⟩).
Hence, when we given an hs-observation as an input to ⋆, we simply pass to the sequence of agent literals (⟨, ⟩). This sequence of literals captures the number of conflict and agreement reports that each agent has provided.
We need one more piece of notation. Given a report history and a set of agents , we write ↾ as a short hand for the sequence of formulas where ∈ . So if represents the set of trusted agents, then ↾ represents the sequence of formulas reported by trusted agents.
We can now define an approach to combined change for trust and belief.
Definition 10. Let ⟨E, ⟩ be an epistemic trust state, let * be a DP operator, and let ⋆ be a graded trust change operator. Then ∘ is defined as follows: 2
⟨E, ⟩ ∘ ⟨ , ⟩ = ⟨ * ↾ * , ⋆ ⟨, ⟩⟩ where = ( ⋆ ⟨, ⟩).
Hence, the new trust state is obtained by strengthening and weakening trust in agents, based on whether they have provided reports that are consistent with the observation . The new epistemic state is obtained by iteratively revising by all reports from trusted agents, and then revising by the observation . Note that the set of trusted agents used for this revision is determined after any trust changes resulting from the given sequence of reports. We illustrate by returning to our motivating example.
Example We can further formalize our motivating example involving Juan( ) and Alma () at the crime scene. Let be the trust state where ( ) = − 1 and () = 1, which reflects our assumption that Juan is initially trusted, while Alma is not. Suppose that ⋆ is the operator defined by the constant 2 for both strengthening and weakening. Recall that Alma reports ∧ , then Juan reports ¬ ∧ ¬, then we observe . So we need to calculate the following: ⟨E, ⟩ ∘ ⟨ (, ∧ ), (, ¬ ∧ ¬), ⟩.
From Definition 10, our new trust state ′ assigns ′( ) = 1 and ′() = − 1. So after all events, only Alma will both be trusted. This also means that the final epistemic state will be E * ( ∧ ) * . Hence, we will not only believe the crowbar is in the house, but we will also believe the door was forced open. This is because Alma’s report has been incorporated, since she is now trusted.
Note that the we can get a diferent result, if we return to the example with one small tweak.
Example Consider the same example, except that ( ) = − 3 while () = 1. In this case, the new trust state ′ assigns ′( ) = − 1 and ′() = − 1. So, despite the fact that Juan has provided an erroneous report, he is still trusted. The intuition here is that Juan has built such a strong reputation that he will still be trusted after a single mistake. In this case, the final epistemic state will be E* ( ∧ ) * (¬ ∧ ¬) * . Following this sequence of revisions, we will believe the crowbar is in the house but we will not believe the door was forced open. This holds despite the fact that Alma has reported otherwise, because Juan is still a trusted source.
Many other small tweaks that could be made to get diferent results. For example, if the ⋆ operator only strengthens trust with a constant = 1, then Alma will not be trusted despite the accuracy of her report. In all of these cases, the basic framework handles the subtle distinctions without any dificulty. 2Note that ∘ actually depends on * and ⋆, so it would be more appropriate to write ∘ * ,⋆. But this notation is cumbersome, so we omit the subscripts unless they are required to reduce ambiguity.
A report filter is any function that maps an hs-observation ⟨, ⟩ to a new hs-observation including a subsequence of the reports from the original. A report filter is observationconsistent if every report in the output subsequence must be consistent with .
Proposition 8. Let be a trust state. The report filter ↾ ( ) is not guaranteed to be observation consistent.
This result is important, because it means the ∘ operator is based on a filter that can include reports that are inconsistent with the observation.
We have seen this in Example 2, where Juan’s report inlfuences the final epistemic state despite the fact that it is inconsistent with the observation. This seems reasonable in this case, because the report is a conjunction and we end up keeping only the “consistent part.” However, in some applications, it would be preferable to discard all inconsistent reports regardless of how much the sender is trusted. We can enforce this condition by providing a modified definition of ∘ .
Let ⟨, ⟩ be an hs-observation and let be the set of agents that have provided a report in that is inconsistent with . The following is immediate.
Proposition 9. Let be a trust state. For every hsobsrvation, the report filter ↾ ( )∪ is observation consistent. This simple change gives us a variation of ∘ that is based on an observation-consistent filter. Specifically, we can modify the definition of ∘ to define ∘ as follows:
⟨E, ⟩ ∘ ⟨, ⟩ = ⟨ * ↾ ∪ * , ⋆ ⟨, ⟩⟩ where is defined as it was previously. Hence ∘ is just like ∘ , except that it filters out all reports inconsistent with before performing belief revision.
The Honesty-based Belief revision System (HBS) is a tool written in Python to automatically solve belief revision problems3. The system allows the user to specify an initial belief state, along with a sequence of reports and observations. The system has a graphical user interface for interactive model, where the user enters the reports and observations directly; it also allows users to enter the required information through external files. In this section, we describe the main funcationality of the software.
The interface for HBS is shown in Figure 1. When HBS is launched, it will initially be set to the Formula Entry tab. While the Initial state radio button is highlighted, this allows the user to enter a set of formulas that define the initial belief state. In interactive mode, formulas are entered with a simple graphic interface that prevents syntax errors. The formula being defined is displayed above the entry box, and it is entered as part of the initial belief state when the user clicks on Add Formula.
The initial belief state can be modified iteratively by adding more formulas, and a panel on the right will display the set of states believed possible. The radio button at the bottom can be toggled to add observations or reports. For observations, the formula is added to the right panel and labelled as an observation. For reports, an agent name must also be provided. All of the items listed in the right panel can be deleted at any time by clicking the X in the corner. As such, what the interface allows the user to do is to specify an expression of the form: * (1, 1) * 1 * · · · * (, ) * .
The user can click Calculate Output to determine the new belief state after the given sequence of operations. Figure 2 shows the contents of the right panel after entering the following: [¬(∧¬)]* (alice, ∨)* (bob, ∧)* ( → ¬) The output at the bottom indicates the new belief state; we explain below how this is determined. We remark that the display can be modified to a simplified form; this will hide the lists of truth values for variables. This can be helpful for large examples with many variables.
Note that the main interface also includes the Agent Trust Entry tab. In this tab, the user can enter the initial trust ranking for all agents. 5.3. Trust Trust change in HBS is based on a set of parameters. There are six diferent parameters available, listed in the following table.
Obs. Decrease (− )
Obs. Increase (+) No Trust Threshold (min) Rep. Decrease (− )
Rep. Increase (− ) Diference Threshold ( ) Informally, − and + are the amounts to decrease (resp. increase) the trust in a reporting agent when they have provided a report that conflicts with an observation. These paramaters represent the trust strengthening and trust weakening parameters from the previous section. Similarly, min is a flexible parameter that allows us to specify set of trusted agents; in our formal theory this was fixed at 0.
The remaining parameters are new, and they are concerned with conflicting reports. The paramater − is a new change constant, which is the amount that () should decrease if provides a report that conflicts with a more trusted agent. Similarly, + is the amount that () should increase if provides a report that agrees with a more trusted agent. However, we do not necessarily make these changes in all cases. We only make these changes if the trust diferential between and the other agent is greater than the diference threshold .
Essentially, these parameters allow the implementation to deal with a slightly more complex notion of trust change. Changes in trust no longer depend on conflict with observation, agents can now become more (or less) trusted based on how much they agree with other reporting agents. However, we remark that we essentially have graded trust change operators if we restrict − and + to be 0.
The change in trust that occurs with this full set of parameters is given in the following definition.
Definition 11. Let min, be a trust state and let = ⟨+, − , +, − , ⟩ be a tuple of natural numbers (called the trust parameter). Define · (⟨, ⟩, ) = ′ where ′() is specified by applying the following procedure: 1. Initially, set ′() = (). Update as follows by comparison with : • If there is a report (, ) in such that |=
¬ , then ′() = () − − . • If there is a report (, ) in such that |=
, then ′() = () + +. 2. Next, compare with reports. For all agents with () < (), if () − () > , then: • If there are reports (, ) and (, ) in with
|= ¬ , then ′() = () − − . • If there are reports (, ) and (, ) in with
|= , then ′() = () + +.
In HBS, the default values for all parameters is 1, but these values can be modified either through the interface or by editing the values in the revision.py file.
We specify a default “idealized” revision operator. The idealized operator is the revision operator that would be used if we only had to incorporate observations. In HBS, the default revision operator is the Dalal operator based on the Hamming distance between states. However, this is not the only revision operator that HBS can capture.
Under the edit menu, the user can change to a weighted
Hamming distance operator. In this case, a weight needs
to be associated with each variable and these weights are
used in the distance calculation. It is easy to see that this
approach to revision can capture many operators beyond
the standard Dalal operator. For example, if we use powers
of two for the weights, we can essentially specify a priority
ordering over paramaters. Hence, the weighted Hamming
distance can be used to capture any parametrized diference
operator [
Suppose that a series of reports followed by a single observation has been entered, and the user presses ’Calculate output.’ Then the following calculations are performed: 1. First, the trust values are updated in accordance with
Definition 11. 2. The new trust values are used to determine the subsequence of formulas for revision. 3. The revision is performed based on the selected revision operator. 4. The new belief state is displayed; it will be used for future revisions.
If the sequence of reports and observations involves several observations (rather than a single terminal observation), then step (1) and (2) involve multiple sweeps through the reports to remove those that are inconsistent with any observation.
Hence, HBS takes a sequence of reports and a single observation, and it returns a new epistemic trust state. It includes the calculation of graded trust change operators as a special case, but it also allows a wider range of operators to be specified. Of course, when we use non-zero values for the new parameters, we no longer have a clear synactic definition for the operators.
We remark also that HBS can actually be used to solve iterated change problems with multiple observations. Since all of the revision operators included support iteration, we simply need to update the trust levels for each agent after every observation before continuing with more reports and observations.
Although the interface allows the user to enter a long sequence of formulas, it can be cumbersome to do so. In order to make the software easier to use, there is also a mechanism to load test cases from a text file in the following format: (Av!A)^B/!A^!B 1,2 alice:AvB bob:A^B :A>!B The first line specifies a set of formulas, separated by slashes. The second line gives weights to all variables, in the order that they appear in the input. These values are for the weighted Hamming distance; they should all be set to 1 if Dalal revision is preferred. The remaining lines specify reports in the form “agent:formula.” If the agent part is left blank, then the line represents an observation. When a test case is loaded from a file in this format, then it automatically populates the right panel with all of the information. This is a much easier way to enter examples involving a long sequence of reports.
Trust has been explored in a variety of formal settings
involving agents with limited beliefs exchanging information
[
There has been previous work on the interaction between
observations and reports in [
Perhaps the closest work in the literature to our approach
is in [
We briefly introduce a potential application for our framework. We propose that graded trust change operators and HBS are well suited for for reasoning about reputation systems, where we have a seller that has been rated based on a series of transactions. The information provided by ratings need not simply be judgments about the “goodness” of the seller; they might include information about the product, the promptness of delivery, or anything else about the transaction. All of this can be encoded in a suitable logical theory. When we read a series of reviews and then make a purchase, we are able to simultaneously update our beliefs and our trust in the ratings through the framework introduced in this paper. Automating this process, we can implement a simple reputation system that can maintain a sound trust ranking over all agents providing reviews.
The automation step here is actually not dificult. Using
HBS, we can solve report revision problems by encoding
them in the format specified.
(Av!B)^(B^!C)
Jordan:AvB, Alma:A^B, obs:AV!B
There is a problem here in that real reputation systems often
include thousands of reviews; the current iteration of HBS
does not use a fast revision solver, so it runs slowly on
problems involving many formulas. However, it is possible
to signicantly improve the running time for revision solvers
by using a competition-level ALLSAT solver [
We introduced graded trust change operators, which let us incrementally change how much we trust informationproviding agents. We then introduced a set of trust-change postulates, and proved that every operator satisfying the postulates is defined by two values: a strengthening constant and a weakening constant. Trust change operators can be combined with DP belief revision operators to define a new class of combined report-revision operators. These operators take a sequence of reports along with an observation as input, and they simultaneously revise the agent’s beliefs and modify their trust in reporting agents. The result is a single operator that combines two rational change functions to ensure both beliefs and trust are changed appropriately.
There are many directions for future work. As noted, the current implementation could be improved in terms of eficiency. The current version of HBS is a proof of concept that is only suitable for small toy problems, due to the computational complexity of belief revision.
At a theoretical level, we remark that basic trust change operators are quite restrictive in that they can only take a literal as input. In future work, we would like to extend the vocabulary of “trust formulas” to permit updates by more complex trust statements. Another direction for future research is to axiomatize the interaction properties of report revision operators. Right now, we know that the revision part satisfies the DP postulates and the trust part satisfies our new trust change postulates. But it would be useful to provide a further set of interaction postulates to describe the properties that must hold when the operators are combined. We are also interested in extending the current framework, so that it can model the interaction between knowledgebased trust and honesty-based trust.