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

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

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

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

Неформальное описание

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

Предположим, что их предпочтения следующие.

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

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

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

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

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

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

Пусть будет множеством альтернатив (предполагается, что оно конечно), также называемых кандидатами , даже если они не обязательно являются лицами: они также могут быть несколькими возможными решениями по данному вопросу. Обозначим через множество избирателей . Пусть будет множеством строгих слабых порядков над : элемент этого множества может представлять предпочтения избирателя, где избиратель может быть безразличен относительно порядка некоторых альтернатив. Правило голосования — это функция . Его входные данные — профиль предпочтений , и оно выдает личность победившего кандидата. ${\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}$ $я$ $P_{i}$ $P_{i}'$ $P_{i}$

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

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

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

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

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

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

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

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

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

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

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

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

Следствие

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

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

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

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

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

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

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

Можно доказать, что если неманипулируемо и недиктаторски, то удовлетворяет независимости нерелевантных альтернатив. Теорема Эрроу о невозможности гласит, что при наличии трех или более альтернатив такая функция должна быть диктатурой . Следовательно, такое правило голосования также должно быть диктатурой. ^[8]^{: 214–215} $f$ $\operatorname {Ранг}$ $\operatorname {Ранг}$ $f$

Более поздние авторы разработали другие варианты доказательства. ^[5]^[6]^[7]^[9]^[10]^[11]^[12]^[13]^[14]^{[ избыточное цитирование ]}

История

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

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

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

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

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

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

Важность

Теорема Гиббарда-Саттертуэйта обычно представляется как результат о системах голосования, но ее также можно рассматривать как важный результат проектирования механизмов , который имеет дело с более широким классом правил принятия решений. Ноам Нисан описывает это отношение: ^[8]^{: 215}

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

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

Смотрите также

Примечания и ссылки

^ Теорема Гиббарда не подразумевает, что кардинальные методы обязательно стимулируют изменение относительного ранга двух кандидатов.

^ Рудольф Фарра и Морис Саллес (октябрь 2006 г.). «Интервью с Майклом Дамметом: от аналитической философии к анализу голосования и далее» (PDF) . Социальный выбор и благосостояние . 27 (2): 347–364. doi :10.1007/s00355-006-0128-9. S2CID 46164353.
^ ab Gibbard, Allan (1973). «Манипуляция схемами голосования: общий результат». Econometrica . 41 (4): 587–601. doi :10.2307/1914083. JSTOR 1914083.
^ ab Satterthwaite, Mark Allen (апрель 1975 г.). «Стратегическая устойчивость и условия Эрроу: теоремы существования и соответствия для процедур голосования и функций общественного благосостояния». Журнал экономической теории . 10 (2): 187–217. CiteSeerX 10.1.1.471.9842 . doi :10.1016/0022-0531(75)90050-2.
^ Вебер, Тьярк (2009). «Альтернативы против результатов: заметка о теореме Гиббарда-Саттертуэйта». Технический отчет (Библиотека Мюнхенского университета) .
^ ab Reny, Philip J. (2001). «Теорема Эрроу и теорема Гиббарда-Саттертуэйта: единый подход». Economics Letters . 70 (1): 99–105. CiteSeerX 10.1.1.130.1704 . doi :10.1016/S0165-1765(00)00332-3.
^ ab Benoît, Jean-Pierre (2000). «Теорема Гиббарда-Саттертуэйта: простое доказательство». Economics Letters . 69 (3): 319–322. doi :10.1016/S0165-1765(00)00312-8. ISSN 0165-1765.
^ ab Sen, Arunava (2001). «Еще одно прямое доказательство теоремы Гиббарда-Саттертуэйта» (PDF) . Economics Letters . 70 (3): 381–385. doi :10.1016/S0165-1765(00)00362-1. ISSN 0165-1765.
^ аб Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
^ Герденфорс, Питер (1977). «Краткое доказательство теоремы о манипулировании функциями общественного выбора». Public Choice . 32 : 137–142. doi : 10.1007/bf01718676. ISSN 0048-5829. JSTOR 30023000. S2CID 153421058.
^ Барбера, Сальвадор (1983). «Стратегическая устойчивость и основные избиратели: прямое доказательство теоремы Гиббарда-Саттертуэйта». International Economic Review . 24 (2): 413–417. doi :10.2307/2648754. ISSN 0020-6598. JSTOR 2648754.
^ Дамметт, Майкл (1984). Процедуры голосования . Oxford University Press. ISBN 978-0198761884.
^ Фара, Рудольф; Саллес, Морис (2006). «Интервью с Майклом Дамметом: от аналитической философии к анализу голосования и далее» (PDF) . Социальный выбор и благосостояние . 27 (2): 347–364. doi :10.1007/s00355-006-0128-9. JSTOR 41106783. S2CID 46164353.
^ Мулен, Эрве (1991). Аксиомы кооперативного принятия решений. Cambridge University Press. ISBN 9780521424585. Получено 10 января 2016 г.
^ Тейлор, Алан Д. (апрель 2002 г.). «Манипулируемость систем голосования». The American Mathematical Monthly . 109 (4): 321–337. doi :10.2307/2695497. JSTOR 2695497.
^ Блэк, Дункан (1958). Теория комитетов и выборов . Кембридж: University Press.
^ Фаркухарсон, Робин (февраль 1956 г.). «Прямолинейность процедур голосования». Oxford Economic Papers . Новая серия. 8 (1): 80–89. doi : 10.1093/oxfordjournals.oep.a042255 . JSTOR 2662065.
^ Дамметт, Майкл; Фаркухарсон, Робин (январь 1961 г.). «Стабильность голосования». Econometrica . 29 (1): 33–43. doi :10.2307/1907685. JSTOR 1907685.
^ Дамметт, Майкл (2005). «Работа и жизнь Робина Фаркухарсона». Социальный выбор и благосостояние . 25 (2): 475–483. doi :10.1007/s00355-005-0014-x. JSTOR 41106711. S2CID 27639067.
^ Дагган, Джон; Шварц, Томас (2000). «Стратегическая манипулятивность без решимости или общих убеждений: обобщение Гиббарда-Саттертуэйта». Social Choice and Welfare . 17 (1): 85–93. doi :10.1007/PL00007177. ISSN 0176-1714. JSTOR 41106341. S2CID 271833.