МЕТОД ПОПАРНОГО СХОДСТВА ДЛЯ ЗАДАЧИ ПОИСКА ЧИСЛА ДОМИНИРОВАНИЯ1

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