В теории общественного выбора , то Gibbard-Satterthwaite теорема является результатом опубликовано независимо философа Алана Gibbard в 1973 году [1] и экономист Марк Satterthwaite в 1975 г. [2] Речь идет о детерминированных порядковых избирательных системах , которые выбирают один победитель. Он гласит, что для каждого правила голосования должно выполняться одно из следующих трех условий:
- Правило диктаторское, то есть существует выдающийся избиратель, который может выбрать победителя; или же
- Правило ограничивает возможные результаты только двумя альтернативами; или же
- Правило подвержено тактическому голосованию : в определенных условиях искренний бюллетень некоторых избирателей может не лучше всего защищать их мнение.
Хотя область применения этой теоремы ограничивается порядковым голосованием, теорема Гиббарда является более общей, поскольку она касается процессов коллективного решения, которые могут не быть порядковыми: например, системы голосования, в которых избиратели выставляют оценки кандидатам. 1978 теоремы Гиббарды и Hylland теорема еще более общие и распространить эти результаты недетерминированных процессов, т.е. там , где результат может зависеть не только от действий избирателей , но может также включать в себя часть случайности.
Неформальное описание
Рассмотрим трех избирателей по имени Алиса, Боб и Кэрол, которые хотят выбрать победителя среди четырех названных кандидатов. , , а также . Предположим, что они используют подсчет Борда : каждый избиратель сообщает о своих предпочтениях относительно кандидатов. По каждому бюллетеню 3 балла присваиваются лучшему кандидату, 2 балла - второму кандидату, 1 балл - третьему и 0 баллов - последнему. После подсчета всех бюллетеней победителем объявляется кандидат, набравший наибольшее количество баллов.
Предположим, что их предпочтения следующие.
Избиратель | Вариант 1 | Вариант 2 | Вариант 3 | Вариант 4 |
---|---|---|---|---|
Алиса | ||||
Боб | ||||
Кэрол |
Если избиратели проголосовали искренне, то баллы будут следующими: . Следовательно, кандидат будет избран с 7 очками.
Но Алиса может стратегически проголосовать и изменить результат. Предположим, что она изменяет свой бюллетень, чтобы создать следующую ситуацию.
Избиратель | Вариант 1 | Вариант 2 | Вариант 3 | Вариант 4 |
---|---|---|---|---|
Алиса | ||||
Боб | ||||
Кэрол |
У Алисы есть стратегически обновленный кандидат и пониженный кандидат . Теперь оценки таковы:. Следовательно,Я выбрал. Алиса удовлетворена модификацией своего бюллетеня, потому что она предпочитает исход. к Это результат, которого она добилась бы, если бы проголосовала искренне.
Мы говорим, что подсчетом Борды можно манипулировать : бывают ситуации, когда искреннее голосование не защищает предпочтения избирателя наилучшим образом.
Теорема Гиббарда – Саттертуэйта утверждает, что каждое правило голосования можно манипулировать, за исключением, возможно, двух случаев: если есть выдающийся избиратель, обладающий диктаторской властью, или если правило ограничивает возможные результаты только двумя вариантами.
Официальное заявление
Позволять быть набором альтернатив (который предполагается конечным), также называемым кандидатами , даже если они не обязательно являются личностями: они также могут быть несколькими возможными решениями по данному вопросу. Обозначим черезнабор избирателей . Позволять- множество строгих слабых порядков над: элемент этого набора может представлять предпочтения избирателя, при этом избиратель может быть безразличен к упорядочиванию некоторых альтернатив. Правило голосования является функцией. Его вход - это профиль предпочтений и это дает личность победившего кандидата.
Мы говорим что можно манипулировать тогда и только тогда, когда существует профиль где какой-то избиратель , заменив ее бюллетень с другим бюллетенем , может получить результат, который она предпочитает (в смысле ).
Обозначим через образ , т.е. набор возможных исходов выборов. Например, мы говорим, что имеет по крайней мере три возможных результата тогда и только тогда, когда мощность составляет 3 или более.
Мы говорим что является диктаторским тогда и только тогда, когда существует избирателькто является диктатором , в том смысле, что победившая альтернатива всегда является ее наиболее любимой среди возможных исходов, независимо от предпочтений других избирателей . Если у диктатора есть несколько одинаково любимых альтернатив среди возможных исходов, то выигрышная альтернатива - просто одна из них.
Теорема Gibbard-Satterthwaite - Если правило голосования имеет по крайней мере 3 возможных результатов и не является диктаторским, то манипулируемо.
Примеры
Серийная диктатура
Последовательная диктатура определяется следующим образом . Если у избирателя 1 есть единственный наиболее понравившийся кандидат, то этот кандидат считается избранным. В противном случае возможные результаты ограничиваются наиболее понравившимися кандидатами, тогда как другие кандидаты исключаются. Затем проверяется бюллетень второго избирателя: если среди невыбранных есть единственный наиболее понравившийся кандидат, то этот кандидат избирается. В противном случае список возможных исходов снова сокращается и т. Д. Если после проверки всех бюллетеней остается несколько невыбранных кандидатов, используется произвольное правило разделения голосов.
Этим правилом голосования нельзя манипулировать: избирателю всегда лучше сообщить о своих искренних предпочтениях. Он также является диктаторским, и его диктатором является избиратель 1: выигрышная альтернатива всегда - это тот, который больше всего нравится конкретному избирателю, или, если есть несколько наиболее популярных альтернатив, он выбирается среди них.
Голосование простым большинством
Если есть только 2 возможных исхода, правило голосования может быть неуправляемым, но не диктаторским. Например, это случай простого большинства голосов: каждый избиратель присваивает 1 балл своей лучшей альтернативе и 0 - другой, и альтернатива с наибольшим количеством баллов объявляется победителем. (Если обе альтернативы набирают одинаковое количество очков, ничья разрывается произвольным, но детерминированным образом, например, результатпобеждает.) Этим правилом голосования нельзя манипулировать, потому что избирателю всегда лучше сообщать о своих искренних предпочтениях; и он явно не диктаторский. Многие другие правила не являются ни манипулируемыми, ни диктаторскими: например, предположим, что альтернатива побеждает, если получит две трети голосов, и в противном случае выигрывает.
Игровая форма, показывающая, что обратное неверно
Учтите следующее правило. Все кандидаты исключаются, кроме кандидата или кандидатов, которые занимают верхнюю позицию в бюллетене для первого избирателя. Затем из неисключенных кандидатов по подсчету Борда выбирается один . Весь этот процесс по определению диктаторский. Однако им можно манипулировать по тем же причинам, что и обычным подсчетом Борды. Таким образом, теорема Гиббарда – Саттертуэйта является импликацией, а не эквивалентностью.
Следствие
Теперь рассмотрим случай, когда по предположению избиратель не может быть безразличным между двумя кандидатами. Обозначим черезнабор строгих итоговых заказов закончилсяи мы определяем строгое правило голосования как функцию. Определения возможных результатов , манипулируемых , диктаторских, имеют естественную адаптацию к этой структуре.
Для строгого правила голосования верно обратное утверждение теоремы Гиббарда – Саттертуэйта. Действительно, строгое правило голосования является диктаторским тогда и только тогда, когда оно всегда выбирает наиболее понравившегося кандидата диктатора среди возможных результатов; в частности, это не зависит от бюллетеней других избирателей. Как следствие, им нельзя манипулировать: диктатор прекрасно защищен своим искренним бюллетенем, а другие избиратели не имеют никакого влияния на результат, следовательно, у них нет стимула отклоняться от искреннего голосования. Таким образом, мы получаем следующую эквивалентность.
Теорема - Если строгое правило голосования имеет по крайней мере 3 возможных результатов, оно не манипулируемо тогда и только тогда , когда это диктаторское.
В теореме, как и в следствии, нет необходимости предполагать, что какая-либо альтернатива может быть избрана. Предполагается только, что по крайней мере три из них могут выиграть, т.е. являются возможными исходами правила голосования. Возможно, что какие-то другие альтернативы не могут быть выбраны ни при каких обстоятельствах: теорема и следствие по-прежнему применимы. Однако следствие иногда представляется в менее общей форме: [3] вместо того, чтобы предполагать, что правило имеет по крайней мере три возможных результата, иногда предполагается, чтосодержит , по меньшей мере , три элемента , и что правило голосования на , то есть каждую альтернативе является возможным результатом. [4] Предположение о принадлежности иногда даже заменяется предположением о том, что правило единодушно , в том смысле, что если все избиратели предпочитают одного и того же кандидата, то она должна быть избрана. [5] [6]
Эскиз доказательства
Теорема Гиббарда – Саттертуэйта может быть доказана на основе теоремы о невозможности Эрроу , которая имеет дело с функциями социального ранжирования , то есть системами голосования, разработанными для получения полного порядка предпочтений кандидатов, а не просто выбора победителя. Приведем набросок доказательства в упрощенном случае, когда правило голосованиясчитается единодушным. Можно построить функцию социального рейтинга, а именно: чтобы решить, есть ли , то функция создает новые предпочтения, в которых а также вынесены в начало списка предпочтений избирателей. Потом, исследует, есть ли выбирает или же . Можно доказать, что если не манипулируем и недиктаторски, тогда удовлетворяет свойствам: единодушие, независимость от несущественных альтернатив, и это не диктатура. Теорема о невозможности Эрроу гласит, что при наличии трех или более альтернатив такаяфункция не может существовать. Следовательно, такое правило голосованиятоже не может существовать. [7] : 214–215
История
Стратегический аспект голосования был замечен еще в 1876 году Чарльзом Доджсоном, также известным как Льюис Кэрролл , пионером теории социального выбора. Его цитата (об особой системе голосования) прославила Дункан Блэк : [8]
Этот принцип голосования делает выборы скорее игрой мастерства, чем настоящей проверкой желаний избирателей.
В 1950-е годы Робин Фаркухарсон опубликовал влиятельные статьи по теории голосования. [9] В статье с Даммите , [10] он предполагает , что детерминированные правила голосования, по крайней мере три вопроса , сталкиваются с эндемическим тактическим голосованием . [11] Эта гипотеза Фаркарсона-Даммета независимо доказана Алланом Гиббардом и Марком Саттертуэйтом . В статье 1973 года Гиббард использует теорему о невозможности Эрроу 1951 года для доказательства результата, который мы теперь знаем как теорему Гиббарда , а затем выводит настоящий результат, который является его непосредственным следствием. [1] Независимо, Саттертуэйт доказывает тот же результат в своей докторской диссертации в 1973 году, а затем публикует его в статье 1975 года. [2] Его доказательство также основано на теореме невозможности Эрроу, но он не раскрывает более общую версию, данную теоремой Гиббарда. Позже несколько авторов развивают варианты доказательства, обычно более короткие, либо для самой теоремы, либо для следствия и ослабленных версий, о которых мы упоминали выше. [4] [5] [6] [12] [13] [14] [15] [16] [17]
Связанные результаты
Теорема Гиббарда имеет дело с процессами коллективного выбора, которые могут не быть порядковыми, т. Е. Когда действие избирателя не может состоять в сообщении порядка предпочтения кандидатам. 1978 теоремы Гиббарды и теорема Хилланда по распространить эти результаты на недетерминированные механизмы, т.е. там , где результат может зависеть не только от избирательных бюллетеней , но может также включать часть случайности.
Теорема Даггана – Шварца [18] расширяет этот результат в другом направлении, имея дело с детерминированными правилами голосования, которые выбирают непустое подмножество кандидатов, а не одного победителя.
Потомство
Теорема Гиббарда-Саттертуэйта обычно представляется как результат, относящийся к области теории социального выбора и применимый к системам голосования, но ее также можно рассматривать как основополагающий результат разработки механизмов , которые имеют дело с концепцией правил для принятия коллективных решений. возможно, в процессах, связанных с денежным переводом. Ноам Нисан описывает это отношение: [7] : 215
Теорема GS, кажется, разрушает любую надежду на создание совместимых со стимулами функций социального выбора. Вся область разработки механизмов пытается избежать этой невозможности с помощью различных модификаций модели.
Основная идея этих «путей выхода» состоит в том, что они имеют дело только с ограниченными классами предпочтений, в отличие от теоремы Гиббарда – Саттертуэйта, которая имеет дело с произвольными предпочтениями. Например, в этой дисциплине часто предполагается, что агенты имеют квазилинейные предпочтения, что означает, что их функция полезности линейно зависит от денег. В этом случае денежные переводы могут быть использованы для побуждения их к правдивым действиям. Это идея успешного аукциона Викри-Кларка-Гроувса .
Смотрите также
- Теорема Гиббарда
- Теорема невозможности Эрроу
- Теорема Даггана – Шварца.
Рекомендации
- ^ а б Гиббард, Аллан (1973). «Манипулирование схемами голосования: общий результат». Econometrica . 41 (4): 587–601. DOI : 10.2307 / 1914083 . JSTOR 1914083 .
- ^ а б Саттертуэйт, Марк Аллен (апрель 1975 г.). «Стратегическая стойкость и условия Эрроу: теоремы существования и соответствия для процедур голосования и функций социального обеспечения». Журнал экономической теории . 10 (2): 187–217. CiteSeerX 10.1.1.471.9842 . DOI : 10.1016 / 0022-0531 (75) 90050-2 .
- ^ Вебер, Тьярк (2009). «Альтернативы против результатов: Примечание к теореме Гиббарда-Саттертуэйта» . Технический отчет (Университетская библиотека Мюнхена) .
- ^ а б Рени, Филип Дж. (2001). «Теорема Эрроу и теорема Гиббарда-Саттертуэйта: единый подход». Письма по экономике . 70 (1): 99–105. CiteSeerX 10.1.1.130.1704 . DOI : 10.1016 / S0165-1765 (00) 00332-3 .
- ^ а б Бенуа, Жан-Пьер (2000). "Теорема Гиббарда-Саттертуэйта: простое доказательство". Письма по экономике . 69 (3): 319–322. DOI : 10.1016 / S0165-1765 (00) 00312-8 . ISSN 0165-1765 .
- ^ а б Сен, Арунава (2001). «Другое прямое доказательство теоремы Гиббарда-Саттертуэйта» (PDF) . Письма по экономике . 70 (3): 381–385. DOI : 10.1016 / S0165-1765 (00) 00362-1 . ISSN 0165-1765 .
- ^ а б Вазирани, Виджай В .; Нисан, Ноам ; Roughgarden, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0.
- ^ Черный, Дункан (1958). Теория комитетов и выборов . Кембридж: Издательство университета.
- ^ Фаркухарсон, Робин (февраль 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-х . JSTOR 41106711 .
- ^ Гарденфорс, Питер (1977). «Краткое доказательство теоремы о манипулировании функциями общественного выбора». Общественный выбор . 32 : 137–142. DOI : 10.1007 / bf01718676 . ISSN 0048-5829 . JSTOR 30023000 .
- ^ Барбера, Сальвадор (1983). «Стратегия-доказательство и основные избиратели: прямое доказательство теоремы Гиббарда-Саттертуэйта». Международное экономическое обозрение . 24 (2): 413–417. DOI : 10.2307 / 2648754 . ISSN 0020-6598 . JSTOR 2648754 .
- ^ Даммит, Майкл (1984). Порядок голосования . Издательство Оксфордского университета. ISBN 978-0198761884.
- ^ Фара, Рудольф; Саллес, Морис (2006). «Интервью с Майклом Даммитом: от аналитической философии к анализу голосования и не только» (PDF) . Социальный выбор и благосостояние . 27 (2): 347–364. DOI : 10.1007 / s00355-006-0128-9 . JSTOR 41106783 .
- ^ Мулен, Эрве (1991). Аксиомы совместного принятия решений . Издательство Кембриджского университета. ISBN 9780521424585. Проверено 10 января +2016 .
- ^ Тейлор, Алан Д. (апрель 2002 г.). «Управляемость систем голосования». Американский математический ежемесячник . 109 (4): 321–337. DOI : 10.2307 / 2695497 . JSTOR 2695497 .
- ^ Дагган, Джон; Шварц, Томас (2000). «Стратегическая управляемость без решимости или разделяемых убеждений: обобщение Гиббарда-Саттертуэйта». Социальный выбор и благосостояние . 17 (1): 85–93. DOI : 10.1007 / PL00007177 . ISSN 0176-1714 . JSTOR 41106341 .