Пополнения данных попарного сравнения, минимизирующие триадную меру несогласованности

Основная информация

• ID статьи: 2510.12351
• Название: Completions of pairwise comparison data that minimize the triad measure of inconsistency
• Авторы: Susana Furtado (CEMS.UL и Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Классификация: math.CO (комбинаторика), math.OC (оптимизация и управление)
• Дата публикации: 15 октября 2025 г. (препринт 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. По возможности Ã является согласованной (ранг 1)
3. Если невозможно, MT(Ã) = MT(A) (мера несогласованности не увеличивается)

Основная теоретическая база

1. Эквивалентные условия согласованности

Для полной обратносимметричной матрицы A ∈ PCn следующие условия эквивалентны:

• A является согласованной (ранг 1)
• Каждый цикл в A имеет произведение, равное 1
• Каждая главная подматрица размера 3×3 в A является согласованной

2. Триадная мера несогласованности

Определяется MT(A) как максимум всех произведений 3-циклов в A: $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) имела ранг 1
2. Многомерный случай: используется хордальный порядок для последовательного определения неуказанных элементов
3. Несвязный случай: каждая связная компонента пополняется отдельно, затем компоненты соединяются согласованной блочной матрицей

Необходимые и достаточные условия согласованного пополнения

Теорема 6: Пусть A — матрица n×n типа PRM и PC+ (каждое полностью определённое произведение цикла равно 1), тогда A имеет согласованное пополнение. Если граф G(A) связен, это пополнение единственно.

Метод доказательства:

1. Выбирается остовное дерево T графа G
2. Частичная матрица, соответствующая T, имеет единственное согласованное пополнение Ã
3. Благодаря условию произведения циклов Ã совпадает с A во всех указанных позициях

Метод приблизительно согласованного пополнения

Анализ одномерной задачи

Для одномерной задачи пополнения A(x) определяются:

• C(A): множество всех произведений 3-циклов, не включающих позицию (1,n)
• C0(A): множество всех произведений 3-циклов, включающих позицию (1,n)
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Теорема 9: Существует x0 > 0 такое, что MT(A(x0)) = MT(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-циклы, действительно не имеют согласованного пополнения
3. Условие на данные: Верификация условия PC+ подтверждает его как необходимое и достаточное условие для согласованного пополнения

Эффективность приблизительного пополнения

1. Сохранение меры MT: Во всех протестированных случаях хордальных графов успешно найдено пополнение с MT(Ã) = MT(A)
2. Допустимые интервалы: Допустимые интервалы для одномерных задач всегда непусты (гарантировано леммой 8)
3. Оптимальный выбор: Дальнейшая оптимизация в допустимом интервале позволяет минимизировать вновь введённые произведения 3-циклов

Применение для снижения несогласованности

Путём модификации отдельных элементов успешно снижено значение MT тестовых матриц от исходного максимума к меньшему значению, что подтверждает практическую применимость метода.

Связанные работы

Пополнение матриц попарного сравнения

1. Ранние работы: Аналитический иерархический процесс Саати заложил основы попарного сравнения
2. Методы пополнения: Бенитес и др. исследовали характеризацию согласованного пополнения
3. Неполные матрицы: Бозоки и др. исследовали задачи оптимального пополнения

Меры несогласованности

1. Индекс Кокзодая: K(A) = 1/(1-MT(A)) эквивалентен мере MT в данной работе
2. Другие меры: Существуют различные меры несогласованности, но MT обладает преимуществами локальности и простоты вычисления
3. Аксиоматические исследования: Чато провёл аксиоматический анализ триадных индексов несогласованности

Применение теории графов в пополнении матриц

1. Теория хордальных графов: Классические работы Голумбика заложили основы теории хордальных графов
2. Пополнение матриц: Гроне и др. применили хордальные графы к пополнению положительно определённых матриц
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 связанных работ, охватывающих важные исследования в области матриц попарного сравнения, мер несогласованности, теории графов и пополнения матриц, обеспечивая прочную теоретическую основу для исследования.

Общая оценка: Это высококачественная теоретическая работа, достигшая значительного теоретического прогресса в важной задаче пополнения обратносимметричных матриц. Хотя в экспериментальной верификации и диапазоне применения имеются некоторые недостатки, её теоретические вклады и методологические инновации имеют важное значение и оказывают позитивное влияние на исследования в области анализа решений и смежных областях.