При голосовании за вашего любимого кандидата на Евровидении или при подсчёте очков гонщиков Формулы 1: задумывались ли вы о том, по какому правилу выбирают победителя? Является ли это правило справедливым? А можно ли перехитрить соперников, манипулируя выборами?

Постановка задачи

Как и в любом моделировании в теории голосования существуют определённые предпосылки.

Пусть существуют:

  • N избирателей;
  • M кандидатов;
  • Предпочтения избирателей на множестве кандидатов, которые являются линейным порядком.

С первыми двумя пунктами всё ясно, но что такое линейный порядок? На самом деле это такие предпочтения, которые удовлетворяют трём требованиям. Говоря о предпочтениях одного (каждого) избирателя:

Связанность (или полнота)

Не существует таких кандидатов, к которым был бы безразличен избиратель.

Пример: вам предлагают на выбор одну из двух книг: Ф. М. Достоевского или И. А. Бунина. Вы отвечаете, что вам безразлично, какую из этих книг брать. Вам дают «Братьев Карамозовых» Достоевского, а потом оказывается, что у Достоевского вы больше любите «Подростка». Получается, что ваши предпочтения неполные: вы можете сказать, что «Подросток» лучше «Братьев Карамазовых», а про И. А. Бунина вы не говорите ничего. На каком месте стоит Бунин в ваших предпочтениях – неизвестно. Такого быть не должно.

 "The\, Raw\, Youth"\,\succ\,"The\, Brothers\, Karamazov"?"Dark\, Avenues"

Транзитивность

Если кандидат A лучше, чем Б. Кандидат Б лучше, чем С. Отсюда следует, что кандидат А лучше, чем С.

Пример: Если «Подросток» лучше «Братьев Карамазовых», а «Братья Карамазовы» лучше, чем «Тёмные аллеи», то отсюда следует, что «Подросток» лучше «Тёмных аллей».

 "The\, Raw\, Youth"\,\succ\,"The\, Brothers\, Karamazov"\\"The\, Brothers\, Karamazov"\,\succ\,"Dark\, Avenues" \\\Longrightarrow"The\, Raw\, Youth"\,\succ\,"Dark\, Avenues"

Ацикличность

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

 A\succ B \succ C\succ A

Немного из истории

Одним из основателей математической теории голосования был Жан-Шарль де Борда, который предложил присваивать кандидатам очки в соответствие с вектором  (m-1, m-2, \ldots , 0) , где    m – это количество кандидатов. То есть кандидат, находящийся на первом месте в предпочтениях голосующего, получает  m-1 очко, на втором –  m-2 и так далее до нуля. Это правило голосования более известно под названием Borda count.

Представьте себе голосование, в котором участвуют четыре кандидата  (M=4) и 100  (N=100) голосующих.

Номер51 избиратель5 избирателей23 избирателя21 избиратель
ПервыйАндрей Екатерина Иван Давид
ВторойЕкатерина Иван Екатерина Екатерина
ТретийИван Давид Давид Иван
ЧетвёртыйДавид Андрей Андрей Андрей

Источник: Википедия

Эту таблицу необходимо читать следующим образом:

51 избиратель имеет предпочтения:  A \succ E \succ I \succ D

5 избирателей:  E \succ I \succ D \succ A

23 избирателя:  I \succ E \succ D \succ A

21 избиратель:  D \succ E \succ I \succ A

Итоговые очки:

Екатерина:   51*2+5*3+23*2+21*2 = 205

Иван:  51*1+5*2+23*3+21*1 = 151

Андрей:  51*3+5*0+23*0+21*0=153

Давид:  51*0+5*1+23*1+21*3=49

Таким образом победителем оказывается Екатерина с наибольшим количеством очков   = 205  .

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

Все правила голосования, в которых кандидатам присваиваются очки, а затем подсчитывается их итоговая сумма, называются scoring rules. Наиболее известными из них являются:

  • Правило большинства (Plurality)
  • Правило Борда (Borda)
  • Вето (Antiplurality (veto)).
  • Одобрительное голосование (k-approval)

Кондорсе доказывает, что ни одно scoring rule не удовлетворяет критерию победителя по Кондорсе. Однако существуют и такие правила, которые удовлетворяют этому критерию. Перед нами встаёт вопрос: всегда ли критерий Кондорсе даёт наилучший исход? Есть ли у него недостатки? Существуют и другие критерии для правил голосования. Более подробно о критериях и правилах голосования смотрите в учебнике F. Brandt,V. Conitzer, U. Endriss, J. Lang, A. Procaccia, H. Moulin. (2016) Handbook of Computational Social Choice. Cambridge (пароль: cam1CSC).

Манипулируемость

С разницей в два года была доказана одна из основных теорем в теории голосования. В 1973 году математик Аллан Гиббард, а затем в 1975 году экономист Марк Саттертуэйт доказывают, что всякое голосование, в котором участвуют три или более кандидатов является манипулируемым. Что это значит?

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

Рассмотрим пример:

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

3 избирателя:  A \succ C \succ B \succ D

2 избирателя:  C \succ B \succ D \succ A

2 избирателя:  B \succ C \succ D \succ A

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

3 избирателя:  A \succ C \succ B \succ D

2 избирателя:  C \succ B \succ D \succ A

2 избирателя:  \neg (B \succ C \succ D \succ A)

2 избирателя:  C \succ B \succ D \succ A

Тогда в выборах выиграет Екатерина с четырьмя очками, Андрей останется с тремя, и Иван не получит ничего.

Открытые вопросы

Но представьте, что перед вами 7 кандидатов и 14 миллионов избирателей, легко ли вам будет манипулировать выборами? В настоящий момент вопрос о сложности манипулирования голосованием остаётся открытым.

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

Автор: Валерия Кука

Редактор: Татьяна Яковлева

Оформление: Валерия Кука, обложка — Виталия Елисеева

Гифки: https://giphy.com/

За идею с гифками спасибо Марии Гребенщиковой

Меню
Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить
%d такие блоггеры, как: