Inferring efficient weights from pairwise comparison matrices

Inferring efficient weights from pairwise comparison matrices. R. Blanquero, E. Carrizosa and E. Conde Facultad de Matem´aticas, Universidad de Sevilla Tarfia s/n, 41012 Seville, Spain {rblanquero,ecarrizosa,educon}@us.es November 14, 2003 Abstract Several Multi-Criteria-Decision-Making methodologies assume the existence of weights associated with the different criteria, reflecting their relative importance. One of the most popular ways to infer such weights is the Analytic Hierarchy Process, which constructs first a matrix of pairwise comparisons, from which weights are derived following one out of many existing procedures, such as the eigenvector method or the least (logarithmic) squares. Since different procedures yield different results (weights) we pose the problem of describing the set of weights obtained by ”sensible” methods: those which are efficient for the (vector-) optimization problem of simultaneous minimization of discrepancies. A characterization of the set of efficient solutions is given, which enables us to assert that the least-logarithmic-squares solution is always efficient, whereas the (widely used) eigenvector solution is not, in some cases, efficient, thus its use in practice may be questionable. Keywords: Analytic Hierarchy Process, Vector Optimization, Eigenvector method, Multiobjective Fractional Programming. 1 Introduction Several strategies have been suggested in the literature to associate with a set D={d1, . . . , dN}of decisions weights x1, x2, . . . , xNreflecting decision-maker’s preferences. In the Analytic Hierarchy Process (AHP), [14, 15, 17, 18], an N×Nmatrix 1This research has been supported by the Spanish Science and Technology Ministry and FEDER Grants No. BFM2002-04525-C02-02 and BFM2002-11282-E. 1 A, A=      a11 a12 · · · a1N a21 a22 · · · a2N . . .. . ..... . . aN1aN2· · · aNN       is obtained after asking the decision-maker (DM) to quantify the ratio of his/her preferences of one decision over another. In other words, for every pair of decisions di, dj,the term aij >0 is requested satisfying aij ≈xi xj (1) The matrix Aso obtained must be a positive reciprocal matrix, i.e., aji =1 aij >0 for all i, j = 1,2, . . . , N. For a given positive reciprocal matrix A, different procedures can be followed in order to obtain weights x1, . . . , xNaccording to (1), see e.g. [1, 2, 7, 9, 13, 16]. In particular, Saaty proposes the so-called Eigenvector method (EM): xis a column vector satisfying the equation Ax =λmaxx, where λmax is the dominant eigenvalue of the positive reciprocal matrix A. See e.g. [15] for further details, and [5] for commercial software with it. Many other choices have been proposed in the literature to derive xaccording to (1), mostly given as optimal solutions of optimization problems such as min x∈IRN ++ N X i,j=1 xi xj −aij!2 ,(2) or min x∈IRN ++ N X i,j=1 log( xi xj )−log(aij)!2 ,(3) where IRN ++ denotes the set of strictly positive vectors in IRN. It should become evident that different procedures, – (EM) or those derived from (2) or (3)–, although following (1), may yield different weights, and even different ranking of decisions may happen, as already shown e.g. in [16]. This naturally leads to the Nonconvex Vector-Optimization problem min x∈IRN ++ (|xi xj −aij|)i6=j(X) We recall the reader, e.g. [4, 20, 21], that, given an optimization problem (P), min x∈S(f1(x), . . . , fk(x)) , 2 y∈Sis said to dominate x∈Sif fi(y)≤fi(x) for all i= 1, . . . , k, with fi(y)< fi(x) for some i. Moreover, x∈Sis said to be efficient for (P) if no y∈Sdominates x, and xis said to be locally efficient for (P) if there exists a neighborhood Vof xin Ssuch that no y∈Vdominates x. Our aim is to find a full description of the set of locally efficient and efficient solutions for (X), and to explore whether the usual weighting methodologies, are (or are not) efficient for (X). 2 A test for efficiency Problem (X) is a multiple-objective nonlinear nonconvex problem whose feasible set is the strictly positive orthant IRN ++, which is not closed. This makes at first glance (X) very hard to solve. However, it is easy to construct an LP-based test of efficiency. Indeed, one has Theorem 1 Let x∗∈IRN ++.For each k, l = 1, . . . , N, define εkl =|x∗ k x∗ l−akl|.Then x∗is efficient for (X)if and only if for each k, l = 1, . . . , N, k 6=l, εkl is the optimal value of the Linear Problem min t s.t. xi−(εij +aij)xj≤0 for all pairs (i, j)6= (k, l) xi+ (εij −aij)xj≥0 for all pairs (i, j)6= (k, l) xk−t≤akl xk+t≥akl xl= 1 x1, . . . , xN≥0 t: unrestricted. (4) Proof It is a well known result of Vector Optimization, e.g. [4], that x∗is efficient for (X) if and only if for any pair of indices k, l = 1, . . . , N, k 6=l, x∗is an optimal solution to the fractional optimization problem (Pkl), [19] inf |xk xl−akl| s.t. |xi xj−aij| ≤ εij for all pairs (i, j)6= (k, l) x1, . . . , xN>0. (Pkl) Let k, l ∈ {1, . . . , N}, k 6=lbe given, and define the vector yas y=1 x∗ lx∗. Then, x∗solves (Pkl) if and only if ydoes, what happens if and only if ysolves (ˆ Pkl), inf |xk−akl| s.t. |xi xj−aij| ≤ εij for all pairs (i, j)6= (k, l) xl= 1 x1, . . . , xN>0. (ˆ Pkl) 3 Problem ( ˆ Pkl) is equivalent to the Linear Problem inf t s.t. xi−(εij +aij)xj≤0 for all pairs (i, j)6= (k, l) xi+ (εij −aij)xj≥0 for all pairs (i, j)6= (k, l) xk−t≤akl xk+t≥akl xl= 1 x1, . . . , xN>0. (5) This problem can also be written equivalently by replacing the strict inequalities xj>0 by non-strict inequalities xj≥0.In other words, we claim that (5) is equivalent to (4). Indeed, any xfeasible for (5) is also feasible for (4). Conversely, for any x, feasible for (4), we have that xl= 1 >0 xl−(εlj +alj)xj≤0 for all j,(6) from which we deduce that xj>0 for all j: else, if xj= 0,(6) would yield xl= 0, which contradicts xl= 1.Hence, the result follows. 2 Although Theorem 1 enables us to check whether a given x∗∈IRN ++ is efficient or not, it does not give insight in the structure of the efficient set. For this reason we devote the remaining of this section to provide alternative characterizations of efficiency for (X). Given a function π: IR++ −→ IR,consider the Vector-Optimization Problem (Xπ), min x∈IRN ++  π xi xj!−π(aij)!i6=j (Xπ) Lemma 2 Let π: IR++ −→ IR be strictly increasing. Then, x∗∈IRN ++ is efficient for (Xπ)iff x∗is locally efficient for (Xπ). Proof For each i, j = 1, . . . , N, i 6=j, the function x∈IRN ++ 7−→ xi xjis quasimonotonous and strictly quasimonotonous, [10] i.e., both lower and upper level sets and strict lower and upper level sets are convex. Since πis strictly increasing, the function x∈IRN ++ 7−→ π(xi xj) is also quasimonotonous and strictly quasimonotonous. Hence, the function x∈IRN ++ 7−→ max nπ(xi xj)−π(aij),−π(xi xj) + π(aij)o=|π(xi xj)−π(aij)| is quasiconvex and strictly quasiconvex, i.e., both its lower and strict lower level sets are convex. By definition, if x∗is efficient then x∗is also locally efficient. Conversely, given x∗,locally efficient, suppose, by contradiction, that it is not efficient. Then there exists y∈IRN ++ such that  π(x∗ i x∗ j )−π(aij) ≥ π(yi yj )−π(aij) ∀i, j, 4 with at least one inequality strict. Since the function is (strictly) quasiconvex, this property also holds for any zin the open segment with endpoints x∗and y, and, in particular, for zarbitrarily close to x∗.This contradicts the assumption that x∗is locally efficient. Hence x∗must be efficient for (Xπ).2 As a first conclusion, taking π(t) = t, we obtain that Theorem 3 x∗∈IRN ++ is efficient for (X)iff x∗is locally efficient for (X). Theorem 4 Let π: IR++ −→ IR be strictly increasing then, x∗∈IRN ++ is efficient for (X)iff x∗is efficient for (Xπ). Proof Let x∗be an efficient solution of problem (X); we will show that x∗is also efficient for (Xπ).Suppose, by contradiction, that x∗is not efficient for (Xπ),thus, by Lemma 2, x∗is not locally efficient for (Xπ). Then there exists y∈IRN ++,sufficiently close to x∗,such that  π x∗ i x∗ j!−π(aij) ≥ π yi yj!−π(aij) ∀i, j, (7) with at least one inequality strict, and satisfying yi yj ≥aij ∀i, j, such that x∗ i x∗ j > aij (8) yi yj ≤aij ∀i, j, such that x∗ i x∗ j < aij (9) Moreover, (7) implies π yi yj!=π(aij),∀i, j such that π x∗ i x∗ j!=π(aij).(10) Since πis assumed to be strictly increasing, (8) and (9) can be rephrased as π yi yj!≥π(aij),∀i, j such that π x∗ i x∗ j!> π(aij),(11) π yi yj!≤π(aij),∀i, j such that π x∗ i x∗ j!< π(aij).(12) By (7) this implies that  yi yj −aij ≤ x∗ i x∗ j −aij ∀i, j, with at least one inequality strict. This contradicts the assumption that x∗is efficient for (X). 5 The converse, is shown analogously using Theorem 3, and will not be given here. 2 Taking π(t) = log t, we have that x∗∈IRN ++ is efficient for (X) iff x∗is efficient for (Xlog), min x∈IRN ++ (|log(xi)−log(xj)−log(aij)|)i6=j(Xlog). For a given x∈IRN ++ let log(x) denote the vector log(x) = (log(x1),log(x2),...,log(xN)) . The discussion above shows the following Corollary 5 x∗∈IRN ++ is efficient for (X)iff log(x∗)is efficient for the piecewise linear convex vector-optimization problem (Y), min y∈IRN(|yi−yj−log(aij)|)i6=j.(Y) Corollary 6 The set of efficient solutions of (X)is connected. Proof By [3], the set EYof efficient solutions of (Y) is connected. Using Corollary 5 one has that the set of efficient solutions of (X) is the image of EYunder the continuous mapping (z1, . . . , zN)7→ (exp(z1),...,exp(zN)), showing connectedness. 2 Corollary 5 shows that, in particular, any optimal solution to min y∈IRN N X i,j=1 |yi−yj−log(aij)|2(13) is efficient for (Y),yielding Corollary 7 The row geometric mean x∗, x∗ i=  N Y j=1 aij  1 N , i = 1, . . . , N (14) is efficient for (X) Proof Optimality conditions, which are both necessary and sufficient for the unconstrained convex smooth program (13) read X j6=k (yk−yi−log(akj)) −X i6=k (yi−yk−log(aik)) = 0, k = 1, . . . , N. (15) 6 Since Ais a positive reciprocal matrix, log(aik) = −log(aki) for all i, k, thus (15) can also be written as Nyk= N X j=1 yj+ N X j=1 log(akj), k = 1, . . . , N, a particular solution of which is given by y, yk=1 N N X j=1 log(akj) = log   N Y j=1 akj  1 N , k = 1, . . . , N Hence, x∗defined in (14) is such that log(x∗) is efficient for (Y).Hence, x∗is efficient for (X). 2 Now we present a geometrical characterization of efficiency. Definition 8 Given y∈IRN, let G(y)be the digraph G(y) := ({1,2, . . . , N}, E(y)), (i, j)∈E(y)iff i6=jand yi−yj≥log(aij) Observe that, by definition, for i, j given, i6=j, either (i, j)∈E(y) or (j, i)∈ E(y),or both. Theorem 9 yis efficient for (Y)iff G(y)is strongly connected. Proof Let y∗be an efficient solution of (Y).This is equivalent, [3], to the fact that y∗is an optimal solution of the scalar problem (Pλ) min y∈IRNρλ(y) := X i6=j λij |yi−yj−log(aij)|(Pλ) for some λ= (λij)i6=j, with λij >0 for all i, j,i6=j. Problem (Pλ) is convex, hence, a necessary and sufficient optimality condition for y∗is 0∈∂ρλ(y∗).(16) The objective of (Pλ) can be written as ρλ(y) = X i6=j λij max {(yi−yj−log(aij)) ,(yj−yi+ log(aij ))}.(17) hence, every subgradient ξat y∗has the form ξ=X (i, j)∈E(y∗) (j, i)/∈E(y∗) λij ei−ej+X (i, j)/∈E(y∗) (j, i)∈E(y∗) λij −ei+ej+ +X (i, j)∈E(y∗) (j, i)∈E(y∗) λij hµij ei−ej+ (1 −µij)−ei+eji 7 where µij ∈[0,1] for all i, j such that {(i, j),(j, i)} ⊂ E(y∗). Hence, condition (16) can be rewritten as 0 = X (i, j)∈E(y∗) (j, i)/∈E(y∗) λij +X (i, j)/∈E(y∗) (j, i)∈E(y∗) −λij +X (i, j)∈E(y∗) (j, i)∈E(y∗) λij [µij −(1 −µij)] ∀i, (18) that is 0 = X (i,j)∈E(y∗) ˆ λij −X (j,i)∈E(y∗) ˆ λji ∀i= 1,2, . . . , N (19) where ˆ λij >0, for all i, j with i6=j. The homogeneous system (19) has at least one positive solution if and only if there exists a feasible flow in G(y∗) verifying the lower bound on the flow ˆ λij ≥1, for every arc (i, j). Following the circulation theorem of Hoffman [8, 11], this is equivalent to the non existence of cuts (S, S) having positive value V(S), where V(S) = d(S) + l(S, S)−u(S, S),(20) and d(S) is the sum of the demands at nodes of S,l() and u() are the sums of lower and upper bounds on the corresponding arcs. In our problem every demand is null, then d(S) = 0. Moreover l(S, S)=#{(i, j)∈G(y∗) : i∈S, j /∈S},(21) that is, l(S, S) is the number of arcs from Sto its complement. On other hand, there is no upper bounds on the individual flows through the arcs, that is u(S, S) = +∞ if (S, S)6=∅. Hence, G(y∗) cannot contain directed cuts, i.e. cuts satisfying (S, S) = ∅, [8, 11], since in other case, there exists Ssuch that u(S, S) = 0 which implies a positive value of V(S) in (20). Finally, note that a directed graph is strongly connected if and only if it has no directed cuts. 2 From the previous results one then obtains Corollary 10 Vector x∈IRN ++ is efficient for (X)iff G(log(x)) is strongly connected. Corollary 11 If x∈IRN ++ is efficient for (X)and x∗∈IRN ++ is such that E(log(x∗)) ⊇ E(log(x)),then x∗is efficient for (X). Remark 12 A characterization similar to that obtained in Corollary 10 is possible for weakly efficient solutions. We recall that x∗∈IRN ++ is said to be weakly efficient for (X)iff no x∈IRN ++ exists with  xi xj −aij < x∗ i x∗ j −aij for all i, j, i 6=j With the same scheme of the proof, one can show that x∗∈IRN ++ is weakly efficient for (X)iff G(log(x∗)) contains at least one cycle. 8 Corollary 10 will be the cornerstone of a geometrical characterization of the efficient set for (X).First we have Lemma 13 Given y∗∈IRN, the following statements are equivalent: 1. y∗is efficient for (Y). 2. For all k= 1, . . . , N, the set Bk(y∗) := nz∈IRN:zk= 0, zi−zj−log(aij)≥0 ∀i, j = 1, . . . , N such that y∗ i−y∗ j−log(aij)≥0ois bounded. Proof y∗is efficient for (Y) iff for all k= 1, . . . , N, (y∗ 1, . . . , y∗ k−1, y∗ k+1, . . . , y∗ N) is efficient for (Yk) min |yi−yj−log(aij)|i6=j, j6=k,|yj+ log(akj)|j6=k,|yi−log(aik)|i6=k(Yk) (Yk) is a linear multiobjective regression problem with design matrix of maximum rank, N−1 (it contains an (N−1) ×(N−1) identity submatrix). Hence, Theorem 1 of [3] applies. Thus, y∗is efficient iff the sets Bk(y∗) are bounded 2 Theorem 14 For x∗∈IRN ++ define C(x∗)as C(x∗) := nx∈IRN +:xi−aijxj≥0,∀i, j = 1, . . . , N such that x∗ i−aijx∗ j≥0o The following statements are equivalent: 1. x∗is efficient for (X). 2. For all k= 1, . . . , N, the set {x∈C(x∗) : xk= 1}is contained in IRN ++ ∪ {0}. 3. C(x∗)⊆IRN ++ ∪ {0}. Proof (1⇒2)Let x∗be an efficient solution for (X) and k∈ {1, . . . , N}. Then the vector xk=1 x∗ k x∗is also efficient for (X), thus by Corollary 5, log xkis efficient for Problem (Y). By Lemma 13 the set Bk(log xk) = nz∈IRN:zk= 0, zi−zj−log(aij)≥0 ∀i, j = 1 . . . N such that log(x∗ i)−log(x∗ j)−log(aij)≥0o =nz∈IRN:zk= 0, zi−zj−log(aij)≥0 ∀i, j = 1 . . . N such that x∗ i−x∗ jaij ≥0o is bounded. Let us suppose by contradiction that there exists x∈C(x∗)∩ {x:xk= 1}, with at least one null component, say x1= 0. 9