UNCORRECTED PROOF
2Se - alued TU-games
3F.R. Fe n
aandez
a
, M.A. Hinojosa
b
, J. Pue o
a,*
4
a
Facul ad de Ma hema icas Dep ., Depa amen o de Es ad
ııs ica e In es igacioon Ope a i a, Uni e sidad de Se illa,
541012 Se illa, Spain
6
b
Depa amen o de Econom
ııa y Emp esa, Uni e sidad Pablo de Ola ide, Se illa, Spain
7Recei ed 6 May 2002; accep ed 3 Ma ch 2003
8Abs ac
9The goal o his pape is o explo e solu ion concep s o se - alued TU-games. Se e al s abili y condi ions can be
10 defined since one can ha e a ious in e p e a ions o an imp o emen wi hin he mul ic i e ia amewo k. We p esen
11 wo diffe en co e solu ion concep s and explo e he ela ionships among hem. These concep s gene alize he classic
12 co e solu ion o scala games and can be conside ed unde diffe en p e e ence s uc u es. We gi e cha ac e iza ions o
13 he non-emp iness o hese co e se s and apply he esul s o ou mul iobjec i e ope a ional esea ch games.
14 2003 Published by Else ie B.V.
15 Keywo ds: Mul iobjec i e analysis; Game heo y; Co e
16 1. In oduc ion
17 I is cu en ly accep ed ha eal-wo ld decision p ocesses a e mul i alued. This asse ion means ha
18 decision-making is ac ually based on se e al (mo e han one) c i e ia. Ob iously, using se e al c i e ia
19 implies he non-exis ence o a o al o de among he e alua ion o he diffe en al e na i es. Thus, ega ding
20 he scala case, whe e all he op imal decisions sha e he same e alua ion, in mul ic i e ia decision-making
21 he abo e p ope y does no make sense. In he la e case, he decision-make may accep many diffe en
22 al e na i es p o ided ha hei e alua ions a e non-domina ed componen wise.
23 Modelling conflic si ua ions whe e se e al c i e ia mus be conside ed simul aneously leads in a na u al
24 way o mul iobjec i e game heo y (see e.g. Be gs esse and Yu, 1977; Blackwell, 1956; Hwang and Lin,
25 1987; Shapley, 1959). In his amewo k he e alua ion gi en o he al e na i es conside ed by he agen s is
26 no a unique alue bu a se o non-domina ed ec o s (see Fe n
aandez e al., 1998; Fe n
aandez and Pue o,
27 1996; Pue o and Fe n
aandez, 1995).
28 The discussion abo e leads us o conside he class o he mul iobjec i e coope a i e TU-games. Wi hin
29 his class any coali ion So playe is gi en a cha ac e is ic se o ec o s. These ec o s ep esen he non-
*
Co esponding au ho . Tel.: +954557940; ax: 954622800.
E-mail add esses: [email p o ec ed] (F.R. Fe n
aandez), [email p o ec ed] (M.A. Hinojosa), [email p o ec ed] (J. Pue o).
0377-2217/03/$ - see on ma e 2003 Published by Else ie B.V.
doi:10.1016/S0377-2217(03)00398-9
Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx
www.else ie .com/loca e/dsw
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
30 domina ed payoffs ha he membe s o a coali ion can ensu e by hemsel es. No ice ha diffe en om he
31 classic scala case, in his amewo k, coali ions may suppo any o hei admissible payoffs in hei
32 cha ac e is ic se o ec o s. Hence, in his class o TU-games one looks no only o ai alloca ions o he
33 g and coali ionÕs payoffs bu o which o he g and coali ionÕs payoffs he abo e ques ion can be answe ed
34 in an affi ma i e way.
35 When he cha ac e is ic se o ec o s a e single ons, we ob ain he class o ec o - alued games (see
36 Fe n
aandez e al., 2002). In addi ion, i he numbe o c i e ia conside ed by he agen s is only one we ob ain
37 he s anda d heo y o coope a i e TU-games.
38 I is also wo h no ing ha wi h his class we can model any game whose cha ac e is ic se o ec o s is
39 gi en implici ly as he se o non-domina ed ec o s o a mul iobjec i e p og am. In pa icula Ope a ion
40 Resea ch games (see Bo m e al., 2001) may be analyzed wi hin his new amewo k when mo e han one
41 objec i e is simul aneously conside ed in he op imiza ion p ocess. Examples a e mul iobjec i e flow games,
42 mul iobjec i e minimum spanning ee games, mul iobjec i e combina o ial op imiza ion games, e c.
43 In o de o illus a e he discussion abo e, we desc ibe in de ail h ee diffe en classes o se - alued TU-
44 games: he mul iobjec i e linea p oduc ion game, he mul iobjec i e con inuous single acili y loca ion
45 game and he mul iobjec i e minimum cos spanning ee game. I is wo h no ing ha he wo o me
46 games come om a con inuous mul iobjec i e OR p oblem ( he scala e sion o hese games we e in-
47 oduced by Owen (1975) and Pue o e al. (2001), espec i ely) while he la e does om a combina o ial
48 one ( he scala e sion o his game was in oduced by Bi d, 1976).
49 1.1. The mul iobjec i e linea p oduc ion game
50 Conside he mul iobjec i e linea p oduc ion p oblem:
½P -max Cx
s: ::x2FðPÞ:¼ x2Rp:Ax 6b;xP0g;
52 whe e C2Rkpis he ma ix whose ows ep esen he kdiffe en objec i es o he p oblem; A2Rmpis he
53 echnological ma ix; b2Rmis he esou ce ec o ; xis he p oduc ion ec o and FðPÞis he decision se
54 o he p oblem [P].
55 The solu ion concep o his p oblem is he se o efficien solu ions:
EðPÞ¼ x2Rp:9=y2FðPÞ e i ying Cy PCx;Cy 6¼ Cxg
57 and he se o alues o he efficien solu ions is:
ZðPÞ¼ zðxÞ:zðxÞ¼Cx;x2EðPÞg:
59 This model can be conside ed as a game when he pool o esou ces is con olled by ndiffe en agen s
60 (playe s). Le us assume ha playe iholds a esou ce ec o bi¼ðbi
1;bi
2;...;bi
mÞ ,i¼1;2;...;n. Thus, i
61 coali ion So playe s is o o m i con ols a bundle o esou ces bðSÞ¼Pi2Sbi. This ec o o esou ces
62 makes possible o he coali ion S o p oduce goods acco ding o he ollowing linea p oduc ion p oblem:
½PS -max Cx
s: ::x2FðPSÞ:¼ x2Rp:Ax 6bðSÞ;xP0g:
64 Finding he se o efficien solu ions EðPSÞo his p oblem, coali ion Sob ains payoff ec o s in he se
65 ZðPSÞ¼ z2Rk:z¼Cx;x2EðPSÞg.
66 This amewo k leads na u ally o in oduce he mul iobjec i e linea p oduc ion game wi h nplaye s
67 (agen s) and whe e each coali ion, S, can gua an ee ec o s in ZðPSÞ.
2F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
68 1.2. The mul iobjec i e con inuous single acili y loca ion game
69 A con inuous single acili y loca ion p oblem is a se o nuse s o a ce ain acili y, placed in ndiffe en
70 poin s in he space Rmwi h mP1. The p oblem consis s o finding a loca ion o he acili y which min-
71 imizes he anspo a ion cos (which depends on he dis ances om he use s o he acili y) plus he se up
72 cos . Fo mally, a con inuous single acili y loca ion p oblem is a 4- uple ðN;U;d;KÞwhe e:
73 •N¼ a1;...;angis a se o ndiffe en poin s in Rm(wi h nP2).
74 •U:Rn!Ris a lowe semicon inuous globalizing unc ion sa is ying ha : (1) Uis defini e, i.e. UðxÞ¼0i
75 and only i x¼0; (2) Uis mono one, i.e. UðxÞ6UðyÞwhene e x6y.
76 •d:RmRm!Ris a measu e o dis ance, sa is ying ha , o e e y ;s2Rm,dð ;sÞ¼ ðk skÞ, whe e
77 is a lowe semicon inuous, non-dec easing and non-nega i e map om R o Rwi h ð0Þ¼0, and kk is
78 a no m on Rm.
79 •Kis he se up cos . This cos is independen o he numbe o use s and o he loca ion o he acili y; i is
80 mos ly ins alla ion cos .
81 Sol ing he con inuous single acili y loca ion p oblem ðN;U;d;KÞ o SNmeans o find an 
xx 2Rm
82 minimizing UðdSðxÞÞ, whe e dSðxÞis he ec o in Rnwhose i h componen is equal o dðx;aiÞi ai2S, and
83 equal o ze o o he wise. We deno e LðSÞ¼minx2RmUðdSðxÞÞ. We impose o simpli y he analysis ha he
84 se up cos mus be g ea e han o equal o he o al anspo a ion cos , i.e. KPLðNÞ.
85 This is he classical e sion o he con inuous single acili y loca ion p oblem. He e we conside a na u al
86 a ian o his p oblem in which he use s in Na e in e es ed no only in finding an op imal loca ion o he
87 acili y, bu also in sha ing he co esponding o al cos s.
88 The e o e we can associa e wi h ðN;U;d;KÞa cos TU-game ðN; Þwhose cha ac e is ic unc ion is
89 defined, o e e y SN¼ a1;...;ang,by:
ðSÞ¼ KþLðSÞi S6¼;;
0i S¼;:

91 E e y cos TU-game defined in his way is wha we call a con inuous single acili y loca ion game. I se e al
92 (mo e han one) globalizing unc ions Uj,j¼1;...;ka e simul aneously conside ed hen we ge a se -
93 alued TU-game. I is wo h no ing ha in his si ua ion LðSÞ¼ -minx2RmðU1ðdSðxÞÞ;...;UkðdSðxÞÞÞ. Thus
94 he se - alued TU game ðN;VÞis gi en by VðSÞ¼KþLðSÞ o any SN, and Vð;Þ ¼ 0g.
95 1.3. The mul iobjec i e minimum spanning ee game
96 Conside a se o Nuse s o some good ha is supplied by a common supplie 0 (N0¼N[ 0g). The e is
97 a mul iobjec i e cos associa ed o he dis ibu ion sys em ha has o be di ided among he use s. This
98 si ua ion can be o mula ed as a se - alued game wi h Nplaye s and a cha ac e is ic unc ion ha asso-
99 cia es o each coali ion Sa se VðSÞ ha ep esen he Pa e o-minimum cos o cons uc ing a dis ibu ion
100 sys em among he use s in S om he sou ce 0.
101 Le G¼ðN0;EÞbe he comple e g aph wi h se o nodes N0and se o edges (links) deno ed by E. The e is
102 a ec o o cos s associa ed wi h he use o each link. Le eij ¼eji ¼ðeij
1;eij
2;...;eij
kÞdeno e he ec o - alued
103 cos o using he link i;jg2E. A ee is a connec ed g aph which con ains no cycles. A Pa e o-minimum
104 cos spanning ee o a gi en connec ed g aph, wi h cos s on he edges, is a spanning ee which has Pa e o-
105 minimum cos s among all spanning ees (see Eh go , 2000).
106 A Pa e o-minimum cos spanning ee game, associa ed o he comple e g aph G¼ðN0;EÞ, is a pai
107 ðN;VÞwhe e Nis he se o playe and Vis he cha ac e is ic unc ion defined by:
F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx 3
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
108 1. Vð;Þ ¼ 0g.
109 2. Fo each non-emp y coali ion SN,
VðSÞ¼ - min P i;jg2ETS0
eij
TS0:spanning ee ;
111 whe e ETS0is he se o edges o he spanning ee, TS0, ha con ains S0¼S[ 0g;and -min s ands o
112 Pa e o-minimiza ion.
113 Rema k ha he esul ing spanning ee TS0mus con ain S0bu i may also con ain some addi ional nodes.
114 To analyze mul iobjec i e games we ex end he classical indi idual and collec i e a ionali y p inciples
115 using wo diffe en o de ings in he payoff space. The fi s one co esponds wi h a comp omise a i ude
116 owa ds nego ia ion whe e coali ions admi payoffs ha a e no wo se in all he componen s han any
117 payoffs ha hey can ensu e by hemsel es. The second one, is a mo e es ic i e o de ing ha only accep
118 payoffs ha ge mo e in all he componen s han all payoffs ha hey can gua an ee by hemsel es. Simila
119 app oaches o hese wo analysis ha e been done in Fe n
aandez e al. (2002), J€
oo ns en e al. (1995) and
120 Nouweland e al. (1989) and an applica ion can be seen in Fe n
aandez e al. (2001).
121 The pape is o ganized as ollows. In he second sec ion we in oduce he defini ion o se - alued TU-
122 game and he concep o alloca ion o hose games. Mo eo e , we analyze wo diffe en domina ion e-
123 la ionships ha ex end he classic domina ion concep in he scala case. In Sec ion 3, we in oduce he non-
124 domina ed alloca ions se s, NDA se s, and we show he ela ionship wi h he co e concep s. In Sec ion 2 we
125 s udy exis ence heo ems o hese solu ion concep s. All he esul s a e illus a ed wi h h ee diffe en
126 classes o games.
127 2. Basic concep s
128 A se - alued TU-game is a pai ðN;VÞ, whe e N¼ 1;2;...;ngis he se o playe s and Vis a unc ion
129 which assigns o each coali ion SNa compac subse VðSÞo Rk, he cha ac e is ic se o coali ion S, such
130 ha Vð;Þ ¼ 0.
131 Vec o s in VðSÞ ep esen he wo hs ha he membe s o coali ion Scan gua an ee by hemsel es.
132 No ice ha he cha ac e is ic unc ion in hese games a e se - o-se maps ins ead o he usual se - o-poin
133 maps.
134 We deno e by GV he amily o all he se - alued TU-games, by G he class o ec o - alued TU-games
135 and by g he amily o all he scala TU-games.
136 Example 2.1. Conside he ollowing wo-objec i e linea p oduc ion p oblem wi h h ee decision make s
137 (playe s) in which he ma ix ha ep esen s he wo objec i es is
C¼24
1:51

139 and he echnological ma ix is
A¼177
488

:
141 The esou ce ec o s o each playe a e b1¼ð14;14;13Þ ,b2¼ð18;9;22Þ and b3¼ð11;18;22Þ . Then,
142 he cha ac e is ic se s o e e y coali ion S(SN) a e VðSÞ¼ZðPSÞ¼con ðzS
1;zS
2Þ(con ðAÞmeans he
4F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
143 con ex hull o he se A):
145145 Example 2.2. Le N¼ a1;a2;a3gbe a se o playe s loca ed a he poin s 0, 1, 2 on he eal line and assume
146 ha 0 <e. We conside wo globalizing unc ions U1,U2gi en by:
U1ðdNðxÞÞ ¼ 1
2
ejx0jþ 1
4
þejx1jþ1
4jx2j;
U2ðdNðxÞÞ ¼ 1
4jx0jþ 1
4
ejx1jþð
1
2þeÞjx2j:
148 The mul iobjec i e con inuous single acili y loca ion game is gi en by he cha ac e is ic se
149 VðSÞ¼KþLðSÞ, o any SNwhe e:
151151
153153 The eade may no ice ha LðSÞa e he non-domina ed alues o he co esponding bic i e ia loca ion
154 p oblems, i.e. LðSÞ¼ minðU1ðdSðxÞÞ;U2ðdSðxÞÞÞ.
155 Example 2.3. Conside he comple e g aph below.
2
157157 The bi-c i e ia Pa e o-minimum cos spanning ee game associa ed o he g aph is:
S{1} {2} {3} {1,2} {1,3} {2,3} N
zS
1(6.5,1.625) (9,2.225) (8.25,3.89) (16.75,4,68) (15,5.41) (17.38,6.27) (25,8.58)
zS
2(3.71,2.78) (9,2.25) (8,4) (15.14,5.35) (11.28,6.96) (17.38,6.27) (28.14,9.36)
S {1}, {2}, {3} {1,2} {1,3}
LðSÞ0
0
 1
4þe
1
4e
 1
4e

xþ1
2
1
4e

xþ1þ2e

o all x2½0;2
S{2,3} N
ðSÞexþ1
4e
1
42e

xþ3
4þ3e

o all x2½1;21
2xþ1
4e2exþ3
4þ3e

o all x2½1;2
S{1} {2} {3} {2,3} {1,2} {1,3} N
VðSÞ1
3
 1
2
 1
5
 2
3
 3
5

;2
6

2
6

;4
5

F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx 5
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS

UNCORRECTED PROOF
159159 I a se - alued TU-game is played hen an in e es ing ques ion is how an achie able ec o N2VðNÞ
160 should be di ided among he playe s. I is wo h no ing ha his is he same si ua ion ha appea s in scala
161 TU-games, whe e he wo h o ðNÞ2Rhas o be alloca ed among he playe s. Ne e heless, in he se -
162 alued case he e a e many elemen s ha can be conside ed o be di ided among he playe s.
163 The ex ension o he idea o alloca ion used in scala games o se - alued TU-games consis s o using a
164 payoff ma ix (an elemen o Rkn) whose ows a e alloca ions o he c i e ia. Since he payoffs a e ec o s,
165 he alloca ions in hese games a e ma ices Xwi h k ows (c i e ia) and ncolumns (playe s). The i h column,
166 Xi, in ma ix X ep esen s he payoffs o i h playe o each c i e ia; he e o e Xi¼ðxi
1;xi
2;...;xi
kÞ a e he
167 payoffs o playe i. The j h ow, Xj, in ma ix Xis an alloca ion among he playe s o he o al amoun
168 ob ained in each c i e ia; Xj¼ðx1
j;x2
j;...;xn
jÞa e he payoffs co esponding o c i e ia j o each playe . The
169 sum XS¼Pi2SXiis he o e all payoff ob ained by coali ion S.
170 Ma ix Xis an alloca ion o he game ðN;VÞ2GVi XN¼Pi2NXi2VðNÞ. The se o he alloca ions o
171 he game is deno ed by IðN;VÞ.
172 3. Dominance and co e concep s
173 An impo an poin in he de elopmen o se - alued TU-games is he use o he new o de ings defined in
174 he se o alloca ions. To his end, we mus eplace he comple e o de ‘‘ 6’’ in R, o he compa ison
175 be ween alloca ions and he cha ac e is ic se s, by he conside ed o de ings in Rk, ha is, ‘‘be be e o equal
176 componen wise’’, deno ed by ‘‘=’’, and ‘‘no be wo se’’, deno ed by ‘‘i’’.
177 To simpli y he p esen a ion in he ollowing, XSiVðSÞmeans XSi S8 S2VðSÞ, ha is, he e does no
178 exis S2VðSÞsuch ha XS5 S,XS6¼ S. Analogously XS=VðSÞmeans XS= S8 S2VðSÞ, ha is,
179 XS
jP S
j8j¼1;2;...;k;8 S2VðSÞ.
180 These o de ings, abo e defined, lead us o wo diffe en co e concep s in se - alued TU-games. When he
181 o de ing is defined as ‘‘i’’, we ha e he ollowing defini ion o co e:
182 Defini ion 3.1. The dominance co e o a game ðN;VÞ2GVis he se o alloca ions, X2IðN;VÞ, such ha
183 XSiVðSÞ8SN. We will deno e his se as CðN;V;iÞ.
184 Ne e heless, i may happen ha in some si ua ions he p e e ence s uc u e assumed by he agen s is
185 s onge , and coali ions only accep alloca ions i hey ge mo e han he wo h gi en by he cha ac e is ic
186 se . This assump ion modifies he a ionale o he decision p ocess unde he game and, he e o e, he co e
187 concep will be modified acco dingly. P oceeding simila ly, we in oduce now he concep o co e wi h
188 espec o he s ong o de ing, ha we will call he p e e ence co e.
189 Defini ion 3.2. The p e e ence co e o a game ðN;VÞ2GVis he se o alloca ions, X2IðN;VÞ, such ha
190 XS=VðSÞ8SN. We will deno e his se as CðN; ;=Þ.
191 The p e e ence co e is always included in he dominance co e. Thus, i may happen ha he o me se is
192 emp y while he la e se is no . Ne e heless, i he p e e ence co e is non-emp y hen he playe s will only
193 ag ee on alloca ions wi hin his se because all he playe s will be be e off wi hou assuming any com-
194 p omise. The e o e, his solu ion concep mus be conside ed in any se - alued game p o ided ha we a e
195 gi en ools o check whe he i is non-emp y.
196 The dominance co e defined abo e coincides wi h he se o s able ou comes (SO) in oduced by an den
197 Nouweland e al. (1989). Thus, ou ea men is simila o ha o hese au ho s al hough ou cha ac e -
6F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
198 iza ion is diffe en . In addi ion, we cha ac e ize he p e e ence co e, a concep no conside ed in he abo e
199 men ioned pape .
200 Example 3.1. Le us assume a p oduc ion si ua ion whe e h ee agen s can p oduce, using h ee diffe en
201 echnologies A, B, C, wo ypes o goods. The cha ac e is ic se o any coali ion Sis gi en by he p oduc ion
202 le els o each good using he exis ing echnologies, i.e. VðSÞis a se o h ee ec o s ( echnologies) wi h wo
203 componen s each one (goods). The ollowing able defines he cha ac e is ic se - alued map o he game
204 ðN;VÞ.
206206 I he agen s decide o coope a e and o p oduce wi h he echnology A hey mus alloca e he ec o
207 o goods (5,4), he alloca ion
X¼221
112

209 is in he p e e ence co e, while
Y¼13=25=2
3=23=21

211 is in he dominance co e and no in he p e e ence co e since Y 1;2g¼ð5=2;3Þjð3;1Þ, he hi d elemen o
212 he cha ac e is ic se Vð 1;2gÞ.
213 Impu a ions in he co e (any o hem) will be accep able i no coali ion can a gue agains i s alloca ed
214 amoun XS. To his end, we use he ollowing dominance concep s, whe e Rk
=s ands o x2Rk:xP0g.
215 Defini ion 3.3. Le us conside wo ma ices X,Y2Rknand a coali ion S2N.
216 1. Ydomina es X h ough Sacco ding o i, and we will deno e Ydom
S
iX, i :
(a) YSiXS,YS6¼ XS,
218 (b) YS2VðSÞRk
=.
219 2. Ydomina es X h ough Sacco ding o =, and we will deno e Ydom
S
PX, i :
(a) YS=XS,YS6¼ XS,
221 (b) YS2VðSÞRk
=.
222 In scala TU-games he se o non-domina ed impu a ions has been widely conside ed (see D iessen, 1988
223 and he e e ences he ein). Ne e heless, in se - alued TU-games he concep which plays he impo an
224 ole is he NDA se . These se s a e defined by:
225 1. NDAðN;V;iÞ¼ X2IðN;VÞsuch ha 9=SN,Y2IðN;VÞ,Ydom
S
iXg,
226 2. NDAðN;V;=Þ¼ X2IðN;VÞsuch ha 9=S2N,Y2IðN;VÞ,Ydom
S
PXg.
S{1} {2} {3} {1,2} {1,3} {2,3} N
A(1/2,1) (5/2,3/2) (1,2) (5,4)
B(1,1/2) (2,2) (2,1) (6,3)
C(4/5,3/4) (3,1) (3/2,4/3) (3,6)
F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx 7
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
227 Ou ollowing esul p o es ha bo h co e se s a e se s o non-domina ed alloca ions.
228 Theo em 3.1. The co e se s hold he ollowing p ope ies:
229 1. CðN;V;=Þ¼NDAðN;V;iÞ,
230 2. CðN;V;iÞ¼NDAðN;V;=Þ.
231 P oo . We only p o e 1. he p oo o 2. being simila .
232 1. )Suppose ha X2CðN;V;=Þand ha X62 NDAðN;V;iÞ. Then he e exis s SNand
233 Y2IðN;VÞ, such ha Ydom
S
iX, ha is, YSiXS,YS6¼ XSand YS2VðSÞRk
=, bu i is no possible
234 because XS=VðSÞ.
235 (Suppose ha X2NDAðN;V;iÞand ha X62 CðN;V;=Þ. Then, he e exis s SNand S2VðSÞ,
236 such ha XSis no be e componen wise hen S, ha is, SiXS. Now le us cons uc an alloca ion, Y,o
237 Sas ollows:
Yi¼
S
jSj8i2S;
08i62 S:

239 Alloca ion Yo S2VðSÞdomina es alloca ion X h ough coali ion Sacco ding o ibecause YS¼ SiXS
240 and YS2VðSÞ. Hence, i con adic s ha X2NDAðN;V;iÞ.
241 4. Exis ence heo ems
242 Once, we ha e defined he wo co e concep s and hei ela ionships i is impo an o gi e condi ions
243 ha ensu e non-emp iness o hese co es.
244 4.1. Dominance co e
245 Fo each scala ized ec o k2K,
K¼k2Rk;kj
(>0;j¼1;...;ksuch ha X
k
j¼1
kj¼1)
247 and any game ðN;VÞ2GV, we define he scala game ðN; kÞ2g as:
kð;Þ ¼ 0; kðSÞ¼ max
S2VðSÞRk
=
k S;8SN;S6¼;:ð1Þ
249 Using he game defined in (1) we es ablish a sufficien condi ion o he non-emp iness o he dominance
250 co e.
251 Theo em 4.1. The co e CðN;V;iÞo he game ðN;VÞ2GVis non-emp y i he e exis s ^
kk 2Ksuch ha he
252 scala game ðN; ^
kkÞ2g is balanced and i sa is ies ^
kkðNÞ 6¼ 0.
253 P oo . Le i ^
kk be a weigh in Ksuch ha he scala game ðN; ^
kkÞ2g , defined in (1), is balanced and e i y
254 ^
kkðNÞ 6¼ 0. Conside zS2ðVðSÞRk
=Þsuch ha ^
kk zS¼ ^
kkðSÞ8SN. No ice ha zS2VðSÞ, o he wise i is
255 possible o find ano he ec o S2VðSÞsuch ha zS5 S,zS6¼ S, and hen ^
kk zS<^
kk S. By Bonda e a and
256 Shapley heo em (see Bonda e a, 1963) he e exis s an alloca ion x2CðN; ^
kkÞ.
8F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS
UNCORRECTED PROOF
257 Now conside he ma ix X2Rknwhose columns a e:
Xi¼xi
^
kkðNÞzN8i2N:
259 Since ^
kkðNÞ 6¼ 0, we p o e ha X2CðN;V;iÞ. Indeed,
XN¼X
n
i¼1
xi
^
kkðNÞzN¼zN
261 and hen X2IðN;VÞ. Assume ha X62 CðN;V;iÞ. Then, he e exis s a coali ion SNand a ec o
262 wS2VðSÞsuch ha XS6wS,XS6¼ wS, ha is, ^
kk XS<^
kk wS. Then:
max
S2VðSÞRk
=
^
kk SP^
kk wS>^
kk XS¼X
i2S
^
kk Xi¼Pi2Sxi
^
kkðNÞ^
kk zN¼xSP ^
kkðSÞ¼ max
S2VðSÞRk
=
^
kk S:
264 This is a con adic ion. 
265 This esul s is use ul in finding elemen s in he dominance co e o diffe en se - alued games.
266 4.1.1. Mul iobjec i e linea p og amming games
267 The se - alued cha ac e is ic unc ion is usually defined h ough he se o non-domina ed alues o a
268 mul iobjec i e p og amming p oblem. A pa icula case o hese games a e he Mul iobjec i e Linea
269 P oduc ion Games. These games a e cha ac e ized because he objec i e unc ions o he mul iobjec i e
270 p og am a e linea . In his si ua ion we can ob ain an alloca ion o he dominance co e o any
271 z¼Cx 2VðNÞ. Indeed, gi en z¼Cx2VðNÞ, i is well-known ha he e exis s a ec o o weigh s ^
kk 2Rk,
272 ^
kk >0, such ha xis he solu ion o he scala p oblem:
½PNð^
kkÞ max ^
kk Cx
s: ::x2FðPNÞ:
274 Le ube an op imal solu ion o he dual p oblem o ½PNð^
kkÞ. The ma ix X¼ðX1;X2;...;XnÞwhose
275 columns a e Xi¼ðubi=^
kk zÞzbelongs o he dominance co e. This ollows om Theo em 4.1. No ice ha
276 Xis an alloca ion o z.
277 We no e in passing ha he choice o z2VðNÞcan be done aking a weigh ing ec o k>0. P ocedu es
278 guiding he agen s o he choice o weigh ing ec o s a e desc ibed in Ma mol e al. (2002) and he e -
279 e ences he ein.
280 Example 2.1 (con inued).Le us ake ^
kk ¼ð0:8;0:2Þ. The p oblem PNð^
kkÞis:
max 1:9x1þ3:4x2
s:a::x1þ8x2643;7x1þ4x2641;7x1þ8x2657;x1;x2P0:
282 An op imal solu ion o PNð^
kkÞis x1¼ð2:^
33;5:08^
33Þwi h objec i e alue z1¼ð25;8:58^
33Þ. An he op imal so-
283 lu ion o he dual o PNð^
kkÞis u¼ð0:179167;0;0:245833Þ. The alloca ion in he dominance co e ob ained by
284 he abo e me hod, is:
X¼6:567 9:938 8:495
2:254 3:412 2:917

:
286 4.1.2. Mul iobjec i e con inuous single acili y loca ion games
287 Fo his class o games we can p o ide a me hod o cons uc alloca ions in he dominance co e. The
288 app oach consis s o applying Theo em 4.1 ans o ming he mul iobjec i e game in o a scala con inuous
F.R. Fe n
aandez e al. / Eu opean Jou nal o Ope a ional Resea ch xxx (2003) xxx–xxx 9
EOR 5770 No. o Pages 15, DTD = 4.3.1
7 July 2003 Disk used ARTICLE IN PRESS