From roles to standards: a dynamic maintenance approach using incentives

In Sys F on DOI 10.1007/s10796-014-9523-4 F om oles o s anda ds: a dynamic main enance app oach using incen i es Ram´ on He moso ·Hen ique Lopes Ca doso · Ma ia Fasli © Sp inge Science+Business Media New Yo k 2014 Abs ac Social coo dina ion has been add essed in mul i- agen sys ems, making use o concep s such as ins i u ions, no ms, commi men s, con en ions, oles, o us . In his pape , we a gue he need o ackle open and dynamic en i- onmen s wi h ye ano he concep : he no ion o a s anda d, seen as a measu able and non-commi ing expec a ion. No much wo k has been done in he ield o mul i-agen sys- ems add essing he e ol ing na u e o oles, especially in open sys ems, in which changes in he popula ion b ing abou changes in he expec a ions gene a ed om oles. Using s anda ds measu ed om oles as he ocus o a en- ion, we p opose an incen i e-based mechanism o main ain oles o e ime. This app oach is pu in con as wi h eo ganiza ion, which is needed when incen i es a e no cos -e ec i e. Di e en sea ch algo i hms a e p oposed o illus a e incen i e-based main enance. Some empi ical esul s a e shown based on he p incipal-agen model om economics. Keywo ds A i icial socie ies ·S anda ds ·Incen i es R. He moso ()·M. Fasli School o Compu e Science and Elec onic Enginee ing, Uni e si y o Essex, Wi enhoe Pa k, Colches e CO4 3SQ, UK e-mail: he [email protected] M. Fasli e-mail: m [email protected] H. Lopes Ca doso LIACC / DEI, Faculdade de Engenha ia, Uni e sidade do Po o, Rua D . Robe o F ias, 4200-465 Po o, Po ugal e-mail: hlc@ e.up.p 1 In oduc ion Since he mid 1990s, a conside able numbe o wo ks ha e been conce ned wi h he de elopmen o in as uc u es o suppo ing social coo dina ion in open mul i-agen sys ems. Taking inspi a ion om social sciences, concep s such as (elec onic) ins i u ions (Es e a e al. 2001; Dignum and Dignum 2001; Fo na a e al. 2008), no ms (Boman 1999; L´opez y L´opez and Luck 2003; Boella e al. 2006;Ga c´ıa- Camino e al. 2007; Lopes Ca doso and Oli ei a 2008), commi men s (Singh 1999; Fo na a and Colombe i 2003; Fasli 2003), con en ions (Walke and Woold idge 1995; Con e and Cas el anchi 1999), and oles (Hubne e al. 2002;Fasli2006; Winiko and C ane ield 2009;He moso e al. 2013) ha e been in oduced and exploi ed in he mul i-agen sys ems domain. In open mul i-agen sys ems, agen s en e and lea e he in e ac ion en i onmen , and beha e in an au onomous and no necessa ily coope a i e manne , exhibi ing sel - in e es ed beha iou s. E en when agen s es ablish commi - men s among hem, he dynamic na u e o he en i onmen may jeopa dize such commi men s i agen s a e no socially conce ned enough and alue mo e hei p i a e goals when e alua ing he new ci cums ances. Mo eo e , in open and dynamic en i onmen s one can- no assume ha agen s will beha e consis en ly o e ime. This may happen ei he because o he agen s’ (lack o ) abil- i y o bene olence a i ude. In some cases, an agen may no be capable o main aining a ce ain beha iou s an- da d h oughou i s li e ime. In o he cases, he agen may in en ionally de ia e om i s p e ious pe o mance. I is he e o e impo an , when conside ing open en i onmen s, o ake in o accoun also he e olu ion o an agen ’s in e nal skills o mo i a ions, besides he dynamics o he in e ac ion en i onmen as a whole. In Sys F on These kind o issues ha e been he mo i a ion o he de elopmen o compu a ional us models, which may be used o enable an in o med selec ion o an in e ac ion pee . Some o hese app oaches comp ise si ua ional us mod- els (Rehak e al. 2006; Ta akoli a d e al. 2008;He moso e al. 2013;U banoe al.2011), in he sense ha agen s a e e alua ed ega ding hei pe o mance in speci ic con ex s, si ua ions, o asks. A ypical assump ion in hese models is ha he measu ed us wo hiness o an agen is upda ed as new expe iences and e idence a e collec ed om he en i onmen . The e is he e o e no collec i e pe spec i e on he g oup o e alua ed agen s – each is assessed indi idu- ally wi hin he mul i-agen sys em, and he e o e no o e all e alua ion is pe o med. Taking an o ganiza ional app oach, and looking a he socie y om a ole-specializa ion pe spec i e, He moso e al. p oposed ole e olu ion (He moso e al. 2013)as a guideline o de elop a coo dina ion mechanism ha enhances pa ne selec ion p ocesses o ask delega ion pu poses. This app oach is based on examining he agen socie y and on iden i ying “ un- ime oles” – so building a ole axonomy – ha clus e s agen s wi h simila skill pa - e ns o a ce ain (se o ) ask(s). F om his pe spec i e, he mechanism p o ides, as a se ice, he iden i ica ion o he ole ha labels agen s conside ed as he mos sui able o pe o m a speci ic ask. Looking a his ole axonomy as p o iding s uc u e o some so o an a i icial o ganiza ion, in his pape we add ess he p oblem o o ganiza ional main enance. Gi en he e ol ing na u e o agen s, as poin ed abo e, a p oblem aced by he o ganiza ion in which agen s ha e been (a i i- cially) embedded is ha o imeliness: a e he agen s wi hin a ole s ill pe o ming as well as hey did a he ime o hei assessmen ? One o wo possible op ions can be chosen when agen s s a unde -pe o ming. The i s is o eo ga- nize so ha he ole axonomy becomes accu a e again. Bu assuming ha his eo ganiza ion may be cos ly, he second app oach is o in luence he agen s’ easoning by making use o incen i es o punishmen s, in an a emp o keep hem on ack. We p opose and exploi he concep o s anda d o cap u e he le el o sui able pe o mance ha agen s ha e o show when hey ca y ou di e en asks. The es o he pape is s uc u ed as ollows. Sec ion 2 p o ides an o e iew o ela ed wo k, looking a se e al means o add essing he p oblem o social coo dina ion, and p o iding suppo o he concep o s anda d. Sec ion 3 summa ises he wo k on ole e olu ion his pape is based on and p esen s a “s anda disa ion” p ocess om oles o c ea e s anda ds as objec i ely measu ed pe o mances o be main ained o each ole. In Sec ion 4, we desc ibe he ac ion appa a us and decision a ionale o agen s based on he p incipal-agen model. Then, in Sec ion 5, we pu o - wa d a model o es ablish and adjus incen i es in o de o main ain s anda ds o e ime. Di e en sea ch algo i hms a e p oposed in his ega d. Sec ion 6discusses he need o eo ganiza ion and desc ibes a a ionale and an app oach o unde ake i . We e alua e ou p oposals and p esen empi ical esul s in Sec ion 7. Sec ion 8p o ides a c i ical discussion o he con ibu ions o his pape and compa es i wi h o he ela ed app oaches in he li e a u e. Finally, we conclude and ske ch ou planned u u e wo k in Sec ion 9. 2 Rela ed wo k This pape p oposes an app oach o ackle open and dynamic en i onmen s, based on he no ions o ole and s anda d. Social coo dina ion is a e y ac i e opic in he mul i-agen sys ems esea ch communi y. The need o app oaches o ackle he open and dynamic na u e o mul i-agen en i onmen s has gi en ise o complemen a y app oaches ha b ing in o his ealm concep s om di e se ields, such as social, o ganiza ional, legal, o beha iou al sciences. The concep o ins i u ion has been bo owed om eco- nomics (No h 1990) and philosophy (Sea le 1995)in wo di ec ions. On he one hand, o p o ide egula ed en i- onmen s consis ing o compu a ional in as uc u es ha ame agen in e ac ions (as e.g. in Es e a e al. (2001)and Lopes Ca doso and Oli ei a (2008)). On he o he , o p o- ide seman ics o agen in e ac ions in e ms o coun s-as ela ions (Jones and Se go 1996; Fo na a e al. 2008). Wi hin hese egula ed en i onmen s he no ion o no ms (Boella e al. 2006) has been exploi ed, as a means o explic- i ly s a e wha o expec om each agen in he sys em. Social no ms (Tuomela 1995) a e based on mu ual belie , consis ing o con en ions (Walke and Woold idge 1995; Con e and Cas el anchi 1999) ha may apply o a la ge g oup o agen s. The speci ica ion o oles (Hubne e al. 2002;Fasli2006; He moso e al. 2010) ha agen s enac in a gi en soci- e y goes in he same di ec ion o making a sys em mo e p edic able in e ms o expec ed beha iou (Winiko and C ane ield 2009). Explici ly handling such expec a ions as no ms (Cas el anchi e al. 2003) allows one o make ole enac ing agen s accoun able o hei ac ions. Al hough closely associa ed wi h some app oaches on he use o no ms, he no ion o commi men (Singh 1999; Fo na a and Colombe i 2003;Fasli2003) emphasizes a delibe a i e iew on no m adop ion: agen s commi o his as a esul o hei delibe a ion p ocess, as opposed o a op- down iew on he use o no ms as a design ool o de ining ules o beha iou in an in e ac ion en i onmen . Wha seems o be missing om hese a i ac s o social coo dina ion is some concep o expec a ion ha is bo h measu able and non-commi ing. Unlike commi men s o In Sys F on no ms, we pu sue a means o es ablishing how well an agen is able o pe o m wi hou ac ually being commi ed o. And unlike con en ions, which ypically apply o collec i e beha iou , we a e in e es ed in measu ing he ou come o ask execu ions. In o de o ill his gap, we use he concep o s anda d. In he li e a u e, one can ind a wide a ie y o wo ks ha adop he concep o s anda d o di e en pu poses. The de ini ion o s anda d is gi en by he Ox o d Dic iona y o English1as: “(noun) 1. a le el o quali y o a ainmen ; 2. some hing used as a measu e, no m, o model in com- pa a i e e alua ions; (adj.) 3. used o accep ed as no mal o a e age”. The e o e, s anda ds desc ibe le els o qual- i y ha a e ecognized o be no mal by indi iduals wi hin a ype o sys em. S anda ds come abou ei he imposed o eme ge as de ac o a e a numbe o obse a ions. Following his dis- inc ion, s anda ds may be classi ied as de ju e o de ac o s anda ds (Salg´e2005). The o me a e egula ions accep ed and obliged by law, and a e endo sed by a o mal s anda ds o ganiza ion. An example o his ype o s anda ds a e IEEE o ISO s anda ds o many di e en pu poses. In con as , de ac o s anda ds a ise when a c i ical mass simply ag ees o use hem in a pa icula en i onmen . Fo example, PDF became a de ac o s anda d o p in able web documen s, al hough i u ned in o a de ju e s anda d as ISO 19005-1 in 2005. In his pape , we wo k on de ac o s anda ds in o de o cap u e he measu ed pe o mance o a se o indi iduals. In he ield o economics, we can ind many app oaches dealing wi h s anda ds. In Busch (2000), Busch sugges s ha s anda ds a e mis akenly conside ed o be me e con e- nien echnologies o o ganizing and egula ing ma ke s so as o educe ansac ion cos s (howe e he cos is assessed). Ne e heless, he au ho a gues ha s anda ds a e pa o he mo al economy o a socie y, since hey also egula e beha iou . The e o e, s anda ds c ea e uni o mi y in he - e ogeneous con ex s. Following up he economic app oach, Mu phy claims ha pe o mance s anda ds eme ge om he desi e o p o ide incen i es while simul aneously paying compe i i e expec ed le els o compensa ion (Mu phy 2000). Tha is, pe o mance s anda ds can be used in o de o gauge he adequacy o an indi idual’s pe o - mance, so p omp ing he possibili y o o e ing incen i es i beha iou al de ia ion exis s. F om a psychological poin o iew, Bandu a and Wood (Bandu a and Wood 1989) claim ha when people belie e he en i onmen is con ollable on ma e s o impo ance o hem, hey a e mo i a ed o pe - o m as well as hey can, which en ails an inc ease in he likelihood o success (o socie al sa is ac ion). Mo eo e , success ul expe iences, in u n, p o ide a sel - alida ion 1h p://ox o ddic iona ies.com/ on he e icacy o he indi idual and o he en i onmen- al con ollabili y. On he con a y, i people ace si ua ions hey belie e as being uncon ollable, hey a e likely o pu in less e o , and his b ings abou ailu e. Consequen ly, o e ime, ailu es ake an inc easing oll on pe cei ed sel - e icacy and belie s abou how much en i onmen al con ol is possible (Bandu a and Wood 1989). This au ho claims ha a es o success and ailu e a e la gely de e mined by he s anda ds agains which a ainmen s a e gauged. The e- o e, in layman’s e ms, pe o mance s anda ds a e used in o de o induce collabo a i e beha iou om coun e - pa s engaged in an in e ac ion. Howe e , as we s a e in his pape , pe o mance s anda ds pe se a e no su icien o keep indi iduals om pe o ming inadequa ely. This ea- u e d i es us o in oduce he concep o incen i e as a means o main aining he pe o mance s anda ds. How s an- da ds a e c ea ed has been s udied by many esea che s om di e en ields as well. This p ocess is called s an- da d se ing and conce ns he me hods o build s anda ds om he in o ma ion a ailable (o po en ially a ailable) in he sys ems (Cizek and Bunch 2007). The e exis s a wide ange o app oaches wi h ega ds o s anda d se ing, om educa ional pu poses (Hamble on e al. 2000) o medical e alua ions (Sou hga e e al. 2001). 3 C ea ing s anda ds om oles Due o he non-s a iona y na u e o open sys ems, in his pape , we add ess he p oblem o how o main ain agen s om a pe o mance quali y pe spec i e as de e mined by he oles hey a e playing. We claim ha he no ion o spe- cialized ole p oposed in He moso e al. (2013) migh be used o es ablish pe o mance s anda ds and so acili a e he ag eemen on commi men s among agen s. We he e o e en ision he possibili y o going om oles as expec a ions o beha iou (Winiko and C ane ield 2009) o pe o - mance (He moso e al. 2013) o he explici handling o such expec a ions as de ac o s anda ds ha may be commi ed o. S anda ds a e he e o e no imposed by he sys em, bu p omo ed a e hey ha e been iden i ied as cu en p ac ice among a g oup o agen s. S anda ds may hus be exploi ed o ind app op ia e agen s, gi en ha hey a e based on e idence abou hei ac ual capabili ies. The a ionale behind c ea ing and main aining pe o - mance s anda ds elies on he concep o ole p oposed by He moso e al. (2013). In his wo k, he au ho s claim ha in open sys ems he e olu ion o he popula ion should en ail ha o ganisa ional s uc u es e ol e as well. Fo ins ance, some o he oles ha exis ed in ou socie y wo cen u ies ago, no longe exis nowadays. The e o e, oles a e some- how linked o he di e en needs o he popula ion a a ce ain poin in ime. Wi h his idea in mind, he au ho s In Sys F on de ine oles as en i ies ha g oup a se o agen s ha ou - pe o m o he s o a ce ain se o asks. Fu he mo e, hey in oduce he concep o specialisa ion, om which oles a e c ea ed as specialisa ions o mo e gene al oles; e.g. he ole su geon is c ea ed as a specialisa ion o he ole doc- o , because hose playing he o me ( hey also play he ole doc o ) a e be e skilled o asks such as ope a e. Thus, he au ho s p opose ha any socie y o agen s may be co e ed by an o e lay ole axonomy o med by ex ac ing capabili ies and us ela ionships among agen s o e ime. The mechanism e ol es he socie y’s ole axonomy, assigning agen s o oles. Then, oles o he ha agen s a e playing in he sys- em p o ide in o ma ion abou hei expec ed capabili ies ega ding ce ain in e ac ions (e.g. he p o isioning o ce - ain se ices o asks). The au ho s assume ha agen s pa icipa ing in he sys em a e a ional, ha is, hey beha e as u ili y maximise s. Thus, he main ask o he mech- anism is wo old: i) o cap u e simila beha iou among pa icipan s ha play a ole; and ii) o manage he ole ax- onomy ha s uc u es di e en posi ions o agen s in he sys em. The mechanism uses a clus e ing algo i hm o iden- i y pa e ns o beha iou , so dis inguishing hose agen s ou pe o ming o he s.0 This mechanism has been exhaus- i ely es ed in di e en condi ions wi h open ask-o ien ed mul i-agen sys ems wi h he e ogeneous and dynamic pop- ula ions, showing a signi ican ly good adap a ion in o de o p o ide an e icien ole axonomy ha imp o es agen s’ pa ne selec ion. The mechanism in He moso e al. (2013) elies on he de ini ion o a Task-o ien ed Mul i-Agen Sys em (T-MAS) as a mul i-agen sys em in which pa icipan s ha e o pe - o m a se o asks (He moso e al. 2013). I is de ined by a se o pa icipan s Ag,ase o asksTand a ole axonomy . We will use he no ion o T-MAS h oughou he pape as he base o ou app oach. The ole axonomy e lec s, a a gi en ime, which agen s a e mo e skilled in he sys em o pe o m di e en asks. As he p ocess o ole axonomy e olu ion is cos ly, in his pape , we ocus on he pe iod among wo consecu i e e olu ions. Gi en a ole axonomy, we will ex ac pe o - mance s anda ds om he oles in i . These s anda ds will eme ge as an indica o o wha is expec ed om he g oup o agen s ( he ones playing a speci ic ole) o a pa icula ask. Thus, s anda ds will be used by agen s as an an icipa- o y measu e on he likely ou come o in e ac ions, and may be used in u he nego ia ions o assu e a ce ain quali y o pe o mance. S anda d se ing p ocess Le A ={a 1,a 2, ..., a n} be he se o a ibu es ha cha ac e izes a ask in T.Fo ins ance, in an e-comme ce domain A ={deli e y ime, quali y ype}would be a se o a ibu es ha migh cha ac e ize he ask supply good.Le xibe a alue o he a ibu e a i. Fo example, xdeli e y ime =5means ha he alue o he a ibu e deli e y ime is 5. Thus, le us de ine he concep o s anda d: De ini ion 1 As anda d ςis a uple  , , xi ha es ab- lishes, o a ole and a ask , a ce ain expec ed le el o quali y xi o he a ibu e a iin . No e ha he concep o s anda d e e s only o one a ibu e o he ask. Tha is, he same ole and he same asks migh ha e di e en s anda ds o di e en a ibu es. Following up he example gi en abo e, he s anda d o deli e y ime migh be 5 while he s anda d o quali y ype migh be 3. The le el o quali y o di e en a ibu es is mean o be a a ge (xi) ep esen ing he expec a ion an agen pe o m- ing a ask gene a es on i s coun e pa s. In o de o a oid ou app oach being domain-dependen , we ake his no ion o a ge ed s anda d o be as abs ac as possible; ha is, we canno s a e a p io i in which si ua ions (in any ype o domain), highe o lowe ou comes ( ega ding he s anda d alue) b ing abou be e o wo se ou comes. As we will u - he explain in Sec ion 4.1, a beha iou showing a de ia ion exceeding he s anda d is equally ha m ul han he one ha does no each i . Thus i he s anda d o deli e y ime is 5 days and a p o ide akes 7 days deli e ing a p oduc , ha is conside ed as undesi able as p o iding he p oduc in 3 days. Al hough his would seem o be a bi coun e -in ui i e, deli e y in ad ance migh mean no s o age oom o he new p oduc s, while la e deli e y migh en ail ha he p oduc ion line will be hal ed. In his pape , we claim ha once he ole e olu ion mechanism desc ibed abo e is in place, oles may be used o c ea e s anda ds which, in u n, could be included in commi men s ha egula e in e ac ions in he sys em. The unde lying idea elies on he agg ega ion o alues o di e - en a ibu es ha cha ac e ize ( he pe o mance o ) a ask wi hin he ole, o es ablish a s anda d o ha ole/ ask pai , as de ined in de ini ion 1. Fo ins ance, in open elec- onic ma ke s (e.g. eBay), oles migh be c ea ed in o de o place p o ide s in di e en ca ego ies o p o ision, while s anda ds would eme ge in o de o acili a e be e in e - ac ion p ocesses, and so p e en agen s om exhibi ing undesi able beha iou s, such as longe deli e y imes, p ice changes, dec ease o quali y, e c. Mo e p ecisely, le us sup- pose we ha e he ole Bike P o ide wi h, among o he s, he a ibu es deli e y ime and quali y ype.Le a1,a2and a3 be h ee agen s playing he ole, wi h a e age deli e y imes o 3, 4 and 5, espec i ely. Then we could use an agg e- ga ion unc ion (e.g. an a e age) o ex ac a s anda d o he ask as ς= =Bike P o ide , =P o ide Bikes ,x deli e y ime =4. Using an a e aging unc ion may make In Sys F on sense i we ake in o accoun ha he clus e ing mechanism ob aining he ole axonomy will, in p inciple, ge us oles wi h high cohesion – o which no much de ia ion should be expec ed in he beginning. 4 Incen i es and he p incipal-agen model A e explaing he pa h om oles as expec a ions o commi men s based on s anda ds, we a e now in a posi- ion o elabo a e on en o cemen schemes ha enable us o main ain he s abili y o he ole axonomy, which is ob ained as explained in Sec ion 3. We will base ou app oach on he well known p incipal-agen model (La on and Ma imo 2002; Caillaud and He malin 2000) om economics, in which a p incipal (a se ice eques e ) eques s an agen ( he p o ide ) o pe o m a speci ic ask. The ou come o he ask execu ion a ec s he p incipal’s u ili y, who will he e o e be in e es ed in in luencing he e o s ha he agen pu s in pe o ming he ask. E o s a e exp essed in e ms o a ailable ac ions, which ha e associa ed execu ion cos s. In he so-called hidden ac ion se ing (Caillaud and He malin 2000), i is assumed ha he ac ual ac ions as execu ed by he agen a e unobse able o he p incipal. Ins ead, only some pe o mance measu es o such ac ions a e obse ed. Ac ions de e mine, usually s ochas ically, he ob ained pe o mance. Pe o mance is he e o e a andom a iable whose p obabili y dis ibu ion depends on he ac ions aken by he agen . This s ochas- ic na u e cap u es he ac ha he e a e ex e nali ies in he en i onmen ha he agen has no con ol o e . The p incipal will he e o e wan o es ablish an incen i e sched- ule in o de o encou age he agen o choose he ac ions be e leading o an in ended pe o mance s anda d. In ou app oach, we sligh ly change he model by pu ing o wa d a new en i y – an incen i e policy make in cha ge o c ea ing and applying incen i e schedules o keep agen s con o ming o di e en s anda ds. In o he wo ds, i is no he p incipal (consume o he se ice), bu his policy make who se s and applies incen i es o he agen s (p o ide s). 4.1 Ta ge ing s anda ds As desc ibed in Sec ion 3, s anda ds a e gene a ed h ough he use o an a e aging unc ion applied o ask execu- ion ou comes o a g oup o p o ide agen s ha ha e been clus e ed wi hin a speci ic ole. Since, acco ding o ou model, s anda ds allow eques e s o iden i y expec ed al- ues o he ou comes o asks when execu ed by a speci ic p o ide , we conside a s anda d as a a ge ha agen s should mee . Any de ia ion om he s anda d is conside ed as a sub-op imal ou come. Figu e 1illus a es his no ion, whe e ς ep esen s he a ge s anda d ha he eques e ϛ 1 2 3 Fig. 1 A s anda d as a a ge would expec , and each concen ic ci cle labelled wi h a δideno es equidis an pe o mances o he a ge . These concen ic lines highligh he ac ha we shall conside de ia ions in any di ec ion (le o igh , upwa ds o down- wa ds) o be equally ha m ul in e ms o expec ed alues. The a ow poin ing owa ds he cen e discloses he aim o ou incen i e-based app oach, wi h which we will y o encou age p o ide s o be e a ge he s anda d. 4.2 Ac ions and ou comes In ou model, we will assume ha each p o ide has a se o ac ions a i s disposal, each wi h a cos and a p obabil- i y unc ion o ob aining di e en pe o mance ou comes. Following a ini e model o ac ions and ou comes, we ha e ha : De ini ion 2 The p o ide has a se o possible ac ions A= {a1, ..., an}a i s disposal, each ha ing an associa ed cos , deno ed by Cos (ai). De ini ion 3 The possible obse able ou comes ha he p o ide may ob ain is an o de ed se Xa ={x1, ..., xm}. No e ha Xa is he se o possible alues o measu ing he pe o mance o he ask being e alua ed a he a ibu e a . Fo he sake o simplici y, om now on we ake in o conside a ion only one o he a ibu es o he ask, in o de o minimise he complexi y in no a ion. Then, X e e s o a Xa o wha e e a ibu e we a e e alua ing in he ask. De ini ion 4 The e is a p obabili y dis ibu ion unc ion o Xgi en an ac ion in A,whe ep(xk|ai)is he p obabili y o In Sys F on ob aining ou come xk∈Xwhen pe o ming ac ion ai∈A. We ha e ha m k=1p(xk|ai)=1, o all i∈[1,n],whe e mis he numbe o possible ou comes and nis he numbe o ac ions. 4.3 Incen i es Gi en he ac ha only ou comes, and no e o s, a e obse able o he p incipal, incen i es a e speci ied h ough an incen i e schedule mapping possible ou comes o incen- i e alues o be collec ed by he p o ide , acco ding o De ini ion 5. De ini ion 5 An incen i e schedule I:X→Imaps each possible ou come in X o a speci ic incen i e alue in I. We look a incen i es as p oducing some change in he u ili y he agen would ob ain by showing i s na u- al beha iou i no incen i es we e in place. In his sense, I={ι:ι∈[−1,1]}, whe e posi i e alues deno e pe cen age inc eases in u ili y and nega i e alues deno e pe cen age dec eases in u ili y. When ι=0 he e is no incen i e in place. The e o e, posi i e incen i es a e consid- e ed as ewa ds o agen s o os e he pe o mance o he ac ions he incen i e is applied o, while nega i e incen i es ep esen an a emp o discou age agen s om pe o ming non-desi ed ac ions. 4.4 P o ide s decision a ionale Based on he s ochas ic model o ac ion ou comes explained abo e, each p o ide is assumed o be an expec ed u ili y maximize agen . The e o e, when choosing he ac ion a o pe o m i will seek o maximize expec ed u ili y (Von Neumann and Mo gens e n 1980): a gmax a∈A Ea= m  i=1 [p(xi|a) ·u(xi,I(x i))]−Cos (a) (1) whe e u(xi,I(x i)) is he u ili y he agen ge s om ob ain- ing pe o mance ou come xi, aking in o accoun he incen- i e I(x i)i will ge om such a pe o mance. We de ine unc ion u(·,·)as ollows: u(x, ι) =u(x) ·(1+sens(ι)) (2) This unc ion encompasses wo sub- unc ions: he p io u il- i y u(x) collec ed acco ding o he ou come xob ained, and he e ec on his u ili y o he incen i e alue ιapplied. We model such an e ec wi h a sensi i i y unc ion sens :I→ [−1,1], which ansla es an incen i e alue o i s ac ual pe cei ed impac on he u ili y o he agen : sens(ι) =2 1+e−ι·B−1(3) Pa ame e B∈N+allows us o une he sensi i i y o he agen wi h espec o incen i es: highe B alues make he agen mo e sensi i e o incen i es, while wi h lowe ones he agen will end o beha e he same ega dless o any incen i es. Figu e 2shows some examples o Eq. 3 o model sens(ι) wi h di e en B alues. When p o ide s a e no o e ed any incen i e, hey simply ob ain he p io u ili y u(x) as a esul o Eq. 2. Nega i e incen i es (punishmen s) diminish he u ili y o he p o ide , whils posi i e incen i es inc ease i . Fig. 2 Di e en cu es o Eq. 3, a ying B In Sys F on 5 Main aining pe o mance s anda ds h ough incen i es Gi en he p e ious pe o mance o each p o ide , on which s anda ds ( ia oles) ha e been de ined (as desc ibed in Sec ion 3), i may be he case ha agen s de ia e om he s anda d hey we e able o mee be o e. This is due o he e ol ing na u e o he en i onmen in which he agen ope a es. Since agen s a e expec ed u ili y maximize s, hei decision ega ding which ac ion o employ when execu ing a ask is condi ioned by a numbe o ac o s, which we can iden i y by analysing Eq. 1. Any changes in hese ac o s a e hus possible causes o a de ia ion om he s anda d cha ac e izing each agen ’s assigned ole: 1. Cos s o he ac ions agen s ha e a hei disposal; 2. E ec i eness o a ailable ac ions, ha is, hei p oba- bili y dis ibu ions o e pe o mance ou comes; 3. P io u ili ies ha agen s ge om ob aining each possi- ble ou come; 4. Sensi i i y o agen s wi h espec o any incen i es hey may be o e ed. No e ha changes in sensi i i y a e only ele an when he e a e al eady incen i es in place. Changes in ac ion cos s may lead he agen o apply less cos ly ac ions, whose ou comes may be di e en . Changes in he e ec i eness o ac ions may be due o en i onmen al ac o s no unde he con- ol o he agen . In his pape , we assume agen s somehow become awa e o changes in any o hese ac o s in o de o ake hem in o accoun when deciding which ac ions o pe o m. We can easily hink o ex e nal ac o s causing hese changes. Fo ins ance, in a supply chain, luc ua ions on p ices o di e en inpu s (e.g. pa s o aw ma e ials ob ained om supplie s) will ce ainly in luence he cos o execu ing he ask. As o ou come p obabili ies, he agen may be able o upda e hese es ima ions on-line, acco ding o un- ime expe ience. These de ia ions in pe o mance ende he ole clus e - ing (ob ained as desc ibed in Sec ion 3) un i o ep esen he cu en pe o mances o agen s in he sys em, in e ms o he s anda ds ex ac ed om he oles. The e o e, in o de o main ain ole s abili y when agen s de ia e om ag eed s anda ds, he sys em may de e mine and employ an app op ia e incen i e schedule I:X→I(see de ini ion 5). Since ac ions a e no obse able, his schedule is based exclusi ely on he measu able ou comes o ask execu ion, which o he sake o de ining app op ia e incen i e sched- ules a e compa ed wi h he a ge ou comes cha ac e izing he oles. The incen i e policy make (IPM) does no ha e access o he ac o s in luencing he agen s’ decision making as his is conside ed o be p i a e in o ma ion. The goal o he IPM is o keep on a ge he agen s playing a speci ic ole, i.e., agen s should ob ain ou comes as close as possible o he a ge ou come o he ole. We assume he IPM p e e s o achie e his aim wi h he leas incen i es needed. In case o ailu e o accomplish his aim, o i by doing so he IPM has o apply a oo cos ly incen i e schedule, hen i is ime o somehow eo ganize he agen s ha a e seen as no longe being able o pe o m he ole a a bea able cos . This is he opic o Sec ion 6. 5.1 Cos -e ec i e incen i e schedules Gi en an incen i e schedule o e ed o he agen s play- ing a speci ic ole, we may de e mine i s e ec i eness by looking a he ou comes ha a e ob ained once ha sched- ule is in place. We should also ake in o accoun he cos o applying he incen i e schedule. Gi en he s ochas ic na u e o agen e o s in e ms o ob ained ou comes, an incen i e schedule’s e ec i eness will ypically oscilla e a ound some alue, ega dless o he e being any changes in he en i onmen ha lead agen s o change hei chosen ac ions. Fo his eason, in o de o compu e an incen i e schedule’s quali y Q(I), we agg ega e a sequence X= x1,x2,...,xnoo noob ained ou comes (xi∈X), and compa e hem wi h he a ge ou come x∗. We de ine Q(I) as: Q(I) =ω· a ge Hi (X) −(1−ω) · o alCos (I, X) (4) a ge Hi (X) =no− no  i=1 |xi−x∗|(5) o alCos (I, X) = no  i=1 |I(xi)|(6) The o al cos o he incen i e schedule akes in o accoun ac ually paid incen i es, which depend on he ou comes ob ained. By using he modulus o he incen i e we seek o gi e he same weigh o paid o collec ed incen i e al- ues – wi hou he modulus he IPM would end o p e e penalizing p o ide s as opposed o paying hem incen i es o o simply s and s ill. We hus ha e ha o alCos (X) ∈ [0,n o]. On he o he hand, a ge hi measu es he incen- i e schedule’s e ec i eness in inducing agen s o mee he a ge . Any alues ou side he a ge a e seen as de ia ions ha need o be minimized in e ms o ole main enance – o simplici y we assume X⊂[0,1], which en ails a ge Hi (X) ∈[0,n o]. Combining hese wo unc ions, we ha e Q(I ) o be wi hin he ange [((ω −1·no), ω ·no]. Fac o ω∈[0,1]allows us o balance he ela i e impo - ance o hese wo con lic ing goals, e.g., by gi ing p io i y o ob ained pe o mance o e how much i cos s o achie e i in e ms o incen i es paid. In Sys F on 5.2 Sea ch space Incen i e schedules speci y, o each x∈X, an incen i e alue ι∈I. We can he e o e ep esen an incen i e sched- ule as a ec o ι=[ι1, ..., ιm],whe em=|X|is he numbe o possible obse able ou comes (see de ini ion 3) and each ιi∈I. In he ques o ind ou he bes incen i e sched- ule, measu ed bo h in e ms o e ec i eness and cos , we need o educe he sea ch space o he IPM, e.g. by limi ing he sea ch o incen i e schedules composed o alues wi hin he se I·10/10, which gi es us disc e e incen i e alues wi h 0.1 s eps. Depending on he numbe o ou comes o conside , his may s ill gi e us a huge numbe o schedules o expe i- men wi h. We can sligh ly alle ia e his issue by aking in o accoun he in ui i e heu is ic ha we should p omo e ou comes close o he a ge no less han ou comes a - he away. Using his p inciple, he numbe o incen i e schedules a ailable is gi en by C|I|+|X|−1 |X|=(|I|+|X|−1)! (|I|−1)!|X|! Table 1shows he numbe o incen i e schedules acco ding o di e en sizes o he ou comes se , and aking |I|=21 (which is he size o se I·10/10 when conside ing I= {ι:ι∈[−1,1]}). As we can see, e en when conside ing a small numbe o ou comes, he numbe o incen i e sched- ules is qui e la ge, g owing exponen ially as |X|inc eases. No ice ha applying a single incen i e o he a ge ou - come may comp ise a subop imal solu ion. On one hand, he IPM does no know how p ecise a e he ac ions cho- sen by he agen s, which means ha he ac ion mos likely ob aining he a ge ou come may s ill be qui e noisy. On he o he hand, cheape incen i e schedules may be ound by aking in o accoun a combina ion o incen i es o di e en ou comes. Table 1 Numbe o incen i e schedules o a ying |X| |X|Numbe o incen i e schedules 2 231 3 1771 4 10626 5 53130 6 230230 7 888030 8 3108105 9 10015005 10 30045015 5.3 Finding app op ia e incen i e schedules Unlike ypical app oaches in game heo y, we do no assume ha agen s’ decision a iables (ac ion cos s, hei p obabil- i y dis ibu ions o e ou comes, o u ili y unc ions on hose ou comes and any employed incen i es) a e known o he incen i e policy make . We he e o e need o go h ough he sea ch space o possible incen i e schedules in o de o ind he ones ha p o e o be mo e cos -e ec i e, by ac u- ally ying hem ou . Gi en he high numbe o schedules o expe imen wi h, some heu is ics a e needed o guide he sea ch. In he ollowing sec ions we in oduce h ee app oaches o sea ching o an app op ia e incen i e schedule. An impo an ea u e o hese app oaches is ha hey a e mean o wo k on-line: he IPM will be sea ching o he mos cos -e ec i e incen i e schedule, while a he same ime y- ing o maximize he accumula ed quali y o he incen i e schedules ha a e ac ually employed. We should men ion a his ime ha i is no ou pu pose o p opose a bes al e na i e in e ms o sea ch s a egies, bu ins ead o compa e a ew app oaches and see how hey a e in e ms o some measu able c i e ia. One such c i e ion is ela ed wi h how each app oach is able o a oid ealloca- ion o agen s o o he oles (which is u he explained in Sec ion 6). 5.3.1 On-line local sea ch Gi en he high numbe o schedules o expe imen wi h, in his sec ion we ollow a local sea ch app oach o seek an op imal incen i e schedule. Mo e speci ically, we employ a hill-climbing p ocedu e, by successi ely ying o ind ou neighbou ing incen i e schedules ha a e be e han he cu en ly employed one. In o de o ind hem, howe e , we need o y ou incen i e schedules be o e we know how wo hy hey a e, which makes he sea ch mo e s ochas ic. Fu he mo e, gi en he dynamics o he en i onmen , hese quali y alues a e no cons an o e ime, and hus explo- a ion mus always be an op ion once a change is de ec ed in he en i onmen . One c ucial aspec o local sea ch algo i hms is he de ini ion o he neighbou hood unc ion. To gene a e he neighbou s o an incen i e schedule, we in oduce a s ep change (upwa ds o downwa ds) in he incen i e alue being applied o any o he ou comes. We hen co ec he schedule ob ained so ha ou comes close o he a ge ha e a leas he same incen i e as ou comes a he away (as men ioned in Sec ion 5.2). This gi es us a ca dinali y o a mos 2 ·|X| in he se o neighbou s o each possible schedule. The local sea ch p ocedu e is illus a ed in Algo i hm 1. A each s ep, we s a by checking i we a e applying he incen i e schedule ha is known o be he bes (line 2): In Sys F on i yes, we upda e i (line 6). I we a e applying a di e - en incen i e schedule (lines 7-10), we compa e he cu en schedule wi h he bes known (line 7), and upda e i i is be - e (lines 8-9). Then we andomly explo e, wi h p obabili y 1−e(||bes Q||−1)·τ(line 11), he neighbou so he bes sched- ule (line 12): ||bes Q|| is he no malized alue o bes Q o he ange [0,1],andτis a empe a u e pa ame e . The be - e he schedule is, he less likely we will explo e, exploi ing ins ead he bes schedule we know o (line 14). When a sig- ni ican change is de ec ed in he en i onmen , measu ed in e ms o a dec ease in he quali y o he bes known schedule (line 3), we p omo e explo a ion by ese ing he empe a u e τ(line 4); τis hen decayed in e e y s ep (line 16) acco ding o he ime we allow he sea ch o p o- ceed (see Sec ion 6), un il i eaches nea ly 0 (de e mining no explo a ion).2 In o de o compu e he quali y o each incen i e sched- ule we need o employ i su icien ime o agg ega e new e idence o ill in sequence X(see Eq. 4). 5.3.2 On-line abu sea ch The sea ch space we a e dealing wi h is qui e pla eaux-like, gi en he ac ha many neighbou s o a gi en schedule will ha e he same exac quali y. This is a challenge o an app oach based on hill-climbing, such as he one p esen ed 2No e ha his empe a u e mechanism is no ela ed o simula ed annealing, in which he empe a u e de e mines he p obabili y o choosing a wo se solu ion; in Algo i hm 1 we use i simply o induce and hen o educe explo a ion, while a new schedule will only be kep i i is ound o be be e han he bes we know o (hence he hill-climbing la ou ). in Sec ion 5.3.1. One well-known echnique o ackle such kind o sea ch spaces is abu-sea ch, which we explo e in his sec ion. Tabu-sea ch includes a lis o o bidden nodes (schedules) wi h he aim o escaping local-op ima. Algo i hm 2 shows ou app oach. The abulis con ains a small numbe o he mos ecen ly isi ed incen i e sched- ules; whene e we add an elemen o his lis (line 13), i he numbe o elemen s exceeds i s size we disca d he mos ou da ed one (in a i s -in- i s -ou ashion). Besides keep- ing he bes schedule ound so a , we also keep he poin om which we will con inue he sea ch, by ollowing one o i s neighbou s ha a e no in he abu-lis (line 12). The emaining pa s o he algo i hm a e simila o Algo i hm 1. 5.3.3 Rein o cemen lea ning Lea ning on-line, i.e. by in e ac ing wi h he en i onmen and ob aining app op ia e ewa ds, is he aim o ein o ce- men lea ning (RL) (Su on and Ba o 1998). In his sec ion, we look a he p oblem o sea ching o an op imal incen i e schedule as a ein o cemen lea ning p oblem. Mo e speci - ically, he se ing we a e add essing is simila o an n-a med bandi p oblem (Su on and Ba o 1998). The incen i e pol- icy make ( he lea ne ) will y o de e mine, by explo ing i s ac ion3se , he bes possible incen i e schedule Iwhose 3We emphasize ha hese a e he lea ne ’s ac ions (i.e., hose a ailable o he IPM), and no he ac ions o he p o ide agen as discussed in Sec ion 4.2.Wehe euse hesame e mac ion because i is well es ablished in RL li e a u e. In Sys F on he ieee wo kshop on dis ibu ed in elligen sys ems: Collec i e in elligence and i s applica ions, DIS ’06. IEEE Compu e Soci- e y, Washing on, DC, (pp. 315–320). Salg´e, F. (2005). Na ional and in e na ional da a s anda ds. In: P.A., Longley M.F., Goodchild D.J., Magui e D.W., Rhind (Eds.) In Geog aphical in o ma ion sys ems. p inciples, echniques, man- agemen and applica ions. 2nd edn. John Wiley, New Yo k, (pp. 693–706). Sea le, J.R. (1995). In The Cons uc ion o Social Reali y.NewYo k: F ee P ess. She s yuk, K. (2000). Pe o mance s anda ds and incen i e pay in agency con ac s. Scandina ian Jou nal o Economics,102(4), 725–736. Singh, M.P. (1999). An on ology o commi men s in mul iagen sys ems: Towa d a uni ica ion o no ma i e concep s. A i icial In elligence and Law,7(1), 97–113. Sou hga e, L., Hays, R.B., No cini, J., Mulholland, H., Aye s, B., Woollisc o , J., Cusimano, M., McA oy, P., Ainswo h, M., Hais , S., Campbell, M. (2001). Se ing pe o mance s anda ds o med- ical p ac ice: a heo e ical amewo k. Medical Educa ion,35(5), 474–81. Su on, R.icha d.S., & Ba o, A.nd ew.G. (1998). In Rein o cemen Lea ning: An In oduc ion. Camb idge: The MIT P ess. Ta akoli a d, M., Knapskog, S.J., He mann, P. (2008). C oss-si ua ion us easoning. In P oceedings o he 2008 ieee/wic/acm in e - na ional con e ence on web in elligence and in elligen agen echnology - olume 03, WI-IAT ’08. IEEE Compu e Socie y, Washing on, DC, USA, (pp. 67–71). Tuomela, R. (1995). In The Impo ance o Us: A Philosophical S udy o Basic Social No ms. S an o d: S an o d Uni e si y P ess. U bano, J., Rocha, A.P., Oli ei a, E. (2011). In T ansac ions on compu- a ional collec i e in elligence , (pp. 84–105). Be lin, Heidelbe g: Sp inge -Ve lag. Von Neumann, J., & Mo gens e n, O. (1980). In Theo y o Games and Economic Beha io , 3 d edn. P ince on: P ince on Uni e si y P ess. Walke , A., & Woold idge, M. (1995). Unde s anding he Eme gence o Con en ions in Mul i-Agen Sys ems. In: V., Lesse & L., Gasse (Eds.) In P oceedings o he i s in e na ional con e ence on mul i-agen sys ems. MIT P ess, San F ancisco, (pp. 384–389). Winiko , M., & C ane ield, S. (2009). Elici ing expec a ions o moni o ing social in e ac ions. In P oceedings o he i s in e - na ional con e ence on compu e -media ed social ne wo king, ICCMSN’08. Sp inge , Be lin Heidelbe g New Yo k, (pp. 171– 185). Ramn He moso is an assis an p o esso a he Uni e si y o Za agoza. Fo me ly, he wo ked as a senio esea ch o ice a he Uni- e si y o Essex and as an assis an p o esso a he Uni e si y Rey Juan Ca los in Mad id (Spain). He ecei ed his PhD om he Uni e - si y Rey Juan Ca los in 2011. His esea ch in e es s span om us and epu a ion mechanism in mul iagen sys ems o he inno a ion man- agemen in social ne wo ks. He is au ho o se e al publica ions in jou nals, books and in e na ional con e ences, and has pa icipa ed in mo e han 15 esea ch p ojec s, unded by bo h na ional and in e na- ional ins i u ions. He has been in ol ed in o ganising in e na ional e en s and pee e iewing o in e na ional jou nals, con e ences and wo kshops. Hen ique Lopes Ca doso ob ained his PhD on In o ma ics Enginee - ing om he Uni e si y o Po o in 2011. He is an Assis an P o esso a he Facul y o Enginee ing o he Uni e si y o Po o (FEUP) and a esea che a he A i icial In elligence and Compu e Science Lab (LIACC). He is also a membe o he di ec i e boa d o he Po uguese Associa ion o A i icial In elligence (APPIA). His esea ch in e es s include dis ibu ed AI, social coo dina ion and egula ion o mul i- agen sys ems, adap i e lea ning agen s, and mul i-agen sys ems ools. He has been an ac i e membe o ele an Eu opean esea ch ne wo ks, namely he COST Ac ion IC0801 on Ag eemen Technologies and he Eu opean Ne wo k o Social In elligence (SINTELNET). Ma ia Fasli is a P o esso in he School o Compu e Science and Elec onic Enginee ing, Uni e si y o Essex whe e she has been a membe o s a since 1999. He esea ch in e es s lie in agen s and mul i-agen sys ems and hei heo e ical ounda ions and p ac ical applica ions, machine lea ning, analysing and modelling complex da a (s uc u ed/uns uc u ed), Big Da a, as well as seman ic-based ech- niques o use p o iling and adap a ion including modelling con ex . She has published in jou nals and in e na ional con e ences and spe- cialis s wo kshops in he ield o a i icial in elligence and mul i-agen sys ems and has pa icipa ed in in e na ional compe i ions such as he T ading Agen Compe i ion. She has been in ol ed in o ganis- ing/chai ing in e na ional e en s and pee e iewing o con e ences and unding o ganisa ions. She is he au ho o Agen Technology o E-comme ce (Wiley, 2007). In 2006, she was awa ded a Na ional Teaching Fellowship by he Highe Educa ion Academy (UK) o he inno a ions and con ibu ions o lea ning and eaching.