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

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

Теорема была независимо сформулирована и доказана экономистом Алланом Гиббардом в 1973 году и политологом Марком Саттертуэйтом в 1975 году. Она является обобщением и развитием более ранней теоремы Эрроу о невозможности, которая, в свою очередь, показала, что не существует идеального правила голосования, удовлетворяющего нескольким разумным критериям (таким как транзитивность, независимость от посторонних альтернатив и парето-эффективность). Теорема Гиббарда — Саттертуэйта сосредотачивается именно на проблеме стратегического голосования, то есть на возможности участников манипулировать результатом, подавая ложные предпочтения.

Формулировка и основные понятия

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

Неманипулируемость (правдивость)

Процедура голосования называется неманипулируемой (или правдивой, strategyproof), если ни один избиратель не может получить более предпочтительный для себя результат, подав ложные предпочтения (то есть солгав о своём истинном ранжировании), при условии, что все остальные избиратели подают свои истинные предпочтения. Иначе процедура называется манипулируемой.

Диктатура

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

Универсальность (полнота)

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

Резольвентность (однозначность)

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

Формулировка теоремы (в наиболее распространённом виде): Любая неманипулируемая и универсальная процедура голосования, которая выбирает одну альтернативу из трёх или более, является диктатурой.

История открытия

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

В 1973 году Аллан Гиббард, в то время аспирант Стэнфордского университета, опубликовал статью «Manipulation of Voting Schemes: A General Result», в которой доказал, что любая процедура голосования с тремя или более альтернативами, не являющаяся диктатурой, подвержена манипулированию. Независимо от него, в 1975 году Марк Саттертуэйт, профессор Северо-Западного университета, опубликовал статью «Strategy-Proofness and Arrow’s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions», которая дала более общее и строгое доказательство, а также установила связь между условиями Эрроу и неманипулируемостью. Саттертуэйт показал, что если процедура голосования неманипулируема, то она должна удовлетворять условию независимости от посторонних альтернатив (одному из условий Эрроу), что, в свою очередь, приводит к диктатуре.

Доказательство и его структура

Доказательство теоремы Гиббарда — Саттертуэйта обычно проводится в два этапа. Первый этап (доказательство Гиббарда) устанавливает, что любая неманипулируемая процедура голосования должна быть монотонной: если альтернатива A выигрывает при некотором профиле предпочтений, и один или несколько избирателей повышают ранг A в своих предпочтениях (при неизменных предпочтениях остальных), то A должна остаться победителем. Монотонность — ключевое свойство, вытекающее из неманипулируемости.

Второй этап (доказательство Саттертуэйта) использует монотонность, чтобы показать, что процедура должна быть диктатурой. Доказательство опирается на понятие «решающей коалиции» — группы избирателей, которые могут обеспечить победу своей наиболее предпочтительной альтернативы, если все они поставят её на первое место. Используя свойства монотонности и универсальности, можно показать, что существует единственный избиратель, который является «решающим» для любой пары альтернатив, то есть является диктатором. Более строгое доказательство использует лемму о том, что для любой неманипулируемой процедуры существует «игрок с вето» (избиратель, который может заблокировать любую альтернативу, кроме своей самой любимой), и затем доказывается, что этот игрок на самом деле является диктатором.

Следствия и интерпретация

Теорема Гиббарда — Саттертуэйта имеет глубокие следствия для теории и практики коллективного принятия решений.

Невозможность идеального голосования

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

Связь с теоремой Эрроу

Теорема Гиббарда — Саттертуэйта является более сильным результатом, чем теорема Эрроу. Теорема Эрроу утверждает, что не существует идеального правила для построения коллективного ранжирования альтернатив. Теорема Гиббарда — Саттертуэйта утверждает, что не существует идеального правила для выбора одной альтернативы, если это правило должно быть защищено от манипуляций. Поскольку любое правило ранжирования можно использовать для выбора одной альтернативы (например, взяв первую в ранжировании), теорема Гиббарда — Саттертуэйта автоматически влечёт за собой теорему Эрроу (в её версии для выбора, а не для ранжирования).

Практические последствия

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

• Правило относительного большинства (мажоритарная система): Простое и понятное, но крайне подвержено тактическому голосованию (например, голосование за «меньшее зло»).
• Правило абсолютного большинства с вторым туром: Снижает риск «размывания» голосов, но также может быть манипулируемо (например, избиратели могут голосовать в первом туре за слабого кандидата, чтобы вывести во второй тур более удобного соперника).
• Метод Борда (ранжированное голосование): Менее подвержен тактическому голосованию, чем мажоритарная система, но всё равно не является полностью неманипулируемым. Более того, он может быть чувствителен к «парадоксу Борда», когда добавление нового кандидата меняет порядок предпочтений для старых.

Исключения и обобщения

Теорема справедлива для строгих предпочтений (избиратель не может ставить две альтернативы на одно место). Если допустить слабые предпочтения (возможность безразличия), то существуют неманипулируемые процедуры, не являющиеся диктатурами, например, правило «победитель по Кондорсе» (если он существует) или процедуры, основанные на «вето» (каждый избиратель по очереди вычёркивает одну альтернативу). Однако эти процедуры часто не являются резольвентными (могут не давать однозначного результата) или не являются универсальными (не определены для всех возможных профилей).

Существуют также обобщения теоремы на случай, когда избиратели могут голосовать не только за одну альтернативу, но и за несколько (например, голосование «за» и «против»). В этих случаях также можно доказать, что любая неманипулируемая процедура является диктатурой, если число альтернатив достаточно велико.

Критика и ограничения

Теорема Гиббарда — Саттертуэйта является математически строгой и не вызывает сомнений в своей корректности. Однако её практическое значение иногда оспаривается. Критики указывают на то, что теорема рассматривает идеализированную ситуацию, в которой:

• Избиратели имеют полную информацию о предпочтениях друг друга (что в реальности редко бывает).
• Избиратели действуют строго рационально и готовы манипулировать, если это выгодно.
• Процедура голосования должна быть определена для всех возможных профилей предпочтений, включая экзотические и маловероятные.

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

Источники

1. Gibbard, A. (1973). «Manipulation of Voting Schemes: A General Result». Econometrica, 41(4), 587-601.
2. Satterthwaite, M. A. (1975). «Strategy-Proofness and Arrow’s Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions». Journal of Economic Theory, 10(2), 187-217.
3. Arrow, K. J. (1951). Social Choice and Individual Values. New York: Wiley.
4. Moulin, H. (1988). Axioms of Cooperative Decision Making. Cambridge University Press.
5. Taylor, A. D. (2005). Social Choice and the Mathematics of Manipulation. Cambridge University Press.