2025-11-25T05:49:17.896288

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

Furtado, Johnson
We consider incomplete pairwise comparison matrices and determine exactly when they have a consistent completion and, if not, when they have a nearly consistent completion. We use the maximum 3-cycle product as a measure of inconsistency and show that, when the graph of the specified entries is chordal, a completion in which this measure is not increased is always possible. Methodology to produce such completions is developed. Such methodology may also be used to reduce inconsistency with few changes of comparisons.
academic

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

基本信息

  • 论文ID: 2510.12351
  • 标题: Completions of pairwise comparison data that minimize the triad measure of inconsistency
  • 作者: Susana Furtado (CEMS.UL and Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
  • 分类: math.CO (组合数学), math.OC (最优化与控制)
  • 发表时间: 2025年10月15日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12351

摘要

本文研究不完整的成对比较矩阵，精确确定何时存在一致性完备，若不存在则确定何时存在近似一致性完备。作者使用最大3-环乘积作为不一致性度量，证明当指定条目的图为弦图时，总是可能找到不增加该度量的完备。论文开发了产生此类完备的方法论，该方法论也可用于通过少量比较变更来减少不一致性。

研究背景与动机

问题背景

  1. 成对比较矩阵的重要性: 在决策分析中，成对比较矩阵A = aij用于表示n个备选方案之间的相对重要性，其中aij表示方案i相对于方案j的重要性比率。这类矩阵广泛应用于层次分析法(AHP)等决策方法中。
  2. 一致性问题: 理想情况下，比较应该是一致的，即满足传递性：aijajk = aik对所有i,j,k成立。然而，实际中由于人类判断的局限性，完全一致的比较矩阵很少出现。
  3. 不完整数据挑战: 在实际应用中，由于各种原因（时间限制、专家知识不足、比较困难等），某些成对比较可能缺失，形成部分互反矩阵(PRM)。

研究动机

  1. 完备性需求: 决策方法通常需要完整的比较矩阵来计算权重向量，因此需要对不完整矩阵进行合理完备。
  2. 一致性优化: 当无法实现完全一致时，需要寻找"近似一致"的完备方案，最小化不一致性度量。
  3. 理论缺口: 现有研究缺乏对何时存在一致完备的精确刻画，以及在弦图条件下保持不一致性度量不增加的系统方法。

核心贡献

  1. 精确刻画一致完备存在条件: 提供了两个角度的完整理论：
    • 基于图结构：当且仅当指定条目图的每个连通分量都是弦图时，存在一致完备
    • 基于数据：当且仅当每个完全指定的环乘积都等于1时，存在一致完备
  2. 弦图情况下的近似一致完备: 证明了当指定条目图为弦图时，总是可以找到不增加三元组不一致性度量MT的完备。
  3. 完备方法论: 开发了具体的算法框架，利用弦序来逐步完备矩阵，确保不恶化不一致性。
  4. 不一致性减少技术: 提出了通过修改少量条目来减少现有完整矩阵不一致性的方法。

方法详解

任务定义

输入: 部分互反矩阵(PRM) A，其中某些条目aij已指定且满足互反性质aji = 1/aij 输出: 完整的互反矩阵Ã，使得：

  1. Ã在指定位置与A一致
  2. 若可能，Ã是一致的(rank-1)
  3. 若不可能，MT(Ã) = MT(A)（不增加不一致性度量）

核心理论框架

1. 一致性的等价条件

对于完整的互反矩阵A ∈ PCn，以下条件等价：

  • A是一致的（rank-1）
  • A中每个环的乘积都等于1
  • A的每个3×3主子矩阵都是一致的

2. 三元组不一致性度量

定义MT(A)为A中所有3-环乘积的最大值： MT(A)=max⁡i<j<k{c(i,j,k),c(k,j,i)}MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\} 其中c(i,j,k) = aijajkaki是3-环乘积。

3. 弦图的重要性质

定理1: 如果G是弦图，存在缺失边的排序，使得逐个添加这些边时每次都保持弦图性质。

这个性质将多变量完备问题分解为一系列单变量问题。

一致完备的充分条件

定理2: 每个部分一致矩阵(PCM)当且仅当其图G的每个连通分量都是弦图时，存在一致完备。如果G连通，则完备唯一。

证明思路:

  1. 单变量情况：对于形如A(x)的矩阵，选择x = (a1,n-1 × a2n)/a2,n-1使A(x)为rank-1
  2. 多变量情况：使用弦序逐个确定未指定条目
  3. 不连通情况：分别完备各连通分量，然后用一致块矩阵连接

一致完备的必要充分条件

定理6: 设A是n×n的PRM且为PC+（每个完全指定的环乘积都等于1），则A有一致完备。如果图G(A)连通，此完备唯一。

证明方法:

  1. 选择G的生成树T
  2. 对应于T的部分矩阵有唯一一致完备Ã
  3. 由于环乘积条件，Ã与A在所有指定位置一致

近似一致完备方法

单变量问题分析

对于单变量完备问题A(x)，定义：

  • C(A): 不涉及位置(1,n)的所有3-环乘积集合
  • C0(A): 涉及位置(1,n)的所有3-环乘积集合
  • S(A) = {a1jajn : 2 ≤ j ≤ n-1}

定理9: 存在x0 > 0使得MT(A(x0)) = MT(A)当且仅当： 1MT(A)⋅MS(A)≤x0≤MT(A)⋅mS(A)\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)

其中MS(A) = max S(A), mS(A) = min S(A)。

弦图情况的完备算法

定理11: 设B是指定条目图为弦图的PRM，则B有互反完备B̃使得MT(B̃) = MT(B)。

算法步骤:

  1. 如果图只是树，直接进行一致完备
  2. 如果图连通且有3-环，按弦序逐个应用定理9
  3. 如果图不连通，先完备各连通分量，再用引理12连接

实验设置

理论验证实例

示例1: 无一致完备的情况

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

图为4-环12341，由于4 = a14 ≠ a12a23a34 = 10/3，无一致完备。

示例2: 弦图完备过程

考虑5×5矩阵N(x,y)，其指定条目图为弦图。通过两步完备：

  1. 首先确定y使MT不增加：y ∈ 1/3, 1/2
  2. 然后确定x使MT不增加：x ∈ √6/4, 2

计算复杂度分析

  • 单变量完备：O(n²)时间确定可行区间
  • 弦图完备：O(m)次单变量问题，其中m为缺失边数
  • 整体复杂度：O(mn²)

实验结果

理论结果验证

一致完备存在性

  1. 弦图条件: 所有测试的弦图PCM都成功找到一致完备
  2. 非弦图反例: 构造的4-环等非弦图PCM确实无一致完备
  3. 数据条件: PC+条件的验证表明其为一致完备的充要条件

近似完备效果

  1. MT度量保持: 在所有弦图测试案例中，都成功找到MT(Ã) = MT(A)的完备
  2. 可行区间: 单变量问题的可行区间总是非空（由引理8保证）
  3. 最优选择: 在可行区间内进一步优化可以最小化新引入的3-环乘积

不一致性减少应用

通过修改单个条目，成功将测试矩阵的MT值从原来的最大值降低到更小值，验证了方法的实用性。

相关工作

成对比较矩阵完备

  1. 早期工作: Saaty的层次分析法奠定了成对比较的基础
  2. 完备方法: Benítez等人研究了一致完备的特征化
  3. 不完整矩阵: Bozóki等人研究了最优完备问题

不一致性度量

  1. Koczkodaj指标: K(A) = 1/(1-MT(A))与本文的MT度量等价
  2. 其他度量: 存在多种不一致性度量，但MT具有局部性和易计算的优势
  3. 公理化研究: Csató对三元组不一致性指标进行了公理化分析

图论在矩阵完备中的应用

  1. 弦图理论: Golumbic的经典工作建立了弦图的基础理论
  2. 矩阵完备: Grone等人将弦图应用于正定矩阵完备
  3. 本文贡献: 首次系统性地将弦图理论应用于互反矩阵完备

结论与讨论

主要结论

  1. 完整理论框架: 建立了互反矩阵一致完备存在性的完整理论，包括基于图结构和基于数据的两个角度
  2. 实用算法: 提供了弦图情况下保持不一致性度量不增加的具体完备算法
  3. 应用拓展: 方法可用于减少现有矩阵的不一致性

局限性

  1. 弦图限制: 近似完备的保证只在弦图情况下成立，一般图情况仍需进一步研究
  2. 度量选择: 虽然MT度量有理论优势，但实际应用中可能需要考虑其他度量
  3. 计算效率: 对于大规模问题，算法的实际效率可能需要进一步优化

未来方向

  1. 一般图扩展: 研究非弦图情况下的近似完备方法
  2. 其他度量: 将方法扩展到其他不一致性度量
  3. 实际应用: 在具体决策问题中验证方法的有效性

深度评价

优点

  1. 理论完备性: 提供了一致完备问题的完整理论刻画，填补了重要理论空白
  2. 方法创新: 巧妙地将弦图理论应用于互反矩阵完备，技术路线新颖
  3. 实用价值: 算法具有多项式时间复杂度，适合实际应用
  4. 写作清晰: 论文结构清晰，定理证明严谨，示例丰富

不足

  1. 应用范围: 主要结果限制在弦图情况，对一般图的处理不够充分
  2. 实验验证: 缺乏大规模数值实验和实际数据验证
  3. 比较分析: 与其他完备方法的系统比较不足
  4. 计算细节: 某些算法步骤的具体实现细节不够详细

影响力

  1. 理论贡献: 为决策分析中的不完整数据处理提供了坚实的理论基础
  2. 方法论价值: 弦序分解的思想可能启发其他矩阵完备问题的研究
  3. 实用潜力: 方法可直接应用于AHP等决策方法中的数据预处理
  4. 学科交叉: 体现了图论、矩阵理论和决策分析的有机结合

适用场景

  1. 决策分析: AHP、ANP等需要成对比较的多准则决策方法
  2. 数据挖掘: 不完整关系数据的预处理和完备
  3. 社会网络: 关系强度矩阵的完备和一致性分析
  4. 经济学: 偏好关系和效用函数的推断

参考文献

论文引用了26篇相关文献，涵盖了成对比较矩阵、不一致性度量、图论和矩阵完备等多个领域的重要工作，为研究提供了坚实的理论基础。

总体评价: 这是一篇高质量的理论论文，在互反矩阵完备这一重要问题上取得了显著的理论进展。虽然在实验验证和应用范围方面有所不足，但其理论贡献和方法创新具有重要价值，对决策分析和相关领域的研究具有积极的推动作用。