Русская Википедия:Теорема Эрроу

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

В рамках кардиналистского подхода, предполагающего количественную измеримость предпочтений, теорема Эрроу в общем случае не работает.

Формулировки

Формулировка 1951 года

Пусть есть N ≥ 2 избирателей, голосующих за n ≥ 3 кандидатов (в терминах теории принятия решений кандидатов принято называть альтернативами). У каждого избирателя есть упорядоченный список альтернатив. Система выборов — функция, превращающая набор из N таких списков (профиль голосования) в общий упорядоченный список.

Система выборов может обладать такими свойствами:

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

Для любого профиля голосования существует результат — упорядоченный список из n альтернатив.

Полнота

Система голосования может давать в качестве результата все n! перестановок альтернатив.

Монотонность

Если во всех N списках некоторая альтернатива x останется на месте или поднимется выше, а порядок остальных не изменится, в общем списке x должен остаться на месте или подняться.

Отсутствие диктатора

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

Независимость от посторонних альтернатив

Если профиль голосования изменится так, что альтернативы x и y во всех N списках останутся в том же порядке, то не изменится их порядок и в окончательном результате.

Формулировка 1963 года

В формулировке 1963 года условия Эрроу таковы.

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

Отсутствие диктатора

Независимость от посторонних альтернатив

Эффективность по Парето, или принцип единогласия

если у каждого избирателя альтернатива x в списке стоит выше y, это же должно быть и в окончательном результате.

Доказательство

Шаблон:Нет источников в разделе Введем следующие обозначения:

• <math>O</math> — множество исходов, которые каждый агент ранжирует в соответствии со своими предпочтениями.
• <math>L_i</math> — линейный порядок предпочтений <math>i</math>-го агента на множестве <math>O</math> заданный отношением <math>\succ_i</math>.
• <math>[\succ']</math> — профиль предпочтений (кортеж, элементами которого являются предпочтения всех агентов).
• <math>W : L^N \to L_W</math> — функция общественного благосостояния.
• <math>\succ_W</math> — коллективные предпочтения.

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

• Парето-эффективность: <math>W</math> парето-эффективна, если для любых исходов <math>o_1, o_2 \in O, \forall i (o_1 \succ_i o_2) \Rightarrow (o_1 \succ_W o_2)</math>.
• Независимость от посторонних альтернатив: <math>W</math> независима от посторонних альтернатив, если для любых исходов <math>o_1, o_2 \in O</math> и для любых двух профилей предпочтений <math>[\succ']</math> и <math display="inline">[\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)</math>.
• Отсутствие диктатора: считаем, что для <math>W</math> отсутствует диктатор, если не существует такого <math>i</math>, что <math>\forall o_1, o_2 \in O (o_1 \succ_i o_2 \Rightarrow o_1 \succ_W o_2)</math>.
• Теорема Эрроу: если <math>|O| \geq 3</math>, то любая Парето-эффективная, независящая от посторонних альтернатив функция общественного благосостояния <math>W</math> имеет диктатора.

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

Этап 1.

Если каждый агент помещает исход <math>b</math> в самый верх или самый низ своего списка предпочтений (при этом не требуется, чтобы все агенты действовали одинаково), то и в <math>\succ_W</math> исход <math>b</math> тоже будет либо вверху, либо внизу списка.

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

Этап 2.

Для всякого исхода <math>b</math> существует агент, который является центральным в том смысле, что, изменив свой голос, он может переместить исход <math>b</math> из самой нижней позиции в списке <math>\succ_W</math> в самую верхнюю позицию в этом списке. Иными словами, найдутся два профиля <math>[\succ^1]</math> и <math>[\succ^2]</math>, отличающихся только предпочтениями агента <math>i</math>, что <math>b</math> находится в конце списка для <math>[\succ^1_W]</math> и в начале списка для <math>[\succ^2_W]</math>.

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

Этап 3.

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

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

Этап 4.

<math>n^*</math> — диктатор над всеми парами <math><a,b></math>.

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

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

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

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

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

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

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

См. также

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

Ссылки

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