Оценка эффективности декомпозиции задачи нахождения линейной медианы Кемени на основе анализа мажоритарного графа

В.Н. Нефедов; В.С. Силаева

doi:10.17759/mda.2026160107

Введение

Рассматривается задача группового выбора, состоящая в нахождении результирующей ранжировки, в наибольшей степени учитывающей индивидуальные предпочтения членов группы.

Существуют различные подходы к решению данной задачи: включая классические теории Ш. Борда и Н. Кондорсе (Миркин, 1974), концепция рационального выбора группы К. Эрроу (Мулен, 1991), а также методы, базирующиеся на анализе близости бинарных отношений (Young, 1988; Петровский, 2009, Нефедов и др., 2018). В данной работе в качестве оптимального агрегированного ранжирования рассматривается линейная медиана Кемени — линейный порядок, минимизирующий сумму расстояний Хемминга до индивидуальных предпочтений. Данный критерий обладает рядом аксиоматических преимуществ и интерпретируется как отражение максимального консенсуса внутри группы (Kemeny, 1959).

Однако нахождение медианы Кемени представляет собой NP-трудную вычислительную задачу (Bartholdi, Tovey, Trick, 1989; Hudry, 2012). Существующие алгоритмы решения данной задачи можно разделить на эвристические, не гарантирующие оптимальности (Петровский, 2009; Литвак, 1982; Корнеенко, 2018; Cook, 2006), и точные, основанные на методах дискретной оптимизации (например, целочисленное программирование, метод ветвей и границ (Нефедов, Осипова, 2022; Azzini, Munda, 2020)). Точные методы в худшем случае требуют перебора

n!

перестановок (где

n

— число альтернатив), что ограничивает их применимость на практике даже для умеренных

n

. Это обуславливает необходимость разработки методов ускорения, использующих специфическую структуру задачи.

Одним из таких перспективных подходов является декомпозиция на основе мажоритарного графа. Мажоритарный граф отражает попарные отношения большинства между альтернативами. Известно, что задача поиска медианы Кемени может быть сведена к задаче устранения контуров в этом графе (Нефедов и др., 2018). Ключевая идея ускорения заключается в том, что, если мажоритарный граф не является сильно связным, его можно разложить на компоненты сильной связности (КСС). Задача поиска глобальной медианы при этом распадается на независимые подзадачи внутри каждой КСС, а их результаты объединяются в соответствии с ациклическим графом конденсации. Теоретически это позволяет снизить вычислительную сложность с

O (n!)

до

O (n_{1}! + \dots + n_{k}!)

, где

n_{i}

— размеры КСС, что эквивалентно

O (n_{m ax}!)

, где

n_{\max} = \max n_{i}

.

Несмотря на очевидный теоретический потенциал, практическая эффективность данного подхода остается недостаточно изученной. Отсутствуют количественные оценки того, насколько часто и при каких условиях мажоритарный граф допускает нетривиальную декомпозицию, и как эффективность этой декомпозиции (размер максимальной КСС) зависит от степени согласованности экспертов.

Целью данного исследования является оценка эффективности метода декомпозиции мажоритарного графа для ускорения нахождения медианы Кемени на основе статистического анализа.

Для этого мы исследуем три последовательно усложняющиеся модели генерации профилей предпочтений: от независимых случайных порядков (M1), затем модель с умеренной согласованностью (М2) до модели с контролируемым уровнем согласованности (M3). Полученные количественные зависимости позволяют априорно оценить ожидаемую сложность задачи и определить условия, при которых декомпозиция дает максимальный вычислительный выигрыш.

Материалы и методы

Постановка задачи нахождения линейной медианы Кемени

Группа из

m

лиц рассматривает несколько возможных вариантов (альтернатив)

A = {a_{1}, \dots, a_{n}}

решения некоторой проблемы. Индивидуальные предпочтения членов группы в общем случае выражаются бинарными отношениями, и задают профиль

⟨ ρ_{1}, \dots, ρ_{m} ⟩

бинарных отношений на

A

.

Обозначим через

LO [n]

совокупность всех линейных порядков на

A

, т. е. бинарных отношений на

A

, являющихся одновременно рефлексивными, антисимметричными, транзитивными и линейными. Под строгим ранжированием понимается любое отношение из

LO [n]

, для нестрогого ранжирования необязательно условие антисимметричности. Расстояние между бинарными отношениями

ρ, ρ^{'} \subseteq A \times A

с матрицами

R (ρ) = {‖ r_{ij} ‖}_{n \times n}

,

R (ρ') = {‖ r_{ij}' ‖}_{n \times n}

, где

r_{ij}, r_{ij}^{'} \in {0,1}

, будем задавать метрикой Хемминга:

d (ρ, ρ^{'}) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} | r_{ij} - r_{ij}' | .

В качестве реляционного правила агрегирования предлагается выбрать линейную медиану Кемени, т. е. результирующую строгую ранжировку, наиболее близкую в смысле метрики Хемминга к мнениям экспертов. Таким образом, рассматриваемая задача сводится к нахождению линейной ранжировки (в общем случае множества ранжировок), минимизирующей функцию

D (ρ) = \sum_{t = 1}^{m} d (ρ, ρ_{t}),

т. е.

\begin{matrix} \hat{ρ} \in Arg \min_{ρ \in LO [n]} D (ρ) . \end{matrix}

В общем случае такая ранжировка может оказаться неединственной и потребуется нахождение всего множества

\begin{matrix} Arg \min_{ρ \in LO [n]} D (ρ) . \end{matrix}

Построение мажоритарного графа

Процедура построения мажоритарного графа предлагается еще в работе (Миркин, 1974). Пусть имеется набор бинарных отношений

ρ_{1}, ρ_{2}, \dots, ρ_{m}

с матрицами смежности

R^{(1)}, R^{(2)}, \dots, R^{(m)}

, где

R^{(t)} = R (ρ_{t}) = ‖ r_{ij}^{(t)} ‖

,

t = 1,2, \dots, m

. Поставим ему в соответствие матрицы

P = \sum_{t = 1}^{m} R^{(t)} = ‖ p_{ij} ‖

,

L = P - P^{T} = ‖ l_{ij} ‖

.

Тогда для данного набора бинарных отношений

ρ_{1}, ρ_{2}, \dots, ρ_{m}

рассмотрим мажоритарное отношение

\tilde{ρ}

. Оно однозначно определяется по «правилу большинства»

{\tilde{r}}_{ij} = 1 \Leftrightarrow l_{ij} \geq 0

, где

R (\tilde{ρ}) = {‖ {\tilde{r}}_{ij} ‖}_{n \times n}

. Будем, кроме того, использовать нестрогий мажоритарный граф

\tilde{G} = (A, \tilde{ρ})

с множеством вершин

A

и множеством дуг

\tilde{ρ}

. Мажоритарный граф

\tilde{G}

можно считать нагруженным, если поставить в соответствие каждой дуге

(a_{i}, a_{j}) \in \tilde{ρ}

вес

l_{ij}

. Определим матрицу весов

C = {‖ c_{ij} ‖}_{n \times n}

этого графа:

c_{ij} = {\begin{matrix} l_{ij}, \\ \infty, \end{matrix} \begin{matrix} если (a_{i}, a_{j}) \in \tilde{ρ}, \\ в противном случае . \end{matrix}

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

Задача нахождения линейной медианы Кемени тождественна задаче разрушения контуров в мажоритарном графе (с минимизацией суммарного веса удаляемых дуг) и последующему расширению полученного ацикличного графа (или множества графов) до всех возможных линейных порядков.

Принцип декомпозиции задачи

Компонента сильной связности (КСС) — это максимальное по включению множество вершин, в котором для любой пары вершин

⟨ u, v ⟩

существует ориентированный путь как из

u

в

v

, так и из

v

в

u

. Все ориентированные циклы (контуры) содержатся целиком внутри КСС. Для выделения КСС могут использоваться алгоритмы Косарайю или Тарьяна (Sharir, 1981; Tarjan, 1972), имеющие линейную сложность

O

относительно числа вершин

n

и дуг

\tilde{ρ} \lor

. Число дуг в графе не превосходит

2 n^{2}

, поэтому трудоемкость поиска КСС

O (n^{2})

.

После нахождения КСС мажоритарного графа

\tilde{G}

строится граф конденсации

{\tilde{G}}_{C}

. Вершинами этого графа являются найденные КСС (обозначим их

C_{1}, C_{2}, \dots, C_{k}

), а дуга от компоненты

C_{s}

к компоненте

C_{t}

проводится, если в исходном графе

\tilde{G}

существует хотя бы одна дуга из некоторой вершины графа

C_{s}

в некоторую вершину графа

C_{t}

.

Граф конденсации всегда является ацикличным: так как наличие цикла между компонентами означало бы, что их вершины принадлежат одной КСС. Таким образом граф

{\tilde{G}}_{C}

(точнее, его транзитивное замыкание) задает частичный порядок на множестве компонент.

Для каждой КСС

C_{i}

независимо от других найдем «локальную» линейную медиану Кемени (или множество локальных линейных медиан) на множестве вершин графа

C_{i}

. Затем рассмотрим прямое произведение всех возможных локальных медиан по всем КСС. Для каждого из случаев рассмотрим граф, полученный из мажоритарного графа заменой каждой из КСС на граф из найденного для этой КСС множества локальных медиан. Полученный в результате такой замены граф не содержит контуров, и его транзитивное замыкание является частичным порядком на всем множестве

A

. Для получения совокупности всех линейных медиан Кемени необходимо всеми возможными способами расширить этот частичный порядок до линейного, к примеру алгоритмом Варола-Ротема (Varol, Rotem, 1981). Нетрудно показать, что любой полученный таким образом линейный порядок

\hat{ρ}

имеет одинаковое значение

D (\hat{ρ}) = \min_{ρ \in LO [n]} D (ρ)

.

Приведем также обоснование в обратную сторону. Если имеется некоторое общее решение

\hat{ρ}

(т.е.

\hat{ρ}

— оптимальный линейный порядок для общей задачи), то он порождает соответствующие «локальные» оптимальные линейные порядки на каждой из КСС, которые войдут в общий перебор для каждой из этих подзадач, а тем самым и в их набор, т.е. линейный порядок

\hat{ρ}

войдет в прямое произведение всех локальных медиан по всем КСС и будет учтен в общем решении задачи.

Описанный подход позволяет, например, применять описанный в (Нефедов, Осипова 2022) метод ветвей и границ решения общей задачи, использующий матрицу

P = \sum_{t = 1}^{m} R^{(t)}

(будем его называть «матричным методом») не ко всей задаче, а к частным задачам, соответствующим КСС, т.е. осуществлять декомпозицию общей задачи на частные. Но, если применение этого метода ко всей задаче имеет естественные ограничения (не более 26–30 альтернатив), то это ограничение теперь будет относиться к частным задачам, что позволяет решать некоторые задачи указанным матричным методом при весьма большом числе альтернатив.

Рассмотрим следующий частный случай, когда мажоритарный граф обладает следующим свойствами: 1)

{\tilde{G}}_{C}

является линейным порядком; 2) если

⟨ C_{s}, C_{t} ⟩ \in {\tilde{G}}_{C}

, то для всех

a_{s_{i}} \in C_{s}

,

a_{t_{i}} \in C_{t}

верно

⟨ a_{s_{i}}, a_{t_{i}} ⟩ \in \tilde{G} .

Такой случай, например, возникает, если бинарные отношения

ρ_{1}, ρ_{2}, \dots, ρ_{m}

являются линейными и асимметричными (турнирами) и

m

— нечетно (Нефедов, 2022). В этом случае решение исходной задачи также основывается на ее декомпозиции на множество частных и сводится к следующим двум этапам:

Для каждой КСС $C_{i}$ найти все возможные локальные медианы (линейные порядки на множестве $C_{i}$ .
Объединить полученные ранжировки в глобальную линейную ранжировку на всем множестве $A$ в соответствии с линейным порядком, задаваемым графом конденсации (конкатенация линейных порядков).

Если для решения задачи необходимо найти не все множество медиан, а только одну из возможных, то можно свести задачу к частному случаю расширив

{\tilde{G}}_{C}

каким-то одним способом до линейного и добавив дуги, чтобы для любых

⟨ C_{s}, C_{t} ⟩ \in {\tilde{G}}_{C}

выполнялось:

⟨ a_{s_{i}}, a_{t_{j}} ⟩ \in \tilde{G}

для всех

a_{s_{i}} \in C_{s}

,

a_{t_{j}} \in C_{t}

. Расширение частичного порядка до одного из возможных линейных порядков, может быть найдено топологической сортировкой (упорядочивание

n

вершин ориентированного ациклического графа по

n

уровням таким образом, чтобы все дуги были направлены от вершин с меньшим уровнем к вершинам с большим) и может быть выполнено всего за

O (n)

, к примеру алгоритмом Кана или алгоритмом Демукрона (Кормен и др., 2005).

Сложность решения исходной задачи в частном случае после декомпозиции определяется размером наибольшей из КСС (

n_{\max} = \max (| C_{1} |, ..., | C_{k} |) = \max (n_{1}, ..., n_{k})

). Даже если внутри каждой компоненты применяется полный перебор, сложность составит порядка

O (n_{\max}!)

(с точностью до полиномиальных множителей). В лучшем случае мажоритарный граф ацикличен, все

C_{i} \lor 1

, и задача решается за полиномиальное время. В худшем случае граф сильно связен (

k = 1

,

n_{\max} = n

), и декомпозиция не дает выигрыша.

Модели генерации данных

Экспериментальное исследование было построено как последовательность трех моделей, каждая из которых устраняет ограничения или отвечает на вопросы, возникшие при анализе предыдущей. Все модели были реализованы для фиксированного числа альтернатив

n = 35

. Для каждого набора параметров проводилось

N = 100 000

(для M1, M2) или

N = 10 000

(для M3) независимых испытаний. В каждом испытании генерировался профиль предпочтений, строился мажоритарный граф, находились его КСС и определялся размер максимальной компоненты

n_{\max}

.

Модель M1: Базовый случай (нулевая априорная согласованность).

Цель модели — определение базового уровня эффективности декомпозиции в условиях максимальной неопределенности, когда мнения экспертов абсолютно независимы и случайны.

Профиль состоит из

m

независимых случайных линейных порядков на множестве

A

. Все

m!

возможных комбинаций равновероятны. Параметры модели:

m \in {3, 5, 7, 9}

(нечетные).

Мы ожидали, что при полной случайности мажоритарный граф будет близок к случайному турниру, где вероятность существования большого контура высока, а значит, декомпозиция будет слабой. Результаты M1 подтвердили это: среднеожидаемый размер максимальной компоненты

\tilde{n} = M [n_{\max}]

был близок к количеству альтернатив

n

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

Модель M2: Управляемая согласованность на линейных порядках.

Цель модели М2: исследовать, как введение согласованности в предпочтения экспертов влияет на эффективность декомпозиции.

Профиль отношений генерируется следующим образом. Задается эталонный линейный порядок

ρ_{0}

(мнение гипотетического идеального эксперта). Мнение каждого из

m

экспертов (включая первого) получается из

ρ_{0}

путем применения фиксированного числа

p

случайных перестановок пар альтернатив. Параметры:

m \in {3, 5, 7, 9}

(нечетные),

p \in {1, 2, \dots,35}

.

В отличие от M1, здесь эксперты не независимы — их мнения отталкиваются от эталонного. Мы исследовали, как мера согласованности, контролируемая параметром p, влияет на

n_{m ax}

. Результаты M2 показали существенный рост эффективности декомпозиции с уменьшением

p

. Однако модель M2 имела методологическое ограничение: параметр

p

— косвенная и нелинейная мера согласованности для всего профиля. Возникла потребность в модели с прямым и четким контролем над степенью согласованности.

Модель M3: Контролируемая согласованность на турнирах (обобщенный случай).

Цели модели М3: ввести прямую количественную меру согласованности профиля; обобщить исследование на более широкий класс предпочтений (турниры, не обязательно транзитивные).

Профиль отношений генерируется следующим образом. Задается эталонный турнир

ρ_{1}

(в нашем случае соответствующий линейному порядку). Для каждого из остальных

m - 1

экспертов генерируется турнир

ρ_{t}

, находящийся на заданном расстоянии Хемминга от

ρ_{1}

. А именно: в матрице смежности

ρ_{1}

инвертируется ровно

k

случайных элементов вне диагонали. Это гарантирует, что

d (ρ_{t}, ρ_{1}) = 2 k

при

t = \bar{2, m}

.

Параметр

k

(смещение относительно эталона) может принимать значения от 0 до

\frac{n (n - 1)}{2}

. Поэтому введем нормированный параметр — степень отклонения индивидуальных мнений от единого эталона

r = \frac{2 k}{n (n - 1)}

. При

r = 0

все эксперты идентичны

ρ_{1}

, при

r = 1

мнения диаметрально противоположны эталону (полная поляризация).

Параметры:

m \in {5, 6, 7, 8}

,

k \in {10, 20, 30, \dots,580, 590}

(т.к. k при данном

n

может принимать значения от 0 до

35 \cdot 34 / 2 = 595

). Т.к.

k

принимает целых 59 значений, то было решено уменьшить количество тестов

N

с

100000

до

10000

.

Модель M3 решает ключевые проблемы M2. Данная модель генерации позволяет получать профили с разным уровнем внутренней согласованности (когерентности) группы, которую мы измеряем как величину обратную среднему попарному расстоянию Хемминга между мнениями экспертов. При

r \to 0

и

r \to 1

внутренняя ожидаемая согласованность высока (консенсус и поляризация соответственно), а при

r \approx 0,5

— минимальна (максимальные разногласия). Это позволяет исследовать, как когерентность группы, а не просто случайность, влияет на структуру мажоритарного графа. Переход от линейных порядков к турнирам делает модель более общей. Также М3 позволяет изучать влияние четности числа экспертов

m

.

Эта модель позволила выявить обратную U-образную зависимость среднеожидаемого размера максимальной КСС

\tilde{n}

от степени отклонения индивидуальных мнений от единого эталона

r

(

\tilde{n}

сначала увеличивается с увеличением

r

, достигает максимума

\tilde{n} = n

, затем уменьшается), что является основным результатом данной работы.

Метрика исследования

Основная метрика:

n_{m ax}

— размер максимальной КСС мажоритарного графа для данного тестового профиля. Для анализа используются: распределение

n_{m ax}

по тестам и среднеожидаемый размер максимальной компоненты

\tilde{n} = M [n_{\max}]

для фиксированных

m

.

Результаты

В данном разделе представлены статистические результаты вычислительных экспериментов для трех моделей генерации данных. Основной измеряемой величиной является размер максимальной компоненты сильной связности (

n_{m ax}

) мажоритарного графа.

Для каждой серии экспериментов приводятся: распределение частоты встречаемости различных значений

n_{m ax}

и среднеожидаемый размер максимальной компоненты

\tilde{n}

при фиксированном

m

.

Результаты модели М1

Было проведено по

N = 100 000

испытаний для каждого нечетного числа экспертов

m \in {3, 5, 7, 9}

при фиксированном числе альтернатив

n = 35

. Гистограммы распределений

n_{m ax}

для фиксированных

m

изображены на рис. 1.

Таблица 1 / Table 1

Среднеожидаемый размер максимальной компоненты для М1 для разных

m

The expected average size of the maximum component for M1 for different

m

$m$	3	5	7	9
${\tilde{n}}_{m}$	33,6	34,1	34,3	34,3

Результаты модели М2

Исследовалось влияние параметра согласованности

p

(число переставленных пар). Для

m \in {3, 5, 7, 9}

и

p \in {1, 2, \dots 35}

проведено по

N = 100 000

испытаний. Гистограммы распределений

n_{m ax}

для фиксированных

m

при

p = 5

изображены на рис. 2, при

p = 10

на рис. 3 и при

p = 30

на рис. 4.

Рис. 2. Гистограммы распределений $n_{m ax}$ М2 при $p = 5$

Fig. 2. Histograms of $n_{m ax}$ distributions of the M2 at $p = 5$

Рис. 3. Гистограммы распределений $n_{m ax}$ М2 при $p = 10$

Fig. 3. Histograms of $n_{m ax}$ distributions of the M2 at $p = 10$

Рис. 4. Гистограммы распределений $n_{m ax}$ М2 при $p = 30$

Fig. 4. Histograms of $n_{m ax}$ distributions of the M2 at $p = 30$

Были посчитаны среднеожидаемые размеры максимальных компонент по p для разных фиксированных

m

. К примеру, в табл. 2 представлены среднеожидаемые размеры максимальных КСС при

m = 5

.

Таблица 2 / Table 2

Среднеожидаемый размер максимальной компоненты для М2 по

p

при

m = 5

The expected average size of the maximum component for M2 depending on

p

at

m = 5

$p$	1	2	3	4	5	6	7	8	9	10	11	12
${\tilde{n}}_{m = 5} (p)$	1,92	5,64	10,35	14,74	18,47	21,62	24,12	26,16	27,60	28,79	29,72	30,39

Результаты модели М3

Исследовалась зависимость от смещения относительно эталона

k

(и соответственной от степени отклонения индивидуальных мнений от единого эталона

r

). Для

n = 35

,

m \in {5, 6, 7, 8}

и различных

k

проведено по

N = 10 000

испытаний. Гистограммы распределений при

k = 60

,

k = 200

и

k = 580

представлены на рис. 5, 6 и 7 соответственно.

Рис. 6. Гистограммы распределений $n_{m ax}$ М3 при $k = 200 (r = 0,336)$

Fig. 6. Histograms of $n_{m ax}$ distributions of the M3 at $k = 200 (r = 0,336)$

Рис. 7. Гистограммы распределений $n_{m ax}$ М3 при $k = 580 (r = 0,975)$

Fig. 7. Histograms of $n_{m ax}$ distributions of the M3 at $k = 580 (r = 0,975)$

Зависимость среднеожидаемого размера максимальной компоненты

\tilde{n}

от параметра

r

для разных

m

изображена на рис. 8. График демонстрирует немонотонную обратную U-образную зависимость: максимальные значения

\tilde{n}

(минимальная эффективность декомпозиции) наблюдается в области

r \approx 0,4 - 0,7

, тогда как при

r \to 0

(консенсус) и

r \to 1

(поляризация) значение

\tilde{n}

существенно снижается.

Рис. 8. График зависимости $\tilde{n}$ от степени отклонения $r$

Fig. 8. Graph of the dependence of $\tilde{n}$ on the extent of deviation $r$

Обсуждение результатов

Эксперименты показали, что эффективность декомпозиции (значение

n_{\max}

) задачи поиска медианы Кемени слабо зависит от количества экспертов (

m

), но критически обусловлена структурой мажоритарного графа, которая, в свою очередь, определяется характером профиля предпочтений. Наблюдаемая зависимость перекликается с результатами параметризованного анализа задачи (De et al., 2024), где разброс мнений рассматривается как один из ключевых параметров, определяющих вычислительную сложность.

Интерпретация результатов по моделям

Высокие значения

\tilde{n}

(близкие к

n = 35

) на модели M1 (независимые случайные порядки) подтверждают, что: при отсутствии какой-либо согласованности мажоритарный граф с высокой вероятностью является почти сильно связным. Небольшое уменьшение

\tilde{n}

относительно

n

объясняется вероятностным возникновением малых изолированных контуров. Практический вывод: для профилей, подобных случайным, метод декомпозиции не дает значимого снижения вычислительной сложности.

Модель M2 продемонстрировала, что введение структурной схожести мнений (через перестановку

p

пар в едином эталоне) значительно увеличивает эффективность метода. Чем выше эта схожесть (меньше

p

), тем меньше размер максимальной компоненты. Увеличение

p

ведет к приближению профиля к случайному (М1). Важно, что даже при умеренных p (например,

p = 10

) средний размер максимальной компоненты (

29,7

) существенно меньше

n

, что указывает на значительный потенциал метода для реальных задач, где мнения экспертов обычно не являются совершенно независимыми, а группируются вокруг некоторых общих тенденций. При увеличении

p

модель ведет себя похоже на М1 (полностью случайные перестановки), что видно при сравнении рис. 1 (М1) с рис. 4 (М2 при

p = 30

). Однако разброс среднего попарного расстояния (величины обратной согласованности группы) в такой модели велика, поэтому была смоделирована модель М3.

Ключевой результат получен на модели M3. Наблюдаемая обратная U-образная зависимость

\tilde{n}

от степени отклонения от эталона

r

(

\tilde{n}

сначала увеличивается с увеличением

r

, достигает максимума

\tilde{n} = n

, затем уменьшается) находит объяснение при анализе внутренней когерентности группы. Параметр

r

служит удобным инструментом для генерации профилей с разным уровнем ожидаемой когерентности, измеряемой как величина обратная среднему попарному расстоянию Хемминга между экспертами:

При

r \to 0

(консенсус) и

r \to 1

(поляризация) ожидаемая когерентность группы высока, что приводит к ациклической или хорошо структурированной форме мажоритарного графа и, как следствие, к его эффективной декомпозиции.

В зоне

r \approx 0,5

внутренние разногласия в группе максимальны (ожидаемая когерентность минимальна), мажоритарный граф близок к случайному турниру, что делает декомпозицию практически невозможной.

Таким образом, метод декомпозиции наиболее эффективен не просто при малом отклонении от гипотетического центра, а именно в условиях высокой внутренней согласованности группы, будь то консенсус или поляризация.

Практическая значимость и рекомендации

Практическая ценность метода заключается в том, что быстрый анализ КСС мажоритарного графа (

O (n ²)

) позволяет априорно оценить сложность исходной NP-трудной задачи по значению

n_{m ax}

и принять обоснованное решение о выборе алгоритма (точный или эвристический).

Полученные результаты трансформируют метод декомпозиции из теоретического приема в ценный диагностический инструмент. Процедура построения КСС мажоритарного графа имеет сложность

O (n^{2})

и может выполняться до запуска ресурсоемкого алгоритма поиска медианы Кемени.

Малое

n_{m ax}

(

15

) сигнализирует о высокой когерентности группы. Рекомендуется применение точного алгоритма к независимым компонентам, что гарантирует нахождение оптимального решения.

Большое

n_{m ax}

(близкое к

n

) указывает на состояние низкую согласованность группы. Это служит основанием для отказа от точных методов в пользу эвристических алгоритмов, либо для пересмотра самого состава группы или процедуры сбора мнений.

Заключение

Экспериментально подтверждено, что метод декомпозиции задачи нахождения медианы Кемени на основе анализа мажоритарного графа обладает значительным потенциалом для значительного снижения вычислительной сложности.

Установлено, что эффективность декомпозиции напрямую коррелирует с уровнем внутренней согласованности (когерентности) группы экспертов, измеряемой через среднее попарное расстояние. Метод наиболее полезен для сильно согласованных (как при консенсусе с эталоном, так и при поляризации от эталона) и малоэффективен для групп с максимально разнородными мнениями, что объясняет наблюдаемую U-образную зависимость от степени отклонения относительно эталона

r

.

Быстрый анализ компонент сильной связности мажоритарного графа служит не только методом ускорения вычислений, но и ценным диагностическим инструментом. Он позволяет априорно оценить ожидаемую сложность NP-трудной задачи по размеру максимальной компоненты

n_{m ax}

и проанализировать структуру разногласий в группе для обоснованного выбора алгоритма решения (точного или эвристического).

Ограничения. Следует отметить ограничения проведенного исследования. Во-первых, анализ проводился на синтетических данных, сгенерированных в рамках трех параметрических моделей, которые могут упрощать структуру реальных экспертных оценок. Во-вторых, все эксперименты выполнены для фиксированного числа альтернатив (

n = 35

); поведение системы при других

n

требует отдельного изучения. В-третьих, использованная метрика Хемминга (расстояние Кемени) является не единственно возможной, и влияние выбора иной метрики на структуру мажоритарного графа остается открытым вопросом

Важным методологическим ограничением является рассмотрение моделей M1 и M2 только для нечетного числа экспертов

m

. Это было сделано для исключения ситуаций равенства голосов и гарантии, что граф конденсации мажоритарного графа является линейным порядком. Однако на практике число участников может быть четным, что приведет к появлению несравнимых пар (при равенстве голосов) и может повлиять на структуру графа конденсаций (Dougherty, Heckelman, 2023). Модель M3 частично снимает это ограничение, рассматривая как четные, так и нечетные

m

, однако ее результаты для четного случая требуют отдельного углубленного анализа, т.к. помимо нахождения медиан для каждой КСС, в случае четного количества экспертов необходимо достраивать граф конденсаций до линейного порядка, что является трудоемкой задачей.

Limitations. There are some limitations that should be noted about this study. The first one is that the analysis was done on synthesized data generated using three parametric models, which might simplify the structure of real expert assessments. The second one is that all the experiments were done for a fixed number of alternatives (

n = 35

); the behaviour of the system for other

n

values need to be studied separately. Third, the Hamming metric (Kemeny distance) used is not the only possible one, and the effect of choosing a different metric on the structure of the majority graph remains an open question.

An important methodological limitation is that models M1 and M2 are considered only for an odd number of experts

m

. This was done to exclude situations of tie votes and to guarantee that the condensation graph of the majority graph is a linear order. However, in practice, the number of participating experts may be even, which will lead to the appearance of incomparable pairs (in the event of a tie) and may affect the structure of the condensation graph (Dougherty, Heckelman, 2023). Model M3 partially removes this restriction by considering both even and odd

m

, but its results for the even case requires a separate in-depth analysis, since in addition to finding medians for each SCC, in the case of an even number of experts, it is necessary to complete the condensation graph to linear order, which is a time-consuming task.

Оценка эффективности декомпозиции задачи нахождения линейной медианы Кемени на основе анализа мажоритарного графа

Резюме

Общая информация

Полный текст

Введение

Материалы и методы

Постановка задачи нахождения линейной медианы Кемени

Построение мажоритарного графа

Принцип декомпозиции задачи

Модели генерации данных

Модель M1: Базовый случай (нулевая априорная согласованность).

Модель M2: Управляемая согласованность на линейных порядках.

Модель M3: Контролируемая согласованность на турнирах (обобщенный случай).

Метрика исследования

Результаты

Результаты модели М1

Результаты модели М2

Результаты модели М3

Обсуждение результатов

Интерпретация результатов по моделям

Практическая значимость и рекомендации

Заключение

Литература

Информация об авторах

Вклад авторов

Конфликт интересов

Метрики

Просмотров web

Скачиваний PDF

Всего