d =
q
j
(27)
ij
∑ k −
i
k =1
and yij is defined as (12).
The matrix of d coefficients is denoted as D. d expresses the aggregated difference
ij
ij
between the position of the i-th alternative in the preference order P and its positions in the
preference orders Pk, k=1, …, K. The distance matrix D is of the form
j = 1 j = 2
L
j = n
O ⎡d
d
L
d
1
11
12
1n ⎤
⎢
⎥
O d
d
L
d
2 ⎢ 21
22
2n ⎥
.
(28)
D =
⎢
⎥
M
M
M
O
M
⎢
⎥
O d
d
L
d
n ⎢
⎣ n1
n 2
n n ⎥⎦
The lower bound of the distance (26) is equal
n
C = ∑d
, where d
=
.
(29)
i min
[
min di1,....,din ]
i min
j
i=1
The value of C is of importance for estimation how close is the group judgement derived to
an “ideal” judgement.
The minimization problem (25) can be rewritten as a linear assignment problem
n
n
min ∑∑d y ,
(30)
ij ij
yij
i=1 j=1
subject to
Group Judgement with Ties. Distance-Based Methods
161
n
∀ ∑y = 1,
(31)
ij
i=1,...,n
j=1
i.e. an alternative can be placed at one position only and
n
∀ ∑y = 1, (32)
ij
j=1,...,n
i=1
i.e. only one alternative can be placed at a given position.
The latter constraint can be easily derived from ( 17 ) in the structure framework.
Summing (17) over l , l = l ,...,
and taking into account (15) one obtains
T
lT
l T
n
n
lT
n
l T
∀
∑∑yl =
yl
y
s
.
(33)
i T
∑ ∑ =
i T
∑ =
i T
∑ γ
l T l T
T=2,...,2n
l=l i=1
i=1 l=l
i=1
l=
T
T
l T
For the case of no ties one has T=2, 4, …, 2n (j=1, 2, …n).
From the table of structures (Table 5) it can be seen that sjj=1 and γjj=1. Finally one
n
gets 1
∀ ∑y = .
i j
j=1,...,n
i=1
This problem was described in details e.g. in Bury & Wagner, (2000) and Cook, (2006).
5.1.2 The Litvak median
Litvak (1982) introduced the notion of so called preference vector. For the preference order
given by k-th expert the preference vector is defined as follows:
k
k
π =[π K π ,
(34)
1 ,
, kn]
where k
π is equal to the number of alternatives preceding the i-th one in this preference
i
order.
Under assumptions taken
k
π = − ,
(35)
i
qki 1
where k
q denotes the position taken by the i-th alternative in the k-th expert’s opinion.
i
Example 3.
For a preference order P1 from Table 1, P1 = {O2, O3, O4, O1, O5} one has 1
π = [3, 0, 1, 2, 4].
The distance between preference orders is expressed in terms of corresponding preference
vectors.
Definition (Litvak, 1982).
Given two preference vectors k
k
k
1
π i 2k
π of the preference orders 1
P an d
2
P respectively.
The distance between these two preference orders is defined as
n
d( k1 k2
P ,P )= ∑ πk1 − πk2 .
(36)
i
i
i=1
It can be shown that the distance defined in such a way satisfies all the axioms describing
the measure of closeness (Litvak, 1982).
162
New Approaches in Automation and Robotics
Definition (Litvak, 1982).
The distance of a preference order P from the set of experts’ preference orders {Pk} is as
follows
K
n
d(
(k )
P,P )= ∑∑ πP − πk .
(37)
i
i
k =1 i=1
Let
k( j)
P( j)
k
h
= π
− π i=1,…,n; j=1,…,n; k=1,…K,
(38)
i
i
i
where P(j)
π is the number of alternatives preceding O
i
i if Oi takes the j-th position in the
preference order P.
Summing k(j)
h
(38) over k (k=1,...,K) one obtains (j)
h
i
i
K
( j)
h =
h
(39)
i
∑ k(j)
i
k =1
The distance (37) may be written as follows
n
n
K
n
n
(k )
(
d P,P ) = ∑∑∑ πP(j) − πk y =
h y
(40)
i
i
ij
∑∑ (j)i ij
i =1 j=1 k =1
i =1 j=1
where yij is defined by (12).
The matrix of (j)
h coefficients is denoted as H, (j)
h expresses the aggregated difference
i
i
between the position of the i-th alternative in the preference order P and its positions in the
preference orders Pk, k=1, …, K.
The distance matrix H is of the form
j = 1 j = 2 L j = n
O ⎡ (1)
(2)
(n )
h
h
L
h ⎤
1 ⎢ 1
1
1
(1)
(2)
(n ) ⎥
O2 ⎢h
h
L
h
.
(41)
2
1
2 ⎥
H =
⎢
⎥
M ⎢ M
M
O
M ⎥
On ⎢⎣ (1)
(2)
(n )
h
h
L
h
n
1
n ⎥
⎦
The lower bound of the distance (40) is equal (Litvak (1982))
n
G = ∑h
, where h
=
(42)
i min
[
min h(1)
i ,...., h(n )
i
]
i min
j
i=1
The problem of determining the Litvak median can be formulated as the following binary
optimization problem (Litvak, 1982; Bury & Wagner, 2000)
n
n
min ∑∑ (j)
h y
(43)
i
ij
yij
i=1 j=1
subject to (31)÷(32).
Group Judgement with Ties. Distance-Based Methods
163
One should note that in the case when in expert judgement tied alternatives can occur the
definition of preference vector makes it easy to determine its components and the distance
matrix. The preference vector for expert judgement with ties is of the same form for classical
as well as for fractional position system. Hence it may be applied for the optimization
problem formulated (43).
Example 2.
For a preference order P2 from Table 1, P2 = {(O2, O3), O4, (O1, O5)} one has 2
π = {3, 0, 0, 2, 3}.
5.1.3 The Kemeny median
The distance for the Kemeny median method is defined with the use of pairwise comparison
matrices (Kemeny, 1959; Kemeny & Snell, 1960).
For a given preference order of n alternatives presented by the k-th expert (k=1,...,K)
Pk: O ,O ,K,O the matrix of pairwise comparisons can be constructed as follows (e.g.
i1
i2
i n
Litvak, 1982); it is assumed that in expert judgement ties can occur.
⎡ k
k
a , K, a ⎤
⎧1
O
for
f O
i
l
k
⎢ 11
1n ⎥
k
⎪
A = ⎢ M
O
M ⎥ , where a = 0
O
for
O , 0
ak =
(44)
ii ^
il
⎨
≈
i
l
⎢ k
k ⎥
⎪− 1
O
for
p O
⎣a , K, a
⎩
n1
nn ⎦
i
l
i=1, …n, l=1, …, n.
The notation O f O ( O ≈ O ) should be read as follows: the i-th alternative O
i
l
i
l
i is better
than (equivalent to) the l-th alternative Ol with respect to a chosen criterion (a set of criteria).
Assume that two preference orders k1
P an d k2
P are given. The distance between these two
preference orders is defined as follows (e.g. Litvak, 1982; Bury & Wagner, 2000)
n
n
1
k1
k2
(
d P ,P ) = ∑∑ k1
a − k2
a .
(45)
il
il
2 i=1 l=1
It can be shown that the distance defined in such a way satisfies all the axioms describing
the measure of closeness (Litvak, 1982).
The distance between a given preference order P and a set of preference orders given by the
experts is defined as
n
n
K
1
d =
(k)
(
d P,P ) = ∑∑∑ P
a − k
a .
(46)
il
il
2 i=1 l=1 k=1
The following equality holds
k
P
k
P
k
P
k
P
a − a + a − a = 2 a − a = 2 a − a
(47)
il
il
li
li
il
il
li
li
so the expression (46) can be rewritten as follows
K
K
k
P
k
P
d = ∑∑∑ a − a + ∑∑∑ a − a
(48)
il
il
il
il
i
l k=1
i
l k=1
(i,l) (1)
I
∈
(i,l) (2)
∈
P
IP
where
164
New Approaches in Automation and Robotics
(1)
I -the set of indices (i,l) for which O f O in the preference order P, i.e. aP = . (49)
il
1
P
i
l
(2)
I -the set of indices (i,l) for which O ≈ O in the preference order P, i.e. aP = . (50)
il
0
P
i
l
Assume that in the preference order P O f O , i.e. aP = . In order to determine the
il
1
i
l
distance of this preference order from a given set {Pk}, use can be made of coefficients
defined as follows
K
K
K
r =
d P,P
a
a
a
1 .
(51)
il
∑ il( (k))= ∑ k − P =
il
il
∑ k −
il
k=1
k=1
k=1
They are called the loss coefficients and the matrix R=[ril] is called the loss matrix
(Litvak,1982). It is assumed that ril=0 for all i=l. It should be noted that elements of the
matrix R depend upon the form of preference orders Pk (k=1,...,K) only and are independent
of position system assumed (classical as well as fractional - if applicable).
Making use of the coefficients ril (i,l=1,...,n) the formulae (48) can be rewritten in the
following form (Bury & Wagner, 2000; Litvak, 1982):
K
k
d = ∑∑r + ∑∑∑ a .
(52)
il
il
i
l
i
l k=1
(i,l) (1)
I
∈
(i,l) (2)
∈
P
IP
If in the group judgement ties are not allowed, then (2)
I = {i,i}, i=1,...,n. In this case we have
P
(Litvak, 1982)
d = ∑r .
(53)
il
(i,l)∈ (1)
IP
This formula can be used to determine the lower bound E of the distance (53). Litvak has
shown that in the case under consideration the following theorem is satisfied.
Theorem (Litvak, 1982).
n −1 n
E = ∑ ∑min(r ,r .
(54)
il
li )
i =1 l =i +1
These results make it possible to propose some heuristic algorithms for determining the
Kemeny median (Bury & Wagner, 2000; Litvak, 1982).
The distance (53) can be written in the form
n
n
(k )
(
d P,P ) = ∑∑r x ,
(55)
il il
i=1 l =1
where
⎧
x = 1
O
for i f O in
the preference
P
order
(56)
il
⎨
l
⎩0
otherwise
The problem of determining a group judgement that minimizes the distance (55) can be
formulated as follows
Group Judgement with Ties. Distance-Based Methods
165
n
n
min ∑∑r x ,
(57)
il il
xil
i=1 l =1
It should be emphasized that this problem (even if ties are not allowed in group judgement)
cannot be solved within the framework presented in this subsection. It needs to be
formulated within the framework of structures presented for the case of ties.
5.2 The case of ties in group judgement
For this case the fractional notation is to be used i.e.
t ∈Ψ ={1, 1½, 2, 2½, 3, 3½, ….., n-1, n-½, n}.
5.2.1 The Cook–Seiford median
The problem (30) ÷ (32) is to be modified (double positions T are applied).
The distance matrix D is of the form
T = 2 T = 3 T = 4 L T = 2n
O
d12 d13
d14
d12n
1
O
d22 d23
d12
d12
2
D =
,
(58)
M
M
M
M
O d12
O
dn2 dn3
d12
d12
n
where
K
diT = ∑ k
2q − T ,
(59)
i
k =1
and k
q is the number of fractional position taken by an alternative O
i
i in the preference
order Pk given by the k-th ekspert.
The optimization problem is as follows
n 2n
min ∑∑diTy ,
(60)
i T
yiT i=1 T=2
with the constraints (15)÷(20).
5.2.2 The Litvak median
For the case of ties it is worth to notice that the number of alternatives preceding a given i-th
one in the preference order is determined by the level l this alternative takes in the table of
structures and equals ( l -1). This means that alternatives from the first level are preceded by
zero alternatives, alternatives from the second level are preceded by one alternative, etc.
The following example shows this observation.
Example 3.
For a preference order P2 from Table 1, P2 = {(O2, O3), O4, (O1, O5)} one has
P2 = {4½, 1½, 1½, 3, 4½}.
166
New Approaches in Automation and Robotics
Hence
(O2, O3) are placed in the positions 1½, 1½ on the level l =1; it is evident there are no
alternatives preceding those ones, 2
π = , 0
2
π = ,
2
0
3
O
2
4 takes the 3rd position on the level l =3, it is preceded by two alternatives, π =
,
4
2
(O1, O5) are placed in the positions 4½, 4½ on the level l =4, they are preceded by three
alternatives, 3
2
π = , 3
2
π = .
1
5
It may be shown that the components of a preference vector for a respective preference
order P may be determined as follows
P(l
π ) =
,
i
(l − Λ
)
1 l l =1, …, n ,
(61)
where Λ is given by ( 14 ).
l
The preference order P2={(O2,O3), O4, (O1, O5)} presented with the use of the table of
structures is as follows
T
2 3 4
5
6
7
8 9 10
t 1 1,5 2 2,5 3 3,5 4 4,5 5
Λ1=1 l =1
(O2, O3)
Λ2=0 l =2
Λ3=1 l =3
O4
Λ4=1 l =4
(O1, O5)
Λ5=0 l =5
Table 7. Positions and levels of alternatives for the preference order P2.
For a preference order P2 given above one has
P(1)
π
=
− Λ = , 0
P(1)
π
= ,
2
(1
)
1 1 0
3
P(3)
π
=
− Λ = ,
4
(3 1) 3 2
P(4)
π
=
− Λ = , 3
P(4)
π
= ,
1
(4
)
1 4 3
5
hence Λ = [1,0, 1, 1, 0] , 2
π = [3, 0, 0, 2, 3].
The coefficients k( )
h l
i
of distance matrix H are of the form:
k(l)
P(l)
k
h
= π
− π
i
i=1,...,n; k=1,...K;
i
i
l =1,...,n. (62)
Summing coefficients k( )
h l
i
(62) ove