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.