From roles to standards: a dynamic maintenance approach using incentives

Inf Syst Front DOI 10.1007/s10796-014-9523-4 From roles to standards: a dynamic maintenance approach using incentives Ram´ on Hermoso ·Henrique Lopes Cardoso · Maria Fasli © Springer Science+Business Media New York 2014 Abstract Social coordination has been addressed in multiagent systems, making use of concepts such as institutions, norms, commitments, conventions, roles, or trust. In this paper, we argue the need to tackle open and dynamic environments with yet another concept: the notion of a standard, seen as a measurable and non-committing expectation. Not much 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 bring about changes in the expectations generated from roles. Using standards measured from roles as the focus of attention, we propose an incentive-based mechanism to maintain roles over time. This approach is put in contrast with reorganization, which is needed when incentives are not cost-effective. Different search algorithms are proposed to illustrate incentive-based maintenance. Some empirical results are shown based on the principal-agent model from economics. Keywords Artificial societies ·Standards ·Incentives R. Hermoso ()·M. Fasli School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, UK e-mail: [email protected] M. Fasli e-mail: [email protected] H. Lopes Cardoso LIACC / DEI, Faculdade de Engenharia, Universidade do Porto, Rua Dr. Roberto Frias, 4200-465 Porto, Portugal e-mail: [email protected] 1 Introduction Since the mid 1990s, a considerable number of works have been concerned with the development of infrastructures for supporting social coordination in open multi-agent systems. Taking inspiration from social sciences, concepts such as (electronic) institutions (Esteva et al. 2001; Dignum and Dignum 2001; Fornara et al. 2008), norms (Boman 1999; L´opez y L´opez and Luck 2003; Boella et al. 2006;Garc´ıaCamino et al. 2007; Lopes Cardoso and Oliveira 2008), commitments (Singh 1999; Fornara and Colombetti 2003; Fasli 2003), conventions (Walker and Wooldridge 1995; Conte and Castelfranchi 1999), and roles (Hubner et al. 2002;Fasli2006; Winikoff and Cranefield 2009;Hermoso et al. 2013) have been introduced and exploited in the multi-agent systems domain. In open multi-agent systems, agents enter and leave the interaction environment, and behave in an autonomous and not necessarily cooperative manner, exhibiting selfinterested behaviours. Even when agents establish commitments among them, the dynamic nature of the environment may jeopardize such commitments if agents are not socially concerned enough and value more their private goals when evaluating the new circumstances. Moreover, in open and dynamic environments one cannot assume that agents will behave consistently over time. This may happen either because of the agents’ (lack of) ability or benevolence attitude. In some cases, an agent may not be capable of maintaining a certain behaviour standard throughout its lifetime. In other cases, the agent may intentionally deviate from its previous performance. It is therefore important, when considering open environments, to take into account also the evolution of an agent’s internal skills or motivations, besides the dynamics of the interaction environment as a whole. Inf Syst Front These kind of issues have been the motivation for the development of computational trust models, which may be used to enable an informed selection of an interaction peer. Some of these approaches comprise situational trust models (Rehak et al. 2006; Tavakolifard et al. 2008;Hermoso et al. 2013;Urbanoetal.2011), in the sense that agents are evaluated regarding their performance in specific contexts, situations, or tasks. A typical assumption in these models is that the measured trustworthiness of an agent is updated as new experiences and evidence are collected from the environment. There is therefore no collective perspective on the group of evaluated agents – each is assessed individually within the multi-agent system, and therefore no overall evaluation is performed. Taking an organizational approach, and looking at the society from a role-specialization perspective, Hermoso et al. proposed role evolution (Hermoso et al. 2013)as a guideline to develop a coordination mechanism that enhances partner selection processes for task delegation purposes. This approach is based on examining the agent society and on identifying “run-time roles” – so building a role taxonomy – that clusters agents with similar skill patterns for a certain (set of) task(s). From this perspective, the mechanism provides, as a service, the identification of the role that labels agents considered as the most suitable to perform a specific task. Looking at this role taxonomy as providing structure for some sort of an artificial organization, in this paper we address the problem of organizational maintenance. Given the evolving nature of agents, as pointed above, a problem faced by the organization in which agents have been (artificially) embedded is that of timeliness: are the agents within a role still performing as well as they did at the time of their assessment? One of two possible options can be chosen when agents start under-performing. The first is to reorganize so that the role taxonomy becomes accurate again. But assuming that this reorganization may be costly, the second approach is to influence the agents’ reasoning by making use of incentives or punishments, in an attempt to keep them on track. We propose and exploit the concept of standard to capture the level of suitable performance that agents have to show when they carry out different tasks. The rest of the paper is structured as follows. Section 2 provides an overview of related work, looking at several means of addressing the problem of social coordination, and providing support for the concept of standard. Section 3 summarises the work on role evolution this paper is based on and presents a “standardisation” process from roles to create standards as objectively measured performances to be maintained for each role. In Section 4, we describe the action apparatus and decision rationale of agents based on the principal-agent model. Then, in Section 5, we put forward a model to establish and adjust incentives in order to maintain standards over time. Different search algorithms are proposed in this regard. Section 6discusses the need for reorganization and describes a rationale and an approach to undertake it. We evaluate our proposals and present empirical results in Section 7. Section 8provides a critical discussion of the contributions of this paper and compares it with other related approaches in the literature. Finally, we conclude and sketch our planned future work in Section 9. 2 Related work This paper proposes an approach to tackle open and dynamic environments, based on the notions of role and standard. Social coordination is a very active topic in the multi-agent systems research community. The need for approaches to tackle the open and dynamic nature of multi-agent environments has given rise to complementary approaches that bring into this realm concepts from diverse fields, such as social, organizational, legal, or behavioural sciences. The concept of institution has been borrowed from economics (North 1990) and philosophy (Searle 1995)intwo directions. On the one hand, to provide regulated environments consisting of computational infrastructures that frame agent interactions (as e.g. in Esteva et al. (2001)and Lopes Cardoso and Oliveira (2008)). On the other, to provide semantics to agent interactions in terms of counts-as relations (Jones and Sergot 1996; Fornara et al. 2008). Within these regulated environments the notion of norms (Boella et al. 2006) has been exploited, as a means to explicitly state what to expect from each agent in the system. Social norms (Tuomela 1995) are based on mutual belief, consisting of conventions (Walker and Wooldridge 1995; Conte and Castelfranchi 1999) that may apply to a large group of agents. The specification of roles (Hubner et al. 2002;Fasli2006; Hermoso et al. 2010) that agents enact in a given society goes in the same direction of making a system more predictable in terms of expected behaviour (Winikoff and Cranefield 2009). Explicitly handling such expectations as norms (Castelfranchi et al. 2003) allows one to make role enacting agents accountable for their actions. Although closely associated with some approaches on the use of norms, the notion of commitment (Singh 1999; Fornara and Colombetti 2003;Fasli2003) emphasizes a deliberative view on norm adoption: agents commit to this as a result of their deliberation process, as opposed to a topdown view on the use of norms as a design tool for defining rules of behaviour in an interaction environment. What seems to be missing from these artifacts for social coordination is some concept of expectation that is both measurable and non-committing. Unlike commitments or Inf Syst Front norms, we pursue a means of establishing how well an agent is able to perform without actually being committed to. And unlike conventions, which typically apply to collective behaviour, we are interested in measuring the outcome of task executions. In order to fill this gap, we use the concept of standard. In the literature, one can find a wide variety of works that adopt the concept of standard for different purposes. The definition of standard is given by the Oxford Dictionary of English1as: “(noun) 1. a level of quality or attainment; 2. something used as a measure, norm, or model in comparative evaluations; (adj.) 3. used or accepted as normal or average”. Therefore, standards describe levels of quality that are recognized to be normal by individuals within a type of system. Standards come about either imposed or emerge as de facto after a number of observations. Following this distinction, standards may be classified as de jure or de facto standards (Salg´e2005). The former are regulations accepted and obliged by law, and are endorsed by a formal standards organization. An example of this type of standards are IEEE or ISO standards for many different purposes. In contrast, de facto standards arise when a critical mass simply agrees to use them in a particular environment. For example, PDF became a de facto standard for printable web documents, although it turned into a de jure standard as ISO 19005-1 in 2005. In this paper, we work on de facto standards in order to capture the measured performance of a set of individuals. In the field of economics, we can find many approaches dealing with standards. In Busch (2000), Busch suggests that standards are mistakenly considered to be mere convenient technologies for organizing and regulating markets so as to reduce transaction costs (however the cost is assessed). Nevertheless, the author argues that standards are part of the moral economy of a society, since they also regulate behaviour. Therefore, standards create uniformity in heterogeneous contexts. Following up the economic approach, Murphy claims that performance standards emerge from the desire to provide incentives while simultaneously paying competitive expected levels of compensation (Murphy 2000). That is, performance standards can be used in order to gauge the adequacy of an individual’s performance, so prompting the possibility of offering incentives if behavioural deviation exists. From a psychological point of view, Bandura and Wood (Bandura and Wood 1989) claim that when people believe the environment is controllable on matters of importance to them, they are motivated to perform as well as they can, which entails an increase in the likelihood of success (or societal satisfaction). Moreover, successful experiences, in turn, provide a self-validation 1http://oxforddictionaries.com/ on the efficacy of the individual and of the environmental controllability. On the contrary, if people face situations they believe as being uncontrollable, they are likely to put in less effort, and this brings about failure. Consequently, over time, failures take an increasing toll on perceived selfefficacy and beliefs about how much environmental control is possible (Bandura and Wood 1989). This author claims that rates of success and failure are largely determined by the standards against which attainments are gauged. Therefore, in layman’s terms, performance standards are used in order to induce collaborative behaviour from counterparts engaged in an interaction. However, as we state in this paper, performance standards per se are not sufficient to keep individuals from performing inadequately. This feature drives us to introduce the concept of incentive as a means to maintaining the performance standards. How standards are created has been studied by many researchers from different fields as well. This process is called standard setting and concerns the methods to build standards from the information available (or potentially available) in the systems (Cizek and Bunch 2007). There exists a wide range of approaches with regards to standard setting, from educational purposes (Hambleton et al. 2000) to medical evaluations (Southgate et al. 2001). 3 Creating standards from roles Due to the non-stationary nature of open systems, in this paper, we address the problem of how to maintain agents from a performance quality perspective as determined by the roles they are playing. We claim that the notion of specialized role proposed in Hermoso et al. (2013) might be used to establish performance standards and so facilitate the agreement on commitments among agents. We therefore envision the possibility of going from roles as expectations of behaviour (Winikoff and Cranefield 2009) or performance (Hermoso et al. 2013) to the explicit handling of such expectations as de facto standards that may be committed to. Standards are therefore not imposed by the system, but promoted after they have been identified as current practice among a group of agents. Standards may thus be exploited to find appropriate agents, given that they are based on evidence about their actual capabilities. The rationale behind creating and maintaining performance standards relies on the concept of role proposed by Hermoso et al. (2013). In this work, the authors claim that in open systems the evolution of the population should entail that organisational structures evolve as well. For instance, some of the roles that existed in our society two centuries ago, no longer exist nowadays. Therefore, roles are somehow linked to the different needs of the population at a certain point in time. With this idea in mind, the authors Inf Syst Front define roles as entities that group a set of agents that outperform others for a certain set of tasks. Furthermore, they introduce the concept of specialisation, from which roles are created as specialisations of more general roles; e.g. the role surgeon is created as a specialisation of the role doctor, because those playing the former (they also play the role doctor) are better skilled for tasks such as operate. Thus, the authors propose that any society of agents may be covered by an overlay role taxonomy formed by extracting capabilities and trust relationships among agents over time. The mechanism evolves the society’s role taxonomy, assigning agents to roles. Then, roles other that agents are playing in the system provide information about their expected capabilities regarding certain interactions (e.g. the provisioning of certain services or 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 clustering algorithm to identify patterns of behaviour, so distinguishing those agents outperforming others.0 This mechanism has been exhaustively tested in different conditions with open task-oriented multi-agent systems with heterogeneous and dynamic populations, showing a significantly good adaptation in order to provide an efficient role taxonomy that improves agents’ partner selection. The mechanism in Hermoso et al. (2013) relies on the definition of a Task-oriented Multi-Agent System (T-MAS) as a multi-agent system in which participants have to perform a set of tasks (Hermoso et al. 2013). It is defined by a set of participants Ag,asetoftasksTand a role taxonomy . We will use the notion of T-MAS throughout the paper as the base for our approach. The role taxonomy reflects, at a given time, which agents are more skilled in the system to perform different tasks. As the process of role taxonomy evolution is costly, in this paper, we focus on the period among two consecutive evolutions. Given a role taxonomy, we will extract performance standards from the roles in it. These standards will emerge as an indicator of what is expected from the group of agents (the ones playing a specific role) for a particular task. Thus, standards will be used by agents as an anticipatory measure on the likely outcome of interactions, and may be used in further negotiations to assure a certain quality of performance. Standard setting process Let Attr={attr1,attr2, ..., attrn} be the set of attributes that characterizes a task in T.For instance, in an e-commerce domain Attr={delivery time, quality type}would be a set of attributes that might characterize the task supply good.Letxibe a value for the attribute attri. For example, xdelivery time =5means that the value for the attribute delivery time is 5. Thus, let us define the concept of standard: Definition 1 Astandard ςis a tuple r, t, xithat establishes, for a role rand a task t, a certain expected level of quality xifor the attribute attriin t. Note that the concept of standard refers only to one attribute of the task. That is, the same role and the same tasks might have different standards for different attributes. Following up the example given above, the standard for delivery time might be 5 while the standard for quality type might be 3. The level of quality of different attributes is meant to be atarget(xi) representing the expectation an agent performing a task generates on its counterparts. In order to avoid our approach being domain-dependent, we take this notion of targeted standard to be as abstract as possible; that is, we cannot state a priori in which situations (in any type of domain), higher or lower outcomes (regarding the standard value) bring about better or worse outcomes. As we will further explain in Section 4.1, a behaviour showing a deviation exceeding the standard is equally harmful than the one that does not reach it. Thus if the standard for delivery time is 5 days and a provider takes 7 days delivering a product, that is considered as undesirable as providing the product in 3 days. Although this would seem to be a bit counter-intuitive, delivery in advance might mean no storage room for the new products, while late delivery might entail that the production line will be halted. In this paper, we claim that once the role evolution mechanism described above is in place, roles may be used to create standards which, in turn, could be included in commitments that regulate interactions in the system. The underlying idea relies on the aggregation of values of different attributes that characterize (the performance of) a task within the role, to establish a standard for that role/task pair, as defined in definition 1. For instance, in open electronic markets (e.g. eBay), roles might be created in order to place providers in different categories of provision, while standards would emerge in order to facilitate better interaction processes, and so prevent agents from exhibiting undesirable behaviours, such as longer delivery times, price changes, decrease of quality, etc. More precisely, let us suppose we have the role Bike Provider with, among others, the attributes delivery time and quality type.Leta1,a2and a3 be three agents playing the role, with average delivery times of 3, 4 and 5, respectively. Then we could use an aggregation function (e.g. an average) to extract a standard for the task as ς=r=Bike Provider,t=Provide Bikes ,x delivery time =4. Using an averaging function may make Inf Syst Front sense if we take into account that the clustering mechanism obtaining the role taxonomy will, in principle, get us roles with high cohesion – for which not much deviation should be expected in the beginning. 4 Incentives and the principal-agent model After explaing the path from roles as expectations to commitments based on standards, we are now in a position to elaborate on enforcement schemes that enable us to maintain the stability of the role taxonomy, which is obtained as explained in Section 3. We will base our approach on the well known principal-agent model (Laffont and Martimort 2002; Caillaud and Hermalin 2000) 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 efforts that the agent puts in performing the task. Efforts are expressed in terms of available actions, which have associated execution costs. In the so-called hidden action setting (Caillaud and Hermalin 2000), it is assumed that the actual actions as executed by the agent are unobservable to the principal. Instead, only some performance measures of such actions are observed. Actions determine, usually stochastically, the obtained 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 has no control over. The principal will therefore want to establish an incentive schedule in order to encourage the agent to choose the actions better leading to an intended performance standard. In our approach, we slightly change the model by putting forward a new entity – an incentive policy maker in charge of creating and applying incentive schedules to keep agents conforming to different standards. In other words, it is not the principal (consumer of the service), but this policy maker who sets and applies incentives to the agents (providers). 4.1 Targeting standards As described in Section 3, 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 1illustrates this notion, where ςrepresents the target standard that the requester ϛ 1 2 3 Fig. 1 A standard as a target would expect, and each concentric circle labelled with a δidenotes equidistant performances to the target. These concentric lines highlight the fact that we shall consider deviations in any direction (left or right, upwards or downwards) 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 target the standard. 4.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. Following a finite model for actions and outcomes, we have that: Definition 2 The provider has a set of possible actions A= {a1, ..., an}at its disposal, each having an associated cost, denoted by Cost(ai). Definition 3 The possible observable outcomes that the provider may obtain is an ordered set Xattr ={x1, ..., xm}. Note that Xattr is the set of possible values for measuring the performance of the task being evaluated at the attribute attr. For the sake of simplicity, from now on we take into consideration only one of the attributes of the task, in order to minimise the complexity in notation. Then, Xrefers to a Xattr for whatever attribute we are evaluating in the task. Definition 4 There is a probability distribution function for Xgiven an action in A,wherep(xk|ai)is the probability of Inf Syst Front obtaining outcome xk∈Xwhen performing action ai∈A. We have that m k=1p(xk|ai)=1, for all i∈[1,n],where mis the number of possible outcomes and nis the number of actions. 4.3 Incentives Given the fact that only outcomes, and not efforts, are observable to the principal, incentives are specified through an incentive schedule mapping possible outcomes to incentive values to be collected by the provider, according to Definition 5. Definition 5 An incentive schedule I:X→Imaps each possible outcome in Xto a specific incentive value in I. We look at incentives as producing some change in the utility the agent would obtain by showing its natural behaviour if no incentives were in place. In this sense, I={ι:ι∈[−1,1]}, where positive values denote percentage increases in utility and negative values denote percentage decreases in utility. When ι=0 there is no incentive in place. Therefore, positive incentives are considered as rewards for agents to foster the performance of the actions the incentive is applied to, while negative incentives represent an attempt to discourage agents from performing non-desired actions. 4.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 a to perform it will seek to maximize expected utility (Von Neumann and Morgenstern 1980): argmax a∈A Ea= m  i=1 [p(xi|a) ·u(xi,I(x i))]−Cost(a) (1) where u(xi,I(x i)) is the utility the agent gets from obtaining performance outcome xi, taking into account the incentive I(x i)it will get from such a performance. We define function u(·,·)as follows: u(x, ι) =u(x) ·(1+sens(ι)) (2) This function encompasses two sub-functions: the prior utility u(x) collected according to the outcome xobtained, and the effect on this utility of the incentive value ιapplied. We model such an effect with a sensitivity function sens :I→ [−1,1], which translates an incentive value to its actual perceived impact on the utility of the agent: sens(ι) =2 1+e−ι·B−1(3) Parameter B∈N+allows us to tune the sensitivity of the agent with respect to incentives: 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. Figure 2shows some examples of Eq. 3to model sens(ι) with different Bvalues. When providers are not offered any incentive, they simply obtain the prior utility u(x) as a result of Eq. 2. Negative incentives (punishments) diminish the utility of the provider, whilst positive incentives increase it. Fig. 2 Different curves for Eq. 3, varying B Inf Syst Front 5 Maintaining performance standards through incentives Given the previous performance of each provider, on which standards (via roles) have been defined (as described in Section 3), it may be the case that agents deviate from the standard they were able to meet before. This is due to the evolving nature of the environment in which the agent operates. Since agents are expected utility maximizers, their decision regarding which action to employ when executing a task is conditioned by a number of factors, which we can identify by analysing Eq. 1. Any changes in these factors are thus possible causes for a deviation from the standard characterizing each agent’s assigned role: 1. Costs of the actions agents have at their disposal; 2. Effectiveness of available actions, that is, their probability distributions over performance outcomes; 3. Prior utilities that agents get from obtaining each possible outcome; 4. Sensitivity of agents with respect to any incentives they may be offered. Note that changes in sensitivity are only relevant when there are already incentives in place. Changes in action costs may lead the agent to apply less costly actions, whose outcomes may be different. Changes in the effectiveness of actions may be due to environmental factors not under the control of the agent. In this paper, we assume agents somehow become aware of changes in any of these factors in order to take them into account when deciding which actions to perform. We can easily think of external factors causing these changes. For instance, in a supply chain, fluctuations on prices for different inputs (e.g. parts or raw materials obtained from suppliers) will certainly influence the cost of executing the task. As for outcome probabilities, the agent may be able to update these estimations on-line, according to run-time experience. These deviations in performance render the role clustering (obtained as described in Section 3) 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 definition 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. The incentive policy maker (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 somehow reorganize the agents that are seen as no longer being able to perform the role at a bearable cost. This is the topic of Section 6. 5.1 Cost-effective 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 are obtained once that schedule is in place. We should also take into account the cost of applying the incentive schedule. Given the stochastic nature of agent efforts in terms of obtained outcomes, an incentive schedule’s effectiveness will typically oscillate around some value, regardless of there being any changes in the environment that lead agents to change their chosen actions. For this reason, in order to compute an incentive schedule’s quality Q(I), we aggregate a sequence X= x1,x2,...,xnoof noobtained outcomes (xi∈X), and compare them with the target outcome x∗. We define Q(I) as: Q(I) =ω·targetHit(X) −(1−ω) ·totalCost(I, X) (4) targetHit(X) =no− no  i=1 |xi−x∗|(5) totalCost(I, X) = no  i=1 |I(xi)|(6) The total cost of the incentive schedule takes into account actually paid incentives, which depend on the outcomes obtained. By using the modulus of the incentive we seek to give the same weight to paid or collected incentive values – without the modulus the IPM would tend to prefer penalizing providers as opposed to paying them incentives or to simply stand still. We thus have that totalCost(X) ∈ [0,n o]. On the other hand, 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], which entails targetHit(X) ∈[0,n o]. Combining these two functions, we have Q(I ) to be within the range [((ω −1·no), ω ·no]. Factor ω∈[0,1]allows us to balance 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. Inf Syst Front 5.2 Search space Incentive schedules specify, for each x∈X, an incentive value ι∈I. We can therefore represent an incentive schedule as a vector ι=[ι1, ..., ιm],wherem=|X|is the number of possible observable outcomes (see definition 3) and each ιi∈I. In the quest to find out the best incentive schedule, measured both in terms of effectiveness and cost, we need to reduce the search space for the IPM, e.g. by limiting the search to incentive schedules composed of values within the set I·10/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. Using this principle, the number of incentive schedules available is given by C|I|+|X|−1 |X|=(|I|+|X|−1)! (|I|−1)!|X|! Table 1shows the number of incentive schedules according to different sizes of the outcomes set, and taking |I|=21 (which is the size of set I·10/10 when considering I= {ι:ι∈[−1,1]}). As we can see, even when considering a small number of outcomes, the number of incentive schedules is quite large, growing exponentially as |X|increases. Notice that applying a single incentive to the target outcome may comprise a suboptimal solution. On one hand, the IPM does not know how precise are the actions chosen by the agents, which means that the action most likely obtaining the target outcome may still be quite noisy. On the other hand, cheaper incentive schedules may be found by taking into account a combination of incentives to different outcomes. Table 1 Number of incentive schedules for varying |X| |X|Number of incentive schedules 2 231 3 1771 4 10626 5 53130 6 230230 7 888030 8 3108105 9 10015005 10 30045015 5.3 Finding appropriate incentive schedules Unlike typical approaches in game theory, we do not assume that agents’ decision variables (action costs, their probability distributions over outcomes, or utility functions on those outcomes and any employed incentives) are known to the incentive policy maker. We therefore need to go through the search space of possible incentive schedules in order to find the ones that prove to be more cost-effective, by actually trying them out. Given the high number of schedules to experiment with, some heuristics are needed to guide the search. In the following sections we introduce three approaches for searching for an appropriate incentive schedule. An important feature of these approaches is that they are meant to work on-line: the IPM will be searching for the most cost-effective incentive schedule, while at the same time trying to maximize the accumulated quality of the incentive schedules that are actually employed. We should mention at this time that it is not our purpose to propose a best alternative in terms of search strategies, but instead to compare a few approaches and see how they fare in terms of some measurable criteria. One such criterion is related with how each approach is able to avoid reallocation of agents to other roles (which is further explained in Section 6). 5.3.1 On-line local search Given the high number of schedules to experiment with, in this section we follow a local search approach to seek an 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 once a change is detected in the environment. One crucial aspect of local search algorithms is the definition of the neighbourhood function. To generate the neighbours of an incentive schedule, we introduce a step change (upwards or downwards) in the incentive value being applied to any of the outcomes. We then correct the schedule obtained so that outcomes closer to the target have at least the same incentive as outcomes farther away (as mentioned in Section 5.2). This gives us a cardinality of at most 2 ·|X| in the set of neighbours of each possible schedule. The local search procedure is illustrated in Algorithm 1. At each step, we start by checking if we are applying the incentive schedule that is known to be the best (line 2): Inf Syst Front if yes, we update it (line 6). If we are applying a different incentive schedule (lines 7-10), we compare the current schedule with the best known (line 7), and update if it is better (lines 8-9). Then we randomly explore, with probability 1−e(||bestQ||−1)·τ(line 11), the neighboursof the best schedule (line 12): ||bestQ|| is the normalized value for bestQ to the range [0,1],andτis a temperature parameter. The better the schedule is, the less likely we will explore, exploiting instead the best schedule we know of (line 14). When a significant change is detected in the environment, measured in terms of a decrease in the quality of the best known schedule (line 3), we promote exploration by resetting the temperature τ(line 4); τis then decayed in every step (line 16) according to the time we allow the search to proceed (see Section 6), until it reaches nearly 0 (determining no exploration).2 In order to compute the quality of each incentive schedule we need to employ it sufficient time to aggregate new evidence to fill in sequence X(see Eq. 4). 5.3.2 On-line tabu search The search space we are dealing with is quite plateaux-like, given the fact that many neighbours of a given schedule will have the same exact quality. This is a challenge for an approach based on hill-climbing, such as the one presented 2Note that this temperature mechanism is not related to simulated annealing, in which the temperature determines the probability of choosing a worse solution; in Algorithm 1 we use it simply to induce and then to reduce exploration, while a new schedule will only be kept if it is found to be better than the best we know of (hence the hill-climbing flavour). in Section 5.3.1. One well-known technique to tackle such kind of search spaces is tabu-search, which we explore in this section. Tabu-search includes a list of forbidden nodes (schedules) with the aim of escaping local-optima. Algorithm 2 shows our approach. The tabulist contains a small number of the most recently visited incentive schedules; whenever we add an element to this list (line 13), if the number of elements exceeds its size we discard the most outdated one (in a first-in-first-out fashion). Besides keeping the best schedule found so far, we also keep the point from which we will continue the search, by following one of its neighbours that are not in the tabu-list (line 12). The remaining parts of the algorithm are similar to Algorithm 1. 5.3.3 Reinforcement learning Learning on-line, i.e. by interacting with the environment and obtaining appropriate rewards, is the aim of reinforcement learning (RL) (Sutton and Barto 1998). In this section, we look at the problem of searching for an optimal incentive schedule as a reinforcement learning problem. More specifically, the setting we are addressing is similar to an n-armed bandit problem (Sutton and Barto 1998). The incentive policy maker (the learner) will try to determine, by exploring its action3set, the best possible incentive schedule Iwhose 3We emphasize that these are the learner’s actions (i.e., those available to the IPM), and not the actions of the provider agent as discussed in Section 4.2.Wehereusethesametermaction because it is well established in RL literature. Inf Syst Front the ieee workshop on distributed intelligent systems: Collective intelligence and its applications, DIS ’06. IEEE Computer Society, Washington, DC, (pp. 315–320). Salg´e, F. (2005). National and international data standards. In: P.A., Longley M.F., Goodchild D.J., Maguire D.W., Rhind (Eds.) In Geographical information systems. principles, techniques, management and applications. 2nd edn. John Wiley, New York, (pp. 693–706). Searle, J.R. (1995). In The Construction of Social Reality.NewYork: Free Press. Sherstyuk, K. (2000). Performance standards and incentive pay in agency contracts. Scandinavian Journal of Economics,102(4), 725–736. Singh, M.P. (1999). An ontology for commitments in multiagent systems: Toward a unification of normative concepts. Artificial Intelligence and Law,7(1), 97–113. Southgate, L., Hays, R.B., Norcini, J., Mulholland, H., Ayers, B., Woolliscroft, J., Cusimano, M., McAvoy, P., Ainsworth, M., Haist, S., Campbell, M. (2001). Setting performance standards for medical practice: a theoretical framework. Medical Education,35(5), 474–81. Sutton, R.ichard.S., & Barto, A.ndrew.G. (1998). In Reinforcement Learning: An Introduction. Cambridge: The MIT Press. Tavakolifard, M., Knapskog, S.J., Herrmann, P. (2008). Cross-situation trust reasoning. In Proceedings of the 2008 ieee/wic/acm international conference on web intelligence and intelligent agent technology - volume 03, WI-IAT ’08. IEEE Computer Society, Washington, DC, USA, (pp. 67–71). Tuomela, R. (1995). In The Importance of Us: A Philosophical Study of Basic Social Norms. Stanford: Stanford University Press. Urbano, J., Rocha, A.P., Oliveira, E. (2011). In Transactions on computational collective intelligence v, (pp. 84–105). Berlin, Heidelberg: Springer-Verlag. Von Neumann, J., & Morgenstern, O. (1980). In Theory of Games and Economic Behavior, 3rd edn. Princeton: Princeton University Press. Walker, A., & Wooldridge, M. (1995). Understanding the Emergence of Conventions in Multi-Agent Systems. In: V., Lesser & L., Gasser (Eds.) In Proceedings of the first international conference on multi-agent systems. MIT Press, San Francisco, (pp. 384–389). Winikoff, M., & Cranefield, S. (2009). Eliciting expectations for monitoring social interactions. In Proceedings of the first international conference on computer-mediated social networking, ICCMSN’08. Springer, Berlin Heidelberg New York, (pp. 171– 185). Ramn Hermoso is an assistant professor at the University of Zaragoza. Formerly, he worked as a senior research officer at the University of Essex and as an assistant professor at the University Rey Juan Carlos in Madrid (Spain). He received his PhD from the University Rey Juan Carlos in 2011. His research interests span from trust and reputation mechanism in multiagent systems to the innovation management in social networks. He is author of several publications in journals, books and international conferences, and has participated in more than 15 research projects, funded by both national and international institutions. He has been involved in organising international events and peer reviewing for international journals, conferences and workshops. Henrique Lopes Cardoso obtained his PhD on Informatics Engineering from the University of Porto in 2011. He is an Assistant Professor at the Faculty of Engineering of the University of Porto (FEUP) and a researcher at the Artificial Intelligence and Computer Science Lab (LIACC). He is also a member of the directive board of the Portuguese Association for Artificial Intelligence (APPIA). His research interests include distributed AI, social coordination and regulation of multiagent systems, adaptive learning agents, and multi-agent systems tools. He has been an active member of relevant European research networks, namely the COST Action IC0801 on Agreement Technologies and the European Network for Social Intelligence (SINTELNET). Maria Fasli is a Professor in the School of Computer Science and Electronic Engineering, University of Essex where she has been a member of staff since 1999. Her research interests lie in agents and multi-agent systems and their theoretical foundations and practical applications, machine learning, analysing and modelling complex data (structured/unstructured), Big Data, as well as semantic-based techniques for user profiling and adaptation including modelling context. She has published in journals and international conferences and specialists workshops in the field of artificial intelligence and multi-agent systems and has participated in international competitions such as the Trading Agent Competition. She has been involved in organising/chairing international events and peer reviewing for conferences and funding organisations. She is the author of Agent Technology for E-commerce (Wiley, 2007). In 2006, she was awarded a National Teaching Fellowship by the Higher Education Academy (UK) for her innovations and contributions to learning and teaching.