1 Introduction↩︎

Pairwise comparison matrices play a central role in several multi-criteria decision-making methodologies such as the Analytic Hierarchy Process (AHP) [2], [3]. However, while pairwise comparisons efficiently decompose complex decision-making problems into simple subproblems, this comes at a price: there is no guarantee of cardinal consistency. For example, if alternative \(A\) is two times better than alternative \(B\), and alternative \(B\) is three times better than alternative \(C\), alternative \(A\) is not necessarily six times better than alternative \(C\), in contrast to their indirect comparison through alternative \(B\). Indeed, both empirical [4] and randomly generated [5], [6] pairwise comparison matrices are usually inconsistent. The level of inconsistency is measured by inconsistency indices [7].

1.1 The need for inconsistency thresholds in the incomplete case↩︎

The numerical value of inconsistency is difficult to interpret on its own, without a sharp threshold that separates acceptable and unacceptable levels of inconsistency. In the latter case, the original comparisons should be revised, for which several inconsistency reduction methods have been suggested [8]. For instance, [9] formulate nonlinear mixed-integer optimisation problems to determine the minimal number of matrix elements to be changed in order to reduce the inconsistency below a given value.

The first inconsistency index and threshold of acceptability have been proposed by the founder of the AHP methodology [2]. It is based on dividing the inconsistency of the matrix by the average inconsistency of random pairwise comparison matrices, the so-called random index. Inconsistency can be tolerated if this ratio remains below 0.1, which directly provides a threshold for inconsistency.

Pairwise comparison matrices have a natural generalisation by allowing for missing entries [10]. Incomplete pairwise comparison matrices extend the range of potential applications to hundreds, or even millions of alternatives. For example, the pairwise comparisons of contestants in sports are usually intransitive [11]–[13] and may be easily incomplete if some pairs of contestants do not play against each other. Such case studies are presented by [14]–[18], among others. Analogously, neither completeness nor consistency holds for bilateral remittances [19] or students’ preferences [20]

Even though some inconsistency indices are available for incomplete pairwise comparison matrices [21], [22], determining the associated thresholds is far from trivial. Naturally, an incomplete pairwise comparison matrix can be completed [23]–[26], but the completion methods are usually based on minimising inconsistency. Consequently, the thresholds derived for complete matrices become too permissive for incomplete matrices: they will accept the inconsistency of several incomplete matrices, which would be rejected unless the decision-maker provides the (almost) optimal values for all missing entries.

1.2 The research question and our contribution↩︎

According to our knowledge, there exists only one proposal of inconsistency thresholds for incomplete pairwise comparison matrices. [27] adopt the idea of Saaty to compute the appropriate thresholds as a function of the number of alternatives and the number of missing entries. Unsurprisingly, the random index decreases if the number of unknown comparisons is higher because the inconsistency minimisation problem contains more variables, which generally implies a lower optimum.

Incomplete pairwise comparisons are often represented by undirected graphs where the vertices are the alternatives and the edges correspond to the known comparisons. The random indices, thus, the inconsistency thresholds depend on the number of vertices and edges [27]. However, is it not possible that other properties of the representing graph should also be considered?

The current paper aims to address this issue. Following the methodology of [27], we compute the average inconsistency of a large number of random incomplete pairwise comparison matrices where not only the number of vertices and edges, but the graph itself is fixed, up to isomorphism. The inconsistency threshold turns out to be strongly related to the spectral radius of the graph. Furthermore, the structure of the edges influences the proportion of randomly generated matrices that have an acceptable level of inconsistency.

1.3 A motivating example↩︎

Consider the following incomplete pairwise comparison matrix: \[\mathbf{A} = \left[ \begin{array}{K{3em} K{3em} K{3em} K{3em}} 1 & 2 & \star & 5 \\ 1/2 & 1 & 4 & \star \\ \star & 1/4 & 1 & 2 \\ 1/5 & \star & 1/2 & 1 \\ \end{array} \right].\] Matrix \(\mathbf{A}\) is inconsistent as \(a_{12} \cdot a_{23} \cdot a_{34} = 2 \cdot 4 \cdot 2 = 16\), but \(a_{14} = 5\). The dominant eigenvalue of the optimally completed matrix is \(\lambda \approx 4.084\), resulting in an inconsistency index \(\mathit{CI} \approx 0.0284\).

According to [27], the random index \(\mathit{RI} \approx 0.306\) if there are \(n = 4\) alternatives and \(m = 2\) missing elements. However, Table ¿tbl:Table1? reveals that the random index is \(\mathit{RI} \approx 0.265\) if the positions of the two missing entries (they are placed in different columns and rows) are taken into account, too.

Therefore, the inconsistency of matrix \(\mathbf{A}\) can be tolerated based on [27]. However, this inconsistency is too high if the famous 10% rule of Saaty is applied in a more sophisticated way. For pairwise comparison matrices with a graph representation analogous to the above example, the novel threshold changes the decision on 1165 matrices whose entries are drawn from the Saaty scale.

1.4 Practical relevance↩︎

Recently, optimal filling in patterns have been recommended for incomplete pairwise comparison matrices that provide the closest weight vectors on average to the complete case [28]–[30]. When the pairwise comparisons are asked from the decision-makers in such a sequence, a large number of incomplete pairwise comparison matrices will have the same graph representation, see the experiment of [31]. Then it is crucial not to use the naïve thresholds given by [27] since they assume random positions for the missing entries in the matrix. The exact thresholds provided in the current paper apply to all incomplete pairwise comparison matrices with the same graph representation; hence, the same value remains valid for matrices collected from different decision-makers, which does not complicate the analysis of inconsistency but makes it more accurate.

Our results are also important for inconsistency monitoring [32]. Since the pairwise comparison matrices are always filled sequentially by the decision-makers, we have a new incomplete pairwise comparison matrix after each step. By continuously checking the inconsistency of these matrices, any serious violation of inconsistency can be immediately reported to the decision-maker. Therefore, it is possible to instantly correct any error or misprint, even before all pairwise comparisons are collected. This might be especially useful due to the mental and time constraints of the experts.

1.5 Structure↩︎

The paper is organised as follows. The methodology is described in Section 2. Our main findings are presented and discussed in Section 3, while Section 4 offers concluding remarks.

2 Methodology↩︎

Inconsistency and incomplete pairwise comparison matrices are introduced in Section 2.1. Section 2.2 presents the background of computing the random index, and Section 2.3 gives an overview of our numerical analysis.

2.1 Inconsistency and incomplete pairwise comparison matrices↩︎

Let \(n\) denote the number of alternatives. The pairwise comparisons of the alternatives are collected into a pairwise comparison matrix \(\mathbf{A} = \left[ a_{ij} \right]\), \(a_{ij} > 0\) means that the \(i\)th alternative is \(a_{ij}\) times more preferred to the \(j\)th alternative. The matrix satisfies the reciprocity property: \(a_{ji} = 1 / a_{ij}\) for all \(1 \leq i,j \leq n\).

A pairwise comparison matrix \(\mathbf{A}\) is consistent if and only if \(a_{ik} = a_{ij} \cdot a_{jk}\) holds for all \(1 \leq i,j,k \leq n\). In other words, the pairwise comparisons are consistent if the direct comparison of any two alternatives coincides with their indirect comparison through any third alternative. Otherwise, the matrix is called inconsistent.

According to the Perron–Frobenius theorem [33]–[36], a pairwise comparison matrix \(\mathbf{A}\) has a dominant real eigenvalue \(\lambda_{\max} \left( \mathbf{A} \right)\). The inconsistency index of Thomas L. Saaty [2] is: \[\mathit{CI} \left( \mathbf{A} \right) = \frac{\lambda_{\max} \left( \mathbf{A} \right) - n}{n-1}.\] \(\mathit{CI} \left( \mathbf{A} \right) = 0\) if and only if the pairwise comparisons are consistent.

Saaty suggests comparing \(\mathit{CI} \left( \mathbf{A} \right)\) to the random index \(\mathit{RI}\), the average \(\mathit{CI}\) of a large number of pairwise comparison matrices whose entries above the diagonal are drawn independently and uniformly from the following Saaty scale: \[\left\{ 1/9,\, 1/8,\, 1/7, \dots ,\, 1/2,\, 1,\, 2, \dots ,\, 8,\, 9 \right\}.\] The values of the random index were computed several times as a function of the number of alternatives \(n\) [5], [37]–[41].

The inconsistency index divided by the random index defines the inconsistency ratio: \[\mathit{CR} \left( \mathbf{A} \right) = \frac{\mathit{CI} \left( \mathbf{A} \right)}{\mathit{RI}}.\]

Incomplete pairwise comparison matrices allow for some missing comparisons. Therefore, \(\mathbf{A} = \left[ a_{ij} \right]\) is an incomplete pairwise comparison matrix if \(a_{ij} > 0\) or \(a_{ij} = \star\) such that \(a_{ij} > 0\) implies \(a_{ji} = 1 / a_{ij}\) and \(a_{ij} = \star\) implies \(a_{ji} = \star\). The number of missing comparisons above the diagonal is denoted by \(m\), hence, \(\lvert (i,j): a_{ij} = \star \rvert = 2m\). Incomplete pairwise comparisons have a natural graph representation. Let \(\mathbf{A}\) be an incomplete pairwise comparison matrix. The associated undirected graph is \(G = (V,E)\), where the vertices correspond to the alternatives and \(e_{ij} \in E\) is an edge if and only if \(i \neq j\) and the pairwise comparison \(a_{ij}\) is known.

The adjacency matrix \(\mathbf{B} = \left[ b_{ij} \right]\) of graph \(G = (V,E)\) is given by \(b_{ij} = 1\) if \(e_{ij} \in E\) and \(b_{ij} = 0\) if \(e_{ij} \notin E\). The spectral radius of a finite graph \(G = (V,E)\) is the maximum of the absolute values of the eigenvalues of its adjacency matrix \(\mathbf{B}\).

Understanding the properties of the spectral radius is an active research field in discrete mathematics [42]. The spectral radius of a \(k\)-regular graph, where each vertex is connected to the same number of vertices \(k\) (has degree \(k\)), is equal to \(k\). Denote the maximum and minimum degree of a graph \(G\) by \(\Delta(G)\) and \(\delta(G)\), respectively. [43] asked the following question more than three decades ago: If \(G\) has the smallest possible spectral radius among all graphs with \(n\) vertices and \(e\) edges, does \(\Delta(G) - \delta(G) \leq 1\) hold, namely, is \(G\) almost regular? The answer seems to be positive, at least for dense graphs with \(e \geq (n-1)(n-2)/2 - 2\) [44]. Analogously, there are recent results on upper bounds of the spectral radius [45], [46].

2.2 The eigenvalue minimisation problem and its solution↩︎

In order to complete an incomplete pairwise comparison matrix \(\mathbf{A}\), [47] and [48] have proposed substituting the \(m\) missing entries above the diagonal with positive variables collected in the vector \(\mathbf{x} = \left[ x_k \right]\), \(1 \leq k \leq m\). Since inconsistency (\(\mathit{CI}\)) is a monotone function of the dominant eigenvalue, the following optimisation problem is worth considering: \[\label{EV95min} \min_{\mathbf{x} > 0} \lambda_{\max} \left( \mathbf{A} \left( \mathbf{x} \right) \right).\tag{1}\]

1  can be transformed into a convex optimisation problem [24]. The necessary and sufficient condition for the existence of a unique solution is the connectedness of the undirected graph [24]. Therefore, we will focus on incomplete pairwise comparison matrices represented by a connected graph. [24] presents an algorithm to obtain the optimal solution to 1 .

As discussed by [27], (at least) three possible approaches exist to calculate the random index for incomplete pairwise comparison matrices, depending on how the missing comparisons are related to the Saaty scale:

• Method 1: all positive variables \(x_k\) are unconstrained, the missing comparisons can be arbitrarily small or high for all \(1 \leq k \leq m\);

• Method 2: all positive variables \(x_k\) are constrained by the bounds of the Saaty scale, \(1/9 \leq x_k \leq 9\) for all \(1 \leq k \leq m\);

• Method 3: all positive variables \(x_k\) are constrained directly by the Saaty scale, \(x_k\) should be either an integer from 1 to 9 or its reciprocal for all \(1 \leq k \leq m\).

Similar to [27], Method 2 will be implemented to avoid numerical difficulties, as well as the problems caused by using a discrete scale for the variables in 1 .

2.3 The computation approach↩︎

In contrast to [27], the positions of the missing entries are not chosen randomly for a given number of unknown comparisons \(m\), but the associated graph is fixed in advance. This does not make any difference if \(m=1\) because all graphs with \(n\) vertices and \(n(n-1)/2 - 1\) edges are isomorphic. However, it can be important if \(m \geq 2\).

Consequently, the random index is computed as follows:

1. We choose a connected graph \(G = (V,E)\) with \(n\) vertices and \(m\) missing edges compared to a complete graph;

2. We generate an incomplete pairwise comparison matrix \(\mathbf{A}\) with graph representation \(G\) such that each element of the Saaty scale is drawn with a probability of \(1/17\) for each known comparison above the diagonal;

3. We solve the minimisation problem 1 by restricting all variables in \(\mathbf{x} > 0\) between \(1/9\) and \(9\) (Method 2 in Section 2.2), which gives a complete pairwise comparison matrix \(\mathbf{\hat{A}}\) as the optimal solution;

4. We compute and save the inconsistency index \(\mathit{CI} \left( \mathbf{\hat{A}} \right)\);

5. We repeat Steps [Step2]–[Step4] to get 1 million random matrices with a given graph representation \(G\);

6. We compute the mean of the inconsistency indices \(\mathit{CI}\) from Step [Step4].

3 Results↩︎

Section 3.1 provides a comprehensive analysis in the case of four alternatives, and Section 3.2 focuses on pairwise comparison matrices with two missing entries. Matrices of size five and six are discussed in Section 3.3. Finally, Section 3.4 presents an approximation formula based on the number of alternatives, the number of missing elements, and the value of the spectral radius that can be used without costly computations even if \(n \geq 7\).

3.1 Incomplete matrices of size four↩︎

If \(n=4\), only the case \(m=2\) unknown entries is interesting. For \(m=1\), only one graph exists since \(a_{14} = \star\) can be assumed without loss of generality. For \(m=3\), a connected graph is necessarily a spanning tree, and the incomplete pairwise comparison matrix has a consistent completion if the missing entries remain unconstrained.

If \(m=2\), there are two possible graphs: (1) the two missing edges are independent, they do not share any vertex (Figure 1); (2) the two missing edges have a common vertex. The probability of case (1) is \[\frac{n(n-1)/2 - (n-2+n-2 + 1)}{n(n-1)/2 - 1} = 1 - \frac{4n - 8}{n(n-1) - 2},\] since there exist \(n(n-1)/2 - 1\) different edges after one is missing, and the missing edge has \(n-2\) neighbouring edges at both of its vertices. This value equals only \(1/5 = 20\%\) for \(n=4\), but converges to \(1\) when \(n\) increases.

The value of the random index \(\mathit{RI}\) can be computed exactly: the number of possible scenarios is \(17^4 = 83{,}521\) for both graphs due to the four known entries and the 17 elements of the Saaty scale. Hence, in contrast to what is done in [27], we carry out a complete enumeration instead of generating 1 million random matrices.

Table ¿tbl:Table1? reports the values of the refined random indices and their implications. The structure of the graph has a non-negligible effect; \(\mathit{RI}\) for Graph 1 is smaller by more than 15% compared to \(\mathit{RI}\) for Graph 2. Ignoring the graph misclassifies 1156 and 248 incomplete pairwise comparison matrices in the two possible cases, respectively. Even though the standard \(\mathit{CI}\) threshold of 0.1 becomes more (less) restrictive for Graph 1 (Graph 2) if the structure of the graph is taken into account, the number of matrices with an acceptable inconsistency is still higher for Graph 2 than for Graph 1.

Considering all possible matrices allows us to exactly compute the difference between Methods 1–3 mentioned in Section 2.2, too. If the missing entries are continuous and not constrained to the interval \(\left[ 1/9; \, 9 \right]\) (Method 1), a closed formula exists for the optimal completion if \(n=4\): [25] prove that the incomplete eigenvector and the incomplete logarithmic least squares methods [24], [49], [50] imply the same optimal completion, and the optimal completion according to the incomplete logarithmic least squares method can be obtained as a solution of a linear system of equations [24], [51]. Thus, there is no need to use the algorithm suggested by [24] to solve optimisation problem 1 . The random indices are 0.2528 and 0.2923 for Graphs 1 and 2, respectively, which are reduced by 7.6% and 4.4% compared to the values presented in Table ¿tbl:Table1?.

If the missing entries are chosen from the discrete Saaty scale (Method 3), the random indices are 0.2663 and 0.3174 for Graphs 1 and 2, respectively, which are higher by 0.31% and 0.65% compared to the values presented in Table ¿tbl:Table1?. Therefore, although our continuous relaxation clearly lowers the random index, the extent of this decrease compared to using the discrete scale seems to be minimal.

3.2 Incomplete matrices with two missing elements↩︎

Figure 2 shows the random indices for the two different incomplete pairwise comparison matrices with two missing entries as a function of the spectral radius of the representing graph if the number of alternatives is between four and nine. The plot has two important messages. First, a higher spectral radius is always associated with a higher value of \(\mathit{RI}\) if \(m=2\). Second, the difference between the two cases gradually disappears when the number of alternatives grows, that is, the random indices provided in [27] become less distorted. This is not surprising since fixing the number of unknown comparisons means that the ratio of known elements increases together with \(n\).

3.3 Incomplete matrices of size five and six↩︎

If \(n=5\), all cases are investigated, that is, the number of missing entries varies from 1 to 5 because \(m=6\) implies the existence of a consistent completion (if the unknown entries remain unconstrained). Only one graph exists if \(m=1\), when the threshold given in [27] remains valid.

Figure 3 presents the 16 possible graphs if \(n=5\) and \(2 \leq m \leq 5\). The \(1 + 2 + 4 + 5 + 5 = 17\) random indices—depending on the structure of the graph—are reported in Table ¿tbl:Table95A1? in the Appendix, together with their probability of occurrence if the number of missing entries \(m\) is fixed. The probabilities are estimated by simulations, contrary to the exact values derived in Section 3.1. For a fixed value of \(m\), the spectral radius is the smallest if the graph is (almost) regular (\(G_{2,2}\), \(G_{3,3}\), \(G_{4,1}\), \(G_{5,5}\)). These graphs have the smallest probability to occur except for \(G_{3,3}\), and the corresponding random index \(\mathit{RI}\) is lower than for any other graphs having the same number of edges.

If \(n=6\), we have computed the random indices only up to \(m=7\) as the number of different graphs increases with \(m\); for instance, 20 scenarios exist for \(n=6\) and \(m=6\) according to Figure 4. The random indices are provided in Table [Table95A2] in the Appendix. Again, the regular graph \(G_{20}\) in Figure 4 occurs with the smallest probability and has the smallest value of \(\mathit{RI}\) if \(m=6\), and the other regular graph \(G_{18}\) has the second smallest random index.

Figure 5 presents the random indices for incomplete pairwise comparison matrices of size five (Figure [Fig5a]) and six (Figure [Fig5b]), as a function of the spectral radius of the associated graph. The monotonic relationship between the spectral radius and \(\mathit{RI}\) breaks first when \(n=5\) and \(m=4\) (see also Table ¿tbl:Table95A1?). However, a higher spectral radius usually implies a higher random index even for \(n=5\) and \(n=6\). If the number of alternatives is six, the spectral radii can overlap for different values of missing entries \(m\), but the random indices still monotonically decrease as a function of \(m\). In other words, the number of variables in the optimisation problem 1 is more important than their relative position in the representing graph with respect to the optimum, which is intuitive.

Table 1 shows the extreme values of the random index \(\mathit{RI}\) for given pairs of parameters \(m\) and \(n\). Unsurprisingly, the influence of the graph decreases if \(m\) is fixed and the number of alternatives grows, but increases if \(n\) is fixed and the number of missing entries increases. Among the 11 scenarios, the random index can be smaller by more than 10% in five cases, and the reduction may exceed 23% if both parameters are equal to five. This reinforces that the underlying graph cannot be ignored in the calculation of inconsistency thresholds for incomplete pairwise comparison matrices.

The strong association between the spectral radius of the representing graph and the random index seems to be unexpected. Hence, we provide some theoretical intuition for this relation. Table ¿tbl:Table3? presents the number of different triads (pairwise comparison matrices of size three) for the 20 graphs with \(n=6\) and \(m=6\) that can be seen in Figure 4. Six alternatives imply 20 triads in all cases, but these triads are quite different with respect to the number of missing entries \(\mu\). For example, in graph \(G_1\), there are 4 triads without missing entries, and 8-8 triads with one and two missing entries, respectively. On the other hand, graph \(G_{20}\) has 18 triads with one missing entry, and 2 triads with three missing entries.

Inconsistency is closely connected to triads since the definition of consistency involves three alternatives. Indeed, several inconsistency indices simply aggregate the inconsistencies of all triads [7]. Even though the inconsistency index \(\mathit{CI}\) is not such a triad-based index, [52] uncovers an extremely strong monotonic increasing correlation between \(\mathit{CI}\) and the inconsistency index suggested by [53], which is the average determinant of all sub-matrices of order three, for \(4 \leq n \leq 7\). Furthermore, there exists a unique inconsistency index (up to multiplication) if \(n=3\) [54]; hence, \(\mathit{CI}\) is functionally related to any reasonable inconsistency index in the case of three alternatives.

Thus, reducing \(\mathit{CI}\) (the objective function of problem 1 ) is essentially equivalent to minimising the inconsistency of the triads. However, the inconsistency of a triad cannot be decreased if it has no missing entries (\(\mu = 0\)), and this is difficult due to the appearance of the same pairwise comparison in \(n-2\) different triads if it has one missing entry (\(\mu = 1\)). Consequently, the optimum of optimisation problem 1 is expected to be lower if there are few triads with \(\mu = 1\) and, especially, \(\mu = 0\) missing entries.

In order to check the connection between the spectral radius and the distribution of triads, we have estimated two linear regressions by ordinary least squares (OLS). The dependent variable is the spectral radius, while the independent variables are the constant and the number of triads with \(\mu = 0\) and \(\mu = 1\) in both cases. The two samples are provided by graphs with \(m=6\) (see Table ¿tbl:Table3?) and \(m=7\) when the number of alternatives is \(n=6\). In both regressions, all coefficients remain significantly positive even at the 0.1% level, and the value of adjusted \(R^2\) exceeds 0.9. Hence, the spectral radius basically depends on the number of these two types of triads.

To summarise, the value of the spectral radius is probably related to the minimisation of the dominant eigenvalue in 1 through the distribution of triads with respect to the number of missing entries \(\mu\). A higher spectral radius is associated with more triads that have at most one missing entry, when decreasing the average inconsistency of triads becomes more challenging. In addition, the optimal value of \(\mathit{CI}\) is almost functionally related to the average inconsistency of triads, as shown by [52].

Finally, Figure 6 presents the relationship between the random index and the proportion of randomly generated incomplete pairwise comparison matrices with the same graph representation that have an acceptable inconsistency. The effect of the graph becomes more important if the number of missing entries \(m\) is higher. Interestingly, a smaller (more restrictive) random index may lead to a higher probability of acceptable inconsistency, similar to what can be seen in Table ¿tbl:Table1? for \(n=4\) alternatives.

3.4 An approximation formula for the random index↩︎

The computations in Section 3.3 are quite complex and time-consuming, which calls for a heuristic predictor of the random value based on the spectral radius \(\rho\).

Let \(\mathcal{G}(n,m)\) be the set of graphs for a given number of alternatives \(n\) and missing comparisons \(m\). Let \(\rho_{n,m}\) and \(\mathit{RI}_{n,m}\) be the expected values of the spectral radius and random index for a fixed pair of \(n\) and \(m\), respectively. For any graph \(G_i \in \mathcal{G}(n,m)\), define \[\Delta \rho_i = \rho \left( G_i \right) - \rho_{n,m} \text{, and}\] \[\Delta \mathit{RI}_i = \mathit{RI} \left( G_i \right) - \mathit{RI}_{n,m}.\] We estimate the linear regression \(\Delta \mathit{RI}_i = \beta \Delta \rho_i\) by ordinary least squares (OLS) for the 73 observations provided by \(n=6\) and \(1 \leq m \leq 7\) in Table [Table95A2] in the Appendix. This gives \(\beta = 0.16119\). However, it is not guaranteed that \(\beta = 0.16119\) remains valid if the number of alternatives is \(n \geq 7\). For example, \(\beta = 0.19219\) if the sample is the set of \(5 \times 5\) matrices, namely, Table ¿tbl:Table95A1?. Indeed, the regression line is apparently steeper in Figure [Fig5a] than in Figure [Fig5b], but the number of observations is only 17 in the first case. Thus, \(\beta = 0.16119\) is assumed to hold for any \(n \geq 7\) in the following.

Then, for any graph \(G_i \in \mathcal{G}(n,m)\), the random index \(\mathit{RI}_i\) is approximated by: \[\label{RI95approx95rho} \mathit{RI}_i \approx \mathit{RI}_{n,m} + \beta \Delta \rho_i.\tag{2}\] In formula 2 , \(\Delta \rho_i\) depends on \(\rho_i\) (the spectral radius of graph \(G_i\)) and \(\rho_{n,m}\). The latter is estimated by generating 100 thousand random pairwise comparison matrices for each pair of parameters \(n\) and \(m\), and computing the average spectral radius if the corresponding graph is connected, which is not guaranteed for a high number of missing comparisons \(m\). These values are presented in Table [Table95A3] in the Appendix for \(6 \leq n \leq 9\). Note that this calculation does not require any specific algorithm or solving any optimisation problem.

On the other hand, if \(n \geq 7\), the values of \(\mathit{RI}_{n,m}\) are neither provided here, nor in [27] for all \(m\). However, [27] present an approximation based on \(\mathit{RI}_n\) that is available for all plausible number of alternatives \(n\) [37]: \[\label{RI95approx95m} \mathit{RI}_{n,m} \approx \left[ 1 - \frac{2m}{(n-1)(n-2)} \right] \mathit{RI}_n.\tag{3}\]

We have checked formula 2 for a pairwise comparison matrix with \(n=8\) alternatives, \(m=5\) missing entries, and a spectral radius of \(\rho_i = 6.097\). The expected value of the spectral radius is \(\rho_{8,5} = 5.862\) (see Table [Table95A3] in the Appendix), which leads to \(\Delta \rho_i = 0.235\). The value of \(\mathit{RI}_{n,m}\) is estimated from 3 as \(1.07\) since \(\mathit{RI}_n = 1.404\). Hence, our heuristic predictor results in \(\mathit{RI}_i = 1.07 + 0.16119 \cdot 0.235 = 1.1076\). The correct random index, given by the methodology described in Section 2.3, equals \(1.117\). Consequently, the error of the approximation is within 1% in this particular case.

4 Conclusions↩︎

Our paper provides refined random indices for incomplete pairwise comparison matrices in order to determine the threshold of acceptability for their inconsistency. The values of [27] are made more accurate by considering not only the number of alternatives and missing entries, but also the graph representing the known comparisons. We show that the graph structure has a non-negligible effect and the random index is in a strict—albeit not perfect—relationship with the spectral radius of the corresponding graph. Furthermore, the underlying graph influences the ratio of randomly generated pairwise comparison matrices whose inconsistency can be accepted, which might question the validity of the 10% rule of Saaty.

The research is far from closed. First, the random indices are fully computed only up to five alternatives due to the complexity of the numerical calculations. Second, even though the association with the spectral radius is surprisingly strong, other measures of graph “robustness” may provide an even better fit.

Acknowledgements↩︎

We acknowledge the Digital Government Development and Project Management Ltd.for awarding us access to the Komondor HPC facility based in Hungary.
We are grateful to Zsombor Szádoczki for useful advice.
Two reviewers and three anonymous colleagues provided valuable comments and suggestions on earlier drafts.
The research was supported by the National Research, Development and Innovation Office under Grants Advanced 152220 and FK 145838, and the János Bolyai Research Scholarship of the Hungarian Academy of Sciences.

Appendix↩︎

References↩︎