Парадокс Кондорсе голосования: когда большинство себе противоречит

Интуиция подсказывает, что если каждый избиратель упорядочивает кандидатов рационально, то и коллективное решение должно быть согласованным. Парадокс Кондорсе голосования показывает, что это не так: складывая индивидуальные предпочтения через попарное большинство, мы можем получить замкнутый цикл $A \succ B \succ C \succ A$, у которого нет единственного победителя. Это не ошибка подсчёта и не редкая экзотика, а фундаментальное свойство агрегации мнений, открытое Жаном-Антуаном де Кондорсе ещё в 1785 году. Разберём механизм парадокса, научимся строить матрицу попарных побед и поймём, как это связано с теоремой Эрроу о невозможности.

Что такое парадокс Кондорсе голосования

Парадокс Кондорсе возникает, когда метод попарного сравнения кандидатов порождает нетранзитивное коллективное предпочтение. Индивидуальное предпочтение транзитивно: если избиратель ставит $A$ выше $B$ и $B$ выше $C$, то он ставит и $A$ выше $C$. Парадокс в том, что сумма таких транзитивных мнений может оказаться нетранзитивной.

Классический пример - три избирателя и три кандидата:

Избиратель 1: A > B > C
Избиратель 2: B > C > A
Избиратель 3: C > A > B

Сравним их попарно. В паре $A$ против $B$ за $A$ голосуют избиратели 1 и 3 - большинство $2:1$. В паре $B$ против $C$ побеждает $B$ (избиратели 1 и 2). В паре $C$ против $A$ побеждает $C$ (избиратели 2 и 3). Получаем цикл $A \succ B \succ C \succ A$: каждого кандидата побеждает кто-то ещё, и устойчивого выбора большинства не существует.

Попарное голосование и матрица побед

Чтобы аккуратно работать с парадоксом Кондорсе голосования, удобно записать все попарные исходы в матрицу. Пусть $n$ кандидатов, тогда матрица $M$ имеет размер $n \times n$, где элемент $M_{ij}$ равен числу избирателей, предпочитающих кандидата $i$ кандидату $j$. Кандидат $i$ побеждает $j$ в паре, если

$M_{ij} > M_{ji}.$

Для примера выше матрица голосов «за строку против столбца» выглядит так:

$$M = \begin{pmatrix} - & 2 & 1 \\ 1 & - & 2 \\ 2 & 1 & - \end{pmatrix}.$$

Здесь строки и столбцы - это $A$, $B$, $C$. Видно, что $M_{AB}=2 > M_{BA}=1$ (A бьёт B), $M_{BC}=2>1$ (B бьёт C), $M_{CA}=2>1$ (C бьёт A) - тот самый цикл. Чтобы не считать матрицу и циклы вручную для своего набора бюллетеней, соберите конфигурацию ниже.

Победитель Кондорсе: когда он есть

Победитель Кондорсе - это кандидат, который побеждает любого другого в честном попарном голосовании. Формально кандидат $w$ является победителем Кондорсе, если $M_{wj} > M_{jw}$ для всех $j \neq w$. Если такой кандидат существует, он единствен, и большинство методов голосования согласны считать его справедливым исходом.

Суть парадокса именно в том, что победитель Кондорсе может отсутствовать. Когда попарные сравнения образуют цикл, граф доминирования содержит замкнутый контур, и ни одна вершина не доминирует все остальные. Метод, который всегда выбирает победителя Кондорсе при его наличии, называют методом, удовлетворяющим критерию Кондорсе.

Полезно противопоставить две ситуации. Если бы в нашем примере один из избирателей поменял свой бюллетень, скажем, на $A \succ C \succ B$, то цикл бы распался: $A$ начал бы побеждать и $B$, и $C$, став однозначным победителем Кондорсе. Парадокс возникает не из-за «плохих» избирателей, а из-за определённой симметрии в распределении предпочтений - когда мнения равномерно «вращаются» по кругу кандидатов.

Граф доминирования и турнирная матрица

Удобный способ увидеть парадокс - представить кандидатов вершинами графа, а каждую попарную победу - направленной стрелкой от победителя к проигравшему. Такой граф называют турниром. Если в турнире нет вершины, из которой стрелки ведут ко всем остальным, то победителя Кондорсе нет, а наличие ориентированного цикла $A \to B \to C \to A$ как раз и есть геометрическая форма парадокса.

Турнирная матрица - это бинарная версия матрицы $M$: элемент равен $1$, если строка побеждает столбец, и $0$ иначе. Сумма по строке даёт «копленд-счёт» кандидата - число его попарных побед. Победитель Кондорсе, если он есть, имеет максимально возможный счёт $n-1$. В цикле же все кандидаты получают одинаковый счёт, и формальное правило «по числу побед» уже не различает их - приходится привлекать более тонкие методы.

Вероятность парадокса растёт с числом кандидатов

Парадокс Кондорсе голосования - не редкая аномалия. При случайных и равновероятных предпочтениях (модель «беспристрастной культуры») вероятность отсутствия победителя Кондорсе растёт с числом альтернатив. Для трёх кандидатов и большого числа избирателей она составляет около $8{,}8\%$, для пяти - уже свыше $25\%$, и стремится к $1$ при росте числа кандидатов. То есть чем шире выбор, тем чаще честное большинство «зацикливается».

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

Как методы голосования борются с парадоксом

Раз победителя Кондорсе может не быть, придумано множество правил «достройки» исхода, когда возникает цикл:

• Метод Копленда: каждому кандидату начисляют очки за попарные победы минус поражения; выигрывает набравший больше. Прост, но допускает ничьи.
• Метод Шульце (beatpath): ищет сильнейшие пути в графе доминирования; всегда выбирает победителя Кондорсе при его наличии.
• Метод минимакса: выбирает кандидата с наименьшим худшим поражением.
• Ранжированные пары (Tideman): фиксирует попарные исходы от самого сильного к слабому, отбрасывая те, что создают цикл.

Все эти методы согласованы с критерием Кондорсе, но различаются тем, как именно разрывают цикл. Важно: ни один метод не устраняет парадокс - они лишь договариваются, какой исход считать «наименьшим злом».

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

Парадокс Кондорсе - частный, но показательный случай более общего результата. Теорема Эрроу (1951) утверждает, что при числе альтернатив $\geq 3$ не существует функции коллективного выбора, которая одновременно удовлетворяла бы всем разумным аксиомам: неограниченности области определения, единогласию (парето-эффективности), независимости от посторонних альтернатив и отсутствию диктатора.

Парадокс Кондорсе нарушает именно ожидание транзитивности коллективного отношения. Эрроу обобщает это: попытка сохранить все «справедливые» свойства одновременно неизбежно ведёт либо к нетранзитивности, либо к диктатуре. Иными словами, циклы Кондорсе - это симптом фундаментального ограничения, доказанного Эрроу. Полный разбор аксиом и логики доказательства мы вынесли в отдельную статью про теорему Эрроу о невозможности.

Частые ошибки

• Путают отсутствие победителя Кондорсе с ошибкой подсчёта. Цикл - это корректный результат честного попарного голосования, а не сбой.
• Считают, что транзитивность индивидов гарантирует транзитивность группы. Именно её нарушение и есть суть парадокса.
• Сравнивают только с одним соперником. Победитель Кондорсе должен побеждать всех остальных, а не одного выбранного оппонента.
• Отождествляют победителя по Кондорсе и по сумме баллов (Борда). Это разные критерии; они могут давать разных победителей.
• Полагают, что хороший метод устранит парадокс. Методы лишь разрывают цикл по фиксированному правилу, но не отменяют его существование.

FAQ

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

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

Как быстро проверить наличие победителя? Постройте матрицу попарных побед $M$ и найдите кандидата, у которого $M_{wj} > M_{jw}$ для всех $j$. Если такого нет - налицо цикл.

Коротко

Парадокс Кондорсе голосования демонстрирует, что попарное большинство может быть нетранзитивным: предпочтения $A \succ B \succ C \succ A$ образуют цикл, и победителя Кондорсе не существует. Проверяется это построением матрицы попарных побед $M$ и поиском кандидата, доминирующего всех. Вероятность парадокса растёт с числом альтернатив, а методы Копленда, Шульце, минимакса и ранжированных пар лишь разрывают цикл по своим правилам. Сам парадокс - частный случай теоремы Эрроу о невозможности идеальной агрегации предпочтений.