Refined thresholds for inconsistency: The effect of the graph associated with incomplete pairwise comparisons

This paper refines inconsistency thresholds for incomplete pairwise comparison matrices by demonstrating that they depend not only on matrix size and missing entries but also critically on the underlying graph structure of known comparisons, enabling more accurate error detection and real-time monitoring.

The Gist

Imagine you are a chef trying to create the perfect menu for a new restaurant. You have a list of dishes (let's call them Alternatives), and you need to decide which ones are better than others. To do this, you ask a group of food critics to compare the dishes two at a time.

• "Is the Steak better than the Salad?"
• "Is the Salad better than the Soup?"
• "Is the Steak better than the Soup?"

If the critics are perfectly logical, their answers should follow a simple rule: If Steak > Salad and Salad > Soup, then Steak must be > Soup. This is called consistency.

However, humans aren't robots. Sometimes a critic says, "Steak is twice as good as Salad," and "Salad is three times as good as Soup," but then claims, "Steak is only five times better than Soup." This is inconsistency. It's a logical glitch.

The Problem: The "Missing Pieces" Puzzle

In the real world, you can't always get every critic to compare every single dish. Maybe the Steak and the Soup were never tasted together because they were served on different nights. This leaves you with a Partial Puzzle (an incomplete matrix).

For decades, experts used a "10% Rule" to decide if a puzzle was good enough. If the logical errors were less than 10%, they said, "Good enough, let's use this menu." If it was over 10%, they said, "Go back and ask the critics again."

But here's the catch: The shape of the missing pieces matters.

The Big Discovery: It's About the Map, Not Just the Count

The authors of this paper realized that the old "10% Rule" was too simple. It only counted how many comparisons were missing. It didn't care which ones were missing.

Think of your dishes as cities on a map, and the comparisons as roads connecting them.

• Scenario A: You have roads connecting City 1 to 2, 2 to 3, and 3 to 4. The missing roads are between 1-3 and 2-4. The roads form a long, winding chain.
• Scenario B: You have roads connecting 1-2, 2-3, and 3-4, but the missing roads are 1-4 and 2-3. The roads form a different shape, like a star or a cluster.

The paper proves that Scenario A and Scenario B have different "tolerance levels" for errors, even if they both have the same number of missing roads.

The Secret Ingredient: The "Spectral Radius" (The Map's Vibe)

The authors found a mathematical way to measure the "shape" or "vibe" of this road map. They call it the Spectral Radius.

• Simple Analogy: Imagine the road map is a musical instrument. The Spectral Radius is like the instrument's "resonance" or how easily sound travels through it.
  • If the roads are spread out evenly (like a regular grid), the sound travels smoothly. This is a "low resonance" map.
  • If the roads are clustered in a way that creates bottlenecks or loops, the sound gets stuck or bounces around wildly. This is a "high resonance" map.

The paper shows that maps with higher resonance (Spectral Radius) are naturally more prone to logical errors. Therefore, they need a stricter rule. You can't accept as many errors in a "bumpy" map as you can in a "smooth" map.

Why This Matters in Real Life

1. Better Software: Imagine an app that helps you make decisions (like choosing a university or a house). As you fill in your answers, the app can now look at the shape of your missing questions. If your answers form a "bumpy" map, the app will say, "Hey, your logical errors are a bit high, but that's expected for this shape. Let's keep going." If they form a "smooth" map, it might say, "Stop! You have too many errors; please rethink your answers."
2. Saving Time: Experts often get tired. If they stop too early because they think they are "too inconsistent," they might miss a great solution. If they keep going when they are actually fine, they waste time. This new method tells them exactly when to stop based on the specific pattern of their missing data.
3. The "10% Rule" is Outdated: The famous "10% rule" is like saying "All cars are safe if they go under 60 mph." But a Formula 1 car and a family minivan have different safety needs. Similarly, a "smooth" decision map and a "bumpy" one need different error limits.

The Bottom Line

This paper is like upgrading the GPS for decision-making. Instead of just counting how many roads are missing, it looks at the topology (the shape) of the road network. By understanding the "Spectral Radius" (the map's resonance), we can set smarter, fairer rules for when a decision is good enough to be trusted.

In short: Don't just count the missing pieces of your puzzle; look at how they fit together. The shape of the hole changes the rules of the game.

Technical Summary

1. Problem Statement

In Multi-Criteria Decision Making (MCDM), specifically within the Analytic Hierarchy Process (AHP), decision-makers often use pairwise comparison matrices to rank alternatives. However, real-world data is frequently incomplete (missing comparisons), and human judgments are rarely perfectly consistent (i.e., $a_{ik} \neq a_{ij} \times a_{jk}$).

To determine if an inconsistent matrix is acceptable, the standard practice is to calculate the Consistency Ratio (CR):
$$CR = \frac{CI}{RI}$$
Where $CI$ is the Consistency Index and $RI$ is the Random Index (the average $CI$ of random matrices). A matrix is usually accepted if $CR \leq 0.1$ (Saaty's 10% rule).

The Core Issue:
Existing methods for calculating the Random Index for incomplete matrices (e.g., Ágoston and Csató, 2022) rely solely on the number of alternatives ($n$) and the number of missing entries ($m$). They assume missing entries are randomly distributed.

• Limitation: This approach ignores the topological structure of the known comparisons.
• Consequence: If the missing entries follow a specific pattern (a specific graph structure), the "naïve" threshold may be too permissive or too restrictive, leading to incorrect decisions about data quality.

2. Methodology

The authors propose a refined methodology where the Random Index is calculated based on the specific undirected graph representing the known comparisons, rather than just the count of missing entries.

Key Definitions

• Graph Representation: An incomplete matrix is represented by a graph $G=(V, E)$ where vertices are alternatives and edges represent known comparisons.
• Spectral Radius ($\rho$): The maximum absolute eigenvalue of the graph's adjacency matrix.
• Optimization: To complete an incomplete matrix, the authors solve a convex optimization problem to minimize the dominant eigenvalue ($\lambda_{max}$) of the matrix by filling in the missing entries (variables $x$) within the Saaty scale bounds $[1/9, 9]$.

Computational Approach

1. Fixed Graphs: Instead of randomizing the position of missing entries, the authors fix the graph structure $G$ (up to isomorphism).
2. Simulation: For a fixed graph $G$ with $n$ vertices and $m$ missing edges:
   • Generate 1 million random incomplete matrices where known entries are drawn from the Saaty scale $\{1/9, \dots, 9\}$.
   • Solve the minimization problem to find the optimal completion for each matrix.
   • Calculate the Consistency Index ($CI$) for the completed matrix.
3. Random Index Calculation: The mean of these $CI$ values constitutes the refined Random Index ($RI$) specific to that graph structure.
4. Comparison: Compare these refined $RI$ values against the "naïve" $RI$ (which averages over all possible graph structures for a given $n, m$).

3. Key Contributions

1. Graph-Dependent Thresholds: The paper demonstrates that the Random Index is not a function of $n$ and $m$ alone, but is strongly dependent on the graph topology of the known comparisons.
2. Spectral Radius Correlation: A strong, positive association is identified between the spectral radius ($\rho$) of the representing graph and the Random Index.
   • Higher spectral radius $\rightarrow$ Higher Random Index (more lenient threshold).
   • Lower spectral radius $\rightarrow$ Lower Random Index (stricter threshold).
3. Triad Analysis: The authors provide theoretical intuition linking the spectral radius to the distribution of triads (sub-matrices of size 3). Graphs with higher spectral radii tend to have fewer "hard-to-fix" triads (triads with 0 or 1 missing entries), making it easier to minimize inconsistency, thus resulting in a higher baseline $RI$.
4. Approximation Formula: For larger matrices ($n \geq 7$) where full enumeration is computationally expensive, the authors propose a heuristic formula:
   $$RI_i \approx RI_{n,m} + \beta(\rho_i - \rho_{n,m})$$
   Where $\beta \approx 0.161$ (derived from regression analysis), allowing practitioners to estimate the specific threshold using the spectral radius.

4. Key Results

• Significant Deviation: For $n=4$ and $m=2$, two different graph structures yielded Random Indices of 0.2646 and 0.3165. The naïve average (0.3061) misclassified hundreds of matrices as acceptable or unacceptable depending on the graph structure.
• Impact on Decision Making: Using the graph-specific threshold changes the acceptability decision for a significant portion of matrices. For example, in the $n=4$ case, the novel threshold changed the decision for 1,165 matrices drawn from the Saaty scale.
• Monotonicity: Generally, as the spectral radius increases, the Random Index increases. However, this relationship is not perfectly monotonic for all $n$ and $m$ combinations, though the correlation remains strong.
• Regular Graphs: Regular or "almost regular" graphs (where degrees are similar) tend to have the lowest spectral radii and, consequently, the lowest Random Indices (stricter thresholds).
• Practical Implication: In scenarios where decision-makers follow a specific sequence of questions (resulting in a fixed graph pattern), using the naïve threshold is statistically invalid. The refined thresholds must be used to ensure accurate inconsistency monitoring.

5. Significance and Applications

• Software Integration: The results can be integrated into decision support software to continuously monitor inconsistency as data is collected. If a user's current graph structure has a low spectral radius, the software can immediately flag high inconsistency that would otherwise be accepted by a naïve threshold.
• Error Detection: Allows for the immediate detection of errors or misprints in pairwise comparisons before the full matrix is completed, saving time and cognitive load for experts.
• Theoretical Advancement: Bridges Graph Theory (spectral properties) with Decision Analysis (inconsistency measurement), suggesting that the "robustness" of the data collection structure is a critical factor in evaluating data quality.
• Refining Saaty's Rule: Challenges the universal application of the 10% rule for incomplete matrices, suggesting that the "acceptable" level of inconsistency is dynamic and structure-dependent.

Conclusion

The paper establishes that the topology of known comparisons is a critical determinant of inconsistency thresholds. By utilizing the spectral radius of the associated graph, decision analysts can derive exact, context-specific Random Indices. This leads to more accurate quality control in MCDM processes, particularly in large-scale applications where missing data patterns are non-random (e.g., sports tournaments, bilateral trade data, or structured expert surveys).