Жёсткие границы искажения рандомизированного и детерминированного распределённого голосования

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

• ID статьи: 2509.17134
• Название: Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting
• Авторы: MohammadAli Abam, Davoud Kareshki, Marzieh Nilipour, MohammadHossein Paydar, Masoud Seddighin
• Учреждения: Технологический университет Шариф (Тегеран, Иран); Тегеранский институт передовых исследований (TeIAS), Университет Хатам
• Классификация: cs.GT (Теория игр)
• Дата публикации: 23 ноября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2509.17134v2

Аннотация

В данной работе исследуется проблема метрического искажения (metric distortion) в распределённом голосовании, где n избирателей разделены на k групп, каждая из которых выбирает локального представителя, а затем из этих представителей (или всех кандидатов) выбирается победитель. Эта постановка моделирует системы, подобные американским президентским выборам. Статья предлагает улучшенные границы искажения для четырёх целевых функций стоимости (avg-avg, avg-max, max-avg, max-max). Для детерминированных механизмов верхняя граница для avg-max снижена с 11 до 7, установлена жёсткая нижняя граница 5 для max-avg (улучшение 2+√5), верхняя граница для max-max уточнена с 5 до 3. Для рандомизированных механизмов установлены жёсткие или почти жёсткие границы в обоих сценариях.

Исследовательский контекст и мотивация

Определение проблемы

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

1. Внутригрупповой этап: каждая группа независимо выбирает локального представителя
2. Межгрупповой этап: из представителей выбирается окончательный победитель

Важность проблемы

1. Широкое практическое применение: система выборщиков США, федеральные решения, многоуровневое голосование в организациях используют распределённую структуру
2. Асимметрия информации: правила голосования имеют доступ только к порядковым предпочтениям (ранжированиям), а не к истинным кардинальным полезностям
3. Теоретические вызовы: необходимо оценить гарантии производительности механизмов при ограниченной информации

Ограничения существующих подходов

• Anshelevich et al. (2022) впервые систематически исследовали искажение в детерминированном распределённом голосовании, но с существенными пробелами:
  • avg-max: 2+√5, 11
  • max-avg: 2+√5, 5
  • max-max: 3, 5
• Рандомизированные механизмы не исследованы: хотя рандомизация в централизованном голосовании может преодолеть нижнюю границу искажения 3, рандомизированные механизмы в распределённых сценариях полностью не изучены
• Специальные метрические пространства: линейные метрики решены Voudouris (2023), но общие метрические пространства остаются открытой проблемой

Исследовательская мотивация

1. Исследовать, может ли рандомизация привести к улучшению искажения в распределённых условиях
2. Уточнить известные границы для детерминированных механизмов
3. Обеспечить почти полную характеризацию искажения в распределённом голосовании

Основные вклады

1. Первое систематическое исследование рандомизированных распределённых механизмов:
   • Механизм rand-det (рандомизация только на втором этапе): установлены жёсткие границы для всех четырёх целей
   • Механизм rand-rand (рандомизация на обоих этапах): установлены жёсткие или почти жёсткие границы
2. Улучшение границ для детерминированных механизмов:
   • avg-max: верхняя граница снижена с 11 до 7
   • max-avg: нижняя граница повышена с 2+√5 до жёсткой 5
   • max-max: верхняя граница уточнена с 5 до 3
3. Введение нового инструмента анализа — турнира смещений (Bias Tournament):
   • Захватывает предпочтения разрешения ничьих для детерминированных правил
   • Используется для построения нижних границ через конструирование примеров высокого искажения
4. Специализированные границы для евклидова пространства:
   • rand-rand: нижняя граница √5-ε
   • rand-det: нижняя граница 2+√5-ε
5. Побочные результаты для централизованного голосования:
   • Доказано, что рандомизированные правила голосования имеют искажение не менее 3-ε для целей max (почти совпадает с известной верхней границей 3)

Детальное описание методов

Определение задачи

Входные данные:

• Множество избирателей V (|V|=n), разделённое на k групп G
• Множество кандидатов C (|C|=m)
• Метрическое пространство d: V×C→ℝ⁺, удовлетворяющее неравенству треугольника
• Предпочтения π: каждый избиратель ранжирует кандидатов в порядке возрастания расстояния

Выходные данные:

• Распределённый механизм Ψ=(f_in, f_ov) выбирает победителя w

Цель: Минимизировать искажение D(Ψ) = sup_I Ecost(w|I) / min_c cost(c|I)

Четыре целевые функции стоимости:

1. avg-avg: среднее внутри групп, затем среднее между группами
2. avg-max: максимум внутри групп, затем среднее между группами
3. max-avg: среднее внутри групп, затем максимум между группами
4. max-max: максимум внутри групп, затем максимум между группами

Основная техническая схема

1. Турнир смещений (Bias Tournament)

Определение: для детерминированного правила f и упорядочения кандидатов σ, построим полный ориентированный граф T(f,C,σ):

• Вершины: каждый кандидат
• Рёбра: для пары кандидатов (u,w), если в выборах с двумя избирателями, имеющими предпочтения σ↑w↑u и σ↑u↑w, правило f выбирает u, то добавляем ребро u→w

Ключевое свойство (Observation 2.2): Любой турнир на m вершинах имеет вершину с входящей степенью ≥⌈(m-1)/2⌉

Применение:

• Идентификация "неудачных кандидатов" (высокая входящая степень)
• Построение примеров, где такой кандидат оптимален, но не может быть выбран
• Используется для доказательства нижних границ для rand-det и det-det

2. Анализ механизма rand-det

Дизайн механизма: (f_pm-par, f_ur)

• Первый этап: Plurality Matching with Pareto Efficiency
• Второй этап: равномерный случайный выбор

Ключевая теорема:

Теорема 3.1 (max-avg): D((f_α, f_ur)) ≤ α+2

• Идея доказательства: используя эффективность по Парето, существует избиратель v_g, предпочитающий w_g победителю o
• Через цепочку неравенств треугольника:

  E[cost(w)] ≤ cost(o) + (1/k)Σ_g d(o,w_g)
               ≤ cost(o) + (1/k)Σ_g [d(o,v_g) + d(v_g,w_g)]
               ≤ cost(o) + 2(1/k)Σ_g d(v_g,o)  [так как d(v_g,w_g)≤d(v_g,o)]
               ≤ (α+2)cost(o)
  

Теорема 3.3 (avg-avg): D((f_α, f_ur)) ≤ α+2-2/k

• Ключевой момент: разделение членов внутри групп и между группами, члены внутри групп дают улучшение -2/k

Теорема 3.5 (avg-max, max-max): D((f_par, f_ur)) ≤ 3

• Достаточна только эффективность по Парето для достижения 3 (не требуется сильное предположение α=3)

Построение нижних границ:

Теорема 3.7 (max-avg, нижняя граница 5):

• Используем турнир смещений для нахождения кандидата c₁ с входящей степенью ≥2
• Построим пример с линейной метрикой: 4 кандидата, 4 избирателя, 2 группы
• Гарантируем, что c₂ и c₃ становятся представителями, cost(c₁)=1/4, cost(c₂)=cost(c₃)=5/4

Теорема 3.8 (avg-avg, нижняя граница 5-2/k):

• Используем метрику кратчайшего пути на графе (не линейная)
• k групп с одним избирателем, 2k кандидатов
• Древовидная структура: центральный кандидат c_2k оптимален, но каждая группа выбирает представителя c_i (1≤i≤k)

3. Анализ механизма rand-rand

Дизайн механизма: (f_rd, f_ur)

• Первый этап: Random Dictatorship (равномерно случайно выбираем избирателя и его первый выбор)
• Второй этап: равномерный случайный выбор

Ключевое наблюдение (Observation 2.6):

E[cost(w)] = (1/k)Σ_g (1/n_g)Σ_{v∈g} cost(top(v))

Стратегия доказательства верхних границ:

Теорема 4.1 (max-max, верхняя граница 3): Для любого избирателя v:

cost(top(v)) = d(v**(top(v)), top(v))
             ≤ d(v**(top(v)), o) + d(o,v) + d(v,top(v))  [неравенство треугольника]
             ≤ d(v**(o), o) + d(v,o) + d(v,o)  [top(v) — ближайший кандидат к v]
             ≤ 3d(v**(o), o) = 3cost(o)

Теорема 4.4 (avg-avg, верхняя граница 3-2/(kn*)):

• Самое сложное доказательство, требует тонкой обработки двойной суммы
• Ключевой момент: разделение членов, где v'=v, даёт улучшение -2/(kn*)
• Когда все группы имеют равный размер, граница становится 3-2/n

Построение нижних границ:

Теорема 4.6 (max-avg, max-max, нижняя граница 3):

• 2 избирателя, 3 кандидата, 2 группы с одним избирателем
• Линейная метрика: c₁(-1), c₂(0), c₃(1); v₁(-0.5), v₂(0.5)
• Необходимо выбрать c₁ или c₃, cost=3/2, тогда как cost(c₂)=1/2

Теорема 4.7 (avg-max, нижняя граница 3-2/n):

• m кандидатов, m избирателей, одна группа
• Построим m примеров I_i, где c_i оптимален в I_i
• Циклические предпочтения: π_i = (c_i, c_{i+1}, ..., c_m, c_1, ..., c_)
• Вероятностный аргумент: существует i такой, что p_i≤1/m

Следствие 4.8: это построение также доказывает нижнюю границу 3-ε для централизованного рандомизированного голосования при целях max

Теорема 4.9 (avg-avg, нижняя граница 3-2/n):

• k групп с одним избирателем, k+1 кандидат
• Древовидная структура: центральный кандидат c_m оптимален, но не является представителем ни одной группы

4. Улучшение механизма det-det

Теорема 5.1 (max-max, верхняя граница 3):

• Механизм Arbitrary Dictator достигает 3
• Улучшение результата Anshelevich et al. с 5

Теорема 5.2 (avg-max, верхняя граница 2β+3):

• Механизм (f_par, f_β)
• Ключевой момент: использование эффективности по Парето, независимость от α
• При β=2 (f_pm-par) получаем верхнюю границу 7

Теорема 5.4 (max-avg, нижняя граница 5):

• Используем турнир смещений и метрику графа (не линейная)
• 4 кандидата, 4 избирателя, 2 группы
• Построим два примера I₁ и I₂, гарантирующих, что в одном из них оптимальный кандидат исключён

Технические инновации

1. Введение турнира смещений:
   • Формализует поведение разрешения ничьих для детерминированных правил как графовую структуру
   • Использует комбинаторные свойства турниров (существование вершины с высокой входящей степенью)
   • Позволяет систематически строить примеры нижних границ
2. Ослабленное использование эффективности по Парето:
   • Доказано, что для avg-max достаточна только эффективность по Парето для достижения 3 (не требуется α=3)
   • Разделяет зависимость искажения между двумя этапами
3. Тонкий анализ двойных сумм:
   • Цель avg-avg требует обработки вложенных средних
   • Разделение диагональных членов (v'=v, g'=g) даёт улучшение
4. Использование нелинейных метрических пространств:
   • Многие нижние границы требуют метрики кратчайшего пути на графе (не вложима в линейное или евклидово пространство)
   • Демонстрирует существенную сложность проблемы
5. Построение в евклидовом суперсимплексе:
   • Конструирование симметричных примеров в R^{l+1}
   • Использование высокомерной геометрии для получения нижней границы √5

Экспериментальная установка

Примечание: данная работа является чисто теоретической и не содержит экспериментальной части. Все результаты установлены математическими доказательствами.

Методы теоретической верификации

1. Конструктивные доказательства:
   • Нижние границы: построение конкретных примеров и вычисление искажения
   • Верхние границы: анализ производительности механизма на произвольных примерах
2. Типы метрических пространств:
   • Общие метрические пространства (удовлетворяющие неравенству треугольника)
   • Линейные метрики (одномерные)
   • Евклидовы пространства (многомерные)
   • Метрики кратчайшего пути на графах
3. Характеристики примеров:
   • Симметричные примеры (все группы одинакового размера)
   • Группы с одним избирателем
   • Малые примеры (2-4 группы, 2-4 кандидата)

Результаты экспериментов

Сводка основных результатов

Таблица 2: Полный обзор результатов

Жирный шрифт обозначает новые результаты, ↑/↓ указывает направление улучшения

Ключевые находки

1. Ценность рандомизации:
   • rand-det достигает или приближается к оптимальности для всех целей
   • rand-rand дополнительно улучшает avg-avg (с 5-2/k до 3-2/n)
   • Но max-avg и max-max не могут преодолеть границу 3
2. Пределы детерминированных механизмов:
   • Жёсткая граница для max-avg равна 5 (выше централизованной 3)
   • max-max может достичь 3 (как в централизованном случае)
   • avg-max всё ещё имеет пробел (7 vs 2+√5)
3. Распределённое vs централизованное голосование:
   • Централизованное рандомизированное голосование: искажение при целях max ≥3-ε (Следствие 4.8)
   • Распределённость добавляет сложность, некоторые цели имеют более высокое искажение
4. Влияние метрического пространства:
   • Линейные метрики: многие нижние границы достижимы на прямой
   • Общие метрики: некоторые нижние границы требуют метрик графов (например, 5 для max-avg)
   • Евклидовы пространства: нижние границы немного ниже (√5 vs 3-2/n)

Технические инсайты

1. Взаимодействие двух этапов:
   • avg-max: второй этап доминирует (2β+3 независимо от α)
   • max-avg: оба этапа важны (α+2)
   • avg-avg: тонкий эффект двойного усреднения (α+2-2/k)
2. Роль эффективности по Парето:
   • Достаточна для достижения 3 в некоторых целях (без полного Plurality Matching)
   • Обеспечивает ключевое ограничение на отношение избиратель-представитель
3. Вызовы вероятностного анализа:
   • Верхняя граница rand-rand для avg-avg требует обработки четырёхкратной суммы
   • Точная обработка диагональных членов критична

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

Искажение в централизованном голосовании

1. Детерминированные механизмы:
   • Anshelevich et al. (2018): нижняя граница 3
   • Gkatzelis et al. (2020): Plurality Matching достигает верхнюю границу 3 (жёсткая)
   • Kizilkaya & Kempe (2022): Plurality Veto упрощённо достигает 3
2. Рандомизированные механизмы:
   • Anshelevich & Postl (2017): Random Dictatorship достигает 3-2/n
   • Charikar & Ramakrishnan (2022): нижняя граница 2.112
   • Charikar et al. (2024): верхняя граница 2.753 (текущий лучший результат)

Распределённое голосование

1. Рамки полезности:
   • Filos-Ratsikas et al. (2020): первое исследование распределённого искажения
   • Filos-Ratsikas & Voudouris (2024): рандомизированные механизмы, искажение Θ(km²)
2. Метрические рамки:
   • Anshelevich et al. (2022): первое систематическое исследование детерминированных механизмов
   • Voudouris (2023): жёсткие границы для линейных метрик
   • Данная работа: рандомизированные механизмы для общих метрик

Другие проблемы социального выбора

1. Размещение объектов: применение рамки метрического искажения
2. Задачи сопоставления: приближение при порядковых предпочтениях
3. Выборы комитета: многопобедительные сценарии

Преимущества данной работы

1. Первое полное исследование рандомизированных распределённых механизмов
2. Почти все границы жёсткие (9/12 жёсткие, 3/12 почти жёсткие)
3. Введение нового инструмента (турнир смещений)
4. Охват множества метрических пространств (общие, линейные, евклидовы)

Заключение и обсуждение

Основные выводы

1. Почти полная характеризация:
   • 9 из 12 границ жёсткие, 3 почти жёсткие
   • Только det-det для avg-avg имеет значительный пробел (7 vs 11)
2. Эффективность рандомизации:
   • rand-det достигает жёсткие границы для всех целей
   • rand-rand дополнительно улучшает avg-avg
   • Простые механизмы (Random Dictatorship + равномерный выбор) достигают оптимальности
3. Улучшение детерминированных механизмов:
   • Решены жёсткие границы для max-avg и max-max
   • avg-max улучшена с 11 до 7
4. Вклад методологии:
   • Турнир смещений обеспечивает систематическую рамку для построения нижних границ
   • Ослабленное использование эффективности по Парето

Ограничения

1. Оставшиеся пробелы:
   • det-det для avg-avg: 7, 11
   • rand-rand для avg-avg: 3-2/n, 3-2/(kn*) (жёсткая только в симметричном случае)
   • rand-rand для avg-max: 3-2/n, 3
2. Механизм det-rand не исследован:
   • Первый этап детерминированный, второй рандомизированный
   • Турнир смещений неприменим к рандомизированному первому этапу
   • Текущие границы грубые, унаследованные от rand-rand и det-det
3. Ограничения метрических пространств:
   • Некоторые нижние границы требуют общих метрик (метрики графов)
   • Границы для евклидовых пространств могут быть ниже
4. Практические соображения:
   • Не рассматривается стратегическое поведение (не стимулоустойчиво)
   • Не рассматривается сложность коммуникации
   • Не рассматривается вычислительная сложность

Направления будущих исследований

1. Механизм det-rand:
   • Разработка новых инструментов анализа
   • Возможно, требуются методы, отличные от турнира смещений
2. Сужение оставшихся пробелов:
   • det-det для avg-avg
   • rand-rand для avg-avg (несимметричный случай)
3. Специальные метрические пространства:
   • Линейные метрики: некоторые цели остаются нерешёнными
   • Евклидовы пространства: возможны более низкие границы
   • Древовидные метрики: промежуточная сложность
4. Расширение постановки:
   • Выборы комитета (многопобедительные)
   • Кардинальная информация (доступ к истинным расстояниям)
   • Стратегическое голосование (стимулоустойчивые механизмы)
5. Вычисления и коммуникация:
   • Эффективные алгоритмические реализации
   • Нижние границы сложности коммуникации
   • Онлайн/потоковые сценарии

Глубокая оценка

Достоинства

1. Теоретическая глубина:
   • 9 из 12 границ жёсткие, демонстрирует глубокое понимание проблемы
   • Методы доказательства разнообразны и изощрены (турнир смещений, анализ двойных сумм, вероятностные аргументы)
2. Систематичность:
   • Охватывает 3 типа механизмов × 4 цели = 12 проблем
   • Единая рамка и нотация
   • Ясное сравнение результатов (Таблица 2)
3. Методологические инновации:
   • Турнир смещений: элегантно захватывает структуру детерминированных правил
   • Ослабленное использование эффективности по Парето: разделяет зависимость между этапами
   • Потенциально имеет независимую ценность
4. Качество изложения:
   • Ясная структура, постепенное усложнение (от простого к сложному)
   • Достаточные интуитивные объяснения и иллюстрации
   • Полные детали доказательств
5. Полнота:
   • Множество метрических пространств (общие, линейные, евклидовы)
   • Симметричные и несимметричные примеры
   • Побочные результаты для централизованного голосования

Недостатки

1. Пробел det-rand:
   • Статья признаёт это основной открытой проблемой
   • Текущие инструменты неприменимы, требуются новые методы
2. Некоторые пробелы не сужены:
   • det-det для avg-avg: 7, 11 остаётся значительным
   • Хотя авторы уже значительно улучшили, полное решение не достигнуто
3. Ограниченная практичность:
   • Чисто теоретические результаты, без экспериментальной верификации
   • Не рассматриваются ограничения реальных систем голосования (стратегичность, вычисления)
   • Анализ наихудшего случая может быть чрезмерно пессимистичным
4. Зависимость от метрического пространства:
   • Некоторые нижние границы требуют сложных метрик графов
   • Реальные метрические пространства могут быть более структурированными
5. Сложность механизмов:
   • Plurality Matching вычислительно сложен (задача сопоставления)
   • Реальные системы могут предпочитать более простые правила

Влияние

1. Теоретический вклад:
   • Почти полное решение проблемы искажения в распределённом голосовании
   • Установление эталонных результатов в этой области
   • Турнир смещений может вдохновить исследования других проблем
2. Последующие исследования:
   • Исследование механизма det-rand
   • Распределённые версии других проблем социального выбора
   • Расширения с учётом стратегичности и вычислений
3. Практическая ценность:
   • Теоретическое руководство для проектирования распределённых систем голосования
   • Количественные гарантии производительности различных механизмов
   • Но расстояние до практического развёртывания всё ещё значительно
4. Воспроизводимость:
   • Чисто теоретическая работа, доказательства проверяемы
   • Построения примеров явны, легко проверяются
   • Без кода или экспериментов, но это не влияет на воспроизводимость

Применимые сценарии

1. Теоретические исследования:
   • Теория социального выбора
   • Алгоритмическая теория игр
   • Приближённые алгоритмы
2. Проектирование систем:
   • Федеральные системы голосования
   • Многоуровневые организационные решения
   • Протоколы распределённого консенсуса
3. Обучение:
   • Примеры теории искажения
   • Применение рандомизированных алгоритмов
   • Методы комбинаторной оптимизации
4. Неприменимые сценарии:
   • Реальные выборы, требующие стимулоустойчивости
   • Системы с ограничениями вычислений в реальном времени
   • Пространства предпочтений, не являющиеся метрическими

Ключевые ссылки

1. Anshelevich et al. (2022): "The distortion of distributed metric social choice" - прямой предшественник данной работы
2. Gkatzelis et al. (2020): "Resolving the optimal metric distortion conjecture" - жёсткая граница 3 для централизованного голосования
3. Filos-Ratsikas et al. (2020): "The distortion of distributed voting" - пионерская работа по распределённому голосованию
4. Charikar et al. (2024): "Breaking the metric voting distortion barrier" - последние достижения в рандомизированном централизованном голосовании
5. Voudouris (2023): "Tight distortion bounds for distributed metric voting on a line" - полное решение для линейных метрик

Общая оценка: Это высококачественная теоретическая работа, которая почти полностью решает проблему искажения в распределённом голосовании, вводит новый инструмент анализа (турнир смещений) и устанавливает 9 жёстких и 3 почти жёстких границы. Хотя механизм det-rand остаётся нерешённым и некоторые пробелы сохраняются, систематичность, техническая глубина и методологические инновации делают эту работу важным вкладом в область. Для теоретических исследователей это обязательное чтение; для практиков она обеспечивает ценные ориентиры гарантий производительности.