A Reputation Management Approach for Resource Constrained Trustee Agents

1 Introduction

In environments that can be modeled as open multi-agent systems (ODMASs) (e.g., e-commerce systems, sensor networks, crowdsourcing systems), agents (both human and artificial) with diverse backgrounds may be self-interested and sometimes even malicious [Sabater and Sierra, 2005]. Agents in these ODMASs often need to rely on the services (e.g., expertise, resources) of other agents in order to achieve their goals. The interactions among agents, coupled with the uncertainty in other agents' behaviors, put their interest at risk. Throughout this paper, we refer to agents who provide services to other agents as trustee agents and agents who need to rely on them as truster agents.

Over the years, a number of computational models have been proposed to carry out trust management in these systems. In existing trust models, truster agents evaluate the interaction outcomes based on the quality of the results received. Usually, the timeliness of task completion is part of the quality metric [Jøsang et al., 2007; Yu et al., 2010]. A trustee's resources are assumed to be able to cope with the amount of requests effectively even as it becomes highly reputable (e.g., in a web-service system). Thus, existing trust models often direct truster agents to delegate tasks to the most reputable trustee agents they can find to improve the expected quality of the interaction results. Existing trust models are not specific on how trustee agents should respond to incoming requests. Since trustee agents are assumed not to be resource constrained, existing trust models expect them to accept all incoming requests (accept-when-requested) in order to maximize their own potential gain.

In applications where trustees are resource constrained (e.g., human workers in a crowdsourcing system, nodes in a sensor network), this approach may overwhelm reputable trustees with requests, causing long delays for trusters and subsequently causing them to give negative ratings to the trustees. In this case, the situation can be modeled as a congestion game [Monderer and Shapley, 1996] where the payoff for each truster depends not only on the trustworthiness of the trustees, but also on how many other trusters are delegating tasks to the same trustee as it is doing. Since the unsatisfied trusters may not be aware of other trusters' choices, they will negatively rate the performance of the trustee which is not fair to the trustee in this situation. This phenomenon has been shown in [Yu et al., 2012] to negatively affect the social welfare of the system.

To enable existing trust models to achieve good performance in ODMASs with resource constrained trustees, we propose a Distributed Request Acceptance approach for Fair utilization of Trustees (DRAFT). The basic idea of DRAFT is illustrated in Figure 1. It can be visualized as a set of control valves that enables each individual trustee agent to dynamically determine how many new interaction requests of different types of tasks should be accepted at each time step using its local knowledge about its own situation. Such decisions strike a balance between maximizing the potential reward for the trustee agent and minimizing the delay experienced by the requesting truster agents.

Theoretical analysis and extensive simulations demonstrated that DRAFT helps trustworthy trustee agents maintain good reputation values regardless of truster agents' choices for interaction partners. If all trustee agents adopt DRAFT, tasks can be allocated efficiently among trustee agents based on their reputation without the overhead of coordination among truster agents. The social welfare of an ODMAS can also be significantly enhanced compared to using the prevailing accept-when-requested approach.

2 Motivating Example and RelatedWork

The level of congestion in a trustee's pending task queues is determined by both the rate of arrival of task requests and the rate at which the trustee serves them. While the serving rate is out of the control of trust models, the arrival rate is affected by the Trust-aware Interaction Decision-making (TID) approach used. The most commonly used TID approach is a greedy approach - each truster selects the most reputable trustee it can find to serve its requests with a predetermined percentage of interactions reserved for trying out unfamiliar trustees [Jøsang and Ismail, 2002; Teacy et al., 2005; Weng et al., 2010].

Such an approach is employed by e-commerce systems such as Taobao.com. The sellers (trustees) on Taobao.com are mainly small and medium businesses which have limited resources in terms of staff and capital. Reputation is an important factor determining the amount of business for each seller on Taobao.com. As the competition among the sellers is fierce, sellers take their reputation very seriously and are generally reluctant to decline incoming orders. The situation is similar to the problem formulated in this paper. As recently in 2012, reports from China about over-worked sellers on Taobao.com dying of exhaustion have surfaced [Zhang, 2012]. The common features of such cases are: 1) the victims are young (in their 20s); 2) the e-shops under their management are highly reputable on Taobao.com; 3) they receive large number of orders; 4) their e-shops are small and medium sized enterprizes which require them to personally handle most business activities; and 5) they misjudged their capacity of serving incoming orders effectively. Although these are extreme cases, they demonstrate the importance of protecting the wellbeing of resource constrained trustees.

Motivated by these observations, we propose DRAFT in this paper. To the best of our knowledge, it is the first approach designed to help resource constrained trustee agents determine how to react to incoming task requests to protect their reputation through minimizing the delay experienced by trusters.

3 SystemModel with Resource Constrained Trustees

In this section, we formally define a system model in which trustee agents are resource constrained and the delays experienced by truster agents are partially due to their collective task delegation choices. In such a system, the trustee agents can be viewed as the base set of congestible resources. A truster agent's payoff is affected by which trustee agents it delegates tasks to and how many other truster agents are delegating tasks to the same set of trustee agents.

In a practical system, a trustee i may only be qualified to perform up to C different types of tasks. In computational trust literature, the trust evidence of a trustee agent i in serving different types of task requests are often kept separately (e.g., a trustee agent can have a high reputation in selling Tshirts but a low reputation in selling gloves, although it is able to sell both items). This is referred to as the context of the trust evidence evidence [Weng et al., 2010] and denoted as c ∈ (1, . . . ,C). The maximum utility for successfully completing one task of each type is represented by the vector ⃗G = (Gcmax ).The general effort (e.g., cost, physical or mental exertion) required to complete one task of each type is denoted as ⃗e = (ec ).The vector ⃗Qi(t) = (Qci (t)), Qci (t) = 0 represents the number of tasks stored in queues for different types of task of trustee i at the beginning of time step t. Due to resource constraints, i is able to expend an effort of up to emax i to serve the tasks in its task queues per time step. The value of emax i depends on an agent's ability and willingness and may differ from agent to agent.

Among the dimensions commonly used to evaluate the trustworthiness of a trustee agent, timeliness of serving requests is unique. It is affected not only by the ability and willingness of the trustee agent, but also by the collective task delegation decisions made by the truster agents. For each type of tasks, there is a generally accepted maximum elapse time represented by the vector ⃗ T = (T c ). The actual gain for i for completing a task depends on whether the result is rated successful by the requesting agent:

The interaction is deemed successful only if the result produced by i is correct and received by the requesting agent within the expected elapse time.

At each time step t, the incoming task requests received by i are denoted as ⃗λ(i) = (λci (t)).. The exact number depends on the collective task delegation decisions made by the truster agents in the ODMAS which may be influenced by i's reputation. The reputation of i in each context at any given time t, which can be assumed to be common knowledge, is represented by γ c i (t). As our focus in this paper is on decision-making by trustee agents, we do not discuss how i's reputation is evaluated. Instead, we assume the existence of a reputation model such as [Jøsang and Ismail, 2002] which produces γ c i (t) in the range of [0, 1] with 1 denoting completely trustworthy and 0 denoting not trustworthy at all.

4 The DRAFT Approach

The common goal of multi-agent trust models is to maximize the social welfare (which is the summation of utility derived from all interactions) in the system. We define a utility function uci (μ) to represent the utility derived by trustee agent i from completing μ tasks of type c. uci (μ) will be defined in later sections of this paper. Then, the social welfare of an ODMAS is the summation of uci (μ) over all i and c. When trustees are resource constrained, the optimization objective can be expressed as:

where the vector (μci (t)) denotes the actual number of tasks of each type completed by i at t. It depends on the availability of resource at trustee agent i's disposal as well as its trustworthiness.

In systems where emax i → ∞, Constraint (3) is redundant (i.e., trustees are not resource constrained). In this case, greedy task delegation decisions made by truster agents, combined with the accept-when-requested approach by trustee agents can maximize (2). However, under our system model, which is similar to a congestion game, the overall level of congestion in the system must be minimized in order to maximize (2). The queuing dynamic of Qci (t) is:

where Aci (t) is the number of new type c task requests accepted by i at time step t; μci (t) is the actual number of type c tasks completed by i during time step t. μci (t) is determined entirely at the discretion of i. The objective of DRAFT is to help i determine the appropriate value of Aci (t) at each time step t so that i would not be overwhelmed by incoming requests.

Although the decisions are made for individual trustees, DRAFT needs to ensure the collective decision also maximizes (2). In order to do so, the first challenge is to quantify the level of congestion in the system. We adopt the Lyapunov functions [Neely, 2010] to measure congestion. They are scalar functions which are easy to construct and interpret. Based on this concept, we define the overall level of task queue congestion in an ODMAS at any t as:

A small value of L(t) indicates that all Qci (t) are having a low level of congestion.

L(t) can be trivially minimized by making trustee agents reject all incoming requests and, therefore, keeping all Qci (t) = 0 for all the time. However, this is not a desirable mode of operation for any ODMAS. Instead, we want to limit the growth of the overall level of congestion while filling in spare capacities whenever they become available with new requests (if there are enough new requests from trusters). To tackle this challenge, DRAFT minimizes the Lyapunov drift [Neely, 2010] which is expressed as a conditional expectation:

where Q(t) = ( ⃗Q1(t), . . . , ⃗QC(t)).The smaller the value of Δ(t), the more efficient the utilization of the collective resources possessed by trustee agents.

Simply balancing the workload on trustee agents can produce small Δ(t) values. However, as trustees may have differing trustworthiness, such an approach gives no guarantee on the quality of the results produced. The reward that can be derived from delegating tasks to trustee agents following a given plan should be maximized.

DRAFT addresses this challenge by formulating a combined optimization objective as a reward-minus-drift expression:

ρ > 0 is a chosen constant that affects the relative emphasis given to the reward and the drift respectively.

reward(t) is defined as the total utility that can be derived from new tasks accepted by trustees at t. Since both reward(t) and Δ(t) partially depends on the behavior of the trustees which cannot be known with certainty, their values can only be estimated. The expected reward from a request acceptance decision can be expressed by:

In the long run, the actual utility gc i is related to the probability of i producing a correct result within the stipulated deadline. Although this probability cannot be definitively known, it can be approximated using i's reputation in performing each type of tasks which can be known by agents in a community including i itself. Therefore,

At each t, the Lyapunov drift Δ(t) is affected by the existing tasks in the task queues and the new tasks admitted into each queue. Thus, it can be estimated by the expressions:

Therefore, the optimization objective for DRAFT is:

By substituting (9) into (11), we have

Algorithm 1 DRAFT

Require: aci (t) values for all c in trustee agent i, the incoming requests λci (t) for all c at i, and emax i .

• 1: ei(t) = emax i

2: for each Qci (t) in i in descending order of its aci (t)

• 3: if aci (t) ec > 0 then

4:

5:

6:

if λci (t) · ec ⩽ ei(t) then

Aci (t) = λci (t)

else

7:

8:

Aci (t) = ⌊ ei(t)

end if

• 10: else

11: Aci (t) = 0

12: end if

• 13: end for

14: Reject unaccepted tasks

15: Return(Aci (t) for each Qci (t) in i)

ec do

where aci (t) = ρ · γ c i (t) · Gcmax - Qci (t) is defined as the availability score of each task queue of i at t. DRAFT helps a trustee agent come up with a task request acceptance plan (Aci (t)) about how many new tasks of different types it should accept at each time step based on an agent's current situation which is represented by the 3-tuple 〈(aci (t)), (λci (t)), emax i 〉. In order to maximize (14), DRAFT proceeds as illustrated in Algorithm 1. In essence, the higher the payoff per unit effort for a task τ c , the higher the reputation of i in performing tasks of type c, and the more spare capacity i currently has in accommodating more requests for performing tasks of type c, the more likely τ c will be accepted by DRAFT on behalf of i. In the case where not all incoming requests are accepted, DRAFT will inform the requesting trusters so that they can look for other alternatives.

5 Analysis

In this section, we envision a situation where all trustee agents in an ODMAS adopt DRAFT and analyze the impact on the size of the task queues and the social welfare.

Assume there are positive constants B, M and ρ such that the reward-minus-drift expression in (8) satisfies:

where U opt is the social welfare produced by the theoretical optimal solution for (11). Taking the expectations over the distribution of Q(t) on both sides of (15), we have:

which holds for all time steps t. Summing both sides over

ec ⌋

t ∈ {0, 1, . . . , T - 1}, we have:

Since uci (·) ⩾ 0 and L(·) ⩾ 0, and suppose the potential utility reward for completing Aci (t) tasks are bounded by ∑i,c uci (Aci (t)) ⩽ Gmax (where Gmax = ∑i,c [Aci (t)·Gcmax ] can be achieved when all new tasks are completed successfully within their respective deadlines), by re-arranging the terms in (17) and dividing both sides by TM, the upper bound on the sizes of the task queues in the MAS is:

Similarly, by rearranging (17) and dividing both sides by Tρ, the lower bound on the social welfare produced by agents in the MAS is:

From the above analysis, it can be deduced that if the condition in (15) can be fulfilled (which can be done through careful choice of the values for B, M and ρ), then, based on (18), a theoretical upper bound exists for all pending request queues for all trustee agents over the long run if the agents follow the recommendations made by DRAFT. This ensures that the request queue lengths will not keep on increasing and the trustee agents always can stop the growth of their request queues so their perceived quality of service can be maintained.

In addition, based on (19), the time averaged social welfare achieved in a given ODMAS through DRAFT can approach that achieved by the theoretical optimal solution within B/ρ in the long run. By increasing ρ, the social welfare produced by DRAFT can be made closer to the optimal social welfare. However, increasing ρ also causes the upper bound to the pending request queue lengths to rise according to (18), thereby increasing the expected time taken to complete a request. Due to the physical limitations of the trustees in a realistic system, if the increase in the value of ρ causes the expected completion time of tasks to start exceeding the stipulated deadlines, social welfare will start to decrease as the trusters' level of satisfaction decreases. Setting the value of ρ arbitrarily high will not make the social welfare produced by DRAFT be indefinitely close the optimal. Thus, the trade-off between quality and the timeliness in receiving services only exists within a limited range of the ρ value. The actual range depends on the physical limitations of the trustees in each given system. On the other hand, in an ODMAS where trustee agents adopt the accept-when-requested approach, these upper and lower bounds cannot be guaranteed.

6 Empirical Evaluation

As the problem in this study is relatively new, there is no existing dataset that can be used to evaluate DRAFT. In addition, real world data are useful for designing a realistic experiment environment, but the behavior patterns of the trustees are fixed for which we do not have ground truth. In order to comprehensively evaluate DRAFT under different circumstances, and to provide more flexible control of trustee agents' behavior, we implement it within a simulated ODMAS environment based on our system model. Our hypotheses in this section are:

• Hypothesis 1: A trustworthy trustee agent can better mitigate the adverse effect of reputation damage by using the DRAFT approach than using the accept-whenrequested approach.
• Hypothesis 2: The social welfare of an ODMAS can be improved through the use of the DRAFT approach.

6.1 Experiment Design

The trustee agent population consists of 100 agents belonging to four groups with different behavior patterns in our experiments. They are labeled as:

1. Hon: honest trustee agents who return high quality task results randomly 90% of the time on average;
2. MH: moderately honest trustee agents who return high quality task results randomly 70% of the time on average;
3. MM: moderately malicious trustee agents who return high quality task results randomly 30% of the time on average;
4. Mal: malicious trustee agents who return high quality task results randomly 10% of the time on average.

The number of them adopting each of the four different behavior patterns is varied in each experiment to simulate different trustee agent population configurations. A trustee agent population configuration is denoted as HonX. It represents a trustee agent population consisting of X/2% Hon trustee agents, X/2%MH trustee agents, (100-X)/2%MM trustee agents, and (100 - X)/2% Mal trustee agents. The average maximum effort each type of trustee agents can expend per time step is shown in Table 1. More trustworthy trustee agents can complete less number of tasks in each time step than less trustworthy ones in order to maintain the quality of their work.

Five categories of tasks are available for trustee agents to serve. Their properties used in the experiments are listed in Table 2. 1,000 truster agents equipped with the Beta Reputation System (BRS) [Jøsang and Ismail, 2002] for evaluating the reputations of the trustee agents are included in the simulation. Each truster agent randomly use 15% of its time for exploration while spending the rest of the time exploiting known reputable trustee agents. During exploitation rounds, truster agents require a trustee agent to have a reputation of over 2/3 in order to consider it as a candidate. At each time step, a number of requests for each type of task are sent out to the trustee agents based on their reputations by the truster agents (assuming truster agents do not intentionally distort their reputation ratings about the trustee agents). The average aggregate workload in the system is similar to that in the Amazon's Mechanical Turk crowdsourcing system as reported in [Ipeirotis, 2010] and [Ross et al., 2010]

Two simulated ODMASs are run in parallel. In one of them, the trustee agents adopt the traditional accept-whenrequested approach for handling incoming task requests. In the other, the trustee agents adopt the proposed DRAFT approach for handling incoming task requests. The results from these two sets of experiments are labeled as TRD and DRAFT respectively in the following figures. If no trustee agent is willing to accept a task request under DRAFT in a particular time step, the truster agent will attempt to propose the same task in the following time steps. Each simulation is run for 1,000 time steps and is repeated 10 times to reduce the effect of random variations.

6.2 Analysis of Results

Hypothesis 1

Figure 2 shows a snapshot of the change in the reputation evaluation of a trustee agent i which belongs to the Hon group (the ground truth trustworthiness is 0.9) over 500 time steps under both TRD and DRAFT. It can be seen that under TRD, the agent's reputation fluctuates significantly. The sequence of event is: during earlier phase of interactions, i was discovered by a few truster agents through exploration and its good performance had gained it a high reputation (about 0.8) compared to other trustee agents. This attracted many other truster agents to request i's services. The sudden influx of requests to i resulted in long backlog in its task queues. Then, i kept working on these tasks and producing high quality results. However, as most of them were completed with long delays, it received a large number of negative ratings from unsatisfied truster agents and its reputation dropped to a very low level, indicating loss of trust from others. This happens without i changing its behavior. As its reputation dropped, the number of requests received by i also decreased. Over time, the backlog in i's task queues had gradually been worked off. After that, i's high quality service was rediscovered by a few truster agents through exploration. Then, a similar sequence of events occurred, causing another round of fluctuation in its reputation.

On the other hand, the reputation of i is closer to the ground truth under DRAFT than under TRD. By dynamically determining when to be greedy, i was protected from the adverse effect of reputation damage caused by truster agents seeking higher expected utility in an uncoordinated fashion.

Hypothesis 2

Overall, the social equity among the group of the most trustworthy trustee agents (Hon) can be gauged through the fairness index (FHon) [Jain et al., 1984; Yu et al., 2012]. If FHon = 1 (perfect equality), all Hon trustee agents complete exactly equal number of tasks; if FHon = 0 (most unfair), one trustee agent completes all the tasks and all others complete no task.

From Figure 3(a), it can be shown that FHon under DRAFT is consistently close to 1 (its value varies between 0.996 and 0.999), whereas FHon under TRD fluctuates erratically over different trustee agent population configurations. Although in some cases, TRD can also lead to a highly fair distribution of tasks among trustee agents. However, such performance cannot be consistently achieved.

A snapshot of the percentage of all tasks delegated to trustee agents under agent population configuration Hon50 is shown in Figure 3(b). Under TRD, clear peaks representing high concentration of tasks on a few trustee agents can be seen; whereas the distribution of tasks is smoother under DRAFT which represents more efficient utilization of the trustee agents' capacities. In addition, DRAFT helps an ODMAS ensure that: 1) more trustworthy agents receive more tasks than less trustworthy ones, and 2) similarly trustworthy agents receive similar amounts of tasks.

Figure 3(c) shows the time averaged social welfare achieved by given trustee agent populations under TRD and DRAFT. By reducing the adverse effect of reputation damage through efficient utilization of trustee agents' capacities, the ODMAS equipped DRAFT consistently achieved significantly higher social welfare than the ODMAS with trustee agents use the traditional accept-when-requested approach.

7 Conclusions

In this paper, we propose DRAFT to enable trustee agents to manage their own reputation through situation-aware management of their workloads. With DRAFT, individual trustee agents can benefit from less fluctuation in their reputation values and more equitable access to task requests from truster agents. Opportunities are passed up by trustee agents who are busy and picked up by agents who have more spare capacities while taking into account of their reputation. Thus, the collective capacity of the trustee agent population can be efficiently utilized which increases the social welfare of the ODMAS over the long run.

As DRAFT can complement existing trust models without requiring them to be modified, it can be easily incorporated into systems which already include trust management mechanisms. In this way, it enables a system and its members to reap the aforementioned benefits without truster agents having to significantly change their mode of operation or to incur extra costs for the underlying system to be modified. This makes it a potentially attractive option for deployed systems (e.g., e-commerce systems, crowdsourcing systems) to enhance user experience and overall system performance.

Acknowledgements

This research is supported in part by Interactive and Digital Media Programme Office (IDMPO), National Research Foundation (NRF) hosted at Media Development Authority (MDA) of Singapore under Grant No.: MDA/IDM/2012/8/82 VOL 01, and the National Natural Science Foundation of China (No.61202212).