Теорема Гиббарда

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

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

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

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

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

Теорема Гиббарда предполагает, что в результате коллективного решения определяется ровно один победитель, и не применима к голосованию с несколькими победителями . Аналогичным результатом для голосования с несколькими победителями является теорема Даггана-Шварца .

Обзор

Рассмотрим некоторых избирателей $1$, $2$ и $3$ желающие выбрать вариант из трех альтернатив: $a$, $b$ и $c$. Предположим, они используют голосование за одобрение : каждый избиратель присваивает каждому кандидату оценку 1 (одобрение) или 0 (отказ от одобрения). Например, $(1,1,0)$ является санкционированным бюллетенем: это означает, что избиратель одобряет кандидатов $a$ и $b$ но не одобряет кандидата $c$. После сбора бюллетеней победителем объявляется кандидат с наивысшей общей оценкой. Связи между кандидатами разбиваются в алфавитном порядке: например, если между кандидатами есть ничья. $a$ и $b$, затем $a$ побеждает.

Предположим, что избиратель $1$ предпочитает альтернативу $a$, затем $b$ а потом $c$. Какой бюллетень лучше всего защитит ее мнение? Например, рассмотрим две следующие ситуации.

• Если два других избирателя проголосовали соответственно $(0,1,1)$ и $(1,1,1)$, тогда избиратель $1$ имеет только один бюллетень, который приводит к избранию ее любимой альтернативы $a$ : $(1,0,0)$.
• Однако, если вместо этого мы предположим, что два других избирателя соответственно проголосовали $(0,0,1)$ и $(0,1,1)$, тогда избиратель $1$ не должен голосовать $(1,0,0)$ потому что это делает $c$ победить; ей лучше проголосовать $(1,1,0)$, что делает $b$ победить.

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

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

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

Позволять ${\mathcal {A}}$ быть множеством альтернатив , которые также можно назвать кандидатами в контексте голосования. Позволять ${\mathcal {N}}=\{1,\ldots ,n\}$ быть набором агентов , которых также можно назвать игроками или избирателями, в зависимости от контекста приложения. Для каждого агента $i$, позволять ${\mathcal {S}}_{i}$ быть набором, который представляет доступные стратегии для агента $i$; предположим, что ${\mathcal {S}}_{i}$ конечно. Позволять $g$ быть функцией, которая для каждого $n$-кортеж стратегий $(s_{1},\ldots ,s_{n})\in {\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}$, отображает альтернативу. Функция $g$ называется игровой формой . Другими словами, форма игры по существу определяется как игра для n игроков , но без каких-либо полезностей, связанных с возможными результатами: она описывает только процедуру, без априорного указания выигрыша, который каждый агент получит от каждого результата.

Мы говорим, что $g$ является стратегически устойчивым (первоначально называлось: «простым» ), если для любого агента $i$ и для любого строгого слабого порядка $P_{i}$ среди альтернатив существует стратегия $s_{i}^{*}(P_{i})$ это доминирует для агента $i$ когда у нее есть предпочтения $P_{i}$: не существует профиля стратегий для других агентов, такого, что другая стратегия $s_{i}$, отличается от $s_{i}^{*}(P_{i})$, приведет к строго лучшему результату (в смысле $P_{i}$). Это свойство желательно для демократического процесса принятия решений: оно означает, что как только агент $i$ определила свои предпочтения $P_{i}$, она может выбрать стратегию $s_{i}^{*}(P_{i})$ это лучше всего защищает ее предпочтения, без необходимости знать или угадывать стратегии, выбранные другими агентами.

Мы позволяем ${\mathcal {S}}={\mathcal {S}}_{1}\times \cdots \times {\mathcal {S}}_{n}$ и обозначим через $g({\mathcal {S}})$ диапазон $g$, т.е. множество возможных исходов игровой формы. Например, мы говорим, что $g$ имеет по крайней мере три возможных исхода тогда и только тогда, когда мощность $g({\mathcal {S}})$ составляет 3 и более. Поскольку множества стратегий конечны, $g({\mathcal {S}})$ также конечен; таким образом, даже если множество альтернатив ${\mathcal {A}}$ не предполагается конечным, подмножество возможных результатов $g({\mathcal {S}})$ обязательно так.

Мы говорим, что $g$ является диктаторским, если существует агент $i$ кто является диктатором , в том смысле, что при любом возможном исходе $a\in g({\mathcal {S}})$, агент $i$ имеет в своем распоряжении стратегию, которая гарантирует, что результат будет $a$, какие бы стратегии ни выбрали другие агенты.

Теорема Гиббарда . Если форма игры не является диктаторской и имеет как минимум 3 возможных исхода, то она не является стратегической.

Примеры

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

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

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

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

Если есть только два возможных исхода, форма игры может быть нестратегической, а не диктаторской. Например, это случай простого большинства голосов: каждый избиратель голосует за наиболее понравившуюся ему альтернативу (среди двух возможных результатов), и альтернатива, набравшая наибольшее количество голосов, объявляется победителем. Эта форма игры не подвержена стратегии, поскольку всегда оптимально голосовать за наиболее понравившуюся альтернативу (если между ними нет безразличия). Однако оно явно не диктаторское. Многие другие формы игры устойчивы к стратегии и не являются диктаторскими: например, предположим, что альтернатива $a$ побеждает, если получает две трети голосов, и $b$ в противном случае выигрывает.

Форма игры, показывающая, что обратное неверно.

Рассмотрим следующую форму игры. Избиратель 1 может проголосовать за кандидата по своему выбору или воздержаться. В первом случае указанный кандидат избирается автоматически. В противном случае остальные избиратели используют классическое правило голосования, например, подсчет Борда . Эта форма игры явно диктаторская, поскольку избиратель 1 может навязать результат. Однако это не является стратегическим: перед остальными избирателями стоит та же проблема стратегического голосования, что и при обычном подсчете голосов в Борде. Таким образом, теорема Гиббарда является импликацией, а не эквивалентностью.

См. также

• Теорема невозможности Эрроу
• Теорема Гиббарда – Саттертуэйта