Bay eu he A bei spapie e zu Wi scha sin o ma ik
Leh s uhl ü
Wi scha sin o ma ik
In o ma ion Sys ems
Managemen
Bay eu h Repo s on In o ma ion Sys ems Managemen
No. 23
2007
Daniel Vei , Geo g Buss (Uni e si y o Mannheim), Bjö n Schnizle , Di k Neumann (Uni e si y o
Ka ls uhe), We ne S ei be ge , To s en Eymann (Uni e si y o Bay eu h)
Theo e ical and Compu a ional Basis o CATNETS -
Annual Repo Yea 3
ISSN
1864-9300
Die A bei spapie e des Leh s uhls ü
Wi scha sin o ma ik dienen de Da s ellung
o läu ige E gebnisse, die i. d. R. noch ü
spä e e Ve ö en lichungen übe a bei e we den.
Die Au o en sind deshalb ü k i ische Hinweise
dankba .
The Bay eu h Repo s on In o ma ion Sys ems
Managemen comp ise p elimina y esul s
which will usually be e ised o subsequen
publica ions. C i ical commen s would be
app ecia ed by he au ho s.
Alle Rech e o behal en. Insbesonde e die de
Übe se zung, des Nachd uckes, des Vo ags,
de En nahme on Abbildungen und Tabellen –
auch bei nu auszugsweise Ve we ung.
All igh s ese ed. No pa o his epo may
be ep oduced by any means, o ansla ed.
Au ho s: In o ma ion Sys ems and Managemen
Wo king Pape Se ies
Edi ed by:
P o . D . To s en Eymann
Managing Assis an and Con ac :
Raimund Ma os
Uni e si ä Bay eu h
Leh s uhl ü Wi scha sin o ma ik (BWL VII)
P o . D . To s en Eymann
Uni e si ä ss asse 30
95447 Bay eu h
Ge many
Email: aimund.ma os@uni-bay eu h.de ISSN
Daniel Vei , Geo g Buss (Uni e si y o Mannheim),
Bjö n Schnizle , Di k Neumann (Uni e si y o
Ka ls uhe), We ne S ei be ge , To s en Eymann
(Uni e si y o Bay eu h)
1864-9300
IST-FP6-003769 CATNETS
Y3 Repo
WP 1: Theo e ical and Compu a ional Basis
Con ac ual Da e o Deli e y o he CEC: 31. Augus 2007
Ac ual Da e o Deli e y o he CEC: 30. Sep embe 2007
Au ho (s): Daniel Vei , Geo g Buss (Uni e si y o Mannheim)
Bj¨o n Schnizle , Di k Neumann (Uni e si y o Ka ls uhe)
We ne S ei be ge , To s en Eymann (Uni e si y o Bay eu h)
Wo kpackage: WP 1 Theo e ical and Compu a ional Basis
Es . pe son mon hs: 19
Secu i y: public
Na u e: submi ed e sion
Ve sion: 1.0
To al numbe o pages: 50
Abs ac :
This epo co e s he esul s o WP1 in Y2, Y3 and hence comp ises mainly he esul s om
T1.4 and T1.5.
Keywo ds (op ional):
Decen alized Ma ke Mechanisms, Cen alized Ma ke Mechanisms, Ca allaxy, Ma ke
Enginee ing, Simula o In eg a ion, P o o ype In eg a ion
CATNETS Conso ium
This documen is pa o a esea ch p ojec pa ially unded by he IST P og amme o he Commission o he Eu-
opean Communi ies as p ojec numbe IST-FP6-003769. The pa ne s in his p ojec a e: LS Wi scha sin o ma ik
(BWL VII) / Uni e si y o Bay eu h (coo dina o , Ge many), A qui ec u a de Compu ado s / Uni e si a Poli ecnica
de Ca alunya (Spain), In o ma ion Managemen and Sys ems / Uni e si y o Ka ls uhe (TH) (Ge many), Dipa imen o
di Economia / Uni e si ´a delle ma che Ancona (I aly), School o Compu e Science and he Welsh eScience Cen e
/ Uni e si y o Ca di (Uni ed Kingdom), Au oma ed Reasoning Sys ems Di ision / ITC-i s T en o (I aly), Chai o
Business Adminis a ion and In o ma ion Sys ems - E-Business and E-Go e nmen / Uni e si y o Mannheim (Ge -
many).
Uni e si y o Bay eu h
LS Wi scha sin o ma ik (BWL VII)
95440 Bay eu h
Ge many
Tel: +49 921 55-2807, Fax: +49 921 55-2816
Con ac pe son: To s en Eymann
E-mail: [email p o ec ed]
Uni e si a Poli ecnica de Ca alunya
A qui ec u a de Compu ado s
Jo di Gi ona, 1-3
08034 Ba celona
Spain
Tel: +34 93 4016882, Fax: +34 93 4017055
Con ac pe son: Felix F ei ag
E-mail: [email p o ec ed]
Uni e si y o Ka ls uhe
Ins i u e o In o ma ion Managemen and Sys ems
Engle s . 14
76131 Ka ls uhe
Ge many
Tel: +49 721 608 8370, Fax: +49 721 608 8399
Con ac pe son: Ch is o Weinha d
E-mail: [email p o ec ed]
Uni e si ´
a delle ma che Ancona
Dipa imen o di Economia
Piazzale Ma elli 8
60121 Ancona
I aly
Tel: 39-071- 220.7088 , Fax: +39-071- 220.7102
Con ac pe son: Mau o Gallega i
E-mail: [email p o ec ed]
Uni e si y o Ca di
School o Compu e Science and he Welsh eScience Cen e
Uni e si y o Ca adi , Wales
Ca di CF24 3AA, UK
Uni ed Kingdom
Tel: +44 (0)2920 875542, Fax: +44 (0)2920 874598
Con ac pe son: Ome F. Rana
E-mail: [email p o ec ed] .ac.uk
ITC-i s T en o
Au oma ed Reasoning Sys ems Di ision
Via Somma i e, 18
38050 Po o - T en o
I aly
Tel: +39 0461 314 314, Fax: +39 0461 302 040
Con ac pe son: Flo iano Zini
E-mail: [email p o ec ed]
Uni e si y o Mannheim
Chai o Business Adminis a ion and In o ma ion Sys ems
- E-Business and E-Go e nmen -
L9, 1-2
68131 Mannheim
Ge many
Tel: +49 621 181 3321, Fax: +49 621 181 3310
Con ac pe son: Daniel Vei
E-mail: [email p o ec ed]
Con en s
1 In oduc ion 3
2 Sel -O ganiza ion in Compu ing Sys ems - Pu ing CATNETS in o a G ea e
Pe spec i e 5
2.1 In oduc ion o Sel -O ganiza ion . ..................... 5
2.2 In as uc u al Sphe es o Sel -O ganizing Compu ing . . . . ....... 6
2.3 The Open Se ice In as uc u e . ..................... 7
2.4 Abou he Necessi y o C ea e an Open SOC Policies In as uc u e . . . . 8
3 Fo mal Desc ip ion o Mechanisms 10
3.1 Cen alized Mechanisms . . . . . ..................... 10
3.2 The Ca allaxy as an Al e na i e Decen alized App oach . . ....... 11
3.2.1 Se up and Va iables De ini ion . . . . . .............. 13
3.2.2 The Nego ia ion S a egy . ..................... 14
3.2.3 Gossip Lea ning . . . . . ..................... 17
3.2.4 The Lea ning Algo i hm . ..................... 17
4 Bidding Issues 20
4.1 Wha Does an Agen Bid? . . . . ..................... 20
4.1.1 No a ion . . ............................ 20
4.1.2 Valua ion Gene a ion . . . ..................... 21
4.1.3 Calib a ion o he Valua ion Gene a o . .............. 23
4.2 When Does an Agen Bid? . . . . ..................... 24
4.2.1 Complex Se ice Agen . ..................... 24
4.2.2 Basic Se ice Agen . . . ..................... 24
4.2.3 Resou ce Se ice Agen . ..................... 27
4.3 Summa y . . ................................ 28
5 In eg a ion o Mechanisms in o Simula o 29
5.1 In eg a ion o he Auc ion Mechanisms . . . . .............. 29
5.1.1 Implemen a ion o he Ma ke s . . . . . .............. 29
5.1.2 In eg a ion in o Op o Sim ..................... 33
5.2 Decen alized Mechanisms (Ca allaxy) . . . . . .............. 35
1

CONTENTS
2
5.2.1 Implemen a ion o he Ma ke s . . . . . .............. 35
5.2.2 In eg a ion in o Op o Sim ..................... 38
5.3 Simula ion Resul s . ............................ 40
6 Rela ions o o he WPs 43
6.1 WP2..................................... 43
6.2 WP3..................................... 43
6.3 WP4..................................... 44
7 Summa y 45
7.1 Re iew ................................... 45
7.2 Con en o Y3 ................................ 46
7.3 Ou look . . . ................................ 47
Bibliog aphy 47
Chap e 1
In oduc ion
The p ima y a ge o he CATNETS p ojec is he quan i a i e compa ison be ween he
echnical and economic e iciency o ma ke -based esou ce alloca ion mechanisms in
applica ion laye ne wo ks such as G ids. He e, wo undamen ally di e en app oaches
a e compa ed. A cen alized – auc ion-based – ma ke mechanism and a decen alized –
Ca allaxy-based – ma ke mechanism.
A e he eo ganiza ion ( ollowing he Y1 e iew) his endea o has been app oached
in he ollowing way:
•Wo kpackage 1 (Theo e ical and Compu a ional Basis): The a ge o his wo kpackage
is he de ini ion o ma ke mechanisms o he cen alized and he decen alized case.
The e o e, so wa e componen s ha e o be iden i ied (T1.1), ma ke equi emen s ha e
o be analyzed (T1.2) and an a chi ec u e o se ices and ALNs has o be designed
(T1.3). Finally a speci ica ion o bidding and in e ac ion issues has o be ca ied ou
(T1.4). A speci ica ion and analysis o he ma ke mechanisms concludes WP1.
•Wo kpackage 2 (Simula ion F amewo k): The co e o his wo kpackage is he imple-
men a ion o a simula o amewo k in eg a ing bo h, he cen alized and he decen al-
ized ma ke mechanism. The goal is o compa e he ou come o he applica ion o bo h
mechanisms quan i a i ely.
•Wo kpackage 3 (P oo -o -Concep Applica ions): In pa allel o WP2 his wo kpackage
ocuses on he implemen a ion o he designed decen alized ma ke mechanisms in o
a p o o ypical ALN-middlewa e so wa e. Quan i a i e e alua ions a e ca ied ou by
unning expe imen s wi h his pla o m.
•Wo kpackage 4 (Pe o mance E alua ion): The aim o his WP is he iden i ica ion and
design o me ics in o de o measu e he ou come o WP2 and WP3. He e, a me ics
amewo k is designed in o de o enable he measu emen o he quali y o alloca ion
esul s in using an economic scale.
3
CHAPTER 1. INTRODUCTION
4
•Wo kpackage 5 (Managemen ): This wo kpackage is designed o ca y ou p ojec
managemen and dissemina ion.
This epo co e s he esul s o WP1 in Y2, Y3 and hence comp ises mainly he
esul s om T1.4 and T1.5.
The emainde o his epo is s uc u ed as ollows: Chap e 2 illus a es esea ch
ques ions o he CATNETS p ojec in he con ex o sel -o ganizing sys ems and d aws a
ision owa ds u u e esea ch opics. In he ollowing, chap e 3 ocuses on he desc ip-
ion o he in oduced ma ke mechanisms. In Sec ion 3.1 he p ope ies o he cen alized
ma ke mechanisms, which ha e been de ined in Y1 epo [SNV+05b] a e b ie ly de-
sc ibed. Sec ion 3.2 p o ides a o mal desc ip ion o he decen alized alloca ion mecha-
nisms. The bidding issues, p esen ed in Chap e 4, elabo a e di e en scena ios connec -
ing he se ice and esou ce ma ke . Ad an ages and disad an ages o hese scena ios a e
compa ed o enable a compa ison o he cen alized and decen alized ma ke mechanism.
In Chap e 5 he in eg a ion o he mechanisms in o he Op o Sim simula o is ou lined
and links o WP2 a e se . The ein, o e all simula ion esul s a e p o ided. Chap e 6 e-
la es Wo kpackage 1 o he o he wo kpackages. Finally, Chap e 7 p o ides a summa y
o he wo k ha was done in wo kpackage 1.
Chap e 2
Sel -O ganiza ion in Compu ing
Sys ems - Pu ing CATNETS in o a
G ea e Pe spec i e
2.1 In oduc ion o Sel -O ganiza ion
The ision o Sel -O ganiza ion in Compu ing Sys ems and Ne wo ks has gained signi i-
can in e es in he las yea s, and e en was labeled wi h a popula buzzwo d: Au onomic
Compu ing [KC03] desc ibes a concep o sel -o ganizing in o ma ion echnology, whe e
he unc ionali y o he compu ing sys em is an eme gen ea u e o he capabili ies and
ac ions o he componen s. Wi hou any cen alized con olle , his sys em is capable o
con igu ing, healing, o ganizing and p o ec ing i sel ( he so-called CHOP p ope ies). In
con as , classical IT con ol in ol es a cen alized con olle ins ance wi h global knowl-
edge abou he cu en s a us o he compu ing sys em, and a de ailed egula ion mecha-
nism o ’heal’ de ia ions om a de ined ’no mal’ s a us. Cen alized compu a ion is said
o be no ha lexible in e ms o scalabili y and adap abili y. Au onomic Compu ing uses
a biological pa adigm as a design and con ol me apho , he au onomic ne ous sys em.
The co e CHOP p ope ies o he Au onomic Compu ing concep a e in ended o be an
elec onic ealiza ion o he espec i e mechanisms o he human body. Sel -o ganiza ion
can be ound in o he pa s o ou na u al en i onmen as well, e.g. biological e olu-
ion, social g oup beha io , ma ke dynamics phenomena and o he complex adap i e
sys ems. Au onomics e e s o ou own human neu al sys em, Ca allaxy [ESMP03] o
sel -o ganizing ma ke s in Economics, S igme gy o coo dina ion wi hou communica-
ion in insec colonies. All hese ideas ha e in common ha he solu ion o g owing
complexi y bo h in scale and seman ics is decen alized con ol, ha is based on local
in o ma ion and execu ed h ough local e ec s which build up o a sys em-wide eme gen
beha io . I is no su p ising ha p ojec s labeled Au onomic Compu ing a e hus man-
i old, coming om di e se backg ounds and academic habi a s, and aiming a a a ie y
5
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
12
Figu e 3.2: Decen alized Se ice Disco e y
decide on hei own, and do no ake he sys em s a e in o accoun . In he Edgewo h
p ocess [Va 94], economic subjec s ade bila e ally wi h each o he only i hei u ili y is
supposed o inc ease a e he ba e . In ha case, he sum o all u ili ies inc eases a e
each success ul ba e ; he inal s a e is Pa e o-op imal and has maximum sys em u ili y.
A heo e ical undamen how he concep s o dynamic ma ke p ocesses, he e oge-
neous agen s and choice unde incomple e in o ma ion a e linked, can be ound in Neo-
Aus ian Economics, in pa icula in F ied ich Augus on Hayeks Ca allaxy concep
[HBKC89]. Ca allaxy desc ibes a s a e o spon aneous o de , which comes in o exis-
ence by he communi y membe s communica ing (ba e ing) wi h each o he and hus
achie ing a communi y goal ha no single use has planned o .
The implemen a ion o Ca allaxy, desc ibed in his pape , uses e o s om bo h agen
echnology and economics, no ably agen -based compu a ional economics [Tes97]. Au-
onomous so wa e agen s nego ia e wi h each o he using an al e na ing o e s p o o-
col [Ros94] and adap hei nego ia ion s a egies using eedback lea ning algo i hms
(e olu iona y algo i hms, nume ical op imiza ion e.g. Nelde /Meads simplex me hod
[PT02], hyb id me hods e.g. B enne s VID model [B e02]). Ongoing communica-
ion by using p ice signaling leads o cons an adap a ion o he sys em as a whole and
p opaga es changes in he sca ci y o esou ces h oughou he sys em. The esul ing
pa e ns a e compa able o hose wi nessed in human ma ke nego ia ion expe imen s
[KR95][P u81][Smi62].

CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
13
3.2.1 Se up and Va iables De ini ion
While he no a ion o buye s, selle s and goods is he same as he one used in he cen al-
ized scena io, we need o add de ini ions o he decision-making p ocess ( he s a egy)
o he agen s. The nego ia ion s a egy desc ibed he e is based on he AVALANCHE
s a egy [ESP98][Eym01]. The s a egy consis s o 5 basic pa ame e s, which de ine he
indi idual beha io (geno ype) o each agen .
Fo e e y adable good he e a e wo ypes o agen s, buye s and selle s. Le agen k
be a buye and agen a selle o a adable good.
Le ikbe he numbe o nego ia ions ha agen khas s a ed and i he numbe o
nego ia ions ha agen has s a ed.
A geno ype de ines he beha io o he agen s in he nego ia ion s a egy. Le he
geno ype o agen ∗ o ∗=k, du ing his nego ia ion i∗be
Gi∗
∗∈[0; 1]5
wi h
Gi∗
∗=(Gi∗
∗,1,...,G
i∗
∗,5)τ=(ai∗
∗,s
i∗
∗,
i∗
∗,b
i∗
∗,wi∗
∗)τ
whe e
ai∗
∗acquisi i eness
si∗
∗sa is ac ion
i∗
∗p iceS ep
bi∗
∗p iceNex
wi∗
∗weigh Memo y.
Acquisi i eness de ines he p obabili y o s icking wi h he las o e made, and no
o make an unila e al concession in he ollowing nego ia ion s ep. The alue in e al is
be ween 0 and 1, and will be challenged by a s ochas ic p obe in e e y nego ia ion s ep.
A alue o 0.7 means a p obabili y o 70% ha he agen will no make a concession –
a highly compe i i e s a egy. An agen wi h acquisi i eness alue 1.0 will ne e change
his p ice and an agen wi h acquisi i eness alue 0.0 will always make an unila e al con-
cession. I he p obe succeeds, a buye agen will ise his o e , a selle agen will lowe
his p ice.
The exac change o he bid alue is de ined by he concession le el (p iceS ep). The
concession le el is ep esen ed by a pe cen age o he di e ence be ween he ini ial s a -
ing p ices. A alue o p iceS ep = 0.25 means a compu a ion o he concession le el as
1/4 o he i s s a ed di e ence. I bo h opponen s a e homogenously nego ia ing and
always concede, hey mee each o he on he hal way in he hi d nego ia ion ound unde
he assump ion o no nego ia ion abo ion.
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
14
Ob iously, wi h an acquisi i eness le el se high, and a p iceS ep se low enough, he
opponen s migh ne e each an ag eemen . The sa is ac ion pa ame e de e mines i an
agen will d op ou om an ongoing nego ia ion. The mo e s eps he nego ia ion akes, o
he mo e excessi e he pa ne ’s o e s a e, he soone he nego ia ion will be discon inued.
E ec i ely, his pa ame e c ea es ime p essu e. Like o acquisi i eness, i does his by
doing a s ochas ic p obe agains a se alue be ween 0 and 1. A sa is ac ion alue o 0.75
means, ha he agen has a chance o 75% o con inue he nego ia ion p ocess. An agen
wi h sa is ac ion = 0.0 will abo all nego ia ion a once and an agen wi h sa is ac ion =
1.0 will ne e abo .
The las piece o he s a egy is an exp ession o sel ishness. Behind each success ul
nego ia ion lies a u u e oppo uni y o gaining mo e o he u ili y sha e, by nego ia ing
ha de . p iceNex hus modi ies he s a ing bid. A success ul selle will inc ease his o e
p ice, a success ul bidde will s a wi h a lowe bid nex ime.
Fo a iable s a egy, he pa icipan s will ha e a close eye on wha o he s deem o
be he ma ke p ice. I no , hey isk being agged as ”excessi e” and hei bids will
ail he sa is ac ion p obe. They hus weigh cu en p ice in o ma ion and his o ic p ice
in o ma ion in a speci ied a io weigh Memo y, balancing sho - ime p ice luc ua ion and
longe - e m oppo uni ies.
A he beginning o he simula ion he genes Gi∗
∗,j o ∗=k, and j∈{1,...,5}a e
dis ibu ed acco ding o he p obabili ies:
U o[mj−δj;mj+δj]
The eby, he cons an s mjand δj o j∈{1,...,5}a e de ined so ha [mj−δj;mj+
δj]⊂[0; 1] .
Addi ionally, each agen ∗has he ollowing a iables:
Mi∗
∗: he ma ke p ice, which is es ima ed by
agen kdu ing his nego ia ion i∗.
Pi∗
∗: he p ice o he he las success ul
nego ia ion 1,2,...,i
∗o agen ∗.
Oi∗
∗: he las o e , which he nego ia ion opponen
has made in nego ia ion numbe i∗ he agen ∗
be o e he nego ia ion ended.
pi∗
∗: he numbe o s o ed plumages o agen ∗
di ec a e his nego ia ion i∗.
3.2.2 The Nego ia ion S a egy
When agen kand agen nego ia e, agen kis he buye and agen he selle . The se-
quence (Pj)j∈IN 0⊂[0,∞[cons i u es he o e in ch onological o de . The buye always
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
15
makes he i s o e . This means, all o e s
P2m∀m∈IN 0
o igina e om he buye and he o e s
P2m+1 ∀m∈IN 0
come om he selle , whe e
m
is he nego ia ion ound.
A he beginning o a nego ia ion he buye kde e mines his ini ial p ice Kand his
maximum p ice K:
K=Mik
k·(1 −bik
k), K =Mik
k
The selle de e mines his s a ing p ice Vand his minimum p ice V:
V=Mi
·(1 + bi
),V=Mi
The buye s a s wi h he i s bid:
P0=K
•Fi s Case: K≥V
Then o e s also
P1=K
and he nego ia ion will be closed success ully o he p ice P1.
•Second Case: K< V
Then o e s his ini ial p ice
P1=V.
Bo h agen s de e mine now hei s eps δj∗
∗ o p ice concessions:
δi∗
∗=(V−K)· i∗
∗ o ∗=k,
In he subsequen nego ia ion ounds, le A1,A
2,A
3,... and S1,S
2,S
3,... be s ochas ic
independen andom a iables wi h he ollowing binomial dis ibu ions:
A2m=1wi h p obabili y aik
k
0wi h p obabili y 1−aik
k
∀m∈IN
A2m+1 =1wi h p obabili y ai
0wi h p obabili y 1−ai
∀m∈IN
S2m=1wi h p obabili y sik
k
0wi h p obabili y 1−sik
k
∀m∈IN
S2m+1 =1wi h p obabili y si
0wi h p obabili y 1−si
∀m∈IN
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
16
•O e numbe 2m; i is he buye ’s k u n:
I S2m=0and P2m−1≥P2(m−1)−1wi h m=1, hen he buye kcancels he nego ia-
ion. This means, Oik
k=P2m−1and Oi
=P2(m−1) .
O he wise, he buye kmakes he ollowing o e :
P2m=min K,(P2(m−1) +δik
k),P
2m−11−A2m
·
P2(m−1)A2m
•Bid numbe 2m+1; i is he selle ’s u n:
I S2m+1 =0and P2m≤P2(m−1), hen he selle cancels he nego ia ion. Tha means,
Oi
=P2mand Oik
k=P2(m−1)+1 .
O he wise he selle makes he ollowing o e :
P2m+1 =min V , (P2(m−1)+1 −δi
),P
2mA2m+1 ·
P2(m−1)1−A2m+1
The nego ia ion ends i ei he one o he agen s cancels he nego ia ion o he nego ia ion
ends success ully wi h
Pj=Pj+1
o a j∈IN . In his case, i holds Oik
k=Pj=Oi
.
Wi h he end o a success ul nego ia ion o he p ice Pj he nego ia ion compu e hei
es ima ed p o i
Πik
k=Mik
k−Pj espec i ely Πi
=Pj−Mi
.
Addi ionally, bo h agen s upda e a e e e y nego ia ion hei es ima ed ma ke p ice
using
Mik+1
k=wik
k·Oik
k+(1−wik
k)·Mik
k
espec i ely
Mi +1
=wi
·Oi
+(1−wi
)·Mi
.
This las s ep is independen o he success o a nego ia ion.
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
17
3.2.3 Gossip Lea ning
The lea ning concep used in his simula ion is de i ed om so-called gossip lea ning.
This means ha he agen s lea n om ecei ed in o ma ion abou o he ansac ions in he
ma ke . This in o ma ion may no be accu a e o comple e, bu se es as an indica ion
abou he g oss di ec ion o he ma ke . In ou implemen a ion, his gossip in o ma ion is
c ea ed and b oadcas by a success ul agen , in analogy o issuing an ad-hoc in o ma ion
in s ock ma ke pe iodicals.
Le nbe an agen and g1,...,g
d he adable goods. The agen nhas inished his ne-
go ia ion insuccess ully wi h an es ima ed p o i o Πin
n(g) o he good g∈{g1,...,g
d}.
Alea ning s ep acco ding o he lea ning algo i hm (see subsec ion 3.2.4) is pe o med
by agen nlas ime a he end o his nego ia ion jk. This means
Gjn+1
n=Gjn+2
n=···=Gin
n.
I agen nwi h he nego ia ion numbe s
jn+1,j
n+2,...,i
n
has success ully comple ed a leas 10 nego ia ions o e e y good, he sends a Plumage
(Gin
n,Fin
n)
o all o he agen s o his ype. Then, his upda ed i ness is Fin
n, which is compu ed as
ollows:
(a) Fo e e y good gj∈{g1,...,g
d} he nex p o i alue Π(gj)is de e mined: Le
Π1(gj),...,Π10(gj)
be he es ima ed p o i s o he las 10 success ul nego ia ions o agen n o he good
gj. Then, he i ness is
Fin
n(gj)= 1
10Π1(gj)+···+Π
10(gj).
(b) The upda ed i ness Fin
n inally is
Fin
n=1
dΠ(g1)+···+Π(gd).
3.2.4 The Lea ning Algo i hm
I is assumed ha he agen s show a coope a i e beha io . This means, he agen s epo
u h ully hei lea ning in o ma ion.

CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
18
A e ha ing ecei ed some gossip in o ma ion message, he agen may modi y his
own s a egy. The compa ison o he own esul s wi h hose o he s a egy ecei ed
may show ha he o he s a egy supe io o he own. In his case, he agen will y o
c oss bo h s a egies o gain compe i i e ad an age. In p ac ice, ou o a lis o ecei ed
geno ype/pe o mance- uples, he agen will choose he bes pe o ming ex e nal geno-
ype, and hen mix, c oss and mu a e wi h his own geno ype.
Le be nan a bi a y agen a he end o his nego ia ion inand le be pin
n he numbe o
plumages, he agen nhas s o ed di ec ly a e his nego ia ion in. The las lea ning s ep
was pe o med by agen na e his nego ia ion jk. Le be ein
n he numbe o nego ia ions,
an agen no he nego ia ion numbe s
jn+1,j
n+2,...,i
n
has success ully inished.
Le be
p=1.
I
pin
n<p o ein
n<10
applies o agen na e his nego ia ion in,nolea ning s ep will be pe o med. This
means, his geno ype will no change:
Gin+1
n=Gin
n.
Hence, i
pin
n≥pand ein
n≥10
applies, he agen npe o ms a lea ning s ep. The geno ype o agen nchanges as ollows:
Fi s , he s o ed plumage o agen nwi h he highes i ness is selec ed. Le be
G =(G ,1,...,G
,5)τ=(a ,s
,
,b
,w
)τ
he ela ed geno ype. Second, a c osso e is pe o med. In doing so, a new geno ype
˜
Gin+1
nis c ea ed, which con ains a andom mix u e o genes o he geno ypes Gin
nand
G . This p ocess ollows a mu a ion s ep hi d: Using he geno ype ˜
Gin+1
nand changing
i s genes sligh ly will esul in he geno ype Gin+1
n.
3.2.4.1 C osso e
Le be C1,...,C
5s ochas ic independen andom a iables wi h he ollowing binomial
dis ibu ion:
Cj=1wi h p obabili y 0,5
0wi h p obabili y 0,5∀j∈{1,...,5}
CHAPTER 3. FORMAL DESCRIPTION OF MECHANISMS
19
Then i is impe a i e
˜
Gin+1
n,j =(1−Cj)·Gin
n,j +Cj·G ,j ∀j∈{1,...,5}.
3.2.4.2 Mu a ion
Le be M1,...,M
5,X
1,...,X
5s ochas ic independen andom a iables wi h he ollow-
ing dis ibu ions:
Mj=1wi h p obabili y 0,05
0wi h p obabili y 0,05 ∀j∈{1,...,5}
Xj∼N(0 ,1) ∀j∈{1,...,5}
Tha means, Xjis ∀j∈{1,...,5}s anda d no mal dis ibu ed.
Then, i holds
Gin+1
n,j =max0; min˜
Gin+1
n,j +
Mj·(1
10Xj)mod(1);1
∀j∈{1,...,5}.
Chap e 4
Bidding Issues
The pu pose o his chap e is o cla i y wha and when an agen bids in he CATNETS
scena io. Wha deno es he alua ion and he ese a ion p ices o agen s, i.e. he
maximal p ice which an agen is willing o pay o a se ice ( esp. he minimum p ice an
agen has o selling a se ice). When deno es he iming o bids, i.e. which e en induces
an agen o bid o a se ice. Bo h cases a e di e en in he cen alized and decen alized
scena io. As such, i is impo an o ind concep s ha a e applicable o bo h scena ios
and, hus, make he esul s compa able.
The chap e is s uc u ed as ollows: Sec ion 4.1 ou lines he alua ion gene a ion
o an agen , i.e. he p ocedu e ha de e mines he alue o an agen ’s bid. Sec ion 4.2
desc ibes he iming o he agen ’s bids, i.e. when does an agen bid o a se ice. Finally,
Sec ion 4.3 summa izes he chap e .
4.1 Wha Does an Agen Bid?
The ollowing sec ion desc ibes wha an agen bids, i.e. he alua ion and ese a ion
p ices. Fo his, a gene ic unc ion is de eloped ha is applicable o bo h, he cen alized
and he decen alized case. The concep is applied o buye s and selle s in bo h ma ke s,
i.e. in he se ice ma ke and in he esou ce ma ke .
4.1.1 No a ion
Be o e he alua ion gene a o is in oduced, he gene al no a ion as deno ed in able 4.1
is p esen ed.
The ansac ion objec gdeno es he se ice o ha a alua ion is o be gene a ed.
20
CHAPTER 4. BIDDING ISSUES
21
T ansac ion objec g
Valua ion in pe iod i V i
Ma ke p ice Mi
Weigh ma ke p ice β
Weigh ed A e age wa i
Weigh ed Memo y wi
Table 4.1: No a ion o he alua ion gene a ion
Fo ins ance, his could be a PDF c ea o in he se ice ma ke . Fo each se ice, an agen
has a alua ion Vi( esp. ese a ion p ice) in each pe iod i. This alua ion deno es he
maximum p ice, an agen is willing o bid o his pa icula se ice.
The alua ion gene a ion is in luenced by ex e nal ac o s such as he ma ke p ice.
In case such a ma ke p ice exis s o a ansac ion objec in pe iod i, i is deno ed by
Mi. Fo he cen alized case, ma ke p ices may no exis s in each pe iod. In hese cases,
an app oxima ed ma ke p ice is used. The e ec a ma ke p ice has on he alua ion
gene a ion is deno ed by β. The lowe his alue is, he lesse he impo ance o old
ma ke p ices.
Finally, he weigh ed a e age wa iand he weigh ed memo y wideno e noise pa am-
e e s.
4.1.2 Valua ion Gene a ion
Based upon he no a ion as in oduced in he p e ious sec ion, he alua ion o a se ice
gin ime pe iod i+1is calcula ed as ollows:
Vi+1(g)=βMi(g)+(1−β)wa i(g)+YX +Z(4.1)
The alua ion o he nex pe iod depends on he ma ke p ice o he cu en pe iod,
he weigh ed a e age o o me alua ions, and some s a is ical noise. The weigh o he
ma ke p ice and he weigh ed a e age depends on he s a ic alue β∈{0,1}which is
p ede ined and ixed. F om an implemen a ion poin -o - iew, he a iable βshould be
de inable ia an ex e nal con igu a ion ile.
I is o no e, ha he s a is ical noise unc ions a e only applied in he cen alized case.
These unc ions a e esponsible o inse ing exogenous ac o s (e.g. di e en dynamics,
densi y scena ios) in he cen alized simula ion. In he decen alized case, his noise is
gene a ed by a gene ic algo i hm. Howe e , his gene ic algo i hm will no be applied
CHAPTER 4. BIDDING ISSUES
28
dle {A, B, C}would be highe han he sum o alua ions o he esou ces {A},{B}
and {C}.
4.3 Summa y
This sec ion ou lines bidding issues in he CATNETS scena io. A alua ion gene a o is
in oduced ha can be applied o buye s and selle s in bo h ma ke s in o de o de e mine
alues o hei bids. The challenge o such a gene a o is o de ine a concep ha is
applicable o he cen alized and he decen alized case and ha leads o compa able
ou comes.

Chap e 5
In eg a ion o Mechanisms in o
Simula o
Subjec o his chap e is he echnical in eg a ion o he cen alized and decen alized
mechanisms in o he simula o (Sec ion 5.1 and Sec ion 5.2). He e, a s ing in e ac ion
wi h WP2 will be ca ied ou in o de o a oid o e laps in documen a ions. Fu he mo e
in Sec ion 5.3 an insigh in o he esul s o he compa ison o he cen alized o he decen-
alized mechanism is gi en. Fo an in dep h analysis he eade is e e ed o [BCC+07].
5.1 In eg a ion o he Auc ion Mechanisms
The objec i e o his sec ion is o desc ibe he implemen a ion o he auc ion mechanisms
(Sec ion 5.1.1) and hei in eg a ion in o Op o Sim (Sec ion 5.1.2).
5.1.1 Implemen a ion o he Ma ke s
In he ollowing, he implemen a ion o he se ice ma ke and he esou ce ma ke is
desc ibed. Bo h ma ke mechanisms a e implemen ed as independen so wa e se ices
which allows us o in eg a e hem in o o he sys ems easily. Beside he in eg a ion in o
Op o Sim, his lexibili y allows us o in eg a e he ma ke s in o he p o o ype in he u u e
such as p oposed in [CJSF06].
5.1.1.1 Se ice Ma ke
As ou lined in he las deli e able [SNV+05a], a double auc ion is applied o he se ice
ma ke . In a double auc ion ma ke [F i91], a la ge numbe o pa icipan s ade a
common objec and can submi bids (buy o de s) and asks (sell o de s). T ading in
29
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
30
double auc ions is o ganized by means o o de books, each o a se o homogeneous
goods. In he CATNETS scena io he e will be ndi e en o de books, each o one o
he ndi e en se ices.
Figu e 5.1 depic s he high le el a chi ec u e o he se ice ma ke o CATNETS
[SNV+05a]. Complex se ice agen s can submi buy o de s o he o de books; basic
se ice agen s can submi sell o de s. Each se o homogeneous se ices (e.g. PDF
c ea o se ices) is aded in a single o de book.
Figu e 5.1: The se ice ma ke including se e al double auc ion o de books.
A simpli ied class diag am o he se ice ma ke implemen a ion is shown in ig-
u e 5.2: Fo each ype o basic se ice aded in he se ice ma ke , an ins ance o he
O de book class is gene a ed. The o de book p o ides unc ionali y o add o de s, e-
mo e hem, and o s a he ou come de e mina ion. Whene e an agen wan s o submi
an o de o he ma ke , i gene a es an ins ance o he O de class and submi s i o he o -
de book. The o de book is also esponsible o igge ing he clea ing p ocess. In case,
a con inuous clea ing is used, he o de book ins an ia es he Alloca o CDA class;
o he wise i uses he call ma ke as implemen ed in he Alloca o CallMa ke
class. Bo h alloca o classes use he ma chmake Ma ch o ind co esponding coun-
e pa o de s. A e he alloca ion and he p ices a e compu ed, an Alloca ion objec
is gene a ed o each ansac ion. This objec poin s o he pa ies ha a e in ol ed in
he ansac ion, i.e. i poin s o an o de om a buye and an o de om a selle . The
alloca ion objec s a e s o ed in a ec o and can be pa sed by he simula o .
As he diag am shows, he implemen a ion suppo s con inuous clea ing and a call
ma ke . In a con inuous clea ing auc ion, buye s and selle s simul aneously and asyn-
ch onously announce bids and o e s. In case a new o de en e s he ma ke , he auc-
ionee ies o clea he ma ke immedia ely. A call ma ke is an auc ion wi h pe iodic
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
31
Figu e 5.2: Class diag am o he mos undamen al classes o he se ice ma ke
uni o m clea ing, e.g. he auc ionee clea s he ma ke e e y i es minu es. All o de s in
a pe iod a e collec ed in an o de book and will be clea ed pe iodically [SNV+05a]. The
clea ing s a egy ha is applied can be selec ed by means o a con igu a ion ile.
Till he end o Y3 we did no succeed in implemen ing he e en d i en ime model
o he con inuous clea ing auc ion in o he simula o . So i was no possible o speed
up simula ion uns om eal ime. The e o e we chose o use he con inuous clea ing
auc ions o he simula ion uns in Y3. Tha enabled us o calib a e and e alua e he
cen alized app oach on a lage da a se .
5.1.1.2 Resou ce Ma ke
Fo alloca ing se ices in he esou ce ma ke , we apply a mul i-a ibu e combina o ial
exchange (MACE) [SNV+05a, SNVW06]. Figu e 5.3 depic s he sequence o he auc ion
in he CATNETS scena io. Agen s (buye s and selle s) submi hei bids o he auc ionee
ins ance. A e ha , he bids a e ans o med in o an in e nal ep esen a ion o m and,
subsequen ly, he winne s a e compu ed (alloca ion). Finally, p ices a e compu ed in
conside a ion o he alloca ion. As a esul o he ma ke mechanism, he agen s ge
in o med whe he o no hey a e pa o he alloca ion.
Figu e 5.4 depic s some o he mos basic componen s o he implemen a ion as a
UML class diag am: The Ma ke class is he cen al componen o he implemen a ion.
On he one hand, i is esponsible o ini ializing all ele an classes. On he o he hand,
he ma ke class con ols he p ocess o submi o de s and o compu e an ou come.
Agen s can submi o de s o an o de book, whe e an o de consis s o a p ice and a
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
32
Figu e 5.3: Sequence o an auc ion o he esou ce ma ke
Bundle, whe e a bundle is a collec ion o Good ins ances. A e he bids a e submi ed
by he agen s, an Ou come is compu ed. Fo his, he ma ke uses a ModelFac o y
and a P icingFac o y. The ModelFac o y is esponsible o p o iding a
winne de e mina ion model in o de o compu e an alloca ion. In he CATNETS
scena io, his model is implemen ed in he Ca ne sResou ceMa ke class. The
P icingFac o y p o ides a se o p ice mechanisms ha can be used. In CATNETS,
he p icing schema as implemen ed in he KP ice class is applied. A e an alloca ion
and co esponding p ices a e de e mined, he esul is s o ed in he Ou come objec .
This objec can be que ied in o de o e ie e he equi ed in o ma ion such as alloca ion
decisions and p ices o each ansac ion.
Fo implemen ing he esou ce ma ke , we make use o he s anda d linea p og am-
ming lib a ies CPLEX and LPSol e. CPLEX is a comme cial p oduc and is cu en ly
he s a e o he a op imiza ion engine1. LPSol e is a ee linea p og amming sol e
ha implemen s he b anch-and-bound me hod o sol ing in ege p oblems2. CPLEX
is cu en ly one o he as es sol ing lib a ies and will be used o he e alua ion o he
mechanisms. The use o LPSol e (mo e speci ically, i s license) allows us o ins all he
esou ce ma ke implemen a ion on e e y machine. As such, he de elopmen and es ing
o he mechanisms can be os e ed.
The beha io o he implemen a ion can be con olled by means o con igu a ion iles.
Among o he s, se e al al e na i e p icing schemas a e implemen ed, e.g. he app oxi-
ma ed Vick ey p icing algo i hm [PKE01]. The conc e e p icing mechanism can be se-
lec ed by means o a con igu a ion pa ame e . Fu he mo e, he clea ing in e al3o he
1See h p://www.cplex.com/ o de ails.
2See h p://www.geoci ies.com/lpsol e/ o de ails.
3The esou ce ma ke is cu en ly es ic ed o a pe iodical clea ing.
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
33
Figu e 5.4: Class diag am o he mos undamen al classes o he esou ce ma ke
ma ke can be con olled by he con igu a ion ile.
5.1.2 In eg a ion in o Op o Sim
This sec ion b ie ly ou lines he in eg a ion o he ma ke s in o Op o Sim. Fo a de ailed
desc ip ion o how hese concep s a e implemen ed, he eade is e e ed o deli e able
D2.2 [CSSZ06].
In Op o Sim, he auc ionee s o he se ice ma ke and esou ce ma ke a e bo h
ealized as agen s. They ge ins an ia ed by he simula o du ing i s ini ializa ion and can
be con ac ed by e e y o he agen . Agen s communica e wi h he auc ionee s in o de
o submi hei bids and o e ie e s a us in o ma ion such as he las ma ke p ice o
a se ice o he alloca ion decision. The communica ion be ween ading agen s and
auc ionee s is ealized by means o messages.
Figu e 5.5 shows he gene al in e ac ion be ween ading agen s and an auc ionee .
Each ime, a complex se ice agen (CSA) wan s o acqui e o se ice, i submi s a
message o i s Pee - o-Pee Manage (P2P). This manage is capable o ad e ising and
ou ing messages o o he agen s. In case a manage ecei es a message om i s CSA, i

CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
34
o wa ds he message o he auc ionee (SMAA). Likewise, a basic se ice agen (BSA)
can also submi an o e message o i s Pee - o-Pee Manage which also o wa ds i o
he auc ionee . On he basis o he messages, he auc ionee compu es an ou come, i.e.
alloca ion decisions and p ices. The esul o his ou come (success ul o unsuccess ul
bid) is subsequen ly sen back o he agen s. The igu e shows he p ocess o he se ice
ma ke exempla ily; o he esou ce ma ke he p ocess is iden ical.
Figu e 5.5: Sequence o an auc ion o he esou ce ma ke .
The cen al in e aces be ween Op o Sim and he auc ionee s a e messages. F om a
concep ual poin o iew, di e en message ypes a e equi ed o di e en ac ions o he
agen s:
Reques Message: A eques message is sen , whene e an agen wan s o buy a se ice.
Fo ins ance, a complex se ice agen submi s such a message o he auc ionee o
bid o a basic se ice. The message con ains in o ma ion abou he ansac ion
objec (which se ice), he agen ’s alua ion p ice (maximum p ice), as well as an
ID o he agen .
O e Message: An o e message is sen , whene e an agen wan s o sell a se ice.
Fo ins ance, a esou ce se ice agen submi s such a message when i wan s o
sell i s esou ces. In analogy o he eques message, he o e message con ains
in o ma ion abou he ansac ion objec (which se ice), he agen ’s ese a ion
p ice (minimum p ice), as as well as an ID o he agen .
Alloca ion Message: A e he auc ionee has compu ed an ou come, alloca ion mes-
sages a e sen back o each pa icipa ing agen . In case he agen was success ul
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
35
in he auc ion (i.e. i is pa o he alloca ion), he message con ains in o ma ion
abou he p ice o he se ice and i s coun e pa . Fo ins ance, i a basic se ice
agen e ie es a success ul alloca ion message om he esou ce ma ke auc ion-
ee , he message con ains in o ma ion abou he esou ce se ice agen who will
p o ide he esou ces. In case an agen was unsuccess ul, he con ains a nega i e
p ice (p=−1).
Dele e Message: Some imes agen s need o cancel o de s which hey ha e submi ed
o he auc ionee . In his case, hey submi a dele e message o auc ionee . This
message con ains all ele an in o ma ion such as he agen ID and an o de ID.
Each message ype is implemen ed o he se ice ma ke and he esou ce ma ke .
The implemen a ion o he messages is desc ibed in he deli e able D2.2 in mo e de ail
[CSSZ06].
5.2 Decen alized Mechanisms (Ca allaxy)
This sec ion b ie ly ou lines he implemen a ion o he decen alized ma ke s and i s in e-
g a ion in o Op o Sim. Sec ion 5.2.1 ocuses on he implemen a ion o he decen alized
(ca allac ic) se ice and esou ce ma ke . The implemen a ion o he s a egy module
and i s adop ion o he ma ke s a e desc ibed in de ail. The in eg a ion in o Op o Sim,
message pa e ns and he in oduced message ypes desc ibes sec ion 5.2.2.
5.2.1 Implemen a ion o he Ma ke s
The implemen a ion o he se ice and esou ce ma ke s use he ca allac ic easone im-
plemen a ion p esen ed in he deli e able D1.1. Bo h ma ke s use he same s a egy im-
plemen a ion o easoning abou p oposals. The e o e, he objec i e o his sec ion is
o desc ibe he implemen a ion o he se ice and esou ce ma ke using he ca allac ic
easone .
Di e ences be ween he se ice and he esou ce ma ke occu a he ini ializa ion o
he s a egy, hei in e ac ion pa e ns and he in eg a ion in o he simula o and p o o ype
en i onmen . In he ollowing, he ocus lies on he in e aces o he s a egy and i s
ini ializa ion. The in e ac ion pa e ns a e dependen on he en i onmen o be in eg a ed.
Thus, hey a e desc ibed in hei co esponding sec ions.
The in e ace o he easone shows igu e 5.6. The implemen a ion o e s cus-
omized easone s o e e y agen ype in he CATNETS scena io, which ex end he
Agen Sou ce easone empla e. The Agen Sou ce class is an implemen a ion o
he bila e al nego ia ion p o ocol which calls he A alanche s a egy o decision making.
Addi ionally, i p o ides access o he e olu iona y lea ning algo i hm.
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
36
F om a concep ual poin o iew, he agen calls he easone wi h a Msg objec which
con ains all in o ma ion acco ding o he bidding language p esen ed in he D1.1 deli -
e able and some addi ional iden i ica ion in o ma ion. The s a egy in e p e s his objec
(in e p e Message) and e u ns a Msg objec . This p ocess sepa a es he message
p opaga ion om he easoning abou he con en using he de ined nego ia ion p o ocol.
The unde lying in as uc u e anspo s he con en o i s des ina ion. The same concep
is applied in he simula o and p o o ype en i onmen .
«Ja a Class»
Agen Sou ce
CLASS_NAME : S ing
s a egy : IP icing
budge : double
Agen Sou ce ( )
ge S a egy ( )
in e p e Message ( )
se P ice ( )
se Geno ype ( )
dec easeBudge ( )
inc easeBudge ( )
in e p e C p ( )
in e p e P oposal ( )
in e p e Accep ( )
in e p e Rejec ( )
pos Rejec anceMe hod ( )
pos Accep anceMe hod ( )
checkRes ic ions ( )
inc easeP iceDis ibu ion ( )
dec easeP iceDis ibu ion ( )
lea n ( )
in e p e Plumage ( )
«Ja a Class»
ComplexSe iceReasone
ComplexSe iceReasone ( )
pos Rejec anceMe hod ( )
pos Accep anceMe hod ( )
execu e ( )
«Ja a Class»
Ca allac icReasone
c ea eC p ( )
c ea eResou ceC p ( )
checkRes ic ions ( )
pos Accep anceMe hod ( )
pos Rejec anceMe hod ( )
«Ja a Class»
BasicSe iceReasone
BasicSe iceReasone ( )
BasicSe iceReasone ( )
pos Rejec anceMe hod ( )
pos Accep anceMe hod ( )
execu eSe iceMa ke ( )
execu eResou ceMa ke ( )
«Ja a Class»
Resou ceReasone
Resou ceReasone ( )
pos Rejec anceMe hod ( )
pos Accep anceMe hod ( )
execu e ( )
«Ja a Class»
Msg
se ialVe sionUID : long
messageType : in
documen Type : in
i emID : S ing
p ice : double
budge : double
basicSe ices : BasicSe iceDa a
e dic : in
msg_plumage : Plumage
hopCoun e : in
basicSe ice : BasicSe iceDa a
ma ke : S ing
smMessage : Objec
eqMessage : Objec
«use»
«use»
«use»
«use»
«use»
Figu e 5.6: The in e ace o he ca allac ic easone .
The ele an a ibu es o he Msg class a e in de ail:
CHAPTER 5. INTEGRATION OF MECHANISMS INTO SIMULATOR
37
MessageType:The ype o he nego ia ion message speci ies he communica i e ac
e e ed o he nego ia ion p o ocol. In he bila e al nego ia ion p o ocol o he
ca allac ic easone he ollowing alues a e used: c p (call- o -p oposal), accep ,
ejec , p oposal.
Con e sa ionID:The iden i ie o he nego ia ion is an unique numbe gene a ed o
each new eques du ing he c ea ion o new c p message. The alues a e andom
gene a ed UUIDs o he Ja a buil -in UUID gene a o .
Documen Type:This pa ame e signals he ca allac ic easone he ype o p ice o
eason abou . A BID e e s o he p oposal ype o be gene a ed by a selle and an
ASK ela es o a buye o e .
I emID:This is he iden i ie o he aded good. In he cu en implemen a ion, his
could be any kind o ex . In Op o Sim, se ices usually a e iden i ied using hei
ype (cs o bs o complex se ice o basic se ice) ollowed by a numbe . The
bundles on he esou ce ma ke a e iden i ied using a sequence o hei single i ems.
Fo example, ”cpu;mem;hdd” e e s o a bundle o he h ee single bundle i ems
cpu, memo y (mem) and ha d disk space (hdd).
P ice:This is he cu en p ice o he aded good. On he se ice ma ke , i is he p ice
o a basic se ice ins ance; on he esou ce ma ke i is he p ice o a esou ce
bundle. In he cu en implemen a ion, he e is a p ede ined p ice o e e y e-
sou ce bundle combina ion. The agen has a p e e ence o ading ce ain esou ce
bundles.
Ma ke :The ma ke pa ame e is used o assign he message o a ma ke . In he CAT-
NETS scena io, he alues a e: SERVICEMARKET, RESOURCEMARKET
Ve dic :This is he e dic on bid se by he s a egy. I ela es o he esul o he
ca allac ic easone . Valid alues a e: accep , ejec , p oposal
Plumage:The plumage pa ame e ep esen s a con aine o lea ning in o ma ion. This
con aine includes he i ness in o ma ion and he geno ype alues o o he agen s
which aded he same good.
The ma ke agen s use he desc ibed message objec o decide he nex ope a ion.
This ope a ion is dependen on he message ype o he ma ke agen and i s ole in he
ma ke . I s gene al bidding beha io o ming he wo ma ke is desc ibed in sec ion 4.2.
The implemen a ion o he agen s ollows his desc ip ion. The nex sec ion p esen s he
ini ializa ion o s a egy o he wo ma ke s in he CATNETS scena io.
ini ializa ion o he s a egy o he se ice and esou ce ma ke : The ini ializa ion
o he easone spli s in o wo a eas: The i s a ea is he ini ializa ion o he i ems and
CHAPTER 6. RELATIONS TO OTHER WPS
44
6.3 WP4
The goal o WP4 is o e alua e he pe o mance o he Ca allac ic app oach by means o
a simula o (see deli e able yea 2 o WP2) and a p o o ype (see deli e able yea 2 o
WP3). The ela ions o WP4 a e as ollows:
•The iden i ica ion and o maliza ion o ele an me ics o compa e cen alized and
decen alized ma ke mechanisms.
•Collabo a ion wi h he de elopmen o he pe o mance measu ing amewo k, due
o he ac ha some o he measu ed me ics a e aken a he economic agen le el.
Repo ing o measu ed da a o he pe o mance measu ing amewo k.

Chap e 7
Summa y
In his chap e he achie emen s om wo kpackage 1 du ing Y2 and Y3 o he p ojec
a e summa ized. Sec ion 7.1 ocuses on he wo k ha has been pe o med in Y2 and Y3.
A b ie e iew is gi en on how his ela es o he i s p ojec yea . In Sec ion 7.2 he
asks pe o med in Y3 a e speci ied. Finally sec ion 7.3 pu s he CATNETS esul s in o a
g ea e pe spec i e.
7.1 Re iew
As desc ibed in he in oduc ion and in he p ojec summa y, he main con ibu ion o
he CATNETS p ojec is he compa ison o cen alized and decen alized economic al-
loca ion mechanisms o esou ces in G ids and applica ion laye ne wo ks (ALNs). In
o de o achie e his, he p ojec has been di ided in o i e wo kpackages. The con en
o he indi idual wo kpackage as well as he di ision and in eg a ion o hose has been
elabo a ed on in Chap e 1 and Chap e 6.
In his epo , he line o wo k ca ied ou in he second p ojec yea (mon h 25 o
mon h 48) is desc ibed. The eby, Chap e 3 ocuses on he o mal desc ip ion o he
cen alized and decen alized mechanisms. The cen alized mechanisms, which also ha e
been con en o yea 1 epo , a e b ie ly discussed and an in dep h p esen a ion o he
decen alized mechanisms as well as he lea ning algo i hms and nego ia ion s a egies
is gi en. The no ion o wo di e en ma ke s – a esou ce and a se ice ma ke – is
in oduced. Bo h ma ke s a e in e connec ed ia a in e media ies.
A e his, Chap e 4 cla i ies when and wha a pa icipan in esou ce and se ice
ma ke s bids. The de ini ions p o ided he e a e subs an ial o he design o bo h (i) he
implemen a ion o he mechanisms in he simula o as well as (ii) he in eg a ion o he
decen alized mechanisms in o he middlewa e.
In Chap e 5 he in eg a ion o he cen alized and decen alized mechanisms in o he
45
CHAPTER 7. SUMMARY
46
Op o Sim simula o amewo k is desc ibed. Besides he p epa a o y wo k ha is con en
o he chap e s be o e, his has been he mos demanding and ex ensi e wo k ha has
been ca ied ou in wo kpackage 1 in yea 2. The challenge he e is o p o ide a lexible,
adap able and dynamic simula ion amewo k ha enables bo h, simula ions based on
cen alized and decen alized ma ke se ups in one scena io in o de o keep he esul s
compa able. Addi ionally o he issues conce ning he implemen a ion i sel , simula ion
esul s om bo h, he cen alized and he decen alized case a e compa ed o each o he .
7.2 Con en o Y3
A e he in eg a ion o he cen alized and he decen alized economic mechanisms in o
he simula o and he in eg a ion o he cen alized mechanism in o he middlewa e was
inished and e ined he ollowing asks we e he main issues o wo kpackage 1:
•2.3 Simula ion o applica ion laye ne wo ks and e inemen : He e, he e o s in wo k-
package 1 was ocused on he calib a ion, alida ion and e i ica ion o he simula ion
model. Addi ional issues we e he assis ance o wo kpackage 2 leade s in ca ying ou
simula ions, ob aining and e alua ing la ge-scale da a om simula ion uns as well as
o in e p e he esul s de i ed om he applied me ics.
•3.3 Pe o mance measu ing componen s o expe imen s: Conce ning his issue, mos
wo k is ca ied ou in wo kpackage 3. Howe e , he economic expe ise in designing
and moni o ing he pe o mance e alua ion bo h, om a echnical and an economic
pe spec i e has been ou mission in yea 3.
•3.4 Dis ibu ed applica ion o execu e on economic-enhanced G id/P2P pla o m and
middlewa e in eg a ion: In his ask, he in eg a ion o middlewa e concep s o no el
app oaches in G id and P2P a chi ec u es was e alua ed. Besides gene a ing sub-
s an ial esul s, he a ge o wo kpackage 1 was he o assis wo kpackage 3 lead-
e s in p o isioning o a s ong oo p in o he wo k pe o med in CATNETS in he
G id/SOA/P2P/Pe asi e Compu ing communi ies.
•4.4 Pe o mance analysis, compa ison, e alua ion: As o all o he pa icipan s, i was
one o he co e issues o analyze, documen and compa e he e alua ion o he p oposed
mechanisms. Wo kpackage 1 con ibu ed o his e o by assis ing wo kpackage 4 p o-
agonis s in o de o show he e iciency and e ec i eness o he p oposed mechanisms
in app op ia e scena ios and ind channels o dis ibu e hese esul s in o all ele an
communi ies.
CHAPTER 7. SUMMARY
47
7.3 Ou look
The co e con ibu ion o he CATNETS p ojec is he quan i a i e compa ison be ween
common cen alized economic alloca ion mechanisms and decen alized nego ia ion o -
ma s based on on Hayek’s Ca allaxy. The e o e, se e al me ics ha e been de ined in
o de o iden i y he quali y o he economic alloca ions. The esul s show, ha he appli-
cabili y o alloca ion mechanisms highly depends on he pa ame e iza ion o he indi id-
ual se up. Co e issues along which he iden i ica ion o he app op ia e mechanism has o
be aligned a a e:
• he size o he alloca ion p oblem,
• he communica ion in ensi y,
• he dis ibu ion o he p ices o e ed by he pa icipan s and
• he dynamics o he ma ke .
All hese pa ame e s again depend upon he indus y b anch in which he indi idual
applica ion, o which he mechanism should be deployed, is loca ed.
The app oaches in es iga ed wi hin he CATNETS p ojec may be subsumed in he
ield o G id Economics. In his ield, cu en ly s ong e o s a e bundled in o de o
iden i y me hodologies ha a e applicable o dynamically alloca ing compu a ional e-
sou ces o applica ions. The ision o his ield is o enable a seamless in eg a ion o dis-
ibu ed ha dwa e o he compu a ion o he e ogeneous on -end applica ions. The idea
is o allow o dynamic alloca ion o esou ces in o de o de e mine he p ices o compu-
a ional esou ces along he ime. In o de o lay he undamen s o such an a chi ec u e,
subs an ial e o s ha e o be ca ied ou in he G id middlewa e domain. Applying he e-
sul s om CATNETS an icipa es a ully unc ional G id middlewa e, which is capable o
ex-an e de e mining he ime speci ic jobs a e unning. This implies a componen , which
judges he un ime o jobs s emming om he e ogeneous applica ions. Ha ing such a
componen in place will allow he applica ion o ma ke based alloca ion schemes such as
hey ha e been p oposed in his wo k.
The key ideas o ou app oaches ha e been p esen ed in di e en communi ies. A
la ge numbe o expe s om he e-In as uc u e communi y, he G id communi y as
well as he SOA and he dis ibu ed sys ems communi ies see g ea po en ial in hese
app oaches. Se e al in dep h coope a ions ha e been s a ed he e.
Bibliog aphy
[AG04] Nadia Ben Azzouna and Fab ice Guillemin. Cha c e is ic o ip a -
ic in comme cial wide a ea ne wo ks. In P oceedings o he In e na-
ional Con e ence on Compu ing, Communca ions and Con ol Technologies
(CCCT’2004), Aus in, Texas (TX), Augus 2004.
[AH00] E. Ada and B.A Hube man. F ee iding on gnu ella. Fi s Monday, 5(10),
2000.
[BCC+07] Geo g Buss, Michele Ca alano, Pablo Chacin, Isaac Chao, To s en Ey-
mann, Felix F ei ag, Sebas ian Hude , Li iu Joi a, Leand o Na a o, Nils
Pa asie, Ome F. Rana, Bj¨o n Schnizle , We ne S ei be ge , and Daniel
Vei . D4.3: Pe o mance e alua ion. Ca ne s deli e able, Uni e si y
o Mannheim,Uni e si ´a delle Ma che Ancona, Uni e si a Poli ecnica de
Ca alunya, Uni e si y o Bay eu h, Uni e si y o Ka ls uhe, Uni e si y o
Ca di , 2007.
[B e02] T. B enne . A beha iou al lea ning app oach o he dynamics o p ices. Com-
pu a ional Economics, pages 67–94, 2002.
[Ca 04] Nicholas G. Ca . Does IT Ma e ? In o ma ion Technology and he Co o-
sion o Compe i i e Ad an age. Ha a d Business School P ess, May 2004.
[CGS+05] Michele Ca alano, Gian anco Giulioni, We ne S ei be ge , Michael
Reinicke, and To s en Eymann. 4.1: E alua ion and me ics amewo k. Ca -
ne s deli e able, Uni e si ´a delle Ma che Ancona, Uni e si y o Bay eu h,
2005.
[CJSF06] P. Chacin, L. Joi a, B. Schnizle , and F. F ei ag. Flexible a chi ec u e o sup-
po ing auc ions in g ids. In P oceedings o he 2nd In e na ional Wo kshop
On Sma G id Technologies 2006 (SGT2006) Wo kshop, 2006.
[CSSZ06] Gae ano Calab ese, Bj¨o n Schnizle , We ne S ei be ge , and Flo iano Zini.
D2.2: Annual epo o wp2. Ca ne s deli e able, ITC-i s T en o, Uni e si y
o Ka ls uhe, Uni e si y o Bay eu h, 2006.
48
BIBLIOGRAPHY
49
[ESH07] To s en Eymann, We ne S ei be ge , and Sebas ian Hude . 5.6: Pe iodic
p og ess epo . Ca ne s deli e able, Uni e si y o Bay eu h, 2007.
[ESMP03] T. Eymann, S. Sackmann, G. M¨ulle , and I. Pippow. Hayek’s ca allaxy:
A o wa d-looking concep o in o ma ion sys ems. In P oceedings o he
Ame ican Con e ence on In o ma ion Sys ems (AMCIS), Tampa, Flo ida,
2003.
[ESP98] To s en Eymann, De le Schode , and Bo is Pado an. A alanche - an agen
based alue chain coo dina ion expe imen . In Wo kshop on A i icial Soci-
e ies and Compu a ional Ma ke s (ASCMA’98), pages 48–53, Minneapolis,
1998.
[Eym01] To s en Eymann. Decen alized economic coo dina ion in mul i-agen sys-
ems. In Hans-Ul ich Buhl, F. Hu he , and A. Rei wiesne , edi o s, In o -
ma ion Age Economy. P oceedings WI-2001., pages 575–588, Heidelbe g,
2001. Physica Ve lag.
[F i91] D. F iedman. The double auc ion ma ke ins i u ion: A su ey. In D. F ied-
man and J. Rus , edi o s, The Double Auc ion Ma ke - Ins i u ions, Theo ies,
and E idence, pages 3–26. Camb idge MA, Pe seus Publishing, 1991.
[HBKC89] F.A. . Hayek, W.W. Ba ley, P.G. Klein, and B. Caldwell. The collec ed
wo ks o .a. hayek. Uni e si y o Chicago P ess, 1989.
[KC03] Je ey O. Kepha and Da id M. Chess. The ision o au onomic compu ing.
Compu e , 36(1):41–50, Janua y 2003.
[KR95] J.H. Kagel and A.E. Ro h. The handbook o expe imen al economics. P ince-
on Uni e si y P ess, 1995.
[Ma 99] Humbe o R. Ma u ana. The o ganiza ion o he li ing: a heo y o he li ing
o ganiza ion. In . J. Hum.-Compu . S ud., 51(2):149–168, 1999.
[PKE01] Da id C. Pa kes, Jayan Kalagnanam, and Ma a Eso. Achie ing budge -
balance wi h ick ey-based paymen schemes in exchanges. In P oceedings
o he Se en een h In e na ional Join Con e ence on A i icial In elligence,
2001.
[P u81] D.G. P ui . Nego ia ion beha io . O ganiza ional and occupa ional psy-
chology. New Yo k: Academic P ess, 1981.
[PT02] W. H. P ess and S. A. Teukolsky. Nume ical Recipes in C++ - The A o
Scien i ic Compu ing. Camb idge, MA, Camb idge Uni e si y P ess, 2002.
[RFH+01] Syl ia Ra nasamy, Paul F ancis, Ma k Handley, Richa d Ka p, and Sco
Schenke . A scalable con en -add essable ne wo k. Technical epo , Be ke-
ley P ess, 2001.

BIBLIOGRAPHY
50
[Ros94] G. Rosenschein, J. S.; Zlo kin. Rules o encoun e - designing con en ions
o au oma ed nego ia ion among compu e s. MIT P ess, Camb idge, 1994.
[Smi62] V.L. Smi h. An expe imen al s udy o compe i i e ma ke beha io . Jou nal
o Poli ical Economy, 70:111–137, 1962.
[SNV+05a] Bj¨o n Schnizle , Di k Neumann, Daniel Vei , Mau o Napole ano, Michele
Ca alano, Mau o Gallega i, Michael Reinicke, We ne S ei be ge , and
To s en Eymann. : En i onmen al analysis o applica ion laye ne wo ks.
Ca ne s deli e able, Uni e si y o Ka ls uhe, Uni e si ´a delle Ma che An-
cona, Uni e si y o Bay eu h, 2005.
[SNV+05b] Bj¨o n Schnizle , Di k Neumann, Daniel Vei , Michael Reinicke, We ne
S ei be ge , To s en Eymann, Felix F ei ag, Isaac Chao, and Pablo Chacin.
Deli e able 1.1; wp 1: Theo e ical and compu a ional basis. Technical e-
po , CATNETS, 2005.
[SNVW06] Bj¨o n Schnizle , Di k Neumann, Daniel Vei , and Ch is o Weinha d . T ad-
ing G id Se ices – A Mul i-a ibu e Combina o ial App oach. Eu opean
Jou nal o Ope a ional Resea ch, o hcoming, 2006.
[Tes97] L. Tes a sion. How economis s can ge ali e. In The Economy as a E ol ing
Complex Sys em II, pages 533–564. A hu , W.B. and Du lau , S. and Lane,
D.A. (H sg.), 1997.
[Va 94] Hal R. Va ian. Mik okonomie. Oldenbou g, 1994.
[Wei99] Ge ha d Weiss, edi o . Mul iagen sys ems: a mode n app oach o dis-
ibu ed a i icial in elligence. MIT P ess, Camb idge, MA, USA, 1999.
[Wie98] N. Wiene . The his o y and p ehis o y o cybe ne ics. Kybe ne es, 27:29–37,
1998.
ISSN
In his documen he de elopmen s in de ining
he compu a ional and heo e ical amewo k o
economical esou ce alloca ion a e desc ibed.
Acco dingly he o mal speci ica ion o he
ma ke mechanisms, bidding s a egies o he
in ol ed agen s and he in eg a ion o he
ma ke mechanisms in o he simula o we e
e ined.
1864-9300