Теорема Гиббарда – Саттертуэйта

Теорема Гиббарда -Саттертуэйта — теорема теории голосования . Впервые это предположение было высказано философом Майклом Дамметом и математиком Робином Фаркухарсоном в 1961 году. а затем независимо доказано философом Алланом Гиббардом в 1973 году. и экономист Марк Саттертуэйт в 1975 году. Он имеет дело с детерминистическими порядковыми избирательными системами , которые выбирают одного победителя, и показывает, что для каждого правила голосования этой формы должно выполняться хотя бы одно из следующих трех условий:

1. Правило является диктаторским, т.е. существует выдающийся избиратель, который может выбрать победителя; или
2. Правило ограничивает возможные результаты только двумя альтернативами; или
3. Это правило непростое, т.е. не существует единой, всегда наилучшей стратегии (той, которая не зависит от предпочтений или поведения других избирателей).

Доказательство теоремы Гиббарда является более общим и охватывает процессы коллективного решения, которые могут не быть порядковыми, например кардинальное голосование . Теорема Гиббарда 1978 года и теорема Хайланда носят еще более общий характер и распространяют эти результаты на недетерминированные процессы, результат которых может частично зависеть от случайности; теорема Даггана-Шварца распространяет эти результаты на избирательные системы с несколькими победителями.

Неофициальное описание

Рассмотрим трех избирателей по имени Алиса, Боб и Кэрол, которые хотят выбрать победителя среди четырех кандидатов с именами $a$, $b$, $c$ и $d$. Предположим, что они используют подсчет Борда : каждый избиратель сообщает о своих предпочтениях по сравнению с кандидатами. По каждому голосованию первому кандидату присваивается 3 очка, второму кандидату – 2 балла, третьему – 1 балл и последнему – 0 баллов. После подсчета всех бюллетеней победителем объявляется кандидат, набравший наибольшее количество баллов.

Предположим, что их предпочтения таковы.

избиратель	Выбор 1	Вариант 2	Вариант 3	Выбор 4
Алиса	$a$	$b$	$c$	$d$
Боб	$c$	$b$	$d$	$a$
Кэрол	$c$	$b$	$d$	$a$

Если избиратели проголосовали искренне, то баллы следующие: $(a:3,b:6,c:7,d:2)$. Следовательно, кандидат $c$ будет избран с 7 очками.

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

избиратель	Выбор 1	Вариант 2	Вариант 3	Выбор 4
Алиса	$b$	$a$	$d$	$c$
Боб	$c$	$b$	$d$	$a$
Кэрол	$c$	$b$	$d$	$a$

У Алисы есть стратегически улучшенный кандидат $b$ и пониженный рейтинг кандидата $c$. Теперь оценки такие: $(a:2,b:7,c:6,d:3)$. Следовательно, $b$ избирается. Алиса удовлетворена изменением своего бюллетеня, потому что она предпочитает результат $b$ к $c$, и именно такой результат она получила бы, если бы проголосовала искренне.

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

Теорема Гиббарда-Саттертуэйта утверждает, что каждым ранжированным голосованием можно манипулировать, за исключением, возможно, двух случаев: если есть выдающийся избиратель, обладающий диктаторской властью, или если правило ограничивает возможные результаты только двумя вариантами.

Официальное заявление

Позволять ${\mathcal {A}}$ быть набором альтернатив (который предполагается конечным), также называемым кандидатами , даже если они не обязательно являются людьми: они также могут быть несколькими возможными решениями по данному вопросу. Обозначим через ${\mathcal {N}}=\{1,\ldots ,n\}$ набор избирателей . Позволять ${\mathcal {P}}$ быть набором строгих слабых ордеров над ${\mathcal {A}}$: элемент этого набора может представлять предпочтения избирателя, при этом избирателю может быть безразлично расположение некоторых альтернатив. Правило голосования – это функция $f:{\mathcal {P}}^{n}\to {\mathcal {A}}$. Его входные данные — профиль предпочтений. $(P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}$ и это дает личность победившего кандидата.

Мы говорим, что $f$ манипулируемым тогда и только тогда , когда существует профиль $(P_{1},\ldots ,P_{n})\in {\mathcal {P}}^{n}$ где какой-то избиратель $i$, заменив свой бюллетень $P_{i}$ с другим бюллетенем $P_{i}'$, может получить результат, который она предпочитает (в смысле $P_{i}$).

Обозначим через $f({\mathcal {P}}^{n})$ образ $f$, то есть набор возможных результатов выборов. Например, мы говорим, что $f$ имеет по крайней мере три возможных исхода тогда и только тогда, когда мощность $f({\mathcal {P}}^{n})$ составляет 3 и более.

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

Теорема Гиббарда – Саттертуэйта . Если порядковое правило голосования имеет как минимум 3 возможных результата и не является диктаторским, то им можно манипулировать.

Контрпримеры и лазейки

Множество «контрпримеров» к теореме Гиббарда-Саттертуэйта существуют, когда условия теоремы не применяются.

Кардинальное голосование

Рассмотрим выборы трех кандидатов, проводимые по результатам голосования . Для избирателя всегда оптимально дать лучшему кандидату максимально возможный балл, а худшему кандидату — минимально возможный балл. Тогда, независимо от того, какой балл избиратель присвоит среднему кандидату, он всегда будет (не строго) между первым и последним баллами; это означает, что результаты голосования избирателя будут слабо соответствовать честному рейтингу этого избирателя. Однако фактический оптимальный результат может зависеть от других поданных бюллетеней, как указано в теореме Гиббарда .

Серийная диктатура

Серийная диктатура определяется следующим образом. Если у избирателя 1 есть уникальный кандидат, пользующийся наибольшим успехом, то этот кандидат избирается. В противном случае возможные результаты ограничиваются наиболее понравившимися кандидатами, тогда как остальные кандидаты исключаются. Затем рассматривается бюллетень избирателя 2: если среди невыбывших есть единственный наиболее понравившийся кандидат, то этот кандидат избирается. В противном случае список возможных исходов снова сокращается и т. д. Если после рассмотрения всех бюллетеней остается несколько невыбывших кандидатов, то применяется произвольное правило разделения голосов.

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

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

Если есть только два возможных результата, правило голосования может быть не поддающимся манипулированию, но не быть диктаторским. Например, это случай простого большинства: каждый избиратель присваивает 1 балл своей лучшей альтернативе и 0 — другой, и альтернатива, набравшая наибольшее количество очков, объявляется победителем. (Если обе альтернативы набирают одинаковое количество очков, ничья прерывается произвольным, но детерминированным образом, например, результат $a$ побеждает.) Этим правилом голосования нельзя манипулировать, потому что избирателю всегда лучше сообщить о своих искренних предпочтениях; и оно явно не диктаторское. Многие другие правила не являются ни манипулируемыми, ни диктаторскими: например, предположим, что альтернатива $a$ побеждает, если получает две трети голосов, и $b$ в противном случае выигрывает.

Следствие

Теперь мы рассмотрим случай, когда по предположению избиратель не может быть безразличен к двум кандидатам. Обозначим через ${\mathcal {L}}$ набор строгих общих заказов ${\mathcal {A}}$ и мы определяем строгое правило голосования как функцию $f:{\mathcal {L}}^{n}\to {\mathcal {A}}$. Определения возможных результатов , манипулируемых и диктаторских, естественным образом адаптируются к этой структуре.

Для строгого правила голосования справедливо обратное утверждение теоремы Гиббарда – Саттертуэйта. Действительно, строгое правило голосования является диктаторским тогда и только тогда, когда оно всегда выбирает наиболее понравившегося кандидата диктатора среди возможных результатов; в частности, оно не зависит от бюллетеней других избирателей. Как следствие, им невозможно манипулировать: диктатор полностью защищен своим искренним голосованием, а другие избиратели не имеют никакого влияния на результат, следовательно, у них нет стимула отклоняться от искреннего голосования. Таким образом, мы получаем следующую эквивалентность.

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

В теореме, как и в следствии, не требуется предполагать возможность выбора любой альтернативы. Предполагается только, что как минимум три из них могут победить, т.е. являются возможными исходами правила голосования. Возможно, что некоторые другие альтернативы не могут быть выбраны ни при каких обстоятельствах: теорема и следствие остаются в силе. Однако следствие иногда представляется в менее общей форме: вместо того, чтобы предполагать, что правило имеет как минимум три возможных результата, иногда предполагается, что ${\mathcal {A}}$ содержит как минимум три элемента и что правило голосования включено , т. е. каждая альтернатива является возможным результатом. Предположение о том, что оно включено, иногда даже заменяется предположением, что правило единогласно , в том смысле, что если все избиратели предпочитают одного и того же кандидата, то она должна быть избрана.

Эскиз доказательства

Теорему Гиббарда-Саттертуэйта можно доказать, используя теорему Эрроу о невозможности для функций социального ранжирования . Мы даем схему доказательства в упрощенном случае, когда некоторое правило голосования $f$ считается эффективным по Парето .

Можно построить функцию социального ранжирования. $\operatorname {Rank}$, а именно: для того, чтобы решить, является ли $a\prec b$, $\operatorname {Rank}$ функция создает новые предпочтения, в которых $a$ и $b$ перемещаются в начало предпочтений всех избирателей. Затем, $\operatorname {Rank}$ проверяет, является ли $f$ выбирает $a$ или $b$.

Можно доказать, что если $f$ не поддается манипулированию и не является диктаторским, $\operatorname {Rank}$ удовлетворяет независимости от нерелевантных альтернатив. Теорема невозможности Эрроу гласит, что при наличии трех и более альтернатив такая $\operatorname {Rank}$ Функция должна быть диктатурой . Отсюда и такое правило голосования $f$ также должна быть диктатура.

Позднее авторы разработали другие варианты доказательства.

История

Стратегический аспект голосования уже заметил в 1876 году Чарльз Доджсон, также известный как Льюис Кэрролл , пионер теории социального выбора. Его цитата (о конкретной системе голосования) стала знаменитой благодаря Дункану Блэку :

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

В 1950-х годах Робин Фаркухарсон опубликовал влиятельные статьи по теории голосования. В статье с Майклом Дамметом , он предполагает, что детерминированные правила голосования, предусматривающие как минимум три результата, никогда не являются простым тактическим голосованием . Эта гипотеза позже была независимо доказана Алланом Гиббардом и Марком Саттертуэйтом . В статье 1973 года Гиббард использует теорему Эрроу о невозможности 1951 года, чтобы доказать результат, который мы теперь знаем как теорему Гиббарда . Независимо, Саттертуэйт доказал тот же результат в своей докторской диссертации в 1973 году, а затем опубликовал его в статье 1975 года. Это доказательство также основано на теореме невозможности Эрроу, но не включает более общую версию, данную теоремой Гиббарда.

Связанные результаты

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

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

Важность

Теорему Гиббарда-Саттертуэйта обычно представляют как результат, касающийся систем голосования, но ее также можно рассматривать как важный результат проектирования механизмов , который имеет дело с более широким классом правил принятия решений. Ноам Нисан описывает эту связь:

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

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

См. также

• Рейтинговое голосование
• Стратегическое голосование
• Теорема Гиббарда
• Теорема невозможности Эрроу
• Теорема Даггана – Шварца