Exchanging Reputation Information between Communities: A Payment-Function Approach

1 Introduction

Several researchers modeling trustworthiness of agents in multiagent systems have proposed the exchange of ratings of agents between peers, in a social network. This is especially useful in settings such as e-marketplaces, where a buying agent having little experience with a selling agent may ask other buyers for advice. One approach that has emerged is creating incentives for honesty when reputation ratings of agents are exchanged, in an effort to provide recipients with reliable information (e.g. [Jurca and Faltings, 2007; Miller et al., 2005]).

In this paper, we examine a similar but distinct problem: how to promote honest exchange of information about the reputation of agents, between communities. By community, we mean a collection of agents that co-exist for a specific purpose. A primary example would be a file sharing community, where agents representing users make decisions about what to upload or download for the community and the reputation of an agent in the community is a reflection of how valuable its contributions are, to the other members. Another example of communities include auction settings where agents are brought together to perform several business transactions over time. Our perspective is that the quality of services that

Robin Cohen

David R. Cheriton School of Computer Science University of Waterloo, Canada rcohen@uwaterloo.ca

a community offers is based on the collective contributions of its agents. It is therefore important for communities to make careful decisions when accepting agents; it is likewise beneficial to encourage agents to be good contributors, in their communities.

Since agents can migrate between, or be members of, multiple communities, how an agent behaves in one community is of interest to others. This is particularly true in situations where communities can decide whether or not to allow a particular agent to join. Thus mechanisms that allow communities to exchange reputation information about agents can improve communities in two important ways. First, community A can use information obtained from community B in order to decide whether to allow an agent to join. Second, if agents are aware that their reputation will follow them from one community to another, then they may have incentive to be better community citizens.

Since communities have their own interests, which may not align with others, they may not always be willing to exchange information about their members freely. There are a variety of reasons for this. For example, consider an agent which participates in an online auction community A in which it has an outstanding contribution. Assume now that this agent is interested in joining another online auction community B. If the agent joins community B it might have to provide part of its contribution that so far was exclusively provided to community A to the new community B. Given this potential loss of contribution, the community Amight be reluctant to truthfully reveal to B the contribution of the agent.

We leverage the fact that communities may be both buyers and sellers of information and construct a payment function that can be used to effectively provide sellers with appropriate payment for providing information.

The two main issues we are interested in addressing are:

1. how a community can be motivated to truthfully report its ratings and
2. how we can value the quality of the rating a community provides in order to compensate it with a fair payment.

As will be seen, we set our payment function to maximize the payment of a community only when it provides a truthful rating (for 1.) and introduce a set of properties a payment function should follow in order to promote honesty and fairness (for 2.), thus, providing an effective proposal for the exchange of reputation information between communities.

A key distinction that we make is between what we refer to as a good or a poor contributor. These are labels that correspond to the desirability for a community to accept or to reject the agent (the key decision-making that each community must undergo). The reputation information that is shared consists of both a rating and a type (good, poor). The community receiving the agent reputation explicitly evaluates the importance of this information. As will be shown, reputation information that leads to the correct decision about accepting or rejecting an agent leads to more lucrative payments to the sellers, thus promoting both honest reporting and fair payments. In Section 5 we return to clarify the distinction between communities sharing ratings of agents and current research where agents share ratings amongst themselves.

2 Model

Let Ci denote community i and let aj denote agent j. We assume that if aj is a member of community Ci then Ci can observe and judge the quality of agent aj. In particular, we assume that community Ci maintains a reputation model for all member agents, and is able to assign a reputation rating rij to agent aj, where rij is some real number from the interval [α, β], 0 ≤ α ≤ β.

If agent aj wishes to join community Ck, then before welcoming aj, community Ck will contact the communities in which aj is currently, or was previously, a member. We denote the set of these communities as S(aj). The communities in S(aj) are asked to provide two bits of information. First, each community Ci is asked to report rij , its reputation rating for agent aj . Since communities may use different reputation models, or may interpret ratings differently, communities are also requested to provide type information, θij , for agent j. We assume that θij ∈ {good, poor}, and that this is the interpretation that community Ci makes concerning its reputation rating rij for agent aj. 1

In exchange for information, community Ci receives a payment from community Ck. This payment, P , depends on how useful or important community Ck finds the information provided by Ci. If community Ck is interested in possibly welcoming agent aj, it will contact the communities in S(aj) to request information about the agent aj. Each community Ci ∈ S(aj) reports its reputation rating (rij ) and type information (θj i ) for agent aj, possibly misreporting the information.

Based on the information received from communities in S(aj), Ck decides whether to accept agent aj or to reject it. If Ck accepts agent aj then it gets to observe and evaluate aj. By doing so, Ck is able to assign both a rating, ˆ r, and a type, θk j to the agent. If communityCk decides to reject agent aj, then the payment procedure is a little more complicated since the community never gets the opportunity to directly observe and evaluate agent aj. Instead, community Ck sets the type of agent aj to be θk j = poor, and computes ˆ r to be the average reputation rating of all communities in S(aj) that also assigned type θij = poor. That is, if B = {i|i ∈ S(aj) and θij = poor} then:

1 For example, a rating 0.55 in one community could indicate an agent which is a poor contributor while in another community, which might be more strict in providing high ratings, the same rating might indicate an agent which is a good contributor.

Only after this decision is made do the communities in S(aj) get paid for the information that they provided. In particular, for each community Ci ∈ S(aj), the payment it receives for its information (rij and θij ) is

where ¯α ∈ R+ and ¯ β ∈ R are constants set by community Ck, and I(rij , ˆ r, θk j ) is the Importance Function used by community Ck to determine the usefulness of the reputation information provided by community Ci.

While the parameters ¯α and ¯ β are interesting in that community Ck can use them to scale the payments made to the other communities, the key part of the payment function is the Importance Function. The rest of this paper focuses on what this function should be, and what properties it should exhibit in order to create an effective payment scheme for exchanging reputation information between communities of agents.

3 The Importance Function

In this section we describe the basic desirable properties of the Importance Function (IMF). In the previous section we informally introduced IMF as I(rij , ˆ r, θk j ) where rij was the reputation rating given by community Ci, ˆ r was community Ck's (the community making the payment) reputation rating of the agent, and θk j was Ck's assigned type to the agent. We define I as I : R × R × {good, poor} → R such that I(x, ˆ r, θ) = -∞ if x < α or x > β for some predefined α, β ≥ 0. Because of this, a community Ci, reporting on agent aj is best off revealing a legal rating.

Our first desired property is that I is continuous when a legal reputation rating is given.

Property 1. Let α ≥ 0. In the restricted domain [α, β] × [α, β] × {good, poor}, I is continuous.

If the community accepts the agent, then it is able to observe and evaluate the agent, and thus determine its own reputation rating, ˆ r. When determining payments we desire that the communities that provided the more accurate information are rewarded. Consider the following example.

Example 1. Assume that community Ck requests information about agent aj . Assume that four communities submitted reputation ratings r1 j = 0.6, r2 j = 0.65, r3 j = 0.75 and r4 j = 0.8. After observing the agent, community Ck set ˆ r = 0.7.

We would like our importance function to reward the communities that submitted reputation ratings of 0.65 and 0.75 more than those that submitted 0.6 and 0.8, respectively. That is, we would like to capture the property that as x approaches ˆ r, the importance of x increases. Property 2 captures this.

Property 2. For any ˆ r ∈ [α, β] and for any θ ∈ {good, poor}, if x ∈ [α, ˆ r] then I(x, ˆ r, θ) is strictly monotonically increasing, and if x ∈ [ˆ r, β] then I(x, ˆ r, θ) is strictly monotonically decreasing.

Given Property 2, the IMF should reward communities C2 and C3 in Example 1 more than communities C1 and C4, respectively. We may want, however, to further distinguish between the information received from communities C2 and C3 since even though the reputation values were equally far from ˆ r, C2 stated that aj had a lower reputation than observed, while community C3 stated aj had a higher reputation than observed.

Define

for any ϵ ∈ (0,min[ˆ r - α, β - ˆ r]]. This measures the difference in the IMF value when communities over-report and under-report by the same amount. If δ(ˆ r, ϵ, θ) = 0 for all ϵ then the IMF would treat over- and under-reported reputation ratings equally. We believe that the IMF should be used to reward communities that provide ratings which deviate towards the correct direction (i.e. good or poor) higher than those communities who provided ratings of equal deviation but towards the wrong direction.

and

In words, Property 3 says that if Ck determines that the agent is a good agent, then communities who reported higher reputation ratings should be rewarded more than communities who reported lower reputation ratings, assuming that the difference from ˆ r is the same. A similar property should hold if Ck determined that the agent was poor. Referring back to Example 1, if Ck determined that θ = good, then community C3 should have a higher IMF value than C2, and C4 should have a higher IMF value than C1. If θ = poor, then C2 should have a higher IMF value than C3 and C1 should have a higher IMF value than C4.

Our last two desired properties describe how δ(ˆ r, ϵ, θ) should behave.

Property 4. For any ˆ r

• δ(ˆ r, ϵ, good) is strictly monotonically increasing in ϵ,
• δ(ˆ r, ϵ, poor) is strictly monotonically decreasing in ϵ.

We interpret Property 4 in that if an agent is judged to be good, then communities who submitted high reputation ratings for the agent deserve higher IMF values, since they were offering support for the agent (and vice-versa for the case when an agent is judged to be poor). Referring back to Example 1, if the agent was judged to be good, then community C4 would receive the highest IMF value, whereas if the agent was judged to be poor, then community C1 would receive the highest IMF value.

Property 5. For any ϵ ∈ (0,min[ˆ r - α, β - ˆ r]] and for any θ ∈ {poor, good}, δ(ˆ r, ϵ, θ) is monotonically decreasing in ˆ r.

Property 5 states that a given deviation ϵ has different significance for different values of ˆ r. For instance, if the agent's type is judged to be good then the significance of a deviation ϵ increases as the reported rating ˆ r decreases. This is due to the fact that as ˆ r decreases the rating ˆ r - ϵ might be crossing the cutoff ¯ r value that a community considers in order to accept an agent or not. In particular, the further the rating ˆ r - ϵ crosses ¯ r the more in doubt it can put a community regarding the agent's real value. Analogous, is the case where the agent's type is judged to be poor.

3.1 Importance Function and Payments

The Importance function (IMF) forms the foundation of our payment system, and thus the properties of the IMF have a profound influence on the properties of the payments, and the incentives for communities to report their reputation ratings and type information when requested.

We first note that if the IMF satisfies Properties 1 and 2, then it is uniquely maximized when communities report ˆ r (i.e. I(ˆ r, ˆ r, θ) is the global maximum). Since the payment a community receives is an affine transformation of the IMF, a community has incentive to report the reputation rating that it truly believes Ck will experience if Ck accepts the agent.

We introduce Properties 3 through 5 so as to ensure a certain level of fairness in the system. While the communities who present the most accurate information to community Ck benefit the most from the IMF, communities, which provide information that tried to convince community Ck to make the appropriate decision with respect to the agent, are also well rewarded payment-wise.

4 AClass of Importance Functions

In the previous section we outlined the desireable properties for an IMF. The obvious question is then Does there exist any functions which could be used as IMFs? In this section we introduce a class of functions that satisfy Properties 1 to 4, and that contains a subclass which satisfies Property 5.

Let φ : [α, β] → R+ and ψ : [α, β] → R+ be arbitrary continuous functions on [α, β]. Let φ be strictly monotonically decreasing and let ψ by strictly monotonically increasing. Now, define IMF I(x, ˆ r, θ) as

We now show that for any choice of ψ and φ, I(x, ˆ r, θ) satisfies Properties 1 to 4. Later we show that for particular choices of φ and ψ it is possible to also satisfy Property 5.

First, since both φ and ψ are continuous on [α, β], then I(x, ˆ r, θ) is also continuous on the restricted domain [α, β] × [α, β]×{good, poor}. That is, I(x, ˆ r, θ) satisfies Property 1.

As the x approaches ˆ r from the left the area that is defined by | ∫ ˆ r x φ(y)dy| is strictly decreasing. Consequently, I(x, ˆ r, θ) is strictly increasing in [a, ˆ r]. As the x goes away from ˆ r then the area that is defined by the | ∫ x ˆ r φ(y)dy| is strictly increasing. Thus, I(x, ˆ r, θ) is strictly decreasing in [ˆ r, β]. Similarly, it can be proved that the function ψ satisfies Property 2 as well.

Property 3 is also satisfied. We can rewrite δ(ˆ r, ϵ, θ) as:

We show the case for θ = good since the case when θ = poor is analogous. Given that ˆ r ∈ [α, β] and φ is strictly monotonically decreasing and positive in [α, β],:

Thus:

Regarding Property 4 we need to show that the partial derivative of δ(ˆ r, ϵ, θ) with respect to ϵ is greater than zero for θ = good and less than zero for θ = poor, where

Given that φ and ψ are strictly monotonically increasing and strictly monotonically decreasing, respectively, and ˆ r ∈ [α, β], where β > α ≥ 0, and ϵ ∈ (0,min[ˆ r - α, β - ˆ r]]: φ(ˆ r + ϵ) < φ(ˆ r - ϵ) and ψ(ˆ r - ϵ) < ψ(ˆ r + ϵ). Thus:

Finally, Property 5 is also satisfied by (2) if:

for ∀ˆ r ∈ [α, β], where β > α ≥ 0, and ∀ϵ ∈ (0,min[ˆ r - α, β - ˆ r]]. More specifically, we need to prove that the partial derivatives of δ(ˆ r, ϵ, θ) with respect to ˆ r are less than or equal to zero. This is true if (4) holds, given that:

Thus, if φ and ψ satisfy inequalities (4) then Property 5 is also satisfied.

Proposition 1 states that certain linear transformations of the functions φ and ψ can be also used to create an IMF.

Proposition 1. Let φ : [α, β] → R+ and ψ : [α, β] → R+ be arbitrary continuous functions on [α, β], β > α ≥ 0. Let φ be strictly monotonically decreasing and let ψ by strictly monotonically increasing in [α, β], and:

for ∀ˆ r ∈ [α, β] and ∀ϵ ∈ (0, min[ˆ r-α, β-ˆ r]]. The function:

where Φ(y) = λ1 ∗ φ(y) + λ2, Ψ(y) = κ1 ∗ ψ(y) + κ2, λ1, κ1 ∈ R+, λ2, κ2 ∈ R and Φ(y), Ψ(y) ≥ 0 in [α, β], is a valid IMF which satisfies Properties 1 to 5.

Due to its simplicity and space limitations the proof is omitted.

4.1 Examples

In this section we introduce two examples of an IMF. Let φ(y) = (β - y)n and ψ(y) = ym. Then:

where x, ˆ r ∈ [α, β], β > α ≥ 0, and n,m ∈ N+. An example of φ(y) with β = 0.8 and n = 2 is depicted in Figure 1.

Since φ and ψ are continuous, positive and strictly monotonically decreasing and strictly monotonically increasing, respectively (as can be seen by a simple check of the first and second derivatives), I(x, ˆ r, θ) satisfies Properties 1 to Property 4. In order to prove that I(x, ˆ r, θ) also satisfies Property 5 it is sufficient to prove that

and

for ∀ˆ r ∈ [α, β] and ∀ϵ ∈ (0,min[ˆ r - α, β - ˆ r]]. Inequality (5) can be proved by induction. More specifically:

For n = 0, we have

Assume that it is true for n = k:

we will prove that it is also true for n = k + 1:

Inequality (8) is true as it is the summation of two negative numbers. Similarly, inequality (6) can be proved.

In the second example we consider φ(y) = (β-y)n e(β-y) and ψ(y) = ymey . In this case the IMF (2) will become:

An example of φ for β = 0.8 and n = 2 is depicted in Figure 1.

Similarly with the first example, since φ and ψ are continuous, positive, and strictly monotonically decreasing and strictly monotonically increasing respectively (as can be seen by a simple check of the first and second derivatives), I(x, ˆ r, θ) satisfies Properties 1 to 4.

As in the case of the first family, in order to prove that IMF (9) also satisfies Property 5 it is sufficient to show that ∀n, m ∈ N, ∀ˆ r ∈ [α, β] and ∀ϵ ∈ (0, min[ˆ r - α, β - ˆ r]]:

and

Consider the case where θ = poor. We will prove that inequality (11) is true by induction (similarly inequality (10) can be proved). 2 For m = 0 we have: 2 - eϵ - e-ϵ which is clearly less or equal to zero. For m = 1 we have:

which is true since it is the summation of two negative numbers. Assume now that (11) is true for m = k:

We will prove that it is also true for m = k + 1.

which is true since it is the summation of two negative numbers. Consequently, the inequality (11) holds for ∀m ∈ N.

Choosing φ and ψ

In order to find the most suitable instances of the above families of functions a number of different criteria could be used. For example, one criterion is bounding the maximum value of δ(ˆ r, ϵ, θ).

More specifically, consider the case of θ = good, a criterion could be to choose the function φ in such a way that the maximum value of the δ(ˆ r, ϵ, θ) (which essentially defines the maximum difference of the IMF value two ratings of equal deviation can have) is bounded by U and L, where U,L ∈ R+, in order to avoid over-penalizing communities that under-reported the rating of an agent. A simple way of finding φ and ψ that satisfy the following bounds:

in an interval [w1,w2], where U,L,w1,w2 ∈ R+ and U ′ , L′ ∈ R- is presented in Proposition 2.

Proposition 2. Given an upper bound U and a lower bound L finding the function φ such that for ∀ϵ ∈ (0,min[w2 - ˆ r, ˆ r - w1]] and ∀ˆ r ∈ [w1, w2]:

2 Given that er > 0 we can omit it.

is equivalent to finding the function φ such that:

where ϵ = min[w2 - ˆ r, ˆ r - w1], and x is the solution to: I (ˆ r + ϵ, ˆ r, good) = I(x, ˆ r, good). While finding the function ψ that for ∀ϵ ∈ (0,min[w2 - ˆ r, ˆ r - w1]] and ∀ˆ r ∈ [w1, w2]

is equivalent to finding the function ψ such that:

where ϵ = min[w2 - ˆ r, ˆ r - w1], and x is the solution to: I (ˆ r - ϵ, ˆ r, poor) = I(x, ˆ r, poor).

Proof. Consider the case where θ = good. 3 Given that δ(ˆ r, ϵ, good) is monotonically increasing in ϵ: i) it is maximized when ϵ = min[ˆ r - w1, w2 - ˆ r], and ii) there will be a x ∈ (ˆ r - ϵ, ˆ r) such that I(x, ˆ r, good) = I(ˆ r + ϵ, ˆ r, good). Thus, we can write δ(ˆ r, ϵ, θ) as:

Essentially, Proposition 2 states that in order to find a φ that leads to an δ(ˆ r, ϵ, θ) whose maximum value is between two bounds L and U, we just have to find a φ such that:

where ϵ = min[w2 - ˆ r, ˆ r - w1], and x is the solution to: I (ˆ r + ϵ, ˆ r, good) = I(x, ˆ r, good). Analogous is the case for the function ψ.

5 Discussion &FutureWork

In this paper we present a payment function approach to promote honest exchange of information about the reputation of agents, between communities. Our payment function is motivated by the work on scoring rules [Savage, 1971]: a framework for eliciting probabilistic information from agents. We differ from the formal definition of scoring rules in that we determine a value based on the community's declarations, whether the information was judged to be good or not (a binary event) and how it relates to the judging agent's valuation (a continuous variable), while scoring rules typically are either concerned with binary events or continuous settings, but not both [Zohar and Rosenschein, 2008]. We still retain the salient features of scoring rules, such as incentive compatibility.

Other authors have investigated the use of incentive mechanisms in order to promote trustworthiness when reporting about agents in multiagent systems [Jurca and Faltings, 2003; 2007; Miller et al., 2005]. Jurca and Faltings offer a side payment mechanism and proves that rational software agents under this mechanismwill truthfully share their reputation information [Jurca and Faltings, 2003]. They further examine how to discourage collusion among the reporting agents [Jurca and Faltings, 2007]. Miller et al. offer a somewhat different kind of incentive mechanism with scores kept in a central location, but is also able to demonstrate that this mechanism is incentive-compatible, creating an equilibrium under certain well-defined conditions [Miller et al., 2005]. Our approach is to also create incentives for honesty but for the case of communities sharing information with other communities and doing so by carefully determining an appropriate payment for information. As a result, it is possible to reward reports that assist the buying communities most effectively (getting these communities closer to the end result of enjoying agents that are good contributors).

3 The proof for θ = poor is analogous.

Unlike other proposed approaches for sharing reputation information that focus primarily on learning how to judge the trustworthiness of the sender, to then discount or disregard reputation ratings that are received [Jurca and Faltings, 2003; Teacy et al., 2006], in our approach we require both type and rating information to be provided and are capable of coping with subjective differences in the way the ratings are calculated. Another approach that aims to explore subjective differences was proposed by Regan et al. [Regan et al., 2006]. They presented a Bayesian-based approach to learn the evaluation function of an agent providing a rating, in order to make use of the information received. In our work we focus on determining the rewards that each community should receive with respect to the quality of the information it provided. A key contribution of our work therefore is that it promotes truthful reports and distributes the payments in a fair manner. Our next step is to take advantage of methods such as those proposed by Regan et al. [Regan et al., 2006], as part of our effort to learn the behaviour of the selling communities and interpret the information that is received.

In our current approach the reputation of the agents is part of the information that it is being exchanged between the communities. Other multiagent researchers have also relied on exchanging reputation ratings [Dellarocas, 2001; Teacy et al., 2006; Ismail and Josang, 2002], although in those cases the exchange of the ratings is between agents. 4 However, a limitation with a reputation rating for the case of communities is that it is highly related to the particular needs of the community. For example, a trustful agent might have low reputation inside a community because although it is willing to contribute, there is no current interest in the services it offers or simply the services it offers do not mesh with the needs of the community. On the other hand a malicious agent can temporarily create a good reputation and then become deceptive in the future, once it has been accepted in another community. An effective reputation system should be able to ensure minimal impact when the second problem occurs but it may not be able to cope with the case of a low reputation simply due to current lack of demand or due to incompatibility of services. Thus, there is a need to find a more comprehensive metric for evaluating an agent. One way we suggest is to consider the trustworthiness of an agent as the extent to which the agent is honest and contributes good quality information or services and is an active and consistent participant. Ultimately, our aim is to integrate a model for the trustworthiness of agents, as part of the buying community's reasoning about accepting agents.

4 Note that our approach could also be used for individual agents.

In conclusion, in this paper we present the properties of a payment function which compensates the participant communities with respect to the importance of the provided information, and then we provide examples of specific families of functions that can be used. Finally, we give directions of possible criteria in selecting a specific instance of the latter families. We also offer an original proposal for exchanging reputation information, consisting of both a rating and a type, allowing the value of information received to affect the evaluation and hence the rewarding of the community providing the information. As such, we demonstrate the value of a payment function approach for exchanging reputation information between communities.