Теория игр
Теория социального выбора и теорема Эрроу
Выборы, рейтинги, решения комитетов, ранжирование поиска - везде нужно агрегировать разные предпочтения в одно. Кажется, это просто: считаем голоса. Но математик Кеннет Эрроу доказал нечто шокирующее: идеальная демократическая процедура математически невозможна.
- **Президентские выборы в США**: кандидат-спойлер (Нэйдер в 2000) мог изменить результат - классическое нарушение IIA
- **Оскар**: академия меняла системы голосования много раз в поисках «справедливой» - теорема Эрроу объясняет, почему идеал недостижим
- **Рейтинги в поиске**: Google агрегирует тысячи сигналов в единый рейтинг - тоже задача социального выбора
Предварительные знания
Задача агрегации предпочтений
Теорема Эрроу (1951) доказывает: ни одна система голосования с 3+ кандидатами не удовлетворяет 3 базовым аксиомам справедливости одновременно. Теория социального выбора изучает, как объединить индивидуальные предпочтения в коллективное решение. Это фундаментальная задача демократии: как голосование, рейтинги, комитеты должны работать, чтобы отражать «волю большинства»?
Маркиз де Кондорсе обнаружил: правило большинства может давать **нетранзитивные** результаты даже при транзитивных индивидуальных предпочтениях. 3 голосующих, 3 альтернативы (A, B, C): • Игрок 1: A > B > C • Игрок 2: B > C > A • Игрок 3: C > A > B Голосования попарно: • A vs B: А побеждает 2:1 (игроки 1 и 3) • B vs C: B побеждает 2:1 (игроки 1 и 2) • C vs A: C побеждает 2:1 (игроки 2 и 3) Результат: A > B > C > A - цикл! Нет победителя Кондорсе.
Парадокс Кондорсе - первый признак фундаментальной проблемы. Простое правило большинства нарушает транзитивность. Может быть, другие правила лучше? Кеннет Эрроу показал: нет.
Три члена комитета выбирают между A, B, C с предпочтениями: 1: A>B>C, 2: B>C>A, 3: C>A>B. Кто побеждает по правилу большинства?
Теорема о невозможности Эрроу
Кеннет Эрроу (1950)
Кеннет Эрроу в своей докторской диссертации (1950) поставил вопрос: какие разумные требования к SWF? Он сформулировал четыре аксиомы - казалось бы, минимальных и очевидных - и доказал что никакая SWF не может удовлетворять всем четырём одновременно, кроме диктатуры. Это называется «impossibility theorem» или «General Possibility Theorem». Эрроу получил Нобелевскую премию в 1972 году в возрасте 51 года - самый молодой лауреат по экономике.
Интуиция IIA (Independence of Irrelevant Alternatives) - самая важная и нарушаемая аксиома. Пример нарушения: кандидат A ведёт над B. Входит третий кандидат C - «спойлер». Некоторые голоса перетекают от A к C, и B побеждает. Порядок A vs B изменился из-за «нерелевантной» альтернативы C.
• **Правило большинства**: нарушает транзитивность (парадокс Кондорсе) • **Метод Борда**: нарушает IIA (добавление нового кандидата меняет порядок) • **Instant runoff (ранговое голосование)**: нарушает IIA и монотонность • **Правило Кондорсе**: нарушает полноту (победитель может не существовать) Теорема Эрроу: любая система нарушает что-то из четырёх аксиом.
Голосование: 60% поддерживают A над B. Затем в бюллетень добавляют третьего кандидата C. Теперь 51% поддерживают B над A. Какую аксиому Эрроу нарушила эта система голосования?
Системы голосования: trade-offs
Теорема Эрроу не говорит «всё плохо» - она говорит «нельзя избежать trade-offs». Разные системы голосования нарушают разные аксиомы. Выбор системы зависит от того, какими свойствами готовы пожертвовать.
| Система | Метод | Нарушает | Применение |
|---|---|---|---|
| Plurality (первая за столб) | Побеждает с наибольшим числом голосов | IIA, Кондорсе | Парламентские выборы в UK/US |
| Метод Борда | Очки за позицию в ранге | IIA | Выбор победителя конкурсов |
| Instant Runoff (ранговое) | Выбывание слабейших итеративно | IIA, монотонность | Австралия, некоторые штаты США |
| Метода Кондорсе | Побеждает тот, кто бьёт всех попарно | Полнота (цикл) | Теоретический идеал |
| Approval voting | Голосуешь за всех приемлемых | Выражает интенсивность | Академические выборы |
| Score voting | Оценки 0-10 для каждого | Стратегические манипуляции | Рейтинги, Олимпиада |
**Победитель Кондорсе** - кандидат, который побеждает всех других при попарном голосовании. Существует не всегда (парадокс), но когда есть - большинство теоретиков считают его «правильным» победителем. **Проигравший Кондорсе** - кандидат, который проигрывает всем. Ни одна разумная система не должна избирать его. **Критерий Кондорсе**: если победитель Кондорсе существует, система должна его выбирать. Plurality и Borda могут его не избрать!
Метод Борда даёт очки: 1-е место = 2 очка, 2-е = 1 очко, 3-е = 0. Кандидат X выигрывает. Затем снимается слабый кандидат Z, и X проигрывает Y. Что это демонстрирует?
Теорема Гиббарда-Саттертуэйта: манипулируемость
Теорема Эрроу - о нормативных свойствах агрегации. Теорема **Гиббарда-Саттертуэйта** (1973-1975) - о стратегических: при каких системах голосования выгодно голосовать честно?
Для m ≥ 3 альтернатив любая функция социального выбора, которая: • Суръективна (может выбрать любую альтернативу) • Strategy-proof (честное голосование - доминирующая стратегия) ...является диктаторской. Вывод: нет системы голосования (кроме диктатуры), в которой всегда выгодно голосовать честно.
Теоремы Эрроу и Гиббарда-Саттертуэйта не означают, что все системы голосования одинаково плохи. Они означают, что **идеальная система невозможна** - нужно выбирать наименее плохую для конкретного контекста. Это активная область исследований: computational social choice, liquid democracy, quadratic voting.
Гиббард-Саттертуэйт доказал, что любая «хорошая» система голосования манипулируема. Какой практический вывод?
Ключевые идеи
- **Парадокс Кондорсе** - правило большинства может давать циклы даже при транзитивных индивидуальных предпочтениях
- **Теорема Эрроу** - нет SWF, удовлетворяющей U + Pareto + IIA + Non-dictatorship при ≥3 альтернативах
- **IIA** - самая часто нарушаемая аксиома: порядок A vs B не должен зависеть от «нерелевантных» C
- **Теорема Гиббарда-Саттертуэйта** - любая не-диктаторская система голосования манипулируема
- **Практический вывод** - trade-offs неизбежны; выбирать систему по тому, чем готовы пожертвовать
Связанные темы
Теория социального выбора - основа для понимания коллективных решений:
- Механизм-дизайн — Теорема Гиббарда-Саттертуэйта - частный случай impossibility для strategy-proof механизмов
- Теория матчинга — Алгоритм Гейла-Шепли - strategy-proof механизм; обходит impossibility через специальную структуру
- Равновесие Нэша — Стратегическое голосование - это игра; Nash equilibria в системах голосования
Вопросы для размышления
- Знаете ли реальный пример, когда «спойлер»-кандидат изменил результат выборов? Какую аксиому это нарушает?
- Если идеальная система невозможна, какие свойства важнее для парламентских выборов vs для выбора победителя конкурса?
- Теорема Эрроу применима к рейтингам в интернете (like/dislike, звёздочки). Каковы последствия для агрегации отзывов?