Теорема Эрроу

Введем следующие обозначения:

• ${\displaystyle O}$ — множество исходов, которые каждый агент ранжирует в соответствии со своими предпочтениями.
• ${\displaystyle L_{i}}$ — линейный порядок предпочтений ${\displaystyle i}$-го агента на множестве ${\displaystyle O}$ заданный отношением ${\displaystyle \succ _{i}}$.
• ${\displaystyle [\succ ']}$ — профиль предпочтений (кортеж, элементами которого являются предпочтения всех агентов).
• ${\displaystyle W:L^{N}\to L_{W}}$ — функция общественного благосостояния.
• ${\displaystyle \succ _{W}}$ — коллективные предпочтения.

Дадим формальные определения:

• Парето-эффективность: ${\displaystyle W}$ парето-эффективна, если для любых исходов ${\displaystyle o_{1},o_{2}\in O,\forall i(o_{1}\succ _{i}o_{2})\Rightarrow (o_{1}\succ _{W}o_{2})}$.
• Независимость от посторонних альтернатив: ${\displaystyle W}$ независима от посторонних альтернатив, если для любых исходов ${\displaystyle o_{1},o_{2}\in O}$ и для любых двух профилей предпочтений ${\displaystyle [\succ ']}$ и ${\textstyle [\succ '']\in L_{n},\forall i(o_{1}\succ '_{i}o_{2}\Leftrightarrow o_{1}\succ ''_{i}o_{2})\Rightarrow (o_{1}\succ '_{W([\succ '])}o_{2}\Leftrightarrow o_{1}\succ ''_{W([\succ ''])}o_{2})}$.
• Отсутствие диктатора: считаем, что для ${\displaystyle W}$ отсутствует диктатор, если не существует такого ${\displaystyle i}$, что ${\displaystyle \forall o_{1},o_{2}\in O(o_{1}\succ _{i}o_{2}\Rightarrow o_{1}\succ _{W}o_{2})}$.
• Теорема Эрроу: если ${\displaystyle |O|\geq 3}$, то любая Парето-эффективная, независящая от посторонних альтернатив функция общественного благосостояния ${\displaystyle W}$ имеет диктатора.

Доказательство проведем в 4 этапа.

Этап 1.

Если каждый агент помещает исход ${\displaystyle b}$ в самый верх или самый низ своего списка предпочтений (при этом не требуется, чтобы все агенты действовали одинаково), то и в ${\displaystyle \succ _{W}}$ исход ${\displaystyle b}$ тоже будет либо вверху, либо внизу списка.

Возьмем произвольный профиль ${\displaystyle [\succ ]}$ такой, что в нём для всех агентов ${\displaystyle i}$ исход ${\displaystyle b}$ расположен либо вверху, либо внизу списка предпочтений ${\displaystyle \succ _{i}}$. Теперь допустим, что наше утверждение неверно, то есть существуют такие ${\displaystyle a,c\in O}$, что ${\displaystyle a\succ _{W}b}$ и ${\displaystyle b\succ _{W}c}$. Изменим тогда профиль ${\displaystyle [\succ ]}$ так, чтобы для всех агентов выполнялось ${\displaystyle c\succ _{i}a}$, не изменяя при этом ранжирования остальных исходов. Обозначим полученный профиль ${\displaystyle [\succ ']}$. Так как после такой модификации исход b для каждого агента все равно останется либо на самой верхней, либо на самой нижней позиции в списке его предпочтений, то из независимости W от посторонних альтернатив можно заключить, что и в новом профиле ${\displaystyle a\succ _{W}b}$ и ${\displaystyle b\succ _{W}c}$. Следовательно, в силу транзитивности ${\displaystyle \succ _{W}}$ получаем ${\displaystyle a\succ _{W}c}$. Но мы предположили, что для всех агентов ${\displaystyle c\succ _{i}a}$, тогда в силу Парето-эффективности должно быть ${\displaystyle c\succ _{W}a}$. Полученное противоречие доказывает утверждение.

Этап 2.

Для всякого исхода ${\displaystyle b}$ существует агент, который является центральным в том смысле, что, изменив свой голос, он может переместить исход ${\displaystyle b}$ из самой нижней позиции в списке ${\displaystyle \succ _{W}}$ в самую верхнюю позицию в этом списке. Иными словами, найдутся два профиля ${\displaystyle [\succ ^{1}]}$ и ${\displaystyle [\succ ^{2}]}$, отличающихся только предпочтениями агента ${\displaystyle i}$, что ${\displaystyle b}$ находится в конце списка для ${\displaystyle [\succ _{W}^{1}]}$ и в начале списка для ${\displaystyle [\succ _{W}^{2}]}$.

Рассмотрим любой профиль предпочтений, в котором все агенты расположили исход ${\displaystyle b}$ в самом низу своего списка предпочтений ${\displaystyle \succ _{i}}$. Ясно, что и в ${\displaystyle \succ _{W}}$ исход ${\displaystyle b}$ находится на самой нижней позиции (в силу Парето-эффективности). Пусть все агенты начали по очереди переставлять исход ${\displaystyle b}$ с самой нижней на самую верхнюю позицию в своих списках предпочтений, не меняя при этом ранжирования остальных исходов. Когда все агенты поставят исход ${\displaystyle b}$ первым в своём списке предпочтений, он будет первым и для ${\displaystyle \succ _{W}}$. Таким образом, в какой-то момент ${\displaystyle \succ _{W}}$ изменится. Пусть ${\displaystyle n^{*}}$ — агент, который, переставив таким образом ${\displaystyle b}$, изменил ${\displaystyle \succ _{W}}$ (в первый раз). Обозначим ${\displaystyle [\succ ^{1}]}$ — профиль предпочтений как раз до того, как ${\displaystyle n^{*}}$ переместил ${\displaystyle b}$, а ${\displaystyle [\succ ^{2}]}$ — профиль предпочтений сразу же после того, как ${\displaystyle n^{*}}$ переместил ${\displaystyle b}$. Таким образом, в ${\displaystyle [\succ ^{2}]}$ исход ${\displaystyle b}$ изменил свою позицию в ${\displaystyle \succ _{W}}$, при этом для всех агентов ${\displaystyle b}$ находится либо на самой верхней, либо на самой нижней позиции ${\displaystyle \succ _{i}}$. Следовательно, в силу утверждения, доказанного на Этапе 1, в ${\displaystyle \succ _{W}}$ исход ${\displaystyle b}$ занимает самую верхнюю позицию.

Этап 3.

${\displaystyle n^{*}}$ — диктатор над всеми парами ${\displaystyle <a,c>}$, не включающими в себя ${\displaystyle b}$.

Выберем из пары ${\displaystyle <a,c>}$ любой элемент. Без потери общности, выберем a. Далее из профиля ${\displaystyle [\succ ^{2}]}$ построим ${\displaystyle [\succ ^{3}]}$ следующим образом: в ${\displaystyle \succ _{n^{*}}}$, переместим исход a на первую позицию, оставив остальное ранжирование неизменным; произвольным образом для всех остальных агентов поменяем местами друг с другом ${\displaystyle a}$ и ${\displaystyle c}$. Тогда, как и в ${\displaystyle [\succ ^{1}]}$ получим, что ${\displaystyle a\succ _{W}b}$ (в силу независимости от посторонних альтернатив) и, как и в ${\displaystyle [\succ ^{2}]}$ получим, что ${\displaystyle b\succ _{W}c}$. Тогда ${\displaystyle a\succ _{W}c}$. Теперь построим профиль предпочтений ${\displaystyle [\succ ^{4}]}$ следующим образом: для всех агентов поместим исход ${\displaystyle b}$ на произвольную позицию в списке предпочтений ${\displaystyle \succ _{i}}$, для агента ${\displaystyle n^{*}}$ поместим исход ${\displaystyle a}$ в произвольную позицию до исхода ${\displaystyle c}$. Ясно, что в силу независимости от посторонних альтернатив ${\displaystyle a\succ _{W}c}$. Мы получили, что все агенты, кроме ${\displaystyle n^{*}}$ имеют совершенно произвольные профили предпочтений, а результат ${\displaystyle a\succ _{W}c}$ получился исходя только лишь из предположения, что ${\displaystyle a\succ _{n^{*}}c}$.

Этап 4.

${\displaystyle n^{*}}$ — диктатор над всеми парами ${\displaystyle <a,b>}$.

Рассмотрим какой-нибудь исход с. В силу Этапа 2 существует некоторый центральный агент ${\displaystyle n^{**}}$ для этого исхода, он же является диктатором для всех пар ${\displaystyle <A,B>}$, где, в частности, ${\displaystyle A=a,B=b}$. Если бы агент ${\displaystyle n^{**}\neq n^{*}}$ был дикатором над ${\displaystyle <a,b>}$, никакая замена предпочтений агента ${\displaystyle n^{*}}$ не могла бы поменять ранжирование ${\displaystyle a}$ и ${\displaystyle b}$ в ${\displaystyle \succ _{W}}$. Но на Этапе 2 агент ${\displaystyle n^{*}}$ переставил ${\displaystyle b}$ с последнего места на первое в ${\displaystyle \succ _{W}}$, и таким образом был обязан поменять местами ${\displaystyle a}$ и ${\displaystyle b}$. Следовательно, можно заключить, что ${\displaystyle n^{**}}$ совпадает с ${\displaystyle n^{*}}$, то есть ${\displaystyle n^{*}}$ и есть диктатор.

Доказательство завершено.

Теорему Эрроу можно слегка переформулировать:

«В избирательных системах без диктатора, в которых реализован принцип единогласия, не может выполняться принцип независимости от посторонних альтернатив».

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

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

• Парадокс Кондорсе — парадокс выборов, обобщением которого явилась теорема Эрроу.
• Коллективный выбор и индивидуальные ценности

• Теорема о невозможности в задаче пропорционального представительства
• Кардиналистское голосование: Путь преодоления парадоксов социального выбора
• Другой вариант доказательства теоремы Эрроу