Set-valued TU-games

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