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

редактировать

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

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

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

Содержание

1 Неформальное описание
2 Формальное заявление
3 Примеры
- 3.1 Последовательная диктатура
- 3.2 Простое большинство голосов
- 3.3 Игровая форма, показывающая, что обратное неверно
4 Следствие
5 Эскиз доказательства
6 История
7 Связанные результаты
8 Потомство
9 См. Также
10 Ссылки

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

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

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

Голосующий	Вариант 1	Вариант 2	Вариант 3	Вариант 4
Алиса	$a {\ displaystyle a}$ $a$	$b {\ displaystyle b}$ $b$	$c {\ displaystyle c}$ $c$	$d {\ displaystyle d}$ $d$
Боб	$c {\ displaystyle c}$ $c$	$b {\ displaystyle b}$ $b$	$d {\ displaystyle d}$ $d$	$a {\ displaystyle a}$ $a$
Кэрол	$c {\ displaystyle c}$ $c$	$b {\ displaystyle b}$ $b$	$d {\ displaystyle d}$ $d$	$a {\ displaystyle a}$ $a$

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

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

Голосующий	Вариант 1	Вариант 2	Вариант 3	Вариант 4
Алиса	$b {\ displaystyle b}$ $b$	$a {\ displaystyle a}$ $a$	$d {\ displaystyle d}$ $d$	$c {\ displaystyle c}$ $c$
Боб	$c {\ displaystyle c}$ $c$	$b {\ displaystyle b}$ $b$	$d {\ displaystyle d}$ $d$	$a {\ displaystyle a}$ $a$
Кэрол	$c {\ displaystyle c}$ $c$	$b {\ displaystyle b}$ $b$	$d {\ displaystyle d}$ $d$	$a {\ displaystyle a}$ $a$

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

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

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

Формальный оператор

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

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

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

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

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

Примеры

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

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

Этим правилом голосования нельзя манипулировать: избирателю всегда лучше сообщать о своих искренних предпочтениях. Он также является диктаторским, и его диктатор - избиратель 1: выигрышная альтернатива всегда - это тот, который больше всего нравится конкретному избирателю, или, если есть несколько наиболее популярных альтернатив, он выбирается среди них.
Голосование простым большинством
Если есть только 2 возможных результата, правило голосования может быть неуправляемым, но не диктаторским. Например, это случай простого большинства голосов: каждый избиратель присваивает 1 балл своей лучшей альтернативе и 0 - другой, и вариант с наибольшим количеством баллов объявляется победителем. (Если обе альтернативы набирают одинаковое количество очков, ничья прерывается произвольным, но детерминированным образом, например, результат $a {\ displaystyle a}$ $a$ побеждает.) Этим правилом голосования нельзя манипулировать, поскольку избирателю всегда лучше сообщать о своих искренних предпочтениях; и это явно не диктаторский режим. Многие другие правила не являются ни управляемыми, ни диктаторскими: например, предположим, что альтернатива $a {\ displaystyle a}$ $a$ выигрывает, если получает две трети голосов, и $b {\ displaystyle b }$ $b$ в противном случае выигрывает.
Игровая форма, показывающая, что обратное неверно.
Учтите следующее правило. Все кандидаты исключаются, кроме кандидата или кандидатов, которые занимают верхнюю позицию в бюллетене для первого избирателя. Затем из неисключенных кандидатов один выбирается с использованием подсчета Борда. Весь этот процесс по определению диктаторский. Однако им можно манипулировать по тем же причинам, что и обычным подсчетом Борды. Таким образом, теорема Гиббарда – Саттертуэйта - это импликация, а не эквивалентность.
Следствие
Теперь рассмотрим случай, когда по предположению избиратель не может быть безразличным между двумя кандидатами. Мы обозначаем $L {\ displaystyle {\ mathcal {L}}}$ ${\ mathcal {L}}$ набор строгих общих заказов на $A {\ displaystyle {\ mathcal {A} }}$ ${\ mathcal {A}}$ и мы определяем строгое правило голосования как функцию $f: L n → A {\ displaystyle f: {\ mathcal {L}} ^ {n} \ to {\ mathcal {A }}}$ ${\ displaystyle f: {\ mathcal {L}} ^ { n} \ to {\ mathcal {A}}}$ . Определения возможных результатов, манипулируемых, диктаторских, имеют естественную адаптацию к этой структуре.

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

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

В теореме, как и в следствии, нет необходимости предполагать, что любая альтернатива может быть выбрана. Предполагается только, что по крайней мере три из них могут выиграть, то есть являются возможными исходами правила голосования. Возможно, что другие альтернативы не могут быть выбраны ни при каких обстоятельствах: теорема и следствие по-прежнему применимы. Однако следствие иногда представляется в менее общей форме: вместо предположения, что правило имеет по крайней мере три возможных результата, иногда предполагается, что $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ содержит по крайней мере три элемента и что действует правило голосования, т.е. каждая альтернатива является возможным исходом. Предположение о принадлежности иногда даже заменяется предположением, что правило единодушно, в том смысле, что если все избиратели предпочитают одного и того же кандидата, то она должна быть избрана.
Схема доказательства
Теорема Гиббарда – Саттертуэйта может быть доказана на основе теоремы о невозможности Эрроу, которая касается функций социального ранжирования, то есть систем голосования, разработанных для определения полного порядка предпочтений кандидатов, а не просто выбирая победителя. Мы даем набросок доказательства в упрощенном случае, когда правило голосования $f {\ displaystyle f}$ $f$ считается единогласным. Можно построить функцию социального ранжирования $Rank {\ displaystyle \ operatorname {Rank}}$ ${\ displaystyle \ operatorname {Rank}}$ следующим образом: чтобы решить, $a ≺ b {\ displaystyle a \ prec b }$ $a \ prec b$ функция $Rank {\ displaystyle \ operatorname {Rank}}$ ${\ displaystyle \ operatorname {Rank}}$ создает новые настройки, в которых $a {\ displaystyle a}$ $a$ и $b {\ displaystyle b}$ $b$ перемещены в верхнюю часть предпочтений всех избирателей. Затем $Rank {\ displaystyle \ operatorname {Rank}}$ ${\ displaystyle \ operatorname {Rank}}$ проверяет, выбирает ли $f {\ displaystyle f}$ $f$ $a {\ displaystyle a}$ $a$ или $b {\ displaystyle b}$ $b$ . Можно доказать, что если $f {\ displaystyle f}$ $f$ не манипулируем и не диктаторски, то $Rank {\ displaystyle \ operatorname {Rank}}$ ${\ displaystyle \ operatorname {Rank}}$ удовлетворяет свойствам: единодушие, независимость от несущественных альтернатив, и это не диктатура. Теорема о невозможности Эрроу гласит, что при наличии трех или более альтернатив такая функция $Rank {\ displaystyle \ operatorname {Rank}}$ ${\ displaystyle \ operatorname {Rank}}$ не может существовать. Следовательно, такое правило голосования $f {\ displaystyle f}$ $f$ также не может существовать.
История
Стратегический аспект голосования уже отмечен в 1876 году Чарльзом Доджсон, также известный как Льюис Кэрролл, пионер теории социального выбора. Его цитата (об особой системе голосования) стала известной благодаря Дункану Блэку :

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

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

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

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

Основная идея этих «путей выхода» состоит в том, что они имеют дело только с ограниченными классами предпочтений, в отличие от теоремы Гиббарда – Саттертуэйта., который имеет дело с произвольными предпочтениями. Например, в этой дисциплине часто предполагается, что агенты имеют квазилинейные предпочтения, что означает, что их функция полезности линейно зависит от денег. В этом случае денежные переводы могут быть использованы для побуждения их к правдивым действиям. Это идея, лежащая в основе успешного аукциона Викри-Кларка-Гроувса.
См. Также
теорему Гиббарда
теорему о невозможности Эрроу
теорема Даггана-Шварца
Ссылки
Экономический портал