Trust and argumentation in multi-agent systems

2.1.1.Fuzzy argumentation and trust

da Costa Pereira, Tettamanzi, and Villata (2011) define a belief revision operator that works along similar lines to Barber and Kim's: it also follows the ‘expansion+consolidation’ method, however the consolidation step is very different, and allows conflicting beliefs to persist, in a way, so that this information is not lost, if a later revision reinstates some beliefs. This is achieved through the use of fuzzy argumentation. An agent's belief base is a possibilistic belief base, as described by daCosta Pereira and Tettamanzi (2010), however, underlying that belief base is a fuzzy argumentation framework. The degree to which a formula is believed in the belief base depends directly on the degree to which the arguments supporting and attacking it are acceptable.

If the acceptability of arguments attacking the formula are stronger than the support, the formula is not believed, and the degree of belief is 0. If the support is stronger than the attacks, then the degree of belief is the difference between the two. We will describe the details of the fuzzy argumentation framework below, but it is important to note that this allows inconsistent arguments to coexist in the argumentation framework: they are simply arguments for and against a formula, while the belief base is guaranteed to be consistent. New information changes the labelling in the argumentation framework, which can cause an entirely different set of formulas to be accepted in the belief base, but information is never erased: it persists in the underlying argumentation framework, and changing trustworthiness, or the reception of new evidence can cause beliefs to be reinstated. In contrast, using Barber and Kim's revision operator, or in most prioritised revision operators, when the belief base is revised with information that is inconsistent with the current base, beliefs are irrevocably erased to be consistent with the new information.

The fuzzy argumentation framework that da Costa Pereira et al. use, is an extension of the reinstatement labelling framework, proposed by Caminada (2006). An argument in the framework is a deductive argument (Besnard & Hunter, 2001): an argument is a tuple ⟨Ψ,ψ⟩, such that Ψ is consistent, and a minimal proof for entailing ψ, in a propositional language L. An argument can attack another argument, either by undercutting it, or rebutting it. ⟨Φ,ϕ⟩ undercuts ⟨Ψ,ψ⟩ iff ϕ=¬(ψ1∧⋯ψn) and {ψ1,…,ψn}⊆Ψ. ⟨Φ,ϕ⟩ rebuts ⟨Ψ,ψ⟩ iff ϕ⇔¬ψ is a tautology.

Da Costa Pereira et al. introduce a fuzzy labelling system over the arguments by considering the trustworthiness of the sources. In Caminada's framework, an argument is labelled as either in, out or undecided. Da Costa Pereira et al. generalise this by considering the acceptability of an argument as a degree between 0 and 1. They first introduce the trustworthiness of an argument, by defining it as the trustworthiness of the most trustworthy source that proposes it. The acceptability of an argument is then computed in an iterative process. At time t=0 they define α₀ of an argument A as its trustworthiness trust(A). At each subsequent time, the acceptability of an argument A is defined as:

This is based upon the intuition that the acceptability of an argument cannot be larger than its trustworthiness, and secondly that it can be lowered if arguments that attack it are sufficiently trustworthy. They prove this iterative process converges, and in general use the acceptability labelling α(A)=limt→∞αt(A) for all arguments A. The speed of this convergence is linear in the number of arguments.

As stated above, the acceptability of arguments is then used to generate a possibilistic belief base and for details we refer to da Costa Pereira et al. (2011). However, from the way the acceptability is computed, it is immediately obvious that new information can have one of two effects: the first is that it adds a new argument, which attacks one of the arguments in the agent's belief base. The second is that new information causes the trustworthiness of arguments to change (for instance, by updating the trustworthiness of the sources, or because a new source adds its support to some argument). Both of these cause belief base revision by triggering the iterative process that computes the acceptability of the arguments, which in turn causes the belief base to change.

Nevertheless, this approach has the same disadvantages as other ‘expansion+consolidation’ approaches: it deals only with belief base revision, not belief set, and the priority of new information is not explicitly taken into account. In the next section we discuss another approach that avoids these issues. Additionally, the method does not account for the number of sources that support an argument: an argument's acceptability is defined as the maximum trustworthiness of any source supporting it. This could be augmented by more advanced trust models.

2.1.2.Trust-based selection in belief revision

Tamargo, García, Thimm, and Krümpelmann (2012) propose an alternative method for using argumentation to perform the belief revision that defines a non-prioritised belief revision operator of the type ‘decision+revision’. They first decide what part, if any, of the new information should be accepted, and then use a prioritised revision operator to revise the agent's beliefs with this accepted information. This method works on belief sets, and explicitly takes the priority of new information into account, although it can be discarded if the source is not sufficiently credible. Similar to da Costa Pereira et al. and unlike Barber and Kim, Tamargo et al. do not attempt to model the trustworthiness of sources, but assume there is a mechanism in place to rate the credibility of sources. Differently to either of the previous approaches, however, they assume that each agent has a total preorder ≤ on the set of all agents in the system. Each belief is annotated with its source. The credibility ordering over the sources can then be used to define a preference ranking between arguments.

Tamargo et al. define, just as da Costa Pereira et al. do, an argument as a deductive argument. The credibility of the sources is then used to define a preference ranking between arguments. An argument ⟨Ψ,ψ⟩ is at least as preferred, to agent A, as another ⟨Φ,ϕ⟩ if and only if for all (B:ψ)∈Ψ there is a (C:ϕ′)∈Φ such that C≤_A B. In other words, the least credible source in the argument is at least as credible as the least credible source in the other argument.

This preference ranking over arguments is used in defining a belief revision operator. This is done, additionally, using argument trees. An argument tree is a tree where the nodes are arguments. The children of a node are arguments that attack the parent. Tamargo et al. do not consider rebuttal attacks, although they could easily be incorporated, but only consider undercutting attacks between arguments, which are defined as described above.

Whether or not an incoming piece of information is accepted is decided using a categoriser, which assigns a value to an argument tree, depending on how strongly this argument tree favours the root argument. For an agent A, they define this categoriser γ as:

This credibility categoriser is then used to evaluate new information. Let agent A have beliefs BA and receive a set of new information I from agent A_i. Now, for any ϕ∈I, we can do the following: the set Pϕ is the set of argument trees for φ that can be constructed in BA∪I, and Cϕ is a similar set of argument trees for ≠g φ. κ is a simple accumulator and is defined as follows:

Agent A credulously accepts φ iff κ(Pϕ,Cϕ)⩾0. Or, in other words, there are at least as many reasons to believe in φ as there are to believe in ≠g φ. The agent skeptically accepts φ iff κ(Pϕ,Cϕ)>0. These two methods define two different ways that allow the agent to decide what information in I to accept, and what to reject. Tamargo et al. show how to use this with a prioritised belief revision function in order to revise the agent's beliefs with new information. They then prove that this revision operator satisfies a number of desiderata for revision operators.

Nevertheless, this work leaves a number of open questions. The first is regarding the computational complexity. An argument in this system is a minimal deductive proof for a formula. However, for propositional logic, the problem of finding a single proof is an NP-complete problem, and the method requires all such proofs for every formula, and its negation, in the set of new information. This is in addition to the computational cost of the prioritised belief revision, which is, in and of itself, NP-complete. While no implementation details were given, this seems prohibitive for anything except the smallest of belief sets.

Secondly, it requires the credibility ordering over the different agents to be a total preorder. In many environments it may not be realistic to expect to have information about the trustworthiness of every potential source. This could probably be solved in a pragmatic manner, because the credibility ordering is only required upon receiving new information from a source, at which point the agent could endeavour to learn how trustworthy that source is, using conventional methods. Nevertheless, they do not go into the details of computational trust models for this purpose, which can be highly context-dependent, and have to deal with the uncertainty and dynamicity of the environment themselves.

Tang, Cai, McBurney, Sklar, and Parsons (2012) take a very similar approach to belief revision as Tamargo et al. do, although they do not formalise their framework in terms of belief revision, but see it rather as an abstract argumentation framework that is augmented with trust. The two approaches are largely complementary, with Tang et al. taking a more pragmatic approach and Tamargo et al. proving that the system satisfies some desirable properties.

Tang et al. use a very similar formalisation of arguments to Tamargo et al. (despite some representational differences), but the main difference between the two methods is that Tang et al. use a so-called trust network. A trust network is a directed graph, in which each node is an agent, and every arc is a trusting relationship, which is labelled with the trust evaluation. An important restriction that they require is that trust is transitive. In other words, if A trusts B, and B trusts C, then A also trusts C: the evaluation, or quantification, of that relationship is left uninstantiated in the general model. In their example scenarios, the evaluation is numerical, and they take the minimum of the values to aggregate a trust evaluation over a path in the network.

By assuming transitivity of trust, they solve one of the issues of Tamargo et al.’s framework: namely that the credibility ordering is a total preorder over the agents. Because of the structure of the agent-centric trust network, each agent has an associated trust evaluation, resulting in exactly such a total preordering.

Tang et al., however, do not specify where the arguments come from. Tamargo et al. require all arguments, or proofs, for a formula to be evaluated, in order to decide whether or not it should be accepted. This seems necessary in order to define a belief revision operator, but Tang et al. leave this question open, and take the more pragmatic approach of specifying how to incorporate trust into an abstract argumentation framework. Thus, rather than proving properties about a belief revision operator, they discuss what impact different methods for aggregating transitive trust has upon the credibility of the arguments. In particular, Parsons, Tang, Sklar, McBurney, and Cai (2011), describe a number of properties that the transitive trust operator can have, and consequently prove whether or not certain desiderata of the argumentation system hold.

Nevertheless, it is unclear whether the properties described, or transitivity of trust itself, actually hold in any real system. A number of prominent computational trust models, such as TidalTrust (Golbeck, 2006) or the model presented by Yu and Singh (2002), rely on transitivity, and are used successfully. However, assuming trust is transitive can probably only be done in certain domains and does not hold in the general case (Falcone & Castelfranchi, 2012). This must be taken into account when using Tang et al.’s framework.

2.2.1.Abductive argumentation for evaluating trust

Prade (2007) explicitly models uncertainty in his representation of trust: a trust evaluation is a range [t⁻, t⁺], with both t⁻ and t⁺ in some range of possible trust values S. The meaning of this is that the agent knows that the true trustworthiness τ is no smaller than t⁻ and no greater than t⁺. If t⁻=t⁺ then the value is crisp.

The trust model itself consists primarily of a rule-based system K, which relates levels of trust to observable behaviours of the target. The rules in this system are abductive arguments of one of two forms: let ρ,σ∈S and ϕ a literal in some language for describing observable behaviour, then a rule has the form:

After observing the target's actual behaviour represented as a set of literals (the observations), an agent can abduce what t⁻ and t⁺ must be to optimise consistency with the rules in K. If this results in t⁺<t⁻, which is not ruled out by the structure of the rules, then the agent should be cautious (or pessimistic), and choose t⁺=t⁻.

One thing that sets this work apart from most of the other work that argues about trust is that the argumentation is performed in the opposite direction from the one expected: Prade formulates the arguments such that the trust evaluation appears in the support, rather than the conclusion of the arguments. This is why the evaluation of trust is done using abductive reasoning, rather than deductive. It also does not use a full argumentation framework, in which different arguments attack each other. In contrast, Stranders et al. (2008) do allow for this, and we will see that this is taken even further in the framework of Villata, Boella, Gabbay, and van der Torre (2013).

2.2.2.Fuzzy argumentation for explaining trust

Stranders et al. (2008) present a decision-support system in which an agent recommends an interaction with another agent: in other words, it recommends whom to trust. The system uses argumentation, based on the framework presented by Amgoud and Prade (2004), to provide the reasoning underlying that decision.

The first step in the decision process is to induce an opponent model from historical data. For this purpose Stranders et al. use a Fuzzy Rule Learner to learn a base of fuzzy rules that describe agents’ expected behaviour. These rules are formulas in a fuzzy logic with the structure ‘if a is A then c is C’, where a is some attribute (such as the capability or honesty of the target) to be learned over, c is the variable to be learned (such as the quality of a delivered product) and A and C are fuzzy sets. They further define two measures to quantify how well the rule fits the data, confidence and match strength.

This rule base is used to construct an argument for deciding whether or not to trust a target agent, using a slightly modified version of Amgoud and Prade's fuzzy argumentation framework. An argument is a triple A=⟨S,C,d⟩, with S the support of the argument, C the consequences and d a decision, such that S∪{d} is a minimal proof for C. The formulas in S are elements of the agent's knowledge base, which contains the fuzzy rules that were learned, and the agent's observations. The formulas in C are goals of the agent, with an associated weight. Using the confidence and match strength of the rules in S, and the weight of the goals in C, Stranders et al. define a way of computing the strength of an argument. One decision is preferred over another if the argument supporting the former is stronger than the argument supporting the latter.

Thus arguments for and against trusting a user can be formulated, for instance: let there be rules ‘if capability is low then quality is low’ and ‘if willingness is high then delivery time is good’. An argument for the decision to trust a target might be based on an observation that the target's willingness is high, while simultaneously an argument for the decision not to trust a target can be based on the observation that he is incapable. The comparative weight of receiving a quality product and a good delivery time play a role in deciding what to recommend to the user, as well as how well the rules are estimated to fit the environment.

The argumentative structure allows this to be presented in a way that is understandable to a user. The main computation of this framework is in inducing fuzzy rules. The example scenario in which they test the framework is very restricted, and the induction process is straightforward. However, generally speaking, the induction of predictive theories from examples, is undecidable; even the more restricted practical tasks are known to be not polynomially PAC-learnable. It is thus not clear how well this method for inducing arguments from data works for more realistic scenarios. Matt, Morge, and Toni (2010) sidestep this computational problem by creating a hybrid system, using a Dempster-Shafer belief function to analyse the target's past behaviour, and argumentation to augment this with justified claims about the target's expected behaviour.

Nevertheless, Stranders et al.’s model is interesting precisely because it highlights an often overlooked aspect of computational trust: in most multi-agent systems, the agents exist to support users, who must authorise any behaviour: being able to explain the trust evaluation is important in this context.

2.2.3.Combining statistics and argumentation

Matt et al. (2010) build upon an established computational trust model (Yu & Singh, 2002) that uses a Dempster–Shafer belief function to estimate the trustworthiness of a target. They do this by first partitioning the past interactions with a target into three sets: the interactions in which the outcome was good, the interactions in which the outcome was bad, and the interactions in which the outcome was inappreciable (the rest). An agent is deemed trustworthy if the difference between the frequency of good interactions and the frequency of bad interactions is greater than a prespecified threshold.

Simultaneously, they use an abstract argumentation framework (Dung, 1995) to specify two types of arguments: forecast arguments support trusting or distrusting a target, and mitigation arguments attack forecast arguments. These arguments are generated from the contracts between agents. A contract regulates the interactions between two agents and provides guarantees about the quality of these interactions along various dimensions. In particular, they specify availability, security, privacy and reliability, but it is easy to see that in different domains, different dimensions are important. The arguments for each dimension d are generated as follows:

They consider trust along each of the dimensions separately and incorporate the argument-based and statistical evidence into a single evaluation by defining an argument-based evidence mass function that evaluates all the evidence in a numerical manner, combining the strength of arguments, their informational value and the statistical evidence. By incorporating more information, the agent should be able to obtain more accurate trust evaluations, and Matt et al., show this empirically.

The main advantage of this method is that it provides a clear computational method for integrating argumentation into a trust model. They are deliberately vague on the content of the arguments, and work with an abstract framework. They generate the arguments from underlying contracts, but in principle there is no reason why the framework must be instantiated this way, and it should be possible to consider more complex argumentational structures.

2.2.4.Meta-argumentation

Villata et al. (2013) take an entirely different approach, and their model can best be considered a hybrid approach, where the trustworthiness of sources is used to evaluate arguments, and in turn arguments can support or attack the trustworthiness of sources.

Villata et al. argue that what is lacking in the models discussed in Section 2.1, is an explicit representation of the sources themselves. One fundamental aspect of argumentation frameworks is that an argument is acceptable if it is not attacked. However, if a source of an argument is untrustworthy, the argument might be unacceptable even if there is no conflicting information.

In order to remedy this, they propose an extended argumentation framework (Boella, Gabbay,van der Torre, & Villata, 2009) in which sources are represented explicitly. The argumentation framework they propose can be seen in two ways: the first is with sources, outside of the framework, proposing arguments. The second is a meta-level in which the previous representation is flattened and the sources are represented explicitly within an argumentation framework. At this meta-level there are a number of auxiliary arguments, and for details we refer to (Villata et al., 2013), but in particular there is the argument trust(A), where A is a source. Because the meta-level is a regular argumentation framework, arguments can attack these meta-arguments. In Villata et al.’s example scenario, one agent proposes a rebuttal attack against the trustworthiness of another. This instantiates a second meta-level argument.

Villata et al. formalise this all, and provide the rules for when a meta-level argument may be instantiated in such a way to prevent infinite regression from happening (for instance, if two agents attack the trustworthiness of each other). Dung-style semantics can then be applied to decide which arguments are accepted.

In many ways this framework is similar to the trust-based belief revision method proposed by Tang et al. (that we discussed in Section 2.1.2): they both extend an argumentation framework by explicitly linking the trustworthiness of sources to the arguments they propose. However, Tang et al. only represent trust, and use this to define the strength of the proposed arguments, whereas Villata et al. focus explicitly on distrust: arguments can attack the trustworthiness of a source. Particularly, in Tang et al.’s framework, if an argument is not attacked, it is necessarily accepted, because all sources are necessarily trusted to some degree, due to the transitivity of trust in their trust network. Villata et al. assume a similar starting point: all agents are trusted, unless there are arguments to the contrary, but they provide the structure for explicitly representing these arguments.

3.1.1.Reasons for having a trust evaluation

Arguments are sentences in the LArg language. This language is defined over LRep. A sentence in LArg is a formula (Φ:α) with α∈LRep and Φ⊆LRep. This definition is based on the framework for defeasible reasoning through argumentation, given by Chesñevar and Simari (2007). Intuitively Φ is the defeasible knowledge required to deduce α. Defeasible knowledge is the knowledge that is rationally compelling, but not deductively valid. The meaning here, is that using the defeasible knowledge Φ and a number of deduction rules, we can deduce α. The defeasible knowledge is introduced in a set of elementary argumentative formulas. These are called basic declarative units.

Arguments are constructed using an argumentative theory Γ and the inference relation ⊢Arg, characterised by the deduction rules Intro-BDU, Intro-AND and Elim-IMP.

An argument (Φ:α) is valid on the basis of argumentative theory Γ iff Γ⊢Arg(Φ:α). Because the deduction rules, and thus ⊢Arg, are the same for all agents, they can all agree on the validity of such a deduction, however each agent builds its own argumentative theory, using its own trust model. Let I be the set of inference rules that specify an agent's trust model. Its bdus are generated from a set of LRep sentences Δ as follows:

Continuing the example from above, our agent might have bdus:

However, if trust evaluations can be based on many different criteria, agents might reach the point where they filter out too much information. To reduce the amount of information discarded, agents, when sending a trust evaluation, could personalise their trust evaluations to the receiver.

3.2.1.Personalising trust recommendations

The argumentation framework by Pinyol et al. that we described in Section 3.1.1 does not allow us to completely address the question of what criteria play a role in computing a trust evaluation, let alone connect these to underlying beliefs and goals. AdapTrust can answer this, but does not provide a language in which to do so. Koster et al. (2012a) extend Pinyol et al.’s argumentation framework with concepts from AdapTrust. The priorities that define the trust model's parameters can be incorporated into the argumentative theory. For this, the dependency of the trust model on the beliefs and goal of an agent must be represented in LArg. Rather than using LRep as the single language on which the argumentation framework is built, the agent can argue about concepts in LKR=LRep∪LPL∪LRules∪LBel∪LGoal, where LPL and LRules are the languages of the priorities and priority rules, respectively, in AdapTrust, LBel the language of the agent's beliefs and LGoal that of the agent's goals.

This allows us to redefine the set of bdus and thus the argumentative theory in such a way that the argumentation supporting a trust evaluation can be followed all the way down to the agent's beliefs and goal. The deduction rules are the same as in Pinyol et al.’s framework, but the bdus for LArg are defined as follows:

In items 1 and 2 the relevant elements of the agent's reasoning are added to the argumentation language. In items 3 and 4 the tools for reasoning about trust are added: in 3 the trust priority rules and in 4 the rules of the trust model. The bdus added in 4 contain a double implication: they state that if an agent has the priorities in Π_L then a trust rule (which was a bdu in Pinyol's argumentative theory) holds. In practice what this accomplishes, is to allow the argumentation to go a level deeper: agents can now argue about why a trust rule, representing an application of a deduction rule in the trust model, holds. An argument for a trust evaluation can be represented in a tree. At each level, a node can be deduced by using the deduction rules of LArg with as preconditions the node's children. A leaf in the tree is a bdu. Each agent can construct its own argumentation tree for a trust evaluation and use this in a dialogue to communicate personalised trust evaluations.

3.2.2.The dialogue protocol

Koster, Sabater-Mir, and Schorlemmer (2012b) define a dialogue protocol, based largely upon a previous protocol for information-seeking dialogue (Prakken, 2005). The dialogue for personalising trust evaluations starts as an information-seeking dialogue, but if the agents discover their priorities are incompatible, they can discover whether this is due to a lack of information of either agent, or whether their world views are simply incompatible. If either agent is lacking information or the agents think they can reach an agreement on beliefs, they can enter a persuasion dialogue to achieve an agreement on the beliefs and trust priority rules. If this succeeds, they can restart the dialogue and see if they now agree on trust evaluations. In this way the argument serves to allow cooperative agents to converge on a similar model of trust and supply each other with personalised trust recommendations.

The main issue with these systems is that they only work if they are adopted by a sufficient number of agents. In particular, the framework for personalised trust recommendations requires agents to use a cognitive agent model with the computational trust model incorporated into it, and is thus only applicable in domains where such a cognitive model is already necessary. However, in such domains, trust will necessarily be subjective, and some process, such as personalisation of trust recommendations, is necessary for communication about trust to be useful at all.