I. INTRODUCTION

In a multi-agent system (M AS) context, trust-based methodologies are recognized as an effective solution to increase MASs performances [17], [28], [29] by promoting social interactions, particularly when software agents are distributed in large-scale networks and reciprocally interact [23].

A trust relationship between two interacting agents (i.e., a trustor requiring a service to a trustee) can involve multiple dimensions based on the chosen perspective. For instance, in e-service domains, trust is defined as: "The quantified belief by a trustor with respect to the competence, honesty, security and dependability of a trustee within a specified context" [12]. In particular, i) the competence is referred to correctly and efficiently perform the requested tasks; ii) the honesty involves the absence of malicious behaviours; iii) the security means the capability to manage private data avoiding their unauthorized access; iv) the reliability is assumed as the degree of reliance assigned on the provided services (e.g., the reliability of an e-Commerce agent is different if the price of the transaction if low enough or is very high).

However, reliability is an individual trust measure, while for the whole community the trust is measured by the reputation, that is fundamental to decide if an agent is a reliable interlocutor or not in absence of sufficient knowledge about it.

To use reliability and reputation measures in MASs, a main issue is represented by the possibility of suitably combining them to support agents' decisions. Indeed, when an agent a has to choose a possible partner, it exploits its reliability model based on its past interactions with other agents. Besides, a usually interacted with a subset of the whole agent community and often its past interactions with an agent are insufficient to obtain a representative trust measure. Thus a should consider also a reputation measure deriving by a reputation model. If for each candidate both reliability and reputation measures are combined in a synthetic preference score, then a could use it to choose its best partner. In this case, the main question is "How much the user should weight the reliability with respect to the reputation?". For answering to this question, authors in [10] proposed a reliability-reputation model, called RRAF, but it has two main limitations, namely:

• The weight assigned to the reliability vs reputation is arbitrarily set by the user based only on his/her experience without considering the system evolution (i.e., it does not give relevance to the reliability changes due, for instance, to new information acquired about the other agents and to the increased expertise level about the domain of interest). • In RRAF, the trust measures perceived from each agent about the other agents are not dependent among them. Indeed, let a and c are two agents that desire a trust opinion about the agent b. The agent a (resp., c) composes its trust opinion τ ab (resp., τ cb ) requiring to the agent c (resp., a) its opinion about b. It is reasonable that τ cb (resp., τ ab ) represents that opinion. This shows the dependence between the trust measures τ ab and τ cb . RRAF operates by considering the opinion that c provides to a about b (and vice versa) as a personal suggestion, not necessarily coinciding with τ cb . A more accurate computation should consider these suggestions as coinciding with the trust measures that each agent has on the other agents but this implies to solve the mathematical relationship existing among all the trust measures.

To solve the two problems highlighted above a new trust model, called Trust-Reliability-Reputation (TRR), is proposed in this paper. For each agent this model builds a global trust evaluation merging both the agent's reliability and reputation measures in a single score (as in RRAF) but without the use of a fixed parameter to weight them (differently from RRAF). Instead, when the agent a computes the trust in another agent b, in TRR the weight representing the relevance given by a to the reliability with respect to the reputation is dynamically computed. This weight depends on the number of interactions performed between a and b and the expertise of a in evaluating b. Moreover, TRR introduces a novel mechanism for computing the reputation where, differently from RRAF, the reputation perceived by an agent a about another agent b is based on the global trust that each other agent of the MAS has in b. This way, the overall trust measures are reciprocally correlated and we argue that they are more accurate than in RRAF because the agent that is computing a trust measure receives by the other agents suggestions that are their actual trust measures instead of "arbitrary" values. Two considerations has to be carried out about this latter issue: i) Our method of computing trust is applicable in MASs in which the agents are collaborative and share their trust measures with each other; ii) In order to apply TRR, each agent has to solve a linear system, instead of the simple computation required by the RRAF model.

To evaluate the performances of TRR with respect to RRAF some test have been executed on the well known ART testbed [3]. The experimental results show a significant advantage, in terms of performances, introduced by TRR, while the reduction of the agent efficiency, due to a more complex computation of the trust measures, is practically negligible.

The paper is organized as follows. In Section II some related work are discussed. The multi-agent scenario is presented in Section III, while Section IV deals with the TRR reliabilityreputation model. The Section V proposes an experimental comparison between RRAF and TRR on the ART Testbed and, finally, in Section VI some conclusions are drown.

II. RELATED WORK

In an open MAS trust-based approaches are available for determining the best partner to interact on the basis of information derived by both direct experiences (i.e., reliability) and opinions of others (i.e., reputation). However, each agent directly interacts only with a subset of the agent population and, therefore, it should exploit also the opinions of the other members of the community to have a reliable opinion about someone. Unfortunately, in a virtual environment some malicious behaviours are possible, encouraged also by the facility to change own identity. To limit them, it is important to have an adequate number of agent providing their opinions to avoid a partial depiction of agents' reputation [4] and preventing identity changes with some form of penalization and/or, for instance, by adopting a Public Key Infrastructure [18], [35].

In the literature a great number of metrics and approaches for measuring reliability and reputations have been proposed [9], [12], [15], [19]- [21], [24]- [26], [28], [30]. Some of them integrate reliability and reputation into a synthetic measure [2], [7], [13], [16] but leaving to the user the task of weighting the reliability with respect to the reputation. However, to compare such trust strategies and their computational costs in a competitive environment, the Agent Reputation and Trust (ART) testbed platform is avalaible [3]. In the following, the examined approaches will be those that, to the best of our knowledge, come closest to the material presented in this paper pointing out differences and similarities with our proposal.

Trust and reputation are represented in [33] by introducing a probabilistic reputation approach in the Ntropi model [1] that is truly decentralized without reliance on any third party and allows all the entities to freely decide how to trust. Reputation and experiential information are combined in Ntropi in a single trust measure exploited to decide if performing the interaction. An agent will rate this experience and will adjust its trust values based on the differences with the recommended ratings. In [33] a Dirichlet reputation algorithm [14] is added to the Ntropi model to set its parameters by using a Maximum Likelihood Estimation method on the observed data. Always for distributed MASs, in [11] is presented an approach made up of time steps that deals with uncertainty and ignorance and takes into account the number of interactions, data dispersion and variability. It computes trust based on three agent expectative, namely: past experiences with that agent (direct); advertisements received from that agent and discrepancies between experience and past advertisements (advertisements-based); recommendations received from others about that agent and discrepancies between experience and past recommendations (recommendations-based). A Global Trust measure aggregates the three components into a single belief referred to the next time step. The system has been tested on the ART testbed [3].

FIRE [13] is conceived for open MASs where agents are benevolent and honest in exchanging information. It considers more trust and reputation sources that in detail are: Interaction trust represented by the direct agent's experience; Role-based trust taking into account the agents' relationships; Witness reputation considering attestations about the behaviour of an agent; Certified reputation about an agent witnessed by thirdparty suggested by the agent itself. As a result, FIRE correctly works in many usual occurrences but it requires a lot of parameters to set on. REGRET [27] is a modular trust and reputation system for cooperative MASs exploiting impressions about other agents derived by both direct experiences (called direct trust) and a reputation model aggregating three type of reputation (i.e.: Witness, based on the information coming from witnesses; Neighborhood, calculated by using social relation; System, depending by roles and general properties). REGRET considers the witnesses' credibility and each agent can neglect one, more or all the reputation components. Finally, a common semantic, called ontological dimension, models the agents' personal points of view considering the multi-dimensional aspects of the reputation.

Within a grid context, in [32] the trust of both clients and providers is computed, using both direct and indirect information and removing biased feedbacks by using a rank correlation method. Direct trust is computed directly by the initiator and it is dominant on the indirect trust, measured by the feedbacks received from agents (in the same or other domains) and weighted based on their credibility determined on criterion as similarity, activity, specificity, etc. Moreover, the reputations of the client and provider are calculated on different parameters being their relationships asymmetric. In presence of uncertain and incomplete information a fuzzy approach can be used, as in [31] where the system collects and weights the opinions of each user about the other users to obtain aggregated trustworthiness scores. Social networks and probabilistic trust models are examined in [8] for different contexts and settings but authors conclude that in several scenarios these techniques exhibit unsatisfactory performances.

Trust has been particularly investigated for file sharing services over P2P networks [15], [19], [34]. In this context, the EigenTrust algorithm has been applied in [16], where each peer rates its transactions for building a trust representation of the other peers, called Local Trust. EigenTrust assumes trust transitivity in order to compute the Global Trust values. Each peer collects by the other peers their Local Trust values and, suitably weighted by means of the peer's trustworthiness, aggregated in a trust matrix in which the trust values asymptotically converge to its eigenvalues. The presence of pre-trusted users, always trusted, can minimize the influence of malicious peers performing collusive activities.

Nowadays, the opportunities given by the wireless technologies to work in mobile contexts, also in absence of stable connections, places great relevance in trusting the counterpart. For instance, Celltrust [18] manages direct and reputation information (suitably weighted) in a centralized manner by using cryptographic techniques. A Bayesian approach is used in [6], where reputation exploits a "second-hand" criterion in which transitive reputation is accepted only if it agrees with the direct rates. To contrast liars in Ad Hoc networks, in [22] is adopted a deviation test, independently of specific implementation, within a stochastic process but tests show that this model defects when the number of liars exceed a certain threshold.

The cited systems trust an agent by exploiting both direct experiences and information about its reputation within the community, as in TRR. In [1], [33] the trust in an agent is computed, as in TRR, only based on individual criterion but, for instance, in REGRET [27] a common ontology is adopted to uniform different trust representations and in [6], [16], [18], [22] trust is domain dependant. To cross malicious agents different strategies are adopted, TRR and [16], [18], [32] suitable weight the reputation sources and [16] exploits also peers always trusted, while in [1], [11], [33] are considered discrepancies between computed trust and observed behaviour to limit the effects of dishonest behaviours and, finally, other systems adopts a PKI approach (that is an orthogonal issue for many trust systems).

III. THE MULTI-AGENT COMMUNITY

In this section, it is described the TRR scenario. Let S be a list of service categories and let C be a software agent community, where each agent a ∈ C can require a service to each other agent b ∈ C that, in its turn, can either accept or reject the request. If the request is accepted and the service consumed then the agent a could evaluate its satisfaction and update its reliability model for b.

A. Reliability

The approach presented in this paper is independent from the particular reliability model chosen by each agent and each agent has its own reliability model, independently of the other agents. The reliability of the agent a with respect to the agent b and the service category γ ∈ S can be represented by the tuple ρ γ ab = ̺ γ ab , i γ ab , e γ , where:

• ̺ γ ab ∈ [0, 1]

is the reliability value that a gives to b referred to the services of the category γ, where ̺ ab = 0 (resp. 1) means that b is totally unreliable (resp., reliable).

• i γ ab is the number of interactions that a and b performed in the past with respect to the services of the category γ. • e γ ∈ [0, 1] is the expertise level that a assumes to have in evaluating the services of the category γ and that depends on the knowledge acquired by a about the category γ. In other words, the TRR approach does not assume that the reliability perceived from a about b is a simple scalar value, but for each category γ it is possible to have a different reliability. To this aim it also considers both the knowledge level that a has of b (represented by i γ ab ) in interactions associated with the category γ and the expertise level that a assumes to have about the services of the category γ (represented by e γ ).

B. Reputation

Let π γ ab be the reputation of b in the whole community as perceived by a and with respect to services belonging to the category γ. To obtain it, a should require to each other agent of the community an opinion about b in providing good services in the category γ. It is important to remark that in the TRR scenario more reputations of an agent b exist since each agent has it personal perception of the b's reputation. This way, the reputation π γ ab is a function (F ) of the set of opinions {o γ cb }, where o γ cb is the opinion that each agent c gives to a about b in providing good services of the category γ. Formally, it is:

π γ ab = F ({o γ cb })(1)

C. Trust

Let τ γ ab be the trust measure that an agent a assigns to another agent b in a given category γ. In the most of the approaches proposed in the past, this measure is obtained by combining in some way the reliability (ρ γ ab ) and the reputation (π γ ab ) measures for taking into account both the direct knowledge that a has about the b's capabilities and the suggestions that the other agents give to a about b. Some of these approaches also requires to specify a coefficient (that we call α) ranging in [0..1] that expresses the relevance assigned to the reliability with respect to the reputation. Vice versa the relevance of the reputation with respect to reliability will be given from 1 − α. In the past approaches, this coefficient α is arbitrarily fixed to a given value accordingly to the user's preference. Differently, we assume that α increases with: i) The number of interactions i γ ab , carried out by the agent a with the agent b for the category γ, since the direct knowledge of a improves when the number of interactions increases; ii) The expertise level e γ the agent a has about the category γ so that the more expert is the agent a and the more great will be its confidence in judging the b's capability and consequently computing the b's reliability. Our viewpoint defines the α coefficient as an α γ ab coefficient, to remark its dependance on the agents a and b and the category γ.

For evaluating a reasonable value for α γ ab , we propose to exploit a direct relationship with both the number of interactions i γ ab and the expertise e γ , such that α γ ab will be 1 only if a is completely expert about the category γ and the number of interaction i γ ab is higher than or equal to a suitable threshold N (set by the system administrator). If i γ ab is higher than or equal to N , the parameter α γ ab will be simply equal to e γ . Otherwise, if i γ ab is smaller than N , the parameter α γ ab will linearly depend on e γ and i γ ab . More formally:

α γ ab = e γ • i γ ab N if i γ ab < N e γ if i γ ab ≥ N (2)

Therefore, the trust measure can be generally expressed as a function G depending on the reliability, the reputation and the α γ ab coefficient:

τ γ ab = G(ρ γ ab , π γ ab , α γ ab )(3)

where:

α γ ab = α γ ab (i γ ab , e γ )(4)

D. An example of TRR model

The TRR scenario cover most of the past trust approaches. For instance, in the RRAF approach [10], the reliability ρ γ ab depends only by the value of ̺ γ ab , since the parameters i γ ab and e γ are not considered. The reliability is updated each time the agent b provides a service to a. To compute the new reliability value the measure of the satisfaction expressed by a for this service is averaged with the current reliability value. Moreover, the reputation π γ ab is obtained by a by requiring to all the other agents an opinion about b in providing services of the category γ and averaging them to compute the new value π γ ab . Finally, the trust value τ γ ab is computed as a weighted mean between reliability and reputation, where the reliability is weighted by a parameter α, set by the agent's owner, and the reputation is weighted by (1 − α). Note that in RRAF the parameter α does not depends on either the category γ or the agent b, but it is the same for all the agents and the categories.

IV. THE TRUST-REPUTATION-RELIABILITY MODEL

In this section, the functions F and G chosen to define the Trust-Reputation-reliability (TRR) model will be described. Fig. 1: The agent 1 evaluates the reputation of the agent 2 based on the suggestions of the agents 3, 4 and 5

A. Reputation in the TRR model

Let π γ ab be the reputation that in TRR an agent a assigns to another agent b for a given category γ. It is obtained as weighted mean of all the trust measures τ γ cb that each agent c (different from a and b) associates with b. In other words, the suggestion that each agent c gives of b to a is represented by the trust that c has in b. This suggestion coming from c is weighted by the trust measure τ γ ac that a has in c. Formally, the function F defined in the Equation 1 becomes:

π γ ab = c∈C−{a,b} τ γ cb • τ γ ac c∈C−{a,b} τ γ ac(5)

For instance, in Figure 1 it is depicted a scenario in which the agent 1 has to evaluate the reputation π 12 of the agent 2 (the category is omitted for simplicity). The agent 1 receives by the agents 3, 4 and 5 "suggestions" about the agent 2 (i.e., the trust that they assign to it) weighted by the agent 1 with the trust measure τ 13 , τ 14 and τ 15 that it assigns to the agents 3, 4 and 5, respectively. Thus, the weighted mean that gives the reputation assigned by the agent 1 to the agent 2 is: π 12 = (0.8 • 0.2 + 0.2 • 0.9 + 0.7 • 0.3)/(0.2 + 0.9 + 0.3) = 0.39

We remark that the high values suggested by the agents 3 and 5 (τ 32 =0.8 and τ 52 =0.7) have been marginally considered for the small trust that the agent 1 assigns to them, while the computed reputation is more similar to the suggestion given by the agent 4, to which the agent 1 assigns a high trust (τ 14 =0.9).

B. Trust in the TRR model

In order to compute the trust τ γ ab that the agent a assigns to the agent b in the category γ, we choose to use a weighted mean of the reliability value ̺ γ ab and the reputation value π γ ab , using the parameter α γ ab to weight the reliability value and (1 − α γ ab ) to weight the reputation. This way, the function G of the Equation 3 has the following form:

τ γ ab = α γ ab • ̺ γ ab + (1 − α γ ab ) • π γ ab(6)

and by considering the Equation 5 it becomes:

τ γ ab = α γ ab • ̺ γ ab + (1 − α γ ab ) • c∈C−{a,b} τ γ cb • τ γ ac c∈C−{a,b} τ γ ac(7)

This equation, written for all the n agents and all the m categories, respectively belonging to C and S, forms a system of m • n • (n − 1) linear equations, containing m • n • (n − 1) variables τ γ ab . This system is equivalent to that described in [5] and admits only one solution.

V. AN EXPERIMENTAL COMPARISON BETWEEN RRAF AND TRR In this section, we perform some experiments using the ART platform. On ART, each agent takes the role of an art appraiser who gives appraisals on paintings presented by its clients. In order to fulfill his appraisals, each agent can ask opinions to other agents. These agents are also in competition among them and thus, they may lie in order to fool opponents. The game is supervised by a simulator that runs in a synchronous and step by step manner, and it can be described as follows:

• The clients, simulated by the simulator, request opinions on paintings to the appraiser agents. Each painting belongs to an era. For each appraisal, an agent earns a given money amount that is stored in its bank amount BA.

• Each agent has a specific expertise level in each era, assigned by the simulator. The error made by an agent while appraising a painting depends on both this expertise and the price the appraiser decides to spend for that appraisal.

• An agent cannot appraise its paintings himself but he has to ask other agents to obtain opinions. Each opinion has a fixed cost for the agent. • Each agent can obtain recommendations about another agent by other players. Each recommendation has a given price. This way, the agent can build a reputation model of the other agents. • Agents weight each received opinion in order to compute the final evaluation of the paintings. • At the end of each step, the accuracy of agents final evaluations is compared to each other, in order to determine the client share for each agent during the next step. In other words, the most accurate agent receives more clients. • At the end of each step, the simulator reveals the real value of each painting, thus allowing each agent to update its reliability and reputation model. • At the end of the game, the winner of the competition is the agent having the highest bank amount BA. The purpose of our experiment is to analyze the improvements the TRR model introduces along the RRAF model. We have built two agents implementing the RRAF and TRR model respectively, and we have run some games in presence of different percentage of unreliable agents P . In particular, in the performed experiment 5 different agent populations characterized by a size of N = 100 agents and a different percentage P of unreliable agents have been considered. Namely, the 5 values of P we have considered are 10%, 30%, 50%, 70% and 90%. For each of these values, we have run an ART game, where the RRAF agent participates to each game using the parameter α = 0, 71. This value was chosen according to [10], where the RRAF agent obtained the maximum bank amount using α = 0, 71 at the same conditions. For each game, besides the RRAF and TRR agents, a population of 98 Simplet agents have run as competitors. Simplet agent is an agent that has participated to the 2008 ART Competition, and whose software can be downloaded at the ART site [3], and that uses a reliability-reputation model. We have programmed two different versions of Simplet agent:

• the former with a low availability to pay for the opinions, thus generating unreliable answers to the opinion requests. This low availability is represented by the internal ART parameter c g = 1.

• the latter with a high availability to pay for the opinions, thus characterized by the parameter c g = 15. Figure 2 reports the results of this experiment, in terms of variation of the bank amount BA of both the RRAF and TRR agents against the different percentage of unreliable agents P .

We note that, while the RRAF agent reaches its maximum bank amount for P = 50% as espected in [10], the performances decrease for other values of P . This is due to the following reasons: i) RRAF agent isn't able to recognize unreliable agents effectively, and ii) it incurs useless costs to ask recommendations when the population is reliable (P < 50%). Differently from the RRAF agent which has an α value that is fixed during the game for all the agents, TRR assigns a different α value for each era of each agent in the community, and also it is able to modify these values at each step of the game. This way, TRR gradually learns to recognize reliable agents thus saving recommendation costs. Moreover, in TRR the reliability is a function of also the number of interaction (i γ ab ) between trustor and trustee, and the expertise of the trustor (e γ ) in evaluating the services. As a consequence, TRR is able to better evaluate the reliability of the other agents thus obtaining more significant results in term of bank amount. Finally, Figure 2 shows that the performance of TRR are not influenced by the presence of unreliable agents.

VI. CONCLUSIONS

The large number of trust-based approaches in MASs emerged in the last recent years implies the necessity of clearly understanding what are the advantages and the limitations of using trust measures to improve the effectiveness of the systems. In particular, the two main measures considered in the literature, i.e. reliability and reputation, should be suitably combined to obtain a trust measure to support agent decisions.

In the past, we proposed a framework, called RRAF, to build competitive agents provided with an internal reliabilityreputation model, where the relevance of reliability with respect to reputation is given by a suitable parameter. However, RRAF introduces some simplifications in computing the trust, that affected the effectiveness of its practical application.

In this paper, it is proposed the TRR model to overcome the RRAF limitations. The TRR model i) dynamically computes the parameter representing the importance of the reliability with respect to the reputation, based on the evolution of the knowledge acquired by the agents in time, and ii) models the interdependence between the trust measures of the agents, considering that, when an agent a computes the trust measure about an agent b, the computation exploits the trust measures about b coming from each other agent of the community.

The TRR model has been tested by comparing it with RRAF on the standard testbed ART. The experimental results clearly shows a significant improvement introduced by ART in the effectiveness of the agent when computing the trust measures. We argue that such improvement is strictly related to the capability of the trust model in capturing the interdependence of the trust measures, highlighting the social aspect of the community in which the agents interact.

As for our ongoing research, we are developing more advanced studies about such social aspects. In particular, we plan to analyze how the characteristics of the agent population, e.g. the honesty, the competence, the privacy requirements etc., can be considered for designing a more accurate trust model.