Coherent weights for pairwise comparison matrices and a mixed-integer linear programming problem

Abstract

Pairwise comparison matrices (PCMs) have been a long standing technique for comparing alternatives/criteria and their role has been pivotal in the development of modern decision making methods. In order to obtain general results, suitable for several kinds of PCMs proposed in the literature, we focus on PCMs defined over a general unifying framework, that is an Abelian linearly ordered group. The paper deals with a crucial step in multi-criteria decision analysis, that is to obtain coherent weights for alternatives/criteria that are compared by means of a PCM. Firstly, we provide a condition ensuring coherent weights. Then, we provide and solve a mixed-integer linear programming problem in order to obtain the closest PCM, to a given PCM, having coherent weights. Isomorphisms and the mixed-integer linear programming problem allow us to solve an infinity of optimization problems, among them optimization problems concerning additive, multiplicative and fuzzy PCMs.

Appendix

Proof of Theorem 1

$1 \Leftrightarrow 2$. The direct implication is straightforward; we have to prove $2\Rightarrow 1$, that is the second equivalence in (17).

Let us assume $w_{i}=w_{j}$. If ad absurdum $g_{ij} \ne e$ then $w_{i}>w_{j}$ (if $g_{ij} > e$) or $w_{i}<w_{j}$ (if $g_{ij} < e$); it is against the assumption. Thus, $g_{ij} = e$. Vice-versa, let us assume $g_{ij} = e$. If ad absurdum $w_{i}\ne w_{j}$ then $g_{ij} > e$ (if $w_{i}>w_{j}$) or $g_{ij} < e$ (if $w_{i}<w_{j}$); it is against the assumption. Thus, $w_{i}=w_{j}$ and the assertion is achieved.

$1 \Leftrightarrow 3$. The direct implication is straightforward; we have to prove $3\Rightarrow 1$.

Let us assume $w_{i}>w_{j}$. If ad absurdum $g_{ij} \le e$ then $w_{i}=w_{j}$ (if $g_{ij} = e$) or $w_{i}<w_{j}$ (if $g_{ij} < e$); it is against the assumption. Thus, $g_{ij} >e$. Let us assume $w_{i}=w_{j}$. If ad absurdum $g_{ij} \ne e$ then $w_{i}>w_{j}$ (if $g_{ij} > e$) or $w_{i}<w_{j}$ (if $g_{ij}< e$); it is against the assumption. Thus, $g_{ij} = e$ and the assertion is achieved. $\square$

Proof of Theorem 2

$1 \Rightarrow 2$. Let us assume that $\mathbf{G }=(g_{ij})_{n \times n}$ is a restricted max–max ${\mathcal {G}}$-transitive PCM (i.e. $\mathbf{G }=(g_{ij})_{n \times n}$ satisfies (20)).

Let $g_{ij}\ge e$. By (20), $g_{ik}\ge \max \{ g_{ij},g_{jk} \} \ge g_{jk}$ for all $g_{jk} \ge e$. Let us assume that $g_{jk} <e$. If ad absurdum, $g_{ik} < g_{jk}$, then, by $g_{ki}>e$, $g_{ij}\ge e$ and (20), $g_{kj}\ge \max \{ g_{ki},g_{ij} \} \ge g_{ki}$. Thus, by ${\mathcal {G}}$-reciprocity, $g_{ik} \ge g_{jk}$; it contradicts $g_{ik} < g_{jk}$. Thus, $g_{ik} \ge g_{jk},$ for all $k \in \{1, \ldots , n\}$.

Vice versa, if $g_{ik} \ge g_{jk}$ for all $k \in \{1, \ldots , n\}$, then for $k=j$, $g_{ij} \ge g_{jj}=e$.

$2 \Rightarrow 1$. Let $g_{ij} \ge e \text { and } g_{jk} \ge e$.

Let us assume ad absurdum that $g_{ik}< \max \{ g_{ij},g_{jk} \}$. If $g_{ik}<\max \{ g_{ij},g_{jk} \}= g_{ij}$, then by $g_{jk} \ge e$ and 2., we have $g_{jl} \ge g_{kl}$ for all $l \in \{1, \ldots , n\}$, and, for $l=i$, $g_{ji} \ge g_{ki}$. Thus, by ${\mathcal {G}}$-reciprocity, $g_{ik} \ge g_{ij}$; it contradicts $g_{ik}< g_{ij}$. If $g_{ik}<\max \{ g_{ij},g_{jk} \}= g_{jk}$, then by $g_{ij} \ge e$ and 2., we have $g_{il} \ge g_{jl}$ for all $l \in \{1, \ldots , n\}$, and, for $l=k$, $g_{ik} \ge g_{jk}$; it contradicts $g_{ik}< g_{jk}$.

Thus, 1. is achieved. $\square$

Proof of Corollary 1

Let $g_{ij} =e$. By Theorem 2, $g_{ik} \ge g_{jk}$ and $g_{jk} \ge g_{ik}, \; \forall k \in \{1, \ldots , n\}$; thus, $g_{ik} =g_{jk}$ for all $k \in \{1, \ldots , n\}$.

Let $g_{ik} =g_{jk}$ for all $k \in \{1, \ldots , n\}$. For $k=j$, $g_{ij} =g_{jj}=e$. $\square$

Proof of Proposition 2

By Theorem 1, it is enough to prove $m_{{\mathcal {G}}}( \mathbf{g }_{i})> m_{{\mathcal {G}}}( \mathbf{g }_{j}) \Leftrightarrow g_{ij}>e.$

Let $m_{{\mathcal {G}}}( \mathbf{g }_{i})> m_{{\mathcal {G}}}( \mathbf{g }_{j})$. If ad absurdum $g_{ij}\le e$, then by ${\mathcal {G}}$-reciprocity $g_{ji}\ge e$ and, by Theorem 2, $g_{jk} \ge g_{ik},$ for all $k \in \{1, \ldots , n\}$ and, as a consequence, $m_{{\mathcal {G}}}( \mathbf{g }_{j})\ge m_{{\mathcal {G}}}( \mathbf{g }_{i})$; it contradicts $m_{{\mathcal {G}}}( \mathbf{g }_{i})> m_{{\mathcal {G}}}( \mathbf{g }_{j})$.

Let $g_{ij}>e$. By Theorem 2, $g_{ik} \ge g_{jk},$ for all $k \in \{1, \ldots , n\}$; thus:

$$\begin{aligned} m_{{\mathcal {G}}}\left( \mathbf{g }_{i}\right) = \left( \bigodot _{k=1}^n g_{ik}\right) ^{\left( \frac{1}{n}\right) } \ge \left( \bigodot _{k=1}^n g_{jk}\right) ^{\left( \frac{1}{n}\right) } = m_{{\mathcal {G}}}\left( \mathbf{g }_{j}\right) . \end{aligned}$$

In order to prove that $m_{{\mathcal {G}}}( \mathbf{g }_{i}) > m_{{\mathcal {G}}}( \mathbf{g }_{j})$, it is enough to prove that there exists a value ${\overline{k}}$ such that $g_{i{\overline{k}}} >g_{j{\overline{k}}}$. If ad absurdum, $g_{ik}=g_{jk}\;$ for all $k \in \{1, \ldots , n\}$, then, for $k=j$, $g_{ij}=g_{jj}=e$; it contradicts the assumption $g_{ij}>e$. Thus, $m_{{\mathcal {G}}}( \mathbf{g }_{i})> m_{{\mathcal {G}}}( \mathbf{g }_{j})$. $\square$