Агрегирование предпочтений: правила Борда, Кондорсе, Кемени

Зачем агрегировать предпочтения

Есть n альтернатив — варианты, объекты, значения — и m «мнений» о них: эксперты, критерии, измерительные приборы. Каждое мнение упорядочивает альтернативы от лучшей к худшей. Нужно получить одно общее упорядочение — ранжирование консенсуса, которое наилучшим образом согласовано со всеми мнениями сразу.

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

Пример: оценивание микроклимата

Производственная площадка разбита на пять зон a₁, …, a₅. Зоны ранжированы по четырём разнородным свойствам — влажности, температуре, скорости воздуха и присутствию опасного оборудования. Влажность нельзя сложить с температурой, но по каждому свойству зоны можно упорядочить. Правило Борда даёт итоговое ранжирование зон a₃ ≻ a₄ ≻ a₅ ≻ a₂ ≻ a₁. У правила Кемени здесь два равноценных решения — это же ранжирование и a₄ ≻ a₃ ≻ a₅ ≻ a₂ ≻ a₁: пример множественности решений, о которой сказано ниже. Пример загружен в демонстрацию.

Ранжирования и профиль

Ранжирование λ_k — упорядочение альтернатив, в котором допускаются равенства: a_i ≻ a_j — «a_i предпочтительнее», a_i ~ a_j — «равноценны» (толерантность). Такое отношение называют слабым порядком. Набор m ранжирований — профиль предпочтений Λ(m, n).

Профиль удобно свернуть в турнирную матрицу S = [s_ij]. За каждое ранжирование, в котором a_i предпочтительнее a_j, к s_ij прибавляется 2, за равноценность — 1; так все элементы матрицы целые:

s_ij = Σ_k=1^m C_ij^k, C_ij^k = 2, если a_i ≻_k a_j; 1, если a_i ~_k a_j; 0, если a_j ≻_k a_i;
s_ii = 0; s_ij + s_ji = 2m при i ≠ j.

Правила агрегирования

Способ получить ранжирование консенсуса задаётся правилом агрегирования. Правил много, и они опираются на разные представления о том, что такое «согласие».

Простое большинство

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

Правило Борда

Каждая альтернатива получает выигрыш z_i = Σ_{j ≠ i} s_ij — сумму строки турнирной матрицы; ранжирование — по убыванию выигрышей. Полиномиальная сложность.

Jean-Charles de Borda (1733–1799)

Правило Кондорсе

Победитель — альтернатива, которая выигрывает у каждой другой в парном сравнении: s_ij > s_ji, то есть s_ij > m, для всех j ≠ i. Самое аксиоматически обоснованное правило, но победителя может не быть — парадокс Кондорсе: a₁ ≻ a₂, a₂ ≻ a₃, a₃ ≻ a₁.

Marquis de Condorcet (1743–1794)

Правило Кемени

Ранжирование консенсуса — строгий порядок β, ближайший ко всему профилю по расстоянию Кемени: β = arg min_ρ D(ρ, Λ), минимум — по всем строгим порядкам ρ. Если победитель Кондорсе есть, в β он стоит первым; но, в отличие от правила Кондорсе, ответ есть всегда — парадокса не возникает.

John G. Kemeny (1926–1992)

Расстояние Кемени между ранжированиями считает несогласованные пары. Для ранжирования λ обозначим σ_ij(λ) = 1, если a_i ≻ a_j; 0, если a_i ~ a_j; −1, если a_j ≻ a_i. Тогда

d(λ, μ) = Σ_i<j |σ_ij(λ) − σ_ij(μ)|, D(ρ, Λ) = Σ_k=1^m d(ρ, λ_k).

Пара в противоположном порядке добавляет к расстоянию 2, равноценность против строгого предпочтения — 1.

У правила Кемени две трудности:

NP-трудность. Число строгих порядков растёт как n!. В коллективе разработан рекурсивный алгоритм ветвей и границ RECURSALL, который находит все точные решения при n < 20.
Множественность решений. Точных решений может быть несколько, с одинаковым расстоянием до профиля. Правило свёртки объединяет их в одно итоговое ранжирование по выигрышам выходного профиля — набора всех точных решений. Итог может содержать толерантности и сохраняет порядок тех пар, в которых все решения согласны.

Демонстрация: проголосуйте сами

Введите ранжирования — по одному на строке, от лучшего к худшему: a₁ > a₂ ~ a₃ > a₄ (> — предпочтительнее, ~ — равноценны). Метка перед двоеточием необязательна. Браузер применит все четыре правила.

От ранжирований к интервалам

Метод IF&PA переносит агрегирование предпочтений на результаты измерений. Диапазон актуальных значений (ДАЗ) — от наименьшей нижней до наибольшей верхней границы интервалов — разбивается на n дискретных значений; это альтернативы. Каждый результат измерения x_k ± u_k — интервал — становится «мнением»: значения внутри интервала предпочтительнее значений снаружи, внутри каждой группы значения равноценны.

Такое ранжирование, наведённое интервалом, называют инранжированием. У инранжирований особая структура: предпочтительные значения всегда идут подряд. Поэтому инранжирований при n значениях ровно n(n + 1)/2 — столько, сколько отрезков из подряд идущих значений.

Профиль инранжирований агрегируется. Победители — значения, которые «предпочитает» наибольшее число результатов измерений, то есть накрытые наибольшим числом интервалов; их медиана — преференциальная медиана. Для профилей инранжирований правила Кемени и Борда дают одну и ту же преференциальную медиану, поэтому NP-трудная задача сводится к полиномиальной.

Алгоритм IF&PA по шагам Посчитать на своих данных

Глоссарий

Все обозначения метода IF&PA собраны в таблице на странице «Метод».

Альтернатива	объект сравнения: вариант, зона, дискретное значение величины
Ранжирование	упорядочение альтернатив от лучшей к худшей с возможными равенствами (слабый порядок)
Толерантность (~)	равноценность двух альтернатив в ранжировании
Профиль предпочтений `Λ`(`m`, `n`)	набор из `m` ранжирований `n` альтернатив
Турнирная матрица	матрица парных выигрышей `s_ij` по всему профилю
Ранжирование консенсуса `β`	итоговое ранжирование, наилучшим образом согласованное с профилем по выбранному правилу
Диапазон актуальных значений (ДАЗ)	отрезок от наименьшей нижней до наибольшей верхней границы интервалов, разбитый на дискретные значения
Норма разбиения `h`	шаг между соседними дискретными значениями ДАЗ
Инранжирование	ранжирование значений ДАЗ, наведённое интервалом: внутри ≻ снаружи
Сводный индикатор `c_i`	число интервалов, содержащих значение `a_i`
Преференциальная медиана (ПМ)	результат комплексирования интервалов: медиана победителей в ранжировании консенсуса профиля инранжирований

Литература

Muravyov S.V. Ordinal measurement, preference aggregation and interlaboratory comparisons // Measurement. 2013. Vol. 46, No. 8. P. 2927–2935.
Muravyov S.V. Dealing with chaotic results of Kemeny ranking determination // Measurement. 2014. Vol. 51. P. 328–334.
Muravyov S.V., Khudonogova L.I., Emelyanova E.Yu. Interval data fusion with preference aggregation // Measurement. 2018. Vol. 116. P. 621–630. DOI: 10.1016/j.measurement.2017.08.045
Muravyov S.V., Emelyanova E.Yu. Kemeny rule for preference aggregation: reducing all exact solutions to a single one // Measurement. 2021. Vol. 182. Art. 109403.
Muravyov S.V. et al. Kemeny and Borda rules in constructing central tendency estimators based on the preferential median // Proc. AISP'25. 2025. DOI: 10.1109/AISP68263.2025.11396113.