Введение

Невозможный результат для систем ранжированного голосования

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

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

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

Пусть – множество альтернатив (которое предполагается конечным), также называемых кандидатами, даже если они не обязательно являются личностями: они могут представлять собой несколько возможных решений по данному вопросу. Обозначим – множество избирателей. Пусть – множество строгих слабых порядков предпочтений на : элемент этого множества может представлять предпочтения избирателя, при этом избиратель может быть безразличен к порядку некоторых альтернатив. Правило голосования – это функция, на вход которой подается профиль предпочтений , а на выходе – победивший кандидат. Говорят, что манипулируемо, если и только если существует профиль , в котором какой-то избиратель , заменив свой бюллетень на другой бюллетень , может получить исход, который он предпочитает (в смысле ). Обозначим образом , то есть множество возможных исходов выборов. Например, говорят, что имеет по крайней мере три возможных исхода, если и только если кардинальность равна 3 или больше. Говорят, что является диктаторским, если и только если существует избиратель , который является диктатором, в том смысле, что выигрышная альтернатива всегда является наиболее предпочтительной для него среди возможных исходов, независимо от предпочтений других избирателей. Если у диктатора есть несколько альтернатив, которые ему одинаково нравятся среди возможных исходов, то выигрышной альтернативой будет любая из них.

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

Существует множество "контрпримеров" к теореме Гиббарда — Саттертвейта, когда условия теоремы не выполняются.

Голосование кардиналов

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

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

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

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

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

Следующее

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

Схема доказательства

Теорема Гиббарда — Саттертвейта может быть доказана с использованием теоремы невозможности Арроу для функций социального ранжирования. Мы приводим схему доказательства в упрощенном случае, когда предполагается, что некоторое правило голосования является эффективным по Парето. Можно построить социальную функцию ранжирования следующим образом: чтобы определить, предпочитает ли , функция создает новые предпочтения, в которых и перемещаются на первое место в предпочтениях всех избирателей. Затем функция проверяет, выбирает ли или . Возможно доказать, что если функция не подвержена манипуляциям и не является диктаторской, то она удовлетворяет независимости от несущественных альтернатив. Теорема невозможности Арроу утверждает, что при трех и более альтернативах такая функция должна быть диктаторской. Следовательно, такое правило голосования также должно быть диктаторским. Позднее другие авторы разработали различные варианты этого доказательства.

История

Стратегический аспект голосования был замечен еще в 1876 году Чарльзом Доджсоном, также известным как Льюис Кэрролл, одним из пионеров теории общественного выбора. Его высказывание (относительно конкретной системы голосования) стало широко известно благодаря Дункану Блэку: «Этот принцип голосования превращает выборы скорее в игру мастерства, чем в истинное выражение воли избирателей». В 1950-х годах Робин Фаркхарсон опубликовал ряд влиятельных статей по теории голосования. В совместной статье с Майклом Дамметтом он высказал предположение, что детерминированные правила голосования, предусматривающие как минимум три варианта исхода, не допускают прямой тактической игры. Эта гипотеза впоследствии была независимо доказана Алланом Гиббардом и Марком Саттертуэйтом. В статье 1973 года Гиббард использовал теорему о невозможности Стрелы, опубликованную в 1951 году, для доказательства результата, который теперь известен как теорема Гиббарда.

Важность

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