ELSEVIER Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
EUROPEAN
JOURNAL
OF OPERATIONAL
RESEARCH
Theo y and Me hodology
Mul i-c i e ia analysis wi h pa ial in o ma ion abou
he weigh ing coe icien s
E. Ca izosa, E. Conde, F.R. Fe nandez, J. Pue o *
Depa amen o de Es ad s ica e In es igaci&n Ope a i a, Uni e sidad de Se illa, 41012 Se illa, Spain
Recei ed Oc obe 1992; e ised Ap il 1993
Abs ac
In his pape we add ess he p oblem o anking a se o al e na i es wi h pa ial in o ma ion abou he weigh ing
coe icien s. We in oduce a amily o quasio de s ha a e easily in e p e able and manageable, which includes
among o he s, he na u al quasio de in R n and o he well known p e e ence s uc u es in he li e a u e. The
en ichmen o he p e e ence s uc u e wi h espec o he na u al quasio de is measu ed by means o an absolu e
measu e we in oduce.
Keywo ds:
Mul iple c i e ia decision making; Pa ial in o ma ion; Weigh s
1. In oduc ion
Nea ly all he eal wo ld decision p oblems
in ol e mo e han one objec i e and can be o -
mula ed in a na u al way using he mul i-c i e ia
app oach:
'Max'
(x) - ( ,(x),..., n(X)) (1)
whe e
i:X--* ~
is he e alua ion o he i- h
objec i e (i = 1 .... , n) and X is he se o al e -
na i es o be anked.
In his o mula ion, and wi hou addi ional in-
o ma ion abou he objec i es, one can ob ain a
pa ial o de R I in X: Gi en wo al e na i es x,
y ~ X, we say ha x is as p e e ed as y ollow-
ing
R, (xRzy)
i
* Co esponding au ho .
i(x)> i(y) Vi=l,...,n,
o equi alen ly,
xRiy
i
~_, Will(X)> ~_, wi i(y )
l <i <_n l <_i <_n
Vw>O, w~ ~.
AS he pa ial o de Rz is ypically oo ague
(and he se o nondomina ed al e na i es is oo
la ge) a numbe o p ocedu es has been p oposed
in o de o en ich he p e e ence s uc u e abo e
(P ome hee [5], Elec e [19], in e ac i e me hods
[11], he u ili y app oach [9], e c.). The in e es ed
eade is e e ed o he seminal pape o Roy
[20] o a syn hesis o he main app oaches o his
p oblem which ha e been s udied.
In he u ili y app oach, one assumes he exis-
ence o a unc ion U: ~ ~ R, in such a way ha
an al e na i e x is conside ed as p e e ed o y i
U( i(x) ..... n(X)) >-- U( l(Y) ..... n(Y))"
0377-2217/95/$09.50 © 1995 Else ie Science B.V. All igh s ese ed
SSDI
0377-2217(93)E0270-8
292
E. Ca izosa e al. ~Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
Fu he mo e, unde mild egula i y condi ions
[12], U is a linea unc ion, i.e.: one assumes he
exis ence o a ec o w* = (w*,...,w*)_> 0 such
ha he Decision Make (D-M) p e e ences a e
gi en by he o de R:
xRy
i
~,, wTk(x ) ~ ~_, w~k(y ).
l~i~n l~i~n
Howe e , one o he main d awbacks o his
app oach is ha he D-M would ha e o es ima e
nume ically he weigh ( he ec o w*) ha each
c i e ion b ings o he inal sco e o an al e na i e
and he is no always willing o do so [6]. This
choice is a c i ical s ep, and, al hough some
me hodologies ha e been de eloped o a ain his
goal, such as he En opy me hod [11], he Saa y
me hod [21], he Solymosi and Dombi echnique
[23,15], e c., hey equi e, in ou opinion, oo
much specialized in o ma ion om he D-M.
Ins ead o p o iding he exac w*, he D-M
migh ha e some knowledge abou w* and his
in o ma ion can be used o ob ain a (pa ial)
anking in X which en iches he o iginal p e e -
ence s uc u e R I.
In his pape we show ha exac nume ical
weigh s a e no always necessa y. Ins ead o his
exac es ima ion, he D-M gi es only ce ain lin-
ea ela ions which exp ess pa ial in o ma ion
abou he ma ginal subs i u ion a es be ween he
c i e ia. This app oach is no new and some wo k
in his ield can be ound in he li e a u e; Ki -
wood and Sa in [13], Hazen [10], o Eisel and
Lapo e [8], de i e condi ions o de e mine o di-
nal ankings be ween al e na i es using pa ial
in o ma ion abou weigh ing cons an s.
Fo ins ance, in he quali a i e app oach [17]
he D-M is eques ed o es ima e only he ank
o de o he c i e ia. I he c i e ia a e a anged
in dec easing o de o p e e ence, wi h w 1 > • • •
> wn, hen
xny
i
w( (x)- (y))>O
Vw>_O,
WI~_ ... ~_Wn
o , equi alen ly (see
[17])
xRy
i g j(x)> ~] j(y) Vi=l,...,n.
j<_i j<i
In a mo e gene al se ing, he D-M is e-
ques ed o es ima e a linea ope a o which mixes
he weigh s, i.e. he D-M asse s ha he ec o
w* belongs o a ce ain polyhed on. Thus, gi en a
linea ope a o A, we de ine he p e e ence be-
ween he al e na i es by means o he bina y
ela ion
R A
as
xRay
i
w( (x)- (y))>_O
Vw>O,
Aw > O. (2)
All hese bina y ela ions a e quasi-o de s (i.e.
e lexi e and ansi i e) [26] and can be used o
pa ially ank he al e na i es, al hough hei use
equi es he solu ion o a linea p oblem o com-
pa e e e y pai o al e na i es.
Howe e , i he ex eme poin s
wl,...,w m
o
n
he poly ype {w :
Aw > O, w > O, F~i= lwi -
1} a e
known, he ela ion
R a
is
xRAy
i
wk( (x)-- (y)) >O
Vk = 1,...,m, (3)
which simpli ies i s use.
The ollowing example iUus a es he com-
men s.
Example 1.1. The s a manage o a consul ing
i m mus ank ou di e en execu i es o a bank
acco ding o he budge hey es ima e o nex
yea based on h ee inancial c i e ia. These c i-
e ia a e: loans gi en o clien s (C1), clien s' sa -
ings deposi s (C 2) and edemp ions achie ed (C3).
Each manage 's budge mus adhe e o he
inancial policy o he bank. This policy is gi en in
o m o h ee cons ain s:
1. The bank wishes ha he c edi s a e g ea e
han he sum o he edemp ions plus 1.5 imes
he sa ings.
2. The edemp ions mus be less han 0.1 imes
he sa ings deposi s.
3. The edemp ions mus be non-nega i e.
Conside he ollowing ma ix whe e he ow i
ep esen s he ac ion p oposed by he manage
i,
i= 1,...,4:
C1 C2 C3
a 1
11 12.2 0
a 2 5 4 5
a3 11 11 13
a 4
11 12 2.3
E. Ca izosa e al. / Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
293
Le F deno e he abo e ma ix. The con-
s ain s imposed by he bank can be w i en as
Wl>I.5w2+w 3,
W2>10W 3, W3>__0.
Thus, he linea ope a o A and he ex eme
poin s ma ix
E,
o he poly ope {w :
Aw > O, w >
0, Ei~__ lW~ = 1} a e espec i ely
(1.-1.5-1) 1527
A= 0 1 -10 and E= 2 10
5 27
1
0 0 1 0
and he qnasio de gi en by he abo e cons ain s
in he ac ion's se is ob ained om he ma ix
F × E b means o he na u al quasio de . Hence,
-11
287 298 ]
25 27
5 2...~3 125
5 27
F×E=
11 11 22- ~
11 zs~ 298.3.
25 27
gene a es a ela ion which can be ep esen ed by
he g aph o Fig. 1.
Howe e , wi h a di e en se o cons ain s
imposed by he bank gi en by he ope a o A ,
and whose ma ix ep esen a ion and ex emes
a e
1 -2.5 -2.5)
A1 = 0 1 -13 ,
0 0 1
1 5 35
7 49
E 1 0 2 13
7 49 ,
0 0
+9
i is easy o see ha he quasio de gene a ed is
ac ually an o de whose g aph is gi en in Fig. 2.
Thus, i is possible in many cases o iden i y he
Fig. 1. The g aph o
R A.
[K]-- [?N-- []
Fig. 2. The g aph o
RA
p e e ed al e na i es wi hou knowing he nu-
me ical es ima es o he c i e ion weigh s.
Howe e , he p e e ence s uc u e de e mina-
ion in i s gene al o mula ion ( he de e mina ion
o he se o non-domina ed al e na i es) is equi -
alen o he e ex polyhed on enume a ion,
which is no a polynomially sol able p oblem in
he size o he inequali y sys em de ining he
polyhed on [7,22].
The pape is s uc u ed as ollows: In Sec ion
2, we in oduce a class o ma ices
(Q-ope a o s)
and s udy some p ope ies o he quasio de s
hey induce. In Sec ion 3, we cha ac e ize some
Q-ope a o s ha a e easily unde s andable and
manageable. In Sec ion 4, we ex end he esul s
ob ained in p e ious sec ions o a b oade class.
The pape inishes wi h some conclusions and
possible ex ensions.
2. The class o Q-ope a o s
E e y linea ope a o A belonging o he se o
eal ma ices o dimension
k×n,
de ines a
quasi-o de
R n
on he se X o al e na i es:
Gi en a ma ix A ~ R kxn we de ine he poly-
opes C~ and CA:
C~=(w:Aw>O,w>O,
i=l~Wi=l} (4)
and
CA = w:Aw>_O,
wi=l , (5)
i=
and he quasio de
R a
on X:
xRaY
i
~wi i(x)>__ ~wi i(y )
i=1 i=1
Vw ~ C + . (6)
In his sec ion we in oduce a class o qua-
294 E. Ca izosa e aL / Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
sio de s induced by linea ope a o s
(Q-ope -
a o s)
ha ha e e y in e es ing p ope ies: he
ex eme poin s o he co esponding C~ can be
e y easily ob ained.
De ini ion
2.1. A linea ope a o A
~R.x.
is
said o be a
Q-ope a o
i de (A) ~ 0 and A -1 _> 0
(componen wise).
Fo a Q-ope a o A, he in e se ope a o A-1
exis s; we deno e i s elemen s by
aii,
and by /x
he ec o o sums o he columns o A-1:
The ma ix abo e is easily shown o be a Q-ope -
a o , hus Paelinck's heo em appea s as a di ec
consequence o ou Theo em 2.1. Indeed, A -a
can be eadily ob ained, and he ex eme poin s
o C~ a e he columns o he ollowing ma ix:
1
1/n
1 ~
...
1 1/n
0 -~ ...
0 0 ... 1/n
1/n
0 0 ... 1/n
A -l=
(aij)
and /xj= E
aij"
(7)
l <_i <_n
Theo em
2.1.
I A E ~Xn is a Q-ope a o , hen
C] is he con ex hull o he columns o A- 1, each
one no malized in o de o add 1.
P oo . As A-l>-0, i ollows ha /~i > 0, Vj =
1,...,n.
Le D be he diagonal ma ix such ha
dii =
1/Izi, Vi,
and le e e R ~ deno e he ec o o
ones. Gi en w e E', one has
w~C~ i 3z such ha
w=A-aDz, Dz>_O,
A-aDz >_ O, eA-1Dz = 1
i.e. ( ecall ha D >_ 0, A -1 _> 0, eA-1D = e)"
weC~ i 3z such ha
w=A-1Dz, z>O,
ez=l.
In o he wo ds, w ~ C~ i w can be ep esen ed
as a con ex combina ion o he columns o A-aD,
as asse ed. []
Rema k
2.1. The well-known Paelinck heo em
[17] p o en, among o he s, in [17,2,6,13], educes
o he calculus o he ex eme poin s o he poly-
hed on
{w e R ~ : w a > w 2 > • • • >_ w~ >_ O, ~i= aWi
= 1}, which is o he o m C~ o he ollowing
ma ix A:
(010 0
1 ~1 ... 0
0 0 ... 1
Rema k 2.2. In he
cen oid me hod
o Solymosi
and Dombi [23,15], gi en he polyhed on C~, one
p oposes as w* he a e age ec o o he ex eme
poin s o C]. By he heo em abo e, his w* is
easy o ob ain when A is a Q-ope a o : w*=
(1/n)A-ae.
Rema k 2.3. I should be no ed ha hese kinds
o quasi-o de s do no necessa ily need n linea
ela ions. I he D-M is only able o supply k < n,
hese ope a o s can be ans o med wi hou in-
co po a ing any addi ional in o ma ion. This is
possible by adding he na u al ela ions w i > 0
and emo ing he edundan ones. As an illus a-
ion, conside a p oblem wi h h ee objec i es,
whe e he D-M s a es ha w a > w 2 bu is unable
o p o ide mo e in o ma ion abou he weigh s.
Then he will ha e he ollowing ope a o A and
i s in e se
A-a:
A= 1 , A -1= 1 0 ,
0 0 1
and he quasi-o de would be
( a(x)
> l(Y),
XRAY
i
~ a(x)
+ 2(x) > x(Y) + 2(Y),
I 3(x) > 3(Y)"
Rema k 2.4. Ano he impo an p ope y o Q-
ope a o s is he ac ha hey induce in e al
weigh s, which a e easy o ob ain, allowing a
ce ain deg ee o sensi i i y analysis in he nu-
E. Ca izosa e al. / Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
295
me ical es ima ion o weigh s. The exac in e al
o
w i ~ C~, Vi = 1 ..... n,
is gi en by
WiG [Inj!n(olij//~j),
max(o ij/IXj)l, i=
1,...,n,
whe e
aij
and /xy we e de ined in (7).
Indeed, o i = 1,...,n, le
z i
be he op imal
alue o he linea p og am
max{w i : w ~ C~ }.
This
z~ is a ained a an ex eme poin o C~ and,
hus, by Theo em 2.1, z~ =
maxj(aiJixj).
Simi-
la ly, one concludes wi h he minimum.
Fo ins ance, o he quasio de
R A
desc ibed
in Rema k 2.1, i is easily seen ha
wl~[1/n, 11,
w2~[0,½1,...,
w,~[O, 1/n].
As a inal consequence, obse e ha one can
also ob ain he maximum and minimum alue
associa ed wi h each al e na i e x E X when he
weigh w a ies in C~, which is he basis o some
decision-making me hods (see, e.g. [3]). Indeed,
as inding he maximum ( espec . he minimum)
alue o
w (x)
when w a ies in C~ educes o
sol ing he linea p og am
max{w (x):w ~ C~}
( espec i ely
min{w (x) : w ~
C~}), Theo em 2.1
implies ha
min
~
ai---k i(x) <_w (x) < max ~ ° ik i(x )
k i=1 Zk k
i=1 ~k
Vw~C~, x~X.
The amily o ope a o s p oposed in he p e i-
ous heo em is maximal in he sense ha he
unique se o weigh s in ~n wi h n ex eme poin s
whe eby all he weigh s gene a ed a e non-nega-
i e a e hose wi h A- ~ _> 0. This is s a ed in he
ollowing heo em:
Fi s , we show ha D A = D~. Indeed, i is
e iden ha D~ c D A. Now, le
w ~ D A,
and we
will show ha w ~ D~. Ob iously, i w = 0, hen
w ~ D~, so we can assume ha w ~ 0; in o he
wo ds, we only ha e o conside he cases
(ew ~ O)
and
(ew < O, w 4= 0).
Case 1. ew>O.
Le w l=(1/(ew))w~C
A=
C~. Hence, w 1 > 0, hus w >_ 0, which ( ecall ha
w E D A)
implies ha w ~ D~.
Case 2. ew < O, w 4= O.
As by assump ion C A ~
¢, he e exis s
w°~ C A = CJ.
De ine w 1 as ol-
lows:
1 -- ew
w 1 -- --w d- w °.
1 - ew 1 - ew
Such w 1 e i ies ha w 1 ~ D A and
ew I
= 0. Fu -
he mo e, a leas one componen o w 1 is nega-
i e. Indeed, i w 1 > 0, hen, as
ew 1 = O,
i would
ollow ha w I = 0, hus
(ew)w °
= w; as w 4= 0,
ew < O,
one would ob ain
ew
< 0, hus 0
<Aw =
(ew)Aw°;
as 0<Aw
°
and
ew
<0, his would
imply ha
Aw °= O,
i.e.: ( ecall ha A -x exis s)
w ° = 0, which is a con adic ion.
Hence, w a has a leas a nega i e componen ,
hus he e exis s some A, 0 < h < 1 such ha he
ec o w 2 = hw* + (1 - h)w ° e i ies ha
Aw 2 >
O, ew 2
> 0, w 2 has a leas a nega i e componen .
By case
1, w e ~D~,
which is a con adic ion.
Hence,
D A = D~,
as we claimed.
Wi h his, we a e in posi ion o show ha
A-l> 0. Indeed, le be a column o A-l; as
AA -1 gi es he iden i y ma ix, i ollows ha
A >_ O,
i.e.,
~ D A,
hus > 0. Then, we ha e
shown ha all he columns o A-1 e i y ha
>_ 0, hus A-1 >_ 0, as asse ed. []
Theo em 2.2.
Le A
~ ~n×n
be a linea ope a o
such ha
de (A) ~ 0
and C A -4= ~J. Then C + = C A
i A-l >O.
P oo . I is e iden ha , i A-l> 0 hen C~ =
C A. We now show he con e se. Le A be an
n × n ma ix wi h de (A) ~ 0 such ha C~ =
C A.
De ine he se s D n and D~:
D4={wE~n:Aw >>. O},
D~={w~n:Aw >O, w>O}.
The p ocess o supplying in o ma ion o he
ini ial mul i-c i e ia p oblem ans o ms he p e -
e ence scheme. Thus in he beginning, i.e. when
no in o ma ion is a ailable, one al e na i e x ~ X
is p e e ed o ano he
y~X
i
(x)>_ (y)
(componen -wise), Tha is, wi h no in o ma ion,
he p e e ence scheme coincides wi h he Pa e o
quasi-o de . So, i seems na u al ha in he p o-
cess o supplying in o ma ion, he mo e p ecise
in o ma ion he D-M gi es, he mo e accu a e
quasi-o de will be gene a ed. I is e iden ha

296
E. Ca izosa e al. / Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
e e y quasi-o de
R A
wi h A- 1 >_ 0, imp o es he
no-in o ma ion- ela ion because i educes he
se o weigh s. Bu gi en wo ela ions
R A
and
R B i is no clea how o de e mine which o hem
is he mos accu a e.
Howe e , his is e y impo an because i al-
lows us o know he deg ee o knowledge shown
by he D-M abou his own p oblem. The mo e
accu a e he quasi-o de , he be e he knowl-
edge o he p oblem. Mo eo e , i seems na u al
ha he accu acy o a ela ion is in e sely p opo -
ional o he magni ude o i s se o weigh s as is
p oposed by Rios [18], so we de ine he accu acy
o
R A
in he ollowing way.
De ini ion
2.2. Gi en a Q-ope a o A, he accu-
acy o
RA,
AC(RA), is de ined as IXn_l(C~) /
/xn_l(C~), whe e /x,_ 1 ep esen s he Lebesgue
measu e in Nn-~.
The limi alues o he accu acy a e gi en in
he ollowing p oposi ion•
P oposi ion
2.1. I A is a Q-ope a o , hen 1 <
AC(RA) < + oo.
P oo . Fi s o all, ix~_l(C~)<lx,_~(C -), VA E
N~xn. Second, as A -1 > 0, C~ is a simplex in he
hype plane El<_i<,wi = 1 and /X,_x(C~)>0.
Then 1 _< AC(R A) < +m. []
The alue 1 co esponds o he i s no-in o -
ma ion case and, hence, we can see he accu acy
as a educ ion measu e o he se o weigh s.
Mo e p ecisely e e y ope a o ha gene a es an
o de on R n has an accu acy +~. An o de
ela ion o his kind could be seen as he limi
case o a con e gen sequence o quasi-o de s
wi h inc easing and mo e p ecise in o ma ion.
Finally we shall gi e he exp ession o he
accu acy:
Theo em
2.3. Le A be a Q-ope a o . Then,
AC(R A) = [de (A)lFIl<j_<~/xj, whe e z k was de-
ined in (7).
P oo . Fi s , ecall ha he olume o he simplex
gene a ed by he poin s xX,..., x n in ~-1 is [1]
1 1 ... 1
1 x~
x 2 ...
x~'
(n- 1)~ de ".
X 1 X 2 X n
n--1 n--1 • " " n--1
Le e i ~ ~" be he ec o whose i- h componen
is one and ze o he es . Conside he sys em o
e e ence ~ in he hype plane H = {w:ew = 1}
ha has e 1 as o igin and he ec o s e i-e 1,
i = 2 ..... n, as gene a o s. Then, any poin w =
(wa,. •., w n) ~ H has coo dina es (w2,..., w n) in
~9~. By Theo em 2.1, CJ is gene a ed by he ec-
o s
Olli// ]Z i I
azz/ Zi. ], i= l,...,n.
I
Olni/~i ]
Hence,
AC(RA)
0/21/],-£1 0/22///£ 2 ...
012n/1.£ n
= de . .
O/nl//l-L 1 ang///L~ 2 ...
Olnn//l~n
Thus ( ecall ha /-~i = E]=laij, Vi),
AC(RA)
[ a11//]£ 1 O/12///'£2 ...
Olln//~n --1.
= de " -.
O/nl//~L~ 1
Oln2/~ 2 ... ann/]£n
In o he wo ds,
1
AC(RA) = [de (A-1)[FI]=l(1//xj)
n
= [de (A) I 1-I/xj,
j=l
as asse ed. []
Example 2.1. Fo he quasio de
R A
desc ibed in
Rema k 2.1, one has ha de (A)= 1 and /xj =j,
Vj', hus AC(R A) = n!
E. Ca izosa e al. / Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
297
Fo he quasio de s
R A
and
RA~
in oduced in
Example 1.1, he imp o emen in he o de ela-
ion om
R A
o
RA1
can be measu ed by means
o he accu acy: AC(R A) = 67.5 and AC(Rq)=
171.5.
3. Some amilies o Q-ope a o s
The wides class o ope a o s we can deal wi h
is cha ac e ized in Theo em 2.2. Howe e , he
condi ion shown in he p e ious pa ag aph is
di icul o check be o ehand. So in o de o
enable he D-M o apply hese ela ions, we
p opose wo sub-classes belonging o he o iginal
one wi h h ee impo an p ope ies:
1. o know be o ehand ha hey belong o he
b oad class;
2. o be easy o he D-M o unde s and and
accep ;
3. o be su e ha he se o weigh s i gene a es
is no emp y.
A p ocedu e o ob ain a class o hese ope a o s
consis s in o e ing he D-M he compa ison o
each c i e ion i(-) wi h a mos a coali ion o he
emaining c i e ia.
Usually, he exac de e mina ion o he weigh s
is made by he ade-o be ween a c i e ion and
he emainde s. Bu his me hodology canno be
used i he D-M does no gi e i s p e e ences so
p ecisely.
Al e na i ely, ou app oach p oposes o e-
place his equi alence by inequali ies which a e
qui e accep able o he D-M. In his p ocess, he
mo e p ecise in o ma ion he D-M supplies, he
mo e accu a e he quasi-o de i gene a es, and
hence i is close o he ca dinal u ili y.
The e o e, he in o ma ion equi ed om he
D-M abou he c i e ion
i(.)
which he is willing
o gi e, will ha e he ollowing o m:
Wi ~--- E aijwj, aij ~ O, E aij ~ 1,
j4=i j~i
whe e
aij
ep esen s he minimum ma ginal sub-
s i u ion a e o
i
o j. We should no ice ha
when no in o ma ion is a ailable, his kind o
ela ion will be wi > 0. Bu , e en by supplying
small alues o
ais
one imp o es he accu acy o
he quasi-o de gi en by he D-M and a oids he
p oblem o he exac es ima ion o he weigh s
(ca dinal u ili y).
Example 3.1. We shall deal wi h he ollowing
example in which he D-M has h ee objec i es, a
se X o easible al e na i es, and he is able o
gi e he equi ed in o ma ion in he o m o
inequali ies.
W 1 ~ 0.5W2,
W 2 ~ 0.5W 1 q- 0.5W3,
w 3 > 0.5w 2 .
Then he ope a o is de ined by he ma ix
A,
whose ex eme poin s a e gi en by he columns o
he second ma ix and he in e al weigh s a e
1 -0.5 0
A = -0.5 1 -0.5
0 -0.5 1
1 1 1
2 4 ~ W1 ~ [61 ' 1]
1 1 1
E = 3 2 X
W2 ~ [31-' 1].
: : :
w.~[L½]
6 4 g
Hence i s accu acy AC(R A) = 18.
This example sugges s he possibili y ha hese
kinds o ope a o s ha e he p ope y o in e se
posi i e. In o de o cla i y he e ms used in he
ollowing esul s we in oduce wo classical con-
cep s [16].
De ini ion 3.1. A linea ope a o A ~ R nxn is
diagonally dominan i
~_, laijl < laiil, i= l,...,n,
]~i
and s ic ly diagonally dominan i s ic inequali-
ies hold o all i = 1 ..... n.
The esul sugges ed by he example abo e is
s a ed in he ollowing heo em.
Theo em 3.1.
Le A ~ ~nXn be a diagonally domi-
nan linea ope a o such ha
aij <_
0,
i ~ j,
aii >
0,
V i = 1 ..... n, and
de (A) ~ 0.
Then A -: > O.
298
E. Ca izosa e aL ~Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
P oo . Fo simplici y and wi hou loss o gene al-
i y, we conside
aii = 1, Vi.
As A is
diagonally
dominan , he inequali ies
aii
>~
--Y'.j~iaij, Vi =
1 .... ,n,
hold. Then e e y
co ac o Aij
o he
ma ix A is nonnega i e [4].
Le A -1 be he in e se o
A,
whose elemen s
a e
a u =Aii/de (A).
Then he sign o aij., Vi, j,
coincides wi h he sign o de (A) and
de (A)
1 a12
... aln
0 1 -- a12a21
... a2n -- alna21
= de
0 an2 -- al2anl ... 1 -- alnanl
1 a12 "'" aln ~
= de O A 1
J
=dee(A1).
Besides, he ma ix A~ is diagonally dominan
because o all i = 2 .... , n hei elemen s e i y
1 - aliail
>
0 and
1+
~ aij+ail (-
~au)>l+
Zaij>_O.
j¢i,j~a j4=l / j#i
Thus, we can epea his easoning n imes and
we ob ain ha de (A) > 0. []
Co olla y 3.1.
Le A ~
~x~
be a s ic ly diago-
nally dominan linea ope a o such ha aii ~
0,
i =~ j, aii > O, Vi = 1 ..... n. Then A- 1
~
O.
he can compa e he impo ance o se e al c i e ia
be ween hem. So he exp ession ob ained o he
c i e ion ~ anked in i- h posi ion is
wi>- ~,auw j, ai~>-O,
j>i
whe e
ai
ep esen s he minimum ma ginal sub-
s i u ion a e o
i
o p
In his sub-class he h ee p ope ies enume -
a ed a he beginning o Sec ion 3 also hold and
hey belong o he class cha ac e ized by Theo-
em 2.2.
Theo em 3.2.
Le A ~ W '×n be a diagonal posi i e
iangula linea ope a o such ha a u < O, Vj > 1.
Then A- 1 > O.
P oo . In his si ua ion de (A)=
~[l<i<naii >
0
and he co ac o s a e
Aij= ]'-I
akk>0
Vi < j,
k~i,k~j
Aii = YI akk > O,
i = l,...,n,
k~i
Aq=0
Vi>j.
Hence, easons analogous o he ones we used in
Theo em 3.1 p o e his heo em. []
4. Non-homogeneous Q-ope a o s
This class o ope a o s is closely ela ed o a
well known amily o linea ope a o s called M-
ope a o s [16,25], bu he i s one exhibi s in i s
a o he easy in e p e abili y and manipula ion
because he M-ope a o s equi e p ope ies o
i educibili y o s ic diagonal dominance, no
needed in he p oposed class.
I mus also be no ed ha he well known
o dinal ela ion men ioned in Rema k 2.1 is an
example o such an ope a o .
Ano he impo an sub-class o ope a o s be-
longing o he class cha ac e ized by Theo em 2.2
a e he iangula and nonposi i e o -diagonal
elemen s. This ype o ope a o co esponds o
he si ua ion in which he D-M is able o do a
ce ain ank o de in he c i e ia and in addi ion,
On many occasions, he D-M is willing o
ob ain a leas ce ain le els in his weigh s [14], so
he quasi-o de is gi en by a linea ope a o A
and a le el ec o A _> 0. In his case, he se o
easible weigh s is gi en by he poly ope
(w ~ ~ :w >__ O, Aw >_, ,
C~,~) =
w i
= 1 / . (8)
E
i=l,...,n I
Hence he pai (A, A) induces he ela ion
R(A,a )
gi en by
XR(A,;~)y
i
w( (x)-- (y)) >O
Vw e C(5,, ). (9)
E. Ca izosa e al. /Eu opean Jou nal o Ope a ional Resea ch 81 (1995) 291-301
299
An in e es ing ype o hese ela ions a e hose
de ined by a ma ix A wi h non-nega i e in e se
(componen wise) and eA-1A < 1. In wha ollows
we say hese ela ions a e induced by a non-ho-
mogeneous Q-ope a o (A, A). To his kind o e-
la ions we can ex end all he p e ious esul s wi h
minimum e o as can be seen om he ollowing
heo em.
Theo em
4.1. Le (A, A) be a non-homogeneous
Q-ope a o . Then
w -A-1A
w~C~,A) i l_eA_lh ~CJ.
P oo .
w~C A,h ) i 3 >OIAw=h + , w>0,
ew = 1; i.e. ( ecall ha
A -1 >__ 0):
w~C~,~) i 3 >OIw-A-~h=A-l ,
ew = 1.
As e(w
-A-1A) =
1 - eA-1h > 0, i ollows ha
1
w~C~,x) i :l >Ol l_eA_lh (W-A-1h)
=A -1 i
3 >__0[W =A-i ,
1 -
eA-1h
e~ = 1,
w -A-1A
whe e - 1-eA-1A i ~C~.
Which concludes he p oo . []
Co olla y
4.1. I (A, A) is a non-homogeneous
Q-ope a o , hen he se C(~,x) is he con ex hull o
he columns o he ollowing ma ix:
/x11(1
- Eke_l ZkAk)
A2
A_I[ 1 -
mogeneous case, we wish o pay some a en ion
o he ollowing p oblem. We know ( ecall Re-
ma k 2.3) ha he e exis many quasi-o de s ha
p oduce he same in e als o hei weigh s; bu ,
a e he e any o hem which mus be empha-
sized?
The answe is a i ma i e and among hese
ope a o s one is pa icula ly in e es ing; i is
known in he li e a u e as E-cone [24] which is
one o ou non-homogeneous Q-ope a o s. This
kind o ope a o ( he E-cone) is based on ela-
ions o he o m w i>_k i, i = 1,...,n (one pe
objec i e)• Thei wo main p ope ies a e ha he
se o weigh s i de ines includes he in e al
weigh s conside ed be o ehand and also is mini-
mal (in he inclusion sense among he ope a o s
o his kind). We s a e and p o e his in he
ollowing heo em•
Le k = (k 1 .... , k n) >_ 0. Conside he se
C+(l,k)---- ( ~n Wi__ Wi= }
w ~ : >ki; ~ 1
l <_i <_n
and o each a,/3 ~ ~n such ha 0 _< ag _< ig _< 1,
Vi, and F,~=la i < 1 < E~=I/3g, he se (see [2])
X(a,13)=(w~n:O NWN/3;
~ wi=l}.
l <_i <_n
Theo em
4.2. The ec o k = (kl,..., k n) wi h k i
= max(a i, 1 - Ej~//3j), i = 1 ..... n, de e mines
he minimum se C Lk) con aining he se X(~, ~).
A 1
1 -/xKl(1 - Ek,2/ZkAk)
An
whe e IX j, j = 1 ..... n, we e de ined in (7).
... A 1
''• /~2
... 1--/X21(1--Ek.n~k; k)
Al hough all he p ope ies holding in he ho-
mogeneous case can be ex ended o he non-ho-
P oo .
Fo all (kl,..., k n) >_ O,
El <_i<_nki __<
1, one
can ob ain, using Co olla y 4,1, ha C(~,k ) is he