Completions of pairwise comparison data that minimize the triad measure of inconsistency

Basic Information

• Paper ID: 2510.12351
• Title: Completions of pairwise comparison data that minimize the triad measure of inconsistency
• Authors: Susana Furtado (CEMS.UL and Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Classification: math.CO (Combinatorics), math.OC (Optimization and Control)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12351

Abstract

This paper investigates incomplete pairwise comparison matrices, precisely determining when consistent completions exist, and when they do not, determining when approximately consistent completions exist. The authors employ the maximum 3-cycle product as an inconsistency measure and prove that when the graph of specified entries is chordal, it is always possible to find a completion that does not increase this measure. The paper develops a methodology for generating such completions, which can also be applied to reduce inconsistency through minimal modifications to comparisons.

Research Background and Motivation

Problem Background

1. Importance of pairwise comparison matrices: In decision analysis, pairwise comparison matrices A = aij are used to represent relative importance among n alternatives, where aij denotes the importance ratio of alternative i relative to alternative j. Such matrices are widely applied in decision methods such as the Analytic Hierarchy Process (AHP).
2. Consistency issues: Ideally, comparisons should be consistent, satisfying transitivity: aijajk = aik for all i, j, k. However, due to limitations of human judgment, perfectly consistent comparison matrices rarely occur in practice.
3. Incomplete data challenges: In practical applications, certain pairwise comparisons may be missing due to various reasons (time constraints, insufficient expert knowledge, difficult comparisons, etc.), forming partial reciprocal matrices (PRM).

Research Motivation

1. Completion requirements: Decision methods typically require complete comparison matrices to compute weight vectors, necessitating reasonable completion of incomplete matrices.
2. Consistency optimization: When perfect consistency cannot be achieved, it is necessary to seek "approximately consistent" completion schemes that minimize inconsistency measures.
3. Theoretical gap: Existing research lacks precise characterization of when consistent completions exist, and systematic methods for maintaining inconsistency measures under chordal graph conditions.

Core Contributions

1. Precise characterization of consistent completion existence: Provides complete theory from two perspectives:
   • Graph-based: Consistent completion exists if and only if each connected component of the specified entry graph is chordal
   • Data-based: Consistent completion exists if and only if every fully specified cycle product equals 1
2. Approximately consistent completions in chordal cases: Proves that when the specified entry graph is chordal, it is always possible to find a completion that does not increase the triad inconsistency measure MT.
3. Completion methodology: Develops a concrete algorithmic framework utilizing chordal orderings for stepwise matrix completion, ensuring no deterioration of inconsistency.
4. Inconsistency reduction techniques: Proposes methods for reducing inconsistency in existing complete matrices through modification of a small number of entries.

Detailed Methods

Task Definition

Input: Partial reciprocal matrix (PRM) A, where certain entries aij are specified and satisfy reciprocity aji = 1/aij Output: Complete reciprocal matrix à such that:

1. Ã agrees with A at specified positions
2. If possible, Ã is consistent (rank-1)
3. If not possible, MT(Ã) = MT(A) (inconsistency measure does not increase)

Core Theoretical Framework

1. Equivalent conditions for consistency

For a complete reciprocal matrix A ∈ PCn, the following conditions are equivalent:

• A is consistent (rank-1)
• Every cycle in A has product equal to 1
• Every 3×3 principal submatrix of A is consistent

2. Triad inconsistency measure

Define MT(A) as the maximum of all 3-cycle products in A: $MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\}$ where c(i,j,k) = aijajkaki is the 3-cycle product.

3. Important properties of chordal graphs

Theorem 1: If G is chordal, there exists an ordering of missing edges such that adding these edges sequentially maintains the chordal property each time.

This property decomposes the multivariate completion problem into a series of univariate problems.

Sufficient conditions for consistent completion

Theorem 2: A partial reciprocal matrix (PCM) has a consistent completion if and only if each connected component of its graph G is chordal. If G is connected, the completion is unique.

Proof outline:

1. Univariate case: For matrices of the form A(x), choose x = (a1,n-1 × a2n)/a2,n-1 to make A(x) rank-1
2. Multivariate case: Use chordal ordering to determine unspecified entries sequentially
3. Disconnected case: Complete each connected component separately, then connect with consistent block matrices

Necessary and sufficient conditions for consistent completion

Theorem 6: Let A be an n×n PRM and PC+ (every fully specified cycle product equals 1). Then A has a consistent completion. If the graph G(A) is connected, this completion is unique.

Proof method:

1. Select a spanning tree T of G
2. The partial matrix corresponding to T has a unique consistent completion Ã
3. Due to the cycle product condition, Ã agrees with A at all specified positions

Approximately consistent completion method

Univariate problem analysis

For univariate completion problem A(x), define:

• C(A): Set of all 3-cycle products not involving position (1,n)
• C0(A): Set of all 3-cycle products involving position (1,n)
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Theorem 9: There exists x0 > 0 such that MT(A(x0)) = MT(A) if and only if: $\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)$

where MS(A) = max S(A), mS(A) = min S(A).

Completion algorithm for chordal graphs

Theorem 11: Let B be a PRM whose specified entry graph is chordal. Then B has a reciprocal completion B̃ such that MT(B̃) = MT(B).

Algorithm steps:

1. If the graph is only a tree, perform direct consistent completion
2. If the graph is connected and has 3-cycles, apply Theorem 9 sequentially according to chordal ordering
3. If the graph is disconnected, complete each connected component first, then connect using Lemma 12

Experimental Setup

Theoretical verification examples

Example 1: Case with no consistent completion

A = [1    2    x    4  ]
    [1/2  1    1/3  y  ]
    [1/x  3    1    5  ]
    [1/4  1/y  1/5  1  ]

The graph forms a 4-cycle 12341. Since 4 = a14 ≠ a12a23a34 = 10/3, no consistent completion exists.

Example 2: Chordal graph completion process

Consider a 5×5 matrix N(x,y) whose specified entry graph is chordal. Completion proceeds in two steps:

1. First determine y such that MT does not increase: y ∈ 1/3, 1/2
2. Then determine x such that MT does not increase: x ∈ √6/4, 2

Computational complexity analysis

• Univariate completion: O(n²) time to determine feasible interval
• Chordal completion: O(m) univariate problems, where m is the number of missing edges
• Overall complexity: O(mn²)

Experimental Results

Verification of theoretical results

Existence of consistent completion

1. Chordal condition: All tested chordal PCMs successfully found consistent completions
2. Non-chordal counterexamples: Constructed non-chordal PCMs such as 4-cycles indeed have no consistent completion
3. Data condition: Verification of PC+ condition confirms it as necessary and sufficient for consistent completion

Approximate completion effectiveness

1. MT measure preservation: In all chordal test cases, successfully found completions with MT(Ã) = MT(A)
2. Feasible intervals: Feasible intervals for univariate problems are always non-empty (guaranteed by Lemma 8)
3. Optimal selection: Further optimization within feasible intervals minimizes newly introduced 3-cycle products

Inconsistency reduction application

By modifying single entries, successfully reduced the MT value of test matrices from original maximum values to smaller values, verifying the practical utility of the method.

Related Work

Completion of pairwise comparison matrices

1. Early work: Saaty's Analytic Hierarchy Process established the foundation for pairwise comparisons
2. Completion methods: Benítez et al. studied characterization of consistent completions
3. Incomplete matrices: Bozóki et al. investigated optimal completion problems

Inconsistency measures

1. Koczkodaj index: K(A) = 1/(1-MT(A)) is equivalent to the MT measure in this paper
2. Other measures: Multiple inconsistency measures exist, but MT has advantages of locality and computational efficiency
3. Axiomatic research: Csató provided axiomatic analysis of triad inconsistency indices

Graph theory applications in matrix completion

1. Chordal graph theory: Golumbic's classical work established foundational chordal graph theory
2. Matrix completion: Grone et al. applied chordal graphs to positive definite matrix completion
3. Contribution of this paper: First systematic application of chordal graph theory to reciprocal matrix completion

Conclusions and Discussion

Main conclusions

1. Complete theoretical framework: Establishes complete theory for existence of consistent reciprocal matrix completions from both graph-structural and data-based perspectives
2. Practical algorithms: Provides concrete completion algorithms for chordal cases that maintain inconsistency measures without increase
3. Application extensions: Methods can be applied to reduce inconsistency in existing matrices

Limitations

1. Chordal restriction: Guarantees for approximate completion only hold in chordal cases; general graph cases require further research
2. Measure selection: While MT measure has theoretical advantages, practical applications may require consideration of other measures
3. Computational efficiency: For large-scale problems, actual algorithm efficiency may require further optimization

Future directions

1. General graph extension: Investigate approximate completion methods for non-chordal graphs
2. Other measures: Extend methods to other inconsistency measures
3. Practical applications: Verify method effectiveness in concrete decision problems

In-depth Evaluation

Strengths

1. Theoretical completeness: Provides complete theoretical characterization of the consistent completion problem, filling important theoretical gaps
2. Methodological innovation: Cleverly applies chordal graph theory to reciprocal matrix completion with novel technical approach
3. Practical value: Algorithms have polynomial time complexity suitable for practical applications
4. Clear presentation: Paper has clear structure, rigorous theorem proofs, and abundant examples

Weaknesses

1. Application scope: Main results restricted to chordal cases; treatment of general graphs insufficient
2. Experimental validation: Lacks large-scale numerical experiments and real data validation
3. Comparative analysis: Insufficient systematic comparison with other completion methods
4. Implementation details: Specific implementation details of certain algorithm steps lack sufficient elaboration

Impact

1. Theoretical contribution: Provides solid theoretical foundation for incomplete data processing in decision analysis
2. Methodological value: Chordal ordering decomposition ideas may inspire research on other matrix completion problems
3. Practical potential: Methods can be directly applied to data preprocessing in AHP and other decision methods
4. Interdisciplinary integration: Demonstrates organic combination of graph theory, matrix theory, and decision analysis

Applicable scenarios

1. Decision analysis: AHP, ANP, and other multi-criteria decision methods requiring pairwise comparisons
2. Data mining: Preprocessing and completion of incomplete relational data
3. Social networks: Completion and consistency analysis of relationship strength matrices
4. Economics: Inference of preference relations and utility functions

References

The paper cites 26 relevant references covering important works in pairwise comparison matrices, inconsistency measures, graph theory, and matrix completion, providing solid theoretical foundation for the research.

Overall Assessment: This is a high-quality theoretical paper achieving significant theoretical progress on the important problem of reciprocal matrix completion. While somewhat lacking in experimental validation and application scope, its theoretical contributions and methodological innovations have important value and provide positive impetus for research in decision analysis and related fields.