Policies for role maintenance through incentives: how to keep agents on track

Policies for role maintenance through incentives: how to keep agents on track Henrique Lopes Cardoso1, Ram´on Hermoso2, and Maria Fasli2 1LIACC / DEI, Faculdade de Engenharia, Universidade do Porto, Portugal [email protected] 2School of Computer Science and Electronic Engineering, University of Essex, UK {rhermoso, mfasli}@essex.ac.uk Abstract. Roles are usually seen as a descriptive concept that agents adopt so showing expectation on its future interacting behaviour. These expectations, so called standards, may be used to articulate contracts among partners in environments dealing with uncertainty. However, few work has been done in the field of multi-agent systems addressing the evolving nature of roles, especially in open systems, in which changes in the population should bring about changes in the way expectations are assessed. In this paper, we put forward a mechanism to search for appropriate incentives aiming to keep agents fulfilling the expectations generated by the roles they play. Furthermore, we also present role evolution policies that allow the system to re-arrange role players when incentives are not effective. We present some empirical results supporting our approach. 1 Introduction In open multi-agent systems, heterogeneous agents may enter and leave at will and exhibit self-interested behaviours while interacting with others. Commitments, as a means to make interactions more predictable, may be jeopardized by the dynamic nature of the environment: when facing new circumstances, if agents are not sufficiently socially concerned, they may value their private goals more highly than the commitments they previously established. In general, in open systems we cannot ensure that participants will behave consistently over time either because of their ability or willingness. The primary objective for agents to operate in such environments is to achieve their design objectives and goals. In some cases, an agent may not be capable of maintaining a certain standard of behaviour throughout its lifetime. In other cases, an agent may deviate from its previous and typical behaviour either intentionally, or because its objectives and goals have changed, and hence, this needs to be reflected in the actions taken or in extreme cases because of underlying errors in its program. Therefore in the context of open environments, it is important to take into account the evolution of an agent’s internal goals, motivations and preferences and even skills and abilities, in addition to the dynamics of the interaction environment as a whole. We adopt the notion of role given by Hermoso et al. in [4]: roles are described as expectations over a set of tasks. In the same work, a role evolution mechanism is presented to enhance partner selection for task delegation purposes. That approach is based on examining the agent society and identifying “run-time roles” – so building a role taxonomy – that cluster agents with similar skill patterns for a certain (set of) task(s). From this perspective, a mechanism allows identifying the role that labels the agents most suitable to perform a specific task. In previous work [5], we have proposed a model to transform these runtime roles into standards that agents may commit to. Given the evolving nature of open environments and inherent uncertainty in agent behaviour as pointed out above, the problem faced by the organization in which agents have been (artificially) embedded is that of accurateness: this translates to the need to assess whether agents originally designated as capable of enacting certain roles are still up to the challenge. If they are not, one may choose to reorganize and assign new roles to them according to their up-to-date performance. If, however, this reorganization involves a non-trivial cost, another potentially less costly approach is to influence the agents’ decision making through incentives in an attempt to keep them on track. The goal of this paper is to explore these two approaches when addressing the problem of role maintenance. The rest of the paper is structured as follows. Section 2 provides some preliminary definitions in which our model is based, namely roles and standards. Section 3 explains the decision making of agents that are seen as playing roles identified by the system and introduces the notion of incentive schedule. Section 4 proposes two different policies to maintain roles. An incentive-based policy implementing a local search procedure tries to find which incentive schedules should be applied in order to maintain role quality. Reorganization is imposed when incentives are not cost-effective. We present some empirical results in Section 5. The paper closes with the conclusions in Section 6. 2 Background The rationale behind creating and maintaining performance standards relies on the concept of role proposed by Hermoso et al. [4]. In this work, the authors claim that in a society of agents, social relationships may evolve, so roles – defining the positions of agents in terms of skills and importance as perceived by others – should also do. A society of agents may be covered by an overlay role taxonomy formed by extracting capacities and trust relationships among agents over time. In particular, the authors show an approach for a coordination mechanism for Task-oriented MAS (T-MAS) in which agents may interact with others by delegating certain tasks. The authors assume that agents participating in the system are rational, that is, they behave as utility maximisers. Thus, the main task of the mechanism is twofold: i) to capture similar behaviour among participants that play a role; and ii) to manage the role taxonomy that structures different positions of agents in the system. The mechanism uses a K-Means clustering algorithm to identify patterns of behaviour, so distinguishing those agents out- performing others and, consequently, being more trusted by the participants. This mechanism has been exhaustively tested in different conditions. This paper addresses the problem of how to maintain the agents’ performance on the level of quality determined by the roles they are playing. In order to take this step, we need to move from roles as expectations of behaviour [10] to the explicit handling of such expectations as conventions and further as norms [2] that can be committed to. In other words, we need to transform information about role specialisations into performance standards that agents could use to estimate interaction outcomes. In order to do that, we adhere to the definition of standard given in previous work [5]. Standards emerge from the notion of task specialisation as an aggregate level of performance that agents playing a role have shown to achieve in past interactions. 3 Dynamics In this section, we introduce the decision making apparatus that agents use when executing tasks. Our approach is based on the well known principal-agent model [7, 1] from economics, in which a principal (a service requester) requests an agent (the provider) to perform a specific task. The outcome of the task execution affects the principal’s utility, who will therefore be interested in influencing the effort that the agent puts in performing the task. The effort is expressed in terms of available actions which have associated execution costs. In the so-called hidden action setting, it is assumed that the actual actions as executed by the provider agent are unobservable to the principal. Instead, only some performance measures of such actions are observed. Actions determine, usually stochastically, the ensuing performance. Performance is therefore a random variable whose probability distribution depends on the actions taken by the agent. This stochastic nature captures the fact that there are externalities in the environment that the agent does not control. The principal will therefore want to establish an incentive schedule in order to encourage the provider agent to choose the actions that are more likely to lead to an intended performance standard. 3.1 Targeting standards As described in previous work [5], standards are generated through the use of an averaging function applied to task execution outcomes of a group of provider agents that have been clustered within a specific role. Since, according to our model, standards allow requesters to identify expected values for the outcomes of tasks when executed by a specific provider, we consider a standard as a target that agents should meet. Any deviation from the standard is considered as a sub-optimal outcome. Figure 1 illustrates this notion, where ςrepresents the target standard that the requester would expect, and each concentric circle labelled with a δidenotes equidistant performances to the target. Concentric lines highlight the fact that we shall consider deviations Fig. 1. A standard as a target in any direction to be equally harmful in terms of expected values. The arrow pointing towards the centre discloses the aim of our incentive-based approach with which we will try to encourage providers to better conform to the standard. 3.2 Actions and outcomes In our model, we will assume that each provider has a set of actions at its disposal, each with a cost and a probability function for obtaining different performance outcomes. Actions can be thought of as the effort the provider puts in when executing a given task: employing more effort, will more likely lead to a higher outcome. Of course, expending more effort also means bearing a higher cost. Following a finite model for actions and outcomes we have that: Definition 1 The provider has an ordered set of possible actions A={a1, ..., an}, where ai≺ajif i<j. This means that Cost(ai)< Cost(aj), i.e., aiis less costly for the provider to execute than aj. Definition 2 The possible observable outcomes that the provider may obtain is an ordered set ¯ X={¯x1, ..., ¯xm}, where ¯xi≺¯xjif i < j (¯xiis a worse outcome than ¯xjand therefore indicates worse performance). Definition 3 There is a probability distribution function for ¯ Xgiven an action in A, where p(¯xk|ai)is the probability of obtaining outcome ¯xk∈¯ Xwhen performing action ai∈ A. We have that Pm k=1 p(¯xk|ai)=1, for all i∈[1, n]. We assume that the monotone likelihood ratio property (MLRP) [1], relating actions with outcomes (as defined in Def. 4), holds for every provider. This property indicates that greater efforts are more likely to produce better outcomes. Definition 4 The MLRP holds iff for any ai, aj∈ A with ai≺ajwe have that the likelihood ratio p(¯xk|ai)/p(¯xk|aj)is non-increasing in k. 3.3 Incentives Given the fact that only outcomes, and not efforts, are observable by the principal, incentives are specified through an incentive schedule mapping possible outcomes to incentive values to be collected or paid by the provider (Def. 5). Definition 5 An incentive schedule I:¯ X → I maps each possible outcome in ¯ Xto a specific incentive value in I. We look at incentives as producing some change in the utility that the agent would get if no incentives were in place. In this sense, D(I) = [−1,1], where positive values denote percentage increases in utility and negative values denote percentage decreases in utility (i.e., they are seen as penalties). A null value means that there is no incentive in place. 3.4 Providers’ decision rationale Based on the stochastic model of action outcomes explained above, each provider is assumed to be an expected utility maximizer agent. Therefore, when choosing the action ato perform it will seek to maximize expected utility [9]: arg max a∈A Ea= m X i=1 p(¯xi|a)u(¯xi, I(¯xi)) −Cost(a) (1) where u(¯xi, I(¯xi)) is the utility the agent gets from obtaining performance outcome ¯xi, taking into account the incentive I(¯xi) it will get from such a performance. Utility is therefore defined as follows: u(¯xi, I(¯x)) = u(¯xi)×(1 + sens(I(¯x))) (2) This function encompasses two sub-functions: the prior utility u(¯xi) collected according to the outcome obtained, and the effect on this utility of the incentive value applied (prior utility remains unchanged when the agent is immune to incentives: sens(I(¯x)) = 0). In order to accommodate different sensitivities, sens :I(¯x)→[0,1] is modelled as follows, where B∈N+: sens(I(¯x)) = 1 1 + e−I(¯x).B (3) Higher Bvalues make the agent more sensitive to incentives, while with lower ones the agent will tend to behave the same regardless of any incentives. 4 Policies As pointed out in Section 2, each provider is assigned to a role according to the performance that it exhibits. Given the evolving nature of the environment in which the agent operates, it may be the case that the agent alters its performance, for better or for worse. We should emphasize at this point that, since the agent is an expected utility maximizer, its decision regarding how much effort to employ is conditioned by a number of factors which we can identify by analysing Equation 1. Any changes in these factors are thus possible causes for a deviation from the standard characterizing the agent’s assigned role: i) costs of the efforts that the agent has at its disposal; ii) effectiveness of efforts, that is, their probability distributions over performance outcomes; iii) utility the agent gets from obtaining each possible outcome; and iv) sensitivity of the agent with respect to any incentives it may be offered. In this paper, we assume the agent somehow becomes aware of changes in these factors in order to take them into account when deciding which action to perform. These deviations in performance render the role clustering unfit to represent the current performances of agents in the system, in terms of the standards extracted from the roles. Therefore, in order to maintain role stability when agents deviate from agreed standards, the system may determine and employ an appropriate incentive schedule I:¯ X → I (see Def. 5). Since actions are not observable, this schedule is based exclusively on the measurable outcomes of task execution, which for the sake of defining appropriate incentive schedules are compared with the target outcomes characterizing the roles. We call the entity responsible for maintaining role stability an incentive policy maker (IPM). The IPM does not have access to the factors influencing the agents’ decision making as this is considered to be private information. The goal of the IPM is to keep on target the agents playing a specific role, i.e., agents should obtain outcomes as close as possible to the target outcome of the role. We assume the IPM prefers to achieve this aim with the least incentives needed. In case of failure to accomplish this aim, or if by doing so the IPM has to apply a too costly incentive schedule, then it is time to rearrange the role – agents are seen as no longer being able to perform the role at a bearable cost for the system and should thus be reassigned to a different role. 4.1 Incentive schedules Given an incentive schedule offered to the agents playing a specific role, we may determine its effectiveness by looking at the outcomes that have been obtained. We should also take into account the cost of applying such an incentive schedule. Given the stochastic nature of agent efforts in terms of obtained outcomes, an incentive schedule’s quality oscillates around some value, regardless of there being any changes in the environment that lead agents to deviate from previously obtained outcomes. In order to compute an incentive schedule’s quality Q(I), we aggregate a sequence ¯ X=h¯x1,¯x2,...,¯xniof nobtained outcomes (¯xi∈¯ X), and compare them with the target outcome ¯x. We define Q(I) as: Q(I) = wo×targetHit(¯ X)−wc×totalCost(I, ¯ X)/(wo×n) (4) targetHit(¯ X) = n− n X i=1 |¯xi−¯x|(5) totalCost(I, ¯ X) = n X i=1 |I(¯xi)|(6) Target hit measures the incentive schedule’s effectiveness in inducing agents to meet the target. Any values outside the target are seen as deviations that need to be minimized in terms of role maintenance – for simplicity we assume ¯ X ⊂ [0,1]. A perfect performance consists of noutcome values at the target ¯x. The total cost of the incentive schedule takes into account actually paid incentives, which depend on the outcomes obtained. In order to normalize Q(I) to the range [0,1], the weighted sum of these two components is divided over the maximum quality value, where all noutcomes are on target and no incentive values are applied. Weights woand wcallow us to define the relative importance of these two conflicting goals, e.g., by giving priority to obtained performance over how much it costs to achieve it in terms of incentives paid. In the quest to find out the best incentive schedule, measured both in terms of effectiveness and cost, the number of different incentive schedules available to the IPM is quite high. In order to reduce this search space, we can limit ourselves to incentive schedules composed of values within the set bI · 10c/10, which gives us discrete incentive values with 0.1 steps. Depending on the number of outcomes to consider, this may still give us a huge number of schedules to experiment with. We can slightly alleviate this issue by taking into account the intuitive heuristic that we should promote outcomes closer to the target no less than outcomes farther away. 4.2 A local search approach Given the high number of schedules to experiment with, we follow a local search approach to find the optimal incentive schedule. More specifically, we employ a hill-climbing procedure, by successively trying to find out neighbouring incentive schedules that are better than the currently employed one. In order to find them, however, we need to try out incentive schedules before we know how worthy they are, which makes the search more stochastic. Furthermore, given the dynamics of the environment, these quality values are not constant over time, and thus exploration must always be an option. To generate the neighbours of an incentive schedule, we introduce a step change (upwards or downwards) on the incentive value being applied to the target outcome. If the change is downwards, we correct the schedule obtained so that outcomes closer to the target have at least the same incentive as outcomes farther away. This gives us a cardinality of at most 2 in the set of neighbours of each possible schedule. The local search procedure is illustrated in Algorithm 1. At each step, we compare the current schedule with the best known (line 4), and update it (line 5). Whenever the current schedule is not better than the best known (which means we have tried a neighbour that was not found to be better), we go back to the best as the current schedule (line 7). Then we randomly explore, with probability 1−Q(best), the neighbours of the best schedule (line 9) – the better the schedule is, the less likely we will explore, exploiting instead the best schedule we know of. In order to compute the quality of each incentive schedule we need to apply it enough time to aggregate new evidence to fill in sequence ¯ X(see Eq. 6). Algorithm 1 Local search for incentive schedules 1: best {the best known incentive schedule} 2: current {the currently applied incentive schedule} 3: loop 4: if Q(current)> Q(best)then 5: best ←current 6: else 7: current ←best 8: end if 9: with probability 1 −Q(best): current ←RandomNeighbour(best) 10: end loop 4.3 Re-organization Given the organizational flavour of role taxonomies, we have preferred an incentivebased policy to a reorganization of the system in terms of up-to-date skills of agents. This preference is due to both practical and fundamental reasons. The computational complexity of creating or updating a role-taxonomy may be considerable, especially when little is known about the agents that are to take part in this organization, and thus about the roles that are to be created (see e.g. the clustering approach in [4]). Furthermore, the very notion of roles as a descriptive facet of an organization presumes some notion of stability as they provide a means to identify specific agents within the organization. If we reorganize too often, this property of long-term existence is lost. Nevertheless, there will be situations in which reorganization is a better option as compared to applying incentive schedules with the aim of influencing the providers’ behaviour. On the one hand, although an effective incentive schedule may be found, applying it may bear a significant cost. On the other, there will be situations in which an effective incentive schedule is not found. This may happen either because the search procedure employed is not able to find it (the local search approach described in the previous section is vulnerable to local optima), or because environmental changes have reduced the influencing ability of the IPM, therefore lowering the effectiveness of the most effective incentive schedule available. In either case, the quality Q(I) of the best incentive schedule found will be lower than a certain value. We may use this information to decide when to reorganize the role taxonomy. By reorganizing we mean to obtain roles that exhibit a higher cohesion in terms of the skills of the agents to which those roles have been assigned. Given the permanent search for better incentive schedules (see Algorithm 1), the stochastic nature of outcomes, and possible environmental changes, Q(I) may oscillate. Therefore, in order to infer that the incentive-based policy is not able to obtain incentive schedules that are cost-effective we must allocate enough time for the search procedure to run. The approach that we take to make such a call is to collect nqquality values q1, q2,...qnqfor the last nqemployed incentive schedules, and to compare the average of those values with a predefined threshold qmin ∈[0,1]. Reorganization is the choice if Pnq i=1 qi/nq< qmin. By increasing the value of parameter qmin, we demand more cost-effective incentive schedules before a reorganization decision is taken. Lower qmin values will allow for less cost-effective schedules, meaning that we consider reorganization as being a more costly operation to undertake. 5 Evaluation The software we have used to empirically evaluate our approach is a simulation framework built using RePast Simphony. We have designed experiments to present how our proposal learns appropriate incentives for different types of providers along time and, in case the search for incentive schedules fails, how the role evolution mechanism can be launched to re-allocate providers in roles more representative of their current skills. 5.1 Provider profiling There are three functions that together determine the behaviour of each provider. Firstly, we define a function for effort costs, as mentioned in Def. 1; these costs are used in the provider’s decision making (see Equation 1). For this purpose, we use Equation 7 to define different profiles of providers. This means that different providers may have different costs for the same efforts. Cost(a) = α·(k+ (1 −k)·a1/β) (7) We model five provider profiles, whose effort cost functions are depicted in Figure 2. Due to length constraints we only use some of them in the experiments. – Flat. The provider’s efforts cost is the same for any effort (α= 0.5, k= 1 and β= 1). – Linear. Effort costs increase linearly. We set α= 1, k= 0 and β= 1. – Concave. Effort costs are modelled with a concave-shaped function. We use α= 1, β= 0.3 and k= 0. We do not use it. – Convex. Effort costs are modelled with a convex-shaped function. We use α= 1, β= 3 and k= 0. – Random. Values for α,kand βare randomly selected with 0.5≤α≤1, 0.3≤β≤3 and 0 ≤k≤0.5. We use the same approach to define the second function: the outcome utility of the providers, that is, the utility the provider obtains from each possible outcome (this is the prior utility u(¯xi) mentioned in Equation 2). The same profiles defined above are applied to this function. The third function we need to put forward is the one relating provider efforts and obtained outcomes, as mentioned in Def. 3 and used in Equation 1. We have modelled this relation by using beta distributions, whose shape is controlled by two parameters, αand β. For each beta distribution, we set α= 1 + (c∗p−c)