теорема эрроу

Пусть имеются конечные множества, $E$ («избиратели», «электорат», «эксперты») и $C$ («кандидаты», «альтернативы»). Каждый из избирателей имеет относительно любого из кандидатов определённое мнение, выражаемое в предпочтениях одних кандидатов по сравнению с другими, т. е. избиратели ранжируют (упорядочивают) множество альтернатив $C$ — создают свой профиль предпочтений. Отношение предпочтения избирателем $e$ кандидата $c_1$ по сравнению с кандидатом $c_2$ запишем в виде $$ c_1 \succ_{e} c_2 , $$ что можно читать: «$c_1$ лучше $c_2$», или «$c_1$ предпочтительнее $c_2$», или «$c_1$ выше $c_2$», или «$c_1$ симпатичнее $c_2$» (с точки зрения $e$). Очевидно, что определённое нами отношение препочтения обладает свойством транзитивности: $$ \big( (a \succ b) \, \& \, (b \succ c ) \big) \Longrightarrow a \succ c. $$

Задача заключается в том, чтобы по заданным индивидуальным профилям предпочтений для каждого избирателя построить профиль общественного предпочтения, т. е. определить ранжировку кандидатов, «справедливую» для всего множества избирателей. Например, пусть из кандидатов $C = ${Хренов, Редькин, Морковьев} избиратели $E = $ {1, 2, 3} * выбирают лучшего и профили их предпочтений таковы:

Тогда профиль общественного предпочтения (итоговая ранжировка множества кандидатов $C$), определённый по большинству голосов: $$ \textit{Редькин} \succ_{E} \textit{Морковьев} \succ_{E} \textit{Хренов}. $$

Сразу заметим, что даже для таких простых случаев, когда выбирают из трёх кандидатов три избирателя простым большинством голосов, могут возникнуть проблемы. Рассмотрим, к примеру, такую ранжировку кандидатов:

тогда, большинством в два голоса против одного, имеем \begin{eqnarray*} & \textit{Редькин} &\succ_{E}& \textit{Морковьев}, \\ & \textit{Морковьев} &\succ_{E}& \textit{Хренов}, \\ & \textit{Хренов} & \succ_{E}& \textit{Редькин}, \end{eqnarray*} т. е. получаются противоречащие друг другу условия и профиль общественного предпочтения в этом случае не существует. Рассмотренный пример — простейшая иллюстрация парадокса Кондорсе (Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet), открытого в 1785 г.

Все известные правила «демократического» голосования имеют существенные недостатки. В качестве иллюстрации приведём два простых примера. Наиболее распостранённое правило простого большинства голосов, когда побеждает тот кандидат, который набрал наибольшее количество голосов. Тогда в ситуации, когда кандидат Хренов получил 40% голосов, а Редькин и Морковьев — по 30%, победит Хренов, несмотря на то, что большинство избирателей в 60% высказалось против него и, быть может, от всей души ненавидят этого кандидата. Другое, также очень распостранённое, правило голосования в два тура: если при первом голосовании никто из кандидатов не набрал более 50% голосов, то два претендента, получившие максимальное число голосов, проходят во второй тур голосования, где победитель определяется по правилу простого большинства. Рассмотрим случай, когда кандидаты в первом туре получили ранжировку, как в (1), но при этом вместо одного избирателя голосуют их коалиции, имеющие в своих составах 1-я — 40%, 2-я — 29,9% и 3-я — 30,1% избирателей. Тогда во второй тур пройдут Хренов и Морковьев, причём победит последний, собрав 60% голосов (считаем, что предпочтения избирателей не меняются за всё время выборов и подсчёт голосов абсолютно честный). Однако, если исключить из списка кандидатов Хренова, вроде бы, не имеющего шансов на победу, то выиграет Редькин. Ясно, что это открывает большие возможности для манипуляций, даже при самом честном подсчёте голосов избирателей.

В связи со сказанным возникает вопрос: возможна ли, хотя бы теоретически, идеальная («справедливая», приемлемая для всех избирателей) избирательная система? Для ответа нужно, во-первых, явно и недвусмысленно указать необходимые требования к такой системе. Американский математик К. Эрроу (Kenneth J. Arrow) сформулировал такие требования в виде следующих четырех аксиом [11]:

1. Универсальность, universality, unrestricted domain. Для любых кандидатов $a$, $b$ и любых индивидуальных их ранжировок общественное предпочтение устанавливает либо $a \succ_E b$, либо $b \succ_E a$, либо $a =_E b$. (В последнем случае кандидаты одинаково предпочтительны).
2. Единогласие, unanimity, weak Pareto principle. Если все избиратели считают, что $a$ лучше $b$, то и в общественном предпочтении $a$ должен быть выше $b$.
3. Независимость от посторонних альтернатив, independence of irrelevant alternatives. Положение любых двух кандидатов зависит только от их положения в индивидуальных профилях предпочтений и не зависит от расположения других кандидатов.
4. Отсутствие диктатора, non-dictatorship. Не существует такого избирателя $d \in E$, который мог бы навязать свой выбор всему электорату: $$ x \succ_d y \, \Rightarrow \, x \succ_E y \; \forall \; x, y \in C. $$

К. Эрроу доказал (1951 г), что эта система аксиом противоречива, когда $|C| \gt 3$. Следовательно, идеальная демократическая избирательная система невозможна, даже теоретически. Особенно печально для «демократов» выглядит тот факт (это будет показано ниже), что отказавшись от четвёртой аксиомы мы получим логически непротиворечивую систему требований, что можно с полным основанием трактовать так: демократия — скрытая форма диктатуры.

Для доказательства теоремы Эрроу достаточно построить специальные профили предпочтений, так как, ввиду аксиомы Универсальности, избирательная система должна «работать» при любых индивидуальных ранжировках. Само доказательство технически не сложно — будем в основном следовать его наиболее простому варианту [12]. Введём определение

Определение 1. Коалицию избирателей $D$, $D \subseteq E$, назовём решающей для кандидатов $a, b$, если \begin{equation} \label{decision_set} (a \succ_D\!b) \& (b \succ_{\!E \setminus D} a) \! \Rightarrow \! a\!\succ_E\!b. \end{equation} Другими словами, если избиратели из $D$ считают, что кандидат $a$ лучше $b$, а все остальные избиратели придерживаются противоположного мнения, то в итоговой ранжировке будет так, как решили члены коалиции $D$.

В случае, когда соотношение (\ref{decision_set}) выполняется для любых кандидатов, коалицию $D$ назовём просто — решающей.

Заметим, что решающая коалиция, в силу аксиомы Единогласия, во-первых, существует (например, таково всё множество $E$) и, во-вторых, не может быть пустой (если никто не ставит $a$ выше $b$, то и общественном предпочтении такого быть не может). Переходя непосредственно к доказательству, обозначим $M$ минимальную по количеству избирателей решающую коалицию и покажем, что:

1. Минимальная решающая коалиция $M$ состоит из одного избирателя $d$.
2. { $d$ } — решающая коалиция.
3. Избиратель $d$ — диктатор.

i. Минимальная решающая коалиция $M$ состоит из одного избирателя $d$. Пусть коалиция $M$ является минимальной решающей относительно кандидатов $a$, $b$ и избиратель $d \in M$. Покажем, что либо коалиция $\{d\}$, либо коалиция $M \setminus \{d\}$ являются решающими и, значит (ввиду минимальности $M$), $M = \{d\}$. Для этого рассмотрим следующие профили предпочтений

Тогда в общественном предпочтении $a \succ_E b$, поскольку так высказались все члены $M$, а остальные избиратели — наоборот, и расположение кандидата $c$ по аксиоме Независимости никак на это не влияет.

Далее, могут быть две возможности:

• $b \succ_E c$, тогда, в силу $a \succ_E b$, выводим (транзитивность), что $a \succ_E c$. Это значит, что коалиция $\{d\}$ — решающая для $a, c$;
• $c \succ_E b$, тогда коалиция $M \setminus \{d\}$ — решающая, что противоречит минимальности $M$.

ii. $\{d\}$ — решающая коалиция. Рассмотрим профили

Так как $\{d\}$ — решающая коалиция, то $a \succ_E b$, и, в соответствии с аксиомой Единогласия $b \succ_E x$, следовательно (транзитивность), $a \succ_E x$. В силу Независимости полученный результат не зависит от $b$ и, поэтому, справедлив при произвольном $x$. Не трудно аналогичным образом построить соответствующие профили так, чтобы для произвольного кандидата $y$ было $y \succ_E a$. Следовательно, если $\{d\}$ образует решающую коалицию для какой-либо пары, то эта одноэлементная коалиция будет решающей и для любой пары, в которой один из её кандидатов заменён другим. Отсюда уже прямо вытекает, что $\{d\}$ — решающая коалиция.

Таким образом, избиратель $d$ может навязать электорату своё мнение, если все остальные избиратели голосуют в точности наоборот. Для доказательства того, что $d$ является диктатором, теперь достаточно показать его независимость от мнения остальных избирателей, т.е., что мнение $d$ относительно ранжировки, скажем, кандидатов $a$, $b$ всегда будет достаточным для того, чтобы и в коллективном мнении было так же.

iii. Избиратель $d$ — диктатор. Пусть избиратели, голосующие так же (относительно предпочтения $a$ по сравнению с $b$), как $d$, образуют множество $P$, все несогласные — множество $Q$. Множества $P$, $Q$ могут быть пустыми. Рассмотрим профили предпочтений

Тогда в коллективном предпочтении $a \succ_E c$ в силу того, что $\{d\}$ — решающая коалиция, и $c \succ_E b$ (Единогласие). Поэтому (транзитивность) $a \succ_E b$ — именно так, как высказался $d$. Следовательно, $d$ — диктатор и, таким образом, теорема Эрроу полностью доказана.