В области конструирования механизмов и теории общественного выбора , теорема Гиббарды является результатом доказан философом Аллана Gibbard в 1973. [1] Он утверждает , что для любого детерминированного процесса коллективного решения, по крайней мере , один из следующих трех свойств должны иметь:
- Процесс является диктаторским, то есть существует выдающийся агент, который может навязывать результат;
- Процесс ограничивает возможные результаты только двумя вариантами;
- Процесс открыт для стратегического голосования : как только агент определил свои предпочтения, вполне возможно, что в его распоряжении нет действия, которое наилучшим образом защищает эти предпочтения, независимо от действий других агентов.
Следствием этой теоремы является теорема Гиббарда – Саттертуэйта о правилах голосования. Основное различие между ними состоит в том, что теорема Гиббарда – Саттертуэйта ограничивается ранжированными (порядковыми) правилами голосования : действие избирателя заключается в предоставлении предпочтения по сравнению с доступными вариантами. Теорема Гиббарда является более общей и рассматривает процессы коллективного решения, которые могут не быть порядковыми: например, системы голосования, в которых избиратели выставляют оценки кандидатам. Теорема Гиббарда может быть доказана с помощью теоремы о невозможности Эрроу .
Теорема Гиббарда сама обобщается теоремой Гиббарда 1978 г. [2] и теоремой Хилланда , которые распространяют эти результаты на недетерминированные процессы, то есть где результат может не только зависеть от действий агентов, но также может включать элемент случайности.
Обзор
Рассмотрим некоторых избирателей , а также желающие выбрать один из трех вариантов: , а также . Предположим, они используют одобрительное голосование : каждый избиратель присваивает каждому кандидату оценку 1 (одобрение) или 0 (неодобрение). Например, авторизованный бюллетень: это означает, что избиратель одобряет кандидатов а также но не одобряет кандидата . После сбора бюллетеней победителем объявляется кандидат с наивысшей общей оценкой. Связи между кандидатами разрываются в алфавитном порядке: например, если между кандидатами есть равенство. а также , тогда побеждает.
Предположим, что избиратель предпочитает альтернативу , тогда а потом . Какой бюллетень лучше всего защитит ее мнение? Например, рассмотрим две следующие ситуации.
- Если два других избирателя соответственно проголосовали а также , затем избиратель имеет только один бюллетень, который приводит к избранию ее любимой альтернативы : .
- Однако, если мы предположим, что два других избирателя соответственно проголосовали а также , затем избиратель не должен голосовать потому что это делает выиграть; она должна проголосовать, что делает выиграть.
Подводя итог, избиратель стоит перед стратегической дилеммой голосования: в зависимости от бюллетеней, которые будут отданы другим избирателям, или же может быть бюллетенем, который лучше всего защищает ее мнение. Затем мы говорим, что одобрительное голосование не является простым делом : как только избиратель определил свои собственные предпочтения, в его распоряжении нет бюллетеня, который наилучшим образом защищает его мнение во всех ситуациях.
Теорема Гиббарда утверждает, что детерминированный процесс коллективного решения не может быть простым, за исключением, возможно, двух случаев: если есть выдающийся агент, обладающий диктаторской властью, или если процесс ограничивает исход только двумя возможными вариантами.
Официальное заявление
Позволять - набор альтернатив , которые также можно назвать кандидатами в контексте голосования. Позволять- набор агентов , которых также можно называть игроками или избирателями, в зависимости от контекста приложения. Для каждого агента, позволять быть набором, который представляет доступные стратегии для агента; предположить, чтоконечно. Позволять быть функцией, которая для каждого -набор стратегий , отображает альтернативу. Функцияназывается игровой формой . Другими словами, игровая форма по существу определяется как игра с n участниками , но без утилит, связанных с возможными результатами: она описывает только процедуру, без указания априори выгоды, которую каждый агент получит от каждого результата.
Мы говорим что будет просто , если и только если для любого агентаи для любого строгого слабого порядка над альтернативами существует стратегия это доминирует для агента когда у нее есть предпочтения : нет профиля стратегий для других агентов, такого что другая стратегия , отличается от , приведет к строго лучшему результату (в смысле ). Это свойство желательно для демократического процесса принятия решений: это означает, что однажды агент определила свои предпочтения , она может выбрать стратегию который лучше всего защищает ее предпочтения, без необходимости знать или угадывать стратегии, выбранные другими агентами.
Мы позволяем и обозначим через диапазон , т.е. множество возможных исходов игровой формы. Например, мы говорим, что имеет по крайней мере 3 возможных результата тогда и только тогда, когда мощность составляет 3 или более. Поскольку наборы стратегий конечны,конечно также; таким образом, даже если множество альтернатив не предполагается конечным, подмножество возможных результатов обязательно так.
Мы говорим что является диктаторским тогда и только тогда, когда существует агенткто такой диктатор , в том смысле, что для любого возможного исхода, агент имеет в своем распоряжении стратегию, которая гарантирует, что результат будет независимо от стратегий, выбранных другими агентами.
Теорема Гиббарда - если форма игры не диктаторская и имеет по крайней мере 3 возможных исхода, то это непросто.
Примеры
Серийная диктатура
Мы предполагаем, что каждый избиратель сообщает кандидатам строгий слабый приказ . Последовательная диктатура определяется следующим образом . Если у избирателя 1 есть единственный наиболее понравившийся кандидат, то этот кандидат считается избранным. В противном случае возможные исходы ограничиваются наиболее понравившимися ему бывшими кандидатами, а другие кандидаты исключаются. Затем проверяется бюллетень второго избирателя: если среди невыбранных у него есть единственный наиболее понравившийся кандидат, то этот кандидат избирается. В противном случае список возможных результатов снова сокращается и т. Д. Если после проверки всех бюллетеней по-прежнему остается несколько невыбранных кандидатов, то используется произвольное правило разделения голосов.
Эта форма игры проста: какими бы ни были предпочтения избирателя, у него есть доминирующая стратегия, заключающаяся в объявлении своего искреннего порядка предпочтений. Он также является диктаторским, и его диктатор - избиратель 1: если он хочет видеть кандидата избранный, то он просто должен сообщить порядок предпочтений, в котором - единственный кандидат, который больше всего нравится.
Голосование простым большинством
Если есть только 2 возможных исхода, форма игры может быть простой, а не диктаторской. Например, это случай простого большинства голосов: каждый избиратель голосует за вариант, который ему больше всего понравился (из двух возможных результатов), и вариант, набравший наибольшее количество голосов, объявляется победителем. Эта форма игры проста, потому что всегда оптимально проголосовать за наиболее понравившуюся альтернативу (если только один из них не безразличен). Однако он явно не диктаторский. Многие другие формы игры просты и не диктаторские: например, предположим, что альтернативный побеждает, если получит две трети голосов, и в противном случае выигрывает.
Игровая форма, показывающая, что обратное неверно
Рассмотрим следующую игровую форму. Избиратель 1 может проголосовать за кандидата по своему выбору или воздержаться. В первом случае автоматически избирается указанный кандидат. В противном случае другие избиратели используют классическое правило голосования, например, подсчет Борда . Эта форма игры явно диктаторская, потому что избиратель 1 может навязывать результат. Однако это непросто: другие избиратели сталкиваются с той же проблемой стратегического голосования, что и при обычном подсчете Борда. Таким образом, теорема Гиббарда - это импликация, а не эквивалентность.
Примечания и ссылки
- ^ Гиббард, Аллан (1973). «Манипуляция схемами голосования: общий результат» (PDF) . Econometrica . 41 (4): 587–601. DOI : 10.2307 / 1914083 . JSTOR 1914083 .
- ^ Гиббард, Аллан (1978). «Прямолинейность игровых форм с лотереями в качестве результата» (PDF) . Econometrica . 46 (3): 595–614. DOI : 10.2307 / 1914235 .