Completaciones de datos de comparación por pares que minimizan la medida triádica de inconsistencia

Información Básica

• ID del Artículo: 2510.12351
• Título: Completaciones de datos de comparación por pares que minimizan la medida triádica de inconsistencia
• Autores: Susana Furtado (CEMS.UL y Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Clasificación: math.CO (Matemática Combinatoria), math.OC (Optimización y Control)
• Fecha de Publicación: 15 de octubre de 2025 (preimpreso arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.12351

Resumen

Este artículo estudia matrices de comparación por pares incompletas, determinando con precisión cuándo existe una completación consistente y, si no existe, cuándo existe una completación aproximadamente consistente. Los autores utilizan el producto máximo de 3-ciclos como medida de inconsistencia, demostrando que cuando el grafo de entradas especificadas es cordal, siempre es posible encontrar una completación que no aumenta esta medida. El artículo desarrolla una metodología para generar tales completaciones, que también puede utilizarse para reducir la inconsistencia mediante cambios en pocas comparaciones.

Antecedentes y Motivación de la Investigación

Contexto del Problema

1. Importancia de las matrices de comparación por pares: En análisis de decisiones, una matriz de comparación por pares A = aij se utiliza para representar la importancia relativa entre n alternativas, donde aij representa la razón de importancia de la alternativa i respecto a la alternativa j. Tales matrices se aplican ampliamente en métodos de decisión como el Proceso Analítico Jerárquico (AHP).
2. Problema de consistencia: Idealmente, las comparaciones deben ser consistentes, es decir, satisfacer la transitividad: aijajk = aik para todo i, j, k. Sin embargo, en la práctica, debido a las limitaciones del juicio humano, las matrices de comparación completamente consistentes rara vez ocurren.
3. Desafío de datos incompletos: En aplicaciones prácticas, por diversas razones (limitaciones de tiempo, conocimiento insuficiente de expertos, dificultad de comparación, etc.), algunas comparaciones por pares pueden faltar, formando una matriz recíproca parcial (PRM).

Motivación de la Investigación

1. Necesidad de completación: Los métodos de decisión típicamente requieren matrices de comparación completas para calcular vectores de pesos, por lo que es necesario completar razonablemente las matrices incompletas.
2. Optimización de consistencia: Cuando no es posible lograr consistencia completa, es necesario buscar esquemas de completación "aproximadamente consistentes" que minimicen la medida de inconsistencia.
3. Brecha teórica: La investigación existente carece de una caracterización precisa de cuándo existe una completación consistente, así como de métodos sistemáticos para mantener la medida de inconsistencia sin aumentarla bajo condiciones de grafos cordales.

Contribuciones Principales

1. Caracterización precisa de condiciones de existencia de completación consistente: Proporciona una teoría completa desde dos perspectivas:
   • Basada en estructura de grafos: Existe una completación consistente si y solo si cada componente conexa del grafo de entradas especificadas es un grafo cordal
   • Basada en datos: Existe una completación consistente si y solo si cada producto de ciclo completamente especificado es igual a 1
2. Completación aproximadamente consistente en caso de grafos cordales: Demuestra que cuando el grafo de entradas especificadas es cordal, siempre es posible encontrar una completación que no aumenta la medida de inconsistencia triádica MT.
3. Metodología de completación: Desarrolla un marco algorítmico concreto que utiliza ordenamientos cordales para completar progresivamente la matriz, asegurando que no se deteriore la inconsistencia.
4. Técnica de reducción de inconsistencia: Propone un método para reducir la inconsistencia de matrices completas existentes mediante la modificación de pocas entradas.

Explicación Detallada de Métodos

Definición de Tareas

Entrada: Matriz recíproca parcial (PRM) A, donde ciertas entradas aij están especificadas y satisfacen la propiedad recíproca aji = 1/aij Salida: Matriz recíproca completa à tal que:

1. Ã coincide con A en posiciones especificadas
2. Si es posible, Ã es consistente (rango-1)
3. Si no es posible, MT(Ã) = MT(A) (no aumenta la medida de inconsistencia)

Marco Teórico Principal

1. Condiciones Equivalentes de Consistencia

Para una matriz recíproca completa A ∈ PCn, las siguientes condiciones son equivalentes:

• A es consistente (rango-1)
• Cada ciclo en A tiene producto igual a 1
• Cada submatriz principal 3×3 de A es consistente

2. Medida de Inconsistencia Triádica

Se define MT(A) como el máximo de todos los productos de 3-ciclos en A: $MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\}$ donde c(i,j,k) = aijajkaki es el producto del 3-ciclo.

3. Propiedades Importantes de Grafos Cordales

Teorema 1: Si G es un grafo cordal, existe un ordenamiento de aristas faltantes tal que al agregar estas aristas secuencialmente, cada vez se mantiene la propiedad de ser cordal.

Esta propiedad descompone el problema de completación multivariable en una serie de problemas univariables.

Condiciones Suficientes para Completación Consistente

Teorema 2: Una matriz de comparación parcial (PCM) tiene una completación consistente si y solo si cada componente conexa de su grafo G es un grafo cordal. Si G es conexa, la completación es única.

Esquema de Prueba:

1. Caso univariable: Para una matriz de la forma A(x), se elige x = (a1,n-1 × a2n)/a2,n-1 para que A(x) sea rango-1
2. Caso multivariable: Se utiliza el ordenamiento cordal para determinar secuencialmente las entradas no especificadas
3. Caso no conexo: Se completan por separado las componentes conexas, luego se conectan con una matriz de bloques consistente

Condiciones Necesarias y Suficientes para Completación Consistente

Teorema 6: Sea A una PRM n×n y sea A ∈ PC+ (cada producto de ciclo completamente especificado es igual a 1), entonces A tiene una completación consistente. Si el grafo G(A) es conexo, esta completación es única.

Método de Prueba:

1. Se selecciona un árbol generador T de G
2. La submatriz parcial correspondiente a T tiene una única completación consistente Ã
3. Debido a la condición de producto de ciclos, Ã coincide con A en todas las posiciones especificadas

Método de Completación Aproximadamente Consistente

Análisis de Problema Univariable

Para un problema de completación univariable A(x), se define:

• C(A): Conjunto de todos los productos de 3-ciclos que no involucran la posición (1,n)
• C0(A): Conjunto de todos los productos de 3-ciclos que involucran la posición (1,n)
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Teorema 9: Existe x0 > 0 tal que MT(A(x0)) = MT(A) si y solo si: $\frac{1}{MT(A)} \cdot mS(A) \leq x_0 \leq MT(A) \cdot MS(A)$

donde MS(A) = máx S(A), mS(A) = mín S(A).

Algoritmo de Completación para Grafos Cordales

Teorema 11: Sea B una PRM cuyo grafo de entradas especificadas es cordal, entonces B tiene una completación recíproca B̃ tal que MT(B̃) = MT(B).

Pasos del Algoritmo:

1. Si el grafo es solo un árbol, se realiza directamente la completación consistente
2. Si el grafo es conexo y tiene 3-ciclos, se aplica secuencialmente el Teorema 9 según el ordenamiento cordal
3. Si el grafo no es conexo, se completan por separado las componentes conexas, luego se conectan usando el Lema 12

Configuración Experimental

Ejemplos de Verificación Teórica

Ejemplo 1: Caso sin Completación Consistente

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

El grafo es un 4-ciclo 12341. Dado que 4 = a14 ≠ a12a23a34 = 10/3, no existe completación consistente.

Ejemplo 2: Proceso de Completación de Grafo Cordal

Considérese una matriz 5×5 N(x,y) cuyo grafo de entradas especificadas es cordal. Mediante dos pasos de completación:

1. Primero se determina y para que MT no aumente: y ∈ 1/3, 1/2
2. Luego se determina x para que MT no aumente: x ∈ √6/4, 2

Análisis de Complejidad Computacional

• Completación univariable: Tiempo O(n²) para determinar el intervalo factible
• Completación de grafo cordal: O(m) problemas univariables, donde m es el número de aristas faltantes
• Complejidad general: O(mn²)

Resultados Experimentales

Verificación de Resultados Teóricos

Existencia de Completación Consistente

1. Condición de grafo cordal: Todas las PCM de grafo cordal probadas encontraron exitosamente una completación consistente
2. Contraejemplos de grafo no cordal: Las PCM de grafo no cordal construidas (como 4-ciclos) confirmaron que no tienen completación consistente
3. Verificación de condición de datos: La verificación de la condición PC+ confirmó que es necesaria y suficiente para completación consistente

Efectividad de Completación Aproximada

1. Preservación de medida MT: En todos los casos de prueba de grafo cordal, se encontró exitosamente una completación con MT(Ã) = MT(A)
2. Intervalo factible: El intervalo factible del problema univariable siempre es no vacío (garantizado por el Lema 8)
3. Selección óptima: La optimización adicional dentro del intervalo factible puede minimizar los productos de 3-ciclos recién introducidos

Aplicación de Reducción de Inconsistencia

Mediante la modificación de una sola entrada, se logró exitosamente reducir el valor MT de la matriz de prueba desde su valor máximo original a un valor más pequeño, verificando la practicidad del método.

Trabajo Relacionado

Completación de Matrices de Comparación por Pares

1. Trabajo temprano: El Proceso Analítico Jerárquico de Saaty sentó las bases para la comparación por pares
2. Métodos de completación: Benítez et al. estudiaron la caracterización de completaciones consistentes
3. Matrices incompletas: Bozóki et al. investigaron problemas de completación óptima

Medidas de Inconsistencia

1. Indicador de Koczkodaj: K(A) = 1/(1-MT(A)) es equivalente a la medida MT de este artículo
2. Otras medidas: Existen múltiples medidas de inconsistencia, pero MT tiene ventajas de localidad y facilidad computacional
3. Investigación axiomática: Csató realizó un análisis axiomático de indicadores de inconsistencia triádica

Aplicación de Teoría de Grafos en Completación de Matrices

1. Teoría de grafos cordales: El trabajo clásico de Golumbic estableció la teoría fundamental de grafos cordales
2. Completación de matrices: Grone et al. aplicaron grafos cordales a la completación de matrices definidas positivas
3. Contribución de este artículo: Primera aplicación sistemática de teoría de grafos cordales a completación de matrices recíprocas

Conclusiones y Discusión

Conclusiones Principales

1. Marco teórico completo: Se establece una teoría completa sobre la existencia de completación consistente de matrices recíprocas, incluyendo dos perspectivas basadas en estructura de grafos y en datos
2. Algoritmo práctico: Se proporciona un algoritmo concreto de completación para grafos cordales que mantiene la medida de inconsistencia sin aumentarla
3. Extensión de aplicaciones: El método puede utilizarse para reducir la inconsistencia de matrices existentes

Limitaciones

1. Restricción de grafo cordal: La garantía de completación aproximada solo se aplica en caso de grafos cordales; el caso de grafos generales requiere investigación adicional
2. Selección de medida: Aunque la medida MT tiene ventajas teóricas, en aplicaciones prácticas puede ser necesario considerar otras medidas
3. Eficiencia computacional: Para problemas a gran escala, la eficiencia práctica del algoritmo puede requerir optimización adicional

Direcciones Futuras

1. Extensión a grafos generales: Investigar métodos de completación aproximada para casos de grafos no cordales
2. Otras medidas: Extender el método a otras medidas de inconsistencia
3. Aplicaciones prácticas: Verificar la efectividad del método en problemas de decisión concretos

Evaluación Profunda

Fortalezas

1. Completitud teórica: Proporciona una caracterización teórica completa del problema de completación consistente, llenando una brecha teórica importante
2. Innovación metodológica: Aplica ingeniosamente la teoría de grafos cordales a la completación de matrices recíprocas, con una ruta técnica novedosa
3. Valor práctico: El algoritmo tiene complejidad de tiempo polinomial, adecuado para aplicaciones prácticas
4. Claridad de escritura: La estructura del artículo es clara, las demostraciones de teoremas son rigurosas, y los ejemplos son abundantes

Insuficiencias

1. Alcance de aplicación: Los resultados principales se limitan al caso de grafos cordales; el tratamiento de grafos generales es insuficiente
2. Verificación experimental: Faltan experimentos numéricos a gran escala y verificación con datos reales
3. Análisis comparativo: Falta comparación sistemática con otros métodos de completación
4. Detalles de implementación: Los detalles de implementación específica de ciertos pasos algorítmicos no son suficientemente detallados

Impacto

1. Contribución teórica: Proporciona una base teórica sólida para el tratamiento de datos incompletos en análisis de decisiones
2. Valor metodológico: La idea de descomposición por ordenamiento cordal puede inspirar investigaciones sobre otros problemas de completación de matrices
3. Potencial práctico: El método puede aplicarse directamente en preprocesamiento de datos en métodos de decisión como AHP
4. Interdisciplinariedad: Refleja la combinación orgánica de teoría de grafos, teoría de matrices y análisis de decisiones

Escenarios Aplicables

1. Análisis de decisiones: Métodos de decisión multicriterio que requieren comparación por pares, como AHP y ANP
2. Minería de datos: Preprocesamiento y completación de datos de relaciones incompletas
3. Redes sociales: Completación y análisis de consistencia de matrices de intensidad de relaciones
4. Economía: Inferencia de relaciones de preferencia y funciones de utilidad

Referencias Bibliográficas

El artículo cita 26 referencias relacionadas, abarcando múltiples campos incluyendo matrices de comparación por pares, medidas de inconsistencia, teoría de grafos y completación de matrices, proporcionando una base teórica sólida para la investigación.

Evaluación General: Este es un artículo teórico de alta calidad que logra avances teóricos significativos en el importante problema de completación de matrices recíprocas. Aunque tiene algunas insuficiencias en verificación experimental y alcance de aplicación, sus contribuciones teóricas e innovaciones metodológicas tienen valor importante y ejercen un efecto promotor positivo en la investigación de análisis de decisiones y campos relacionados.