Аксиомы эрроу формулировка теоремы невозможности. Аксиомы эрроу

Выше мы привели примеры нескольких различных систем голосования. Возможны и другие системы. В качестве приме­ров можно указать на систему многотурового выбора с вычер­киванием кандидатов, набравших наименьшее число голосов , на систему вычеркивания нежелаемых кандидатов (appro ­ val votinq) и т.д.

Систематическое исследование всех возможных систем го­лосования провел в 1951 г. Кеннет Эрроу из Стенфордского университета . Он поставил вопрос в наиболее общем виде: можно ли создать такую систему голосования, чтобы она была одновременно рациональной (без противоречий), демократиче­ской (один человек - один голос) и решающей (позволяла осу­ществить выбор). Вместо попыток изобретения такой системы Эрроу предложил набор требований, аксиом, которым эта сис­тема должна удовлетворять. Эти аксиомы были интуитивно по­нятны, приемлемы с точки зрения здравого смысла и допуска­ли математическое выражение в виде некоторых условий. На основе этих аксиом Эрроу попытался в общем виде доказать су­ществование системы голосования, удовлетворяющей одновре­менно трем перечисленным выше принципам: рациональная, демократическая и решающая .

Первая аксиома Эрроу требует, чтобы система голосования была достаточно общей для того, чтобы учитывать все возмож­ные распределения голосов избирателей. Интуитивно это требо­вание вполне очевидно. Заранее нельзя предсказать распреде­ление голосов. Совершенно необходимо, чтобы система была

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

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

Третья аксиома Эрроу получила название независимости от несвязанных альтернатив. Пусть избиратель считает, что из пары кандидатов А и В лучшим является А. Это предпочте­ние не должно зависеть от отношения избирателя к прочим кандидатам. Третья аксиома достаточно привлекательна, но не столь очевидна с точки зрения каждодневного человеческого поведения. Так, в приводится убедительный пример нару­шения этой аксиомы. Посетитель ресторана первоначально сравнивает блюдо А и В и хочет заказать А, потому что приго­товление блюда В требует высокой квалификации повара, а по его мнению, такой повар вряд ли есть в данном ресторане. Вдруг он замечает в меню блюдо С - очень дорогое и также требующее высокого искусства приготовления. Тогда он выби­рает блюдо В, считая, что повар умеет хорошо готовить.

Часто третья аксиома Эрроу нарушается судьями в фигур­ном катании. Давая сравнительные оценки двум сильным фи­гуристам в одиночном катании, они стараются учесть возмож­ность хорошего выступления третьего сильного кандидата, ос­тавляя ему шансы стать победителем. Отличное выступление в произвольном катании фигуриста С, имевшего ранее не очень высокий результат в обязательной программе, может повлиять на оценки фигуристов А и В. Если А имел отличный результат в обязательной программе, судьи иногда ставят его ниже фигу­риста В при примерно равном выступлении, чтобы повысить шансы фигуриста С.

Тем не менее возможность предъявления требования неза­висимости к системе голосования в качестве обязательного не вызывает сомнения.

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

Пятая аксиома Эрроу является уже знакомым условием транзитивности: если в соответствии с мнением избирателей кандидат В не лучше кандидата А (хуже или эквивалентен), кандидат С не лучше кандидата В, то кандидат С не лучше кандидата А. Считается, что система голосования, не допус­кающая нарушения транзитивности, ведет себя рациональным образом.

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

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

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

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

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

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

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

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

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

Универсальность Для любого профиля голосования существует результат - упорядоченный список из n альтернатив. Полнота Система голосования может давать в качестве результата все n ! перестановок альтернатив. Монотонность Если во всех N списках некоторая альтернатива x останется на месте или поднимется выше, а порядок остальных не изменится, в общем списке x должен остаться на месте или подняться. Отсутствие диктатора Нет избирателя, предпочтение которого определяло бы результат выборов независимо от предпочтений других избирателей. Независимость от посторонних альтернатив Если профиль голосования изменится так, что альтернативы x и y во всех N списках останутся в том же порядке, то не изменится их порядок и в окончательном результате.

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

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

Универсальность Отсутствие диктатора Независимость от посторонних альтернатив Эффективность по Парето , или принцип единогласия если у каждого избирателя альтернатива x в списке стоит выше y , это же должно быть и в окончательном результате.

Доказательство теоремы Эрроу

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

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

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

• Парето-эффективность : $W$ парето-эффективна, если для любых исходов $o\_1,\; o\_2\; \backslash in\; O,\; \backslash forall\; i\; (o\_1\; \backslash succ\_i\; o\_2)\; \backslash Rightarrow\; (o\_1\; \backslash succ\_W\; o\_2)$.
• Независимость от посторонних альтернатив : $W$ независима от посторонних альтернатив, если для любых исходов $o\_1,\; o\_2\; \backslash in\; O$ и для любых двух профилей предпочтений $[\backslash succ"]$ и $[\backslash 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 0_1 \succ_{W([\succ ])} o_2).
• Отсутствие диктатора : считаем, что для $W$ отсутствует диктатор, если не существует такого $i$, что $\backslash forall\; o\_1,\; o\_2\; \backslash in\; O\; (o\_1\; \backslash succ\_i\; o\_2\; \backslash Rightarrow\; o\_1\; \backslash succ\_W\; o\_2)$.
• Теорема Эрроу : если $|O|\; \backslash geq\; 3$, то любая Парето-эффективная, независящая от посторонних альтернатив функция общественного благосостояния $W$ имеет диктатора.

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

Этап 1. Если каждый агент помещает исход $b$ в самый верх или самый низ своего списка предпочтений (при этом не требуется, чтобы все агенты действовали одинаково), то и в $\backslash succ\_W$ исход $b$ тоже будет либо вверху, либо внизу списка.

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

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

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

Этап 3. $n^*$ - диктатор над всеми парами , не включающими в себя $b$.

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

Этап 4. $n^*$ - диктатор над всеми парами .

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

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

См. также

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

Напишите отзыв о статье "Теорема Эрроу"

Ссылки

Примечания

Институт выборов Уровень выборов Избирательные системы Избирательная кампания Голосование Избирательное право Электоральная география Нарушения на выборах Псефология

Отрывок, характеризующий Теорема Эрроу

На Пьера не находили, как прежде, минуты отчаяния, хандры и отвращения к жизни; но та же болезнь, выражавшаяся прежде резкими припадками, была вогнана внутрь и ни на мгновенье не покидала его. «К чему? Зачем? Что такое творится на свете?» спрашивал он себя с недоумением по нескольку раз в день, невольно начиная вдумываться в смысл явлений жизни; но опытом зная, что на вопросы эти не было ответов, он поспешно старался отвернуться от них, брался за книгу, или спешил в клуб, или к Аполлону Николаевичу болтать о городских сплетнях.
«Елена Васильевна, никогда ничего не любившая кроме своего тела и одна из самых глупых женщин в мире, – думал Пьер – представляется людям верхом ума и утонченности, и перед ней преклоняются. Наполеон Бонапарт был презираем всеми до тех пор, пока он был велик, и с тех пор как он стал жалким комедиантом – император Франц добивается предложить ему свою дочь в незаконные супруги. Испанцы воссылают мольбы Богу через католическое духовенство в благодарность за то, что они победили 14 го июня французов, а французы воссылают мольбы через то же католическое духовенство о том, что они 14 го июня победили испанцев. Братья мои масоны клянутся кровью в том, что они всем готовы жертвовать для ближнего, а не платят по одному рублю на сборы бедных и интригуют Астрея против Ищущих манны, и хлопочут о настоящем Шотландском ковре и об акте, смысла которого не знает и тот, кто писал его, и которого никому не нужно. Все мы исповедуем христианский закон прощения обид и любви к ближнему – закон, вследствие которого мы воздвигли в Москве сорок сороков церквей, а вчера засекли кнутом бежавшего человека, и служитель того же самого закона любви и прощения, священник, давал целовать солдату крест перед казнью». Так думал Пьер, и эта вся, общая, всеми признаваемая ложь, как он ни привык к ней, как будто что то новое, всякий раз изумляла его. – «Я понимаю эту ложь и путаницу, думал он, – но как мне рассказать им всё, что я понимаю? Я пробовал и всегда находил, что и они в глубине души понимают то же, что и я, но стараются только не видеть ее. Стало быть так надо! Но мне то, мне куда деваться?» думал Пьер. Он испытывал несчастную способность многих, особенно русских людей, – способность видеть и верить в возможность добра и правды, и слишком ясно видеть зло и ложь жизни, для того чтобы быть в силах принимать в ней серьезное участие. Всякая область труда в глазах его соединялась со злом и обманом. Чем он ни пробовал быть, за что он ни брался – зло и ложь отталкивали его и загораживали ему все пути деятельности. А между тем надо было жить, надо было быть заняту. Слишком страшно было быть под гнетом этих неразрешимых вопросов жизни, и он отдавался первым увлечениям, чтобы только забыть их. Он ездил во всевозможные общества, много пил, покупал картины и строил, а главное читал.
Он читал и читал всё, что попадалось под руку, и читал так что, приехав домой, когда лакеи еще раздевали его, он, уже взяв книгу, читал – и от чтения переходил ко сну, и от сна к болтовне в гостиных и клубе, от болтовни к кутежу и женщинам, от кутежа опять к болтовне, чтению и вину. Пить вино для него становилось всё больше и больше физической и вместе нравственной потребностью. Несмотря на то, что доктора говорили ему, что с его корпуленцией, вино для него опасно, он очень много пил. Ему становилось вполне хорошо только тогда, когда он, сам не замечая как, опрокинув в свой большой рот несколько стаканов вина, испытывал приятную теплоту в теле, нежность ко всем своим ближним и готовность ума поверхностно отзываться на всякую мысль, не углубляясь в сущность ее. Только выпив бутылку и две вина, он смутно сознавал, что тот запутанный, страшный узел жизни, который ужасал его прежде, не так страшен, как ему казалось. С шумом в голове, болтая, слушая разговоры или читая после обеда и ужина, он беспрестанно видел этот узел, какой нибудь стороной его. Но только под влиянием вина он говорил себе: «Это ничего. Это я распутаю – вот у меня и готово объяснение. Но теперь некогда, – я после обдумаю всё это!» Но это после никогда не приходило.
Натощак, поутру, все прежние вопросы представлялись столь же неразрешимыми и страшными, и Пьер торопливо хватался за книгу и радовался, когда кто нибудь приходил к нему.
Иногда Пьер вспоминал о слышанном им рассказе о том, как на войне солдаты, находясь под выстрелами в прикрытии, когда им делать нечего, старательно изыскивают себе занятие, для того чтобы легче переносить опасность. И Пьеру все люди представлялись такими солдатами, спасающимися от жизни: кто честолюбием, кто картами, кто писанием законов, кто женщинами, кто игрушками, кто лошадьми, кто политикой, кто охотой, кто вином, кто государственными делами. «Нет ни ничтожного, ни важного, всё равно: только бы спастись от нее как умею»! думал Пьер. – «Только бы не видать ее, эту страшную ее ».

В начале зимы, князь Николай Андреич Болконский с дочерью приехали в Москву. По своему прошедшему, по своему уму и оригинальности, в особенности по ослаблению на ту пору восторга к царствованию императора Александра, и по тому анти французскому и патриотическому направлению, которое царствовало в то время в Москве, князь Николай Андреич сделался тотчас же предметом особенной почтительности москвичей и центром московской оппозиции правительству.
Князь очень постарел в этот год. В нем появились резкие признаки старости: неожиданные засыпанья, забывчивость ближайших по времени событий и памятливость к давнишним, и детское тщеславие, с которым он принимал роль главы московской оппозиции. Несмотря на то, когда старик, особенно по вечерам, выходил к чаю в своей шубке и пудренном парике, и начинал, затронутый кем нибудь, свои отрывистые рассказы о прошедшем, или еще более отрывистые и резкие суждения о настоящем, он возбуждал во всех своих гостях одинаковое чувство почтительного уважения. Для посетителей весь этот старинный дом с огромными трюмо, дореволюционной мебелью, этими лакеями в пудре, и сам прошлого века крутой и умный старик с его кроткою дочерью и хорошенькой француженкой, которые благоговели перед ним, – представлял величественно приятное зрелище. Но посетители не думали о том, что кроме этих двух трех часов, во время которых они видели хозяев, было еще 22 часа в сутки, во время которых шла тайная внутренняя жизнь дома.
В последнее время в Москве эта внутренняя жизнь сделалась очень тяжела для княжны Марьи. Она была лишена в Москве тех своих лучших радостей – бесед с божьими людьми и уединения, – которые освежали ее в Лысых Горах, и не имела никаких выгод и радостей столичной жизни. В свет она не ездила; все знали, что отец не пускает ее без себя, а сам он по нездоровью не мог ездить, и ее уже не приглашали на обеды и вечера. Надежду на замужество княжна Марья совсем оставила. Она видела ту холодность и озлобление, с которыми князь Николай Андреич принимал и спроваживал от себя молодых людей, могущих быть женихами, иногда являвшихся в их дом. Друзей у княжны Марьи не было: в этот приезд в Москву она разочаровалась в своих двух самых близких людях. М lle Bourienne, с которой она и прежде не могла быть вполне откровенна, теперь стала ей неприятна и она по некоторым причинам стала отдаляться от нее. Жюли, которая была в Москве и к которой княжна Марья писала пять лет сряду, оказалась совершенно чужою ей, когда княжна Марья вновь сошлась с нею лично. Жюли в это время, по случаю смерти братьев сделавшись одной из самых богатых невест в Москве, находилась во всем разгаре светских удовольствий. Она была окружена молодыми людьми, которые, как она думала, вдруг оценили ее достоинства. Жюли находилась в том периоде стареющейся светской барышни, которая чувствует, что наступил последний шанс замужества, и теперь или никогда должна решиться ее участь. Княжна Марья с грустной улыбкой вспоминала по четвергам, что ей теперь писать не к кому, так как Жюли, Жюли, от присутствия которой ей не было никакой радости, была здесь и виделась с нею каждую неделю. Она, как старый эмигрант, отказавшийся жениться на даме, у которой он проводил несколько лет свои вечера, жалела о том, что Жюли была здесь и ей некому писать. Княжне Марье в Москве не с кем было поговорить, некому поверить своего горя, а горя много прибавилось нового за это время. Срок возвращения князя Андрея и его женитьбы приближался, а его поручение приготовить к тому отца не только не было исполнено, но дело напротив казалось совсем испорчено, и напоминание о графине Ростовой выводило из себя старого князя, и так уже большую часть времени бывшего не в духе. Новое горе, прибавившееся в последнее время для княжны Марьи, были уроки, которые она давала шестилетнему племяннику. В своих отношениях с Николушкой она с ужасом узнавала в себе свойство раздражительности своего отца. Сколько раз она ни говорила себе, что не надо позволять себе горячиться уча племянника, почти всякий раз, как она садилась с указкой за французскую азбуку, ей так хотелось поскорее, полегче перелить из себя свое знание в ребенка, уже боявшегося, что вот вот тетя рассердится, что она при малейшем невнимании со стороны мальчика вздрагивала, торопилась, горячилась, возвышала голос, иногда дергала его за руку и ставила в угол. Поставив его в угол, она сама начинала плакать над своей злой, дурной натурой, и Николушка, подражая ей рыданьями, без позволенья выходил из угла, подходил к ней и отдергивал от лица ее мокрые руки, и утешал ее. Но более, более всего горя доставляла княжне раздражительность ее отца, всегда направленная против дочери и дошедшая в последнее время до жестокости. Ежели бы он заставлял ее все ночи класть поклоны, ежели бы он бил ее, заставлял таскать дрова и воду, – ей бы и в голову не пришло, что ее положение трудно; но этот любящий мучитель, самый жестокий от того, что он любил и за то мучил себя и ее, – умышленно умел не только оскорбить, унизить ее, но и доказать ей, что она всегда и во всем была виновата. В последнее время в нем появилась новая черта, более всего мучившая княжну Марью – это было его большее сближение с m lle Bourienne. Пришедшая ему, в первую минуту по получении известия о намерении своего сына, мысль шутка о том, что ежели Андрей женится, то и он сам женится на Bourienne, – видимо понравилась ему, и он с упорством последнее время (как казалось княжне Марье) только для того, чтобы ее оскорбить, выказывал особенную ласку к m lle Bоurienne и выказывал свое недовольство к дочери выказываньем любви к Bourienne.

Американский математик Кеннет Джордж Эрроу профессор Стэндфордского, Гарвардского и ряда других университетов, лауреат Нобелевской премии по экономике (1972г.) за пионерские работы в области теории общего экономического равновесия, заложил основы современной теории выбора, а его работа до сих пор определяет развитие этой теории.

В 1951г. Кеннет Эрроу, обобщив парадокс Кондорсе, доказал теорему о невозможности, суть которой состоит в том, что не существует правила коллективного выбора, способного одновременно удовлетворить следующие шесть требований:

Полнота. Правило должно обеспечивать выбор между любыми двумя альтернативами, отдавая предпочтение одной из них либо признавая обе равноценными.

Универсальность. Правило обеспечивает результативный выбор при любом сочетании индивидуальных предпочтений.

Транзитивность. Для любого набора из трех альтернатив x, y и z, если xRy и yRz, то xRz.

Единогласие. Если xRi y выполняется для любого i, т.е. все участники коллективного выбора отдают предпочтение первой из двух альтернатив, то xRy, иначе говоря, коллективный выбор совершается в пользу первой альтернативы (это не что иное, как выполнение требования Парето-оптимизации).

Независимость от посторонних альтернатив. Коллективный выбор между любыми двумя альтернативами x и y зависит от того, как индивиды оценивают эти две альтернативы по отношению друг кдругу, но не зависят от отношения индивидов к какой бы то ни было посторонней альтернативе z, (например, будет ли признано xRy, может зависеть, в частности, от того, верно ли, что xRiy, но не от того, справедливо ли, что xRiz или что xRjzRjy).

Отсутствие диктатора. Среди участников коллективного выбора нет такого индивида, любое предпочтение которого xRjy влекло бы за собой xRy независимо от предпочтений всех других индивидов.

Введя понятие рационального выбора, можно сформулировать теорему иным образом: выбор является рациональным, если он отвечает требованиям полноты и транзитивности. Рациональность индивидуального выбора - одна из ключевых аксиом микроэкономики.

Решающая коалиция - совокупность индивидов, входящих в общее число участников коллективного выбора и при единогласии внутри этой коалиции позиция ее членов становится результатом коллективного выбора. Решающей коалиция может быть только для конкретной пары альтернативных вариантов (а против в). Коалиции, которые являются решающими для любой допустимой пары альтернатив, называются решающими без указания конкретной пары.

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

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

История демократических институтов достаточно четко говорит о том, их решения далеко не всегда лучше частных решений. Руководствуясь решением ареопага, афиняне осудили на смерть Сократа и едва не казнили Аристотеля. Единогласно принимались решения коллективного руководящего органа НАТО о начале операции в Югославии и политбюро СССР о вводе ограниченного контингента в Афганистан. При этом последствия этих решений и в настоящее время до конца не ясны.

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

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

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

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

Можно заметить, что количество мнений, которые может высказать эксперт, равно n!, где n -- число кандидатов. Если экспертов m, то они могут высказаться (n!)^m способами. Функция обработки каждому из этих вариантов должна сопоставлять коллективное мнение. Поэтому число таких функций есть количество отображений множества из (n!)^m элементов во множество из n! элементов, т.е. равно (n!)^{n!^m}. Из всего этого изобилия теорема Эрроу оставляет нам только m способов, по числу экспертов. Уже при m=n=3 (см. одну из прошлых записей о манипуляции общественным мнением) количество способов обработки равно 6 в степени 216. Вместо этого астрономического 169-значного числа мы остаёмся только с тремя возможностями назначить одного из экспертов диктатором.

Доказательство будет проходить в несколько этапов. Цель -- выявить предполагаемого диктатора. Ключевой идеей является следующая. Пусть A, B -- некоторые кандидаты. Допустим, что одна часть экспертов поставила A выше B, а другая -- В выше A. Допустим, что в коллективном мнении А стоит выше B. Ясно тогда, что диктатор (если он имеется) находится в первой группе. Наш шанс угадать его тем выше, чем меньше по составу первая группа. В идеале хотелось бы иметь такую группу из одного человека, который и являлся бы диктатором. Это приводит к следующему определению.

Пусть X -- некоторая группа экспертов, все представители которой поставили кандидата A выше кандидата B, и пусть все остальные эксперты поступили наоборот. Допустим, что в коллективном мнении A стоит выше B. Тогда группу X назовём решающей коалицией относительно (упорядоченной) пары A, B.

Сделаем несколько замечаний. Данное определение корректно ввиду Принципа Независимости, так как знание порядка следования A и B друг относительно друга в мнении каждого из экспертов однозначно определяет их порядок следования в коллективном мнении. Отметим, что порядок, в котором мы называем кандидатов A, B в общем случае важен (т.е. априори не очевидно, что та же коалиция останется решающей относительно пары B, A). Ясно, что группа из всех экспертов всегда будет решающей относительно любой пары кандидатов ввиду Принципа Единогласия. По этой же причине решающая коалиция не может оказаться пустой, т.е. не содержать ни одного эксперта.

Группу экспертов будем называть просто решающей коалицией , если она является решающей относительно какой-нибудь пары кандидатов. Выберем теперь минимальную решающую коалицию, т.е. такую решающую коалицию M , в которую входит минимально возможное число экспертов. Установим последовательно три факта.

Лемма 1. Коалиция M состоит ровно из одного эксперта d.

Лемма 2. Эксперт d образует решающую коалицию для любой пары.

Лемма 3. Эксперт d -- диктатор.

Докажем Лемму 1. Пусть выбранная коалиция M является решающей относительно кандидатов A, B. В неё входит хотя бы один эксперт d. Рассмотрим три группы экспертов: 1) D ={d} (она состоит только из d), 2) M \ D (все эксперты из M кроме d) и 3) E \ M (все эксперты, не входящие в M ). Поскольку число кандидатов не меньше трёх, мы можем рассмотреть ещё одного кандидата C. Наша задача - показать, что либо коалиция D , либо коалиция M \ D будет также решающей (относительно некоторой пары с участием C). Ввиду минимальности коалиции M , отсюда сразу будет следовать, что M состоит только из d.

Предположим, что эксперты из каждой группы расставили кандидатов в следущем порядке:

1). .... A ..... B ..... C .....

3) ..... B ..... C ..... A .....

В коллективном мнении кандидат A стоит выше кандидата B, так как именно так постановили все эксперты из M (первая и вторая группы), а все остальные эксперты (третья группа) поступили в точности наоборот. Из Принципа Независимости вытекает, что порядок следования кандидатов A, B, C в коллективном мнении однозначно определён. Рассмотрим два случая.

а) Кандидат B стоит выше C в коллективном мнении. Тогда, с учётом того, что A стоит выше B, заключаем, что A стоит выше C. Но кто из экспертов поставил A выше C? Только эксперт d, а все остальные высказали противоположное мнение. Отсюда следует, что коалиция D из одного эксперта d будет решающей для пары A, C. Убедимся, что это на самом деле так. Рассмотрим произвольное голосование, в котором только d поставил в своём мнении A выше C, а остальные поступили наоборот. По Принципу Независимости, в коллективном мнении порядок следования A и C однозначно определён, в каком бы порядке ни были расположены все остальные. Поэтому можно считать без ограничения общности, что кандидат B в мнениях экспертов расположен так, как указано выше. При этом мы уже знаем, что в коллективном мнении A стоит выше C. Поэтому так будет всегда, стоит лишь эксперту d поставить A выше C, а остальным поступить наоборот.

Это рассуждение показывает, что в рамках рассматриваемого случая коалиция D ={d} будет решающей относительно пары A, С. В силу минимальности коалиции M , мы можем сделать вывод, что вторая группа не включает в себя ни одного эксперта, т.е. M совпадает с {d}.

б) Кандидат C стоит выше B в коллективном мнении. Тогда оказывается, что вторая группа образует решающую коалицию относительно пары C, B. Но это очевидным образом противоречит минимальности коалиции M .

Лемма 1 доказана.

Чтобы убедиться в справедливости Леммы 2, заметим, что для любого кандидата C должен иметь место случай а) из предыдущей леммы. Иными словами, эксперт d (наш "кандидат в диктаторы") образует решающую коалицию относительно пары A, C. Из соображений симметрии ясно, что этот же эксперт будет образовывать решающую коалицию и относительно пары C, B. Всё сказанное позволяет заключить, что если d образует решающую коалицию для какой-то пары, то он будет образовывать её для любой пары, в которой один из её элементов (первый или второй) заменён на какой-либо другой. Но от любой пары к любой можно при помощи таких замен перейти максимум за три шага -- наибольшего числа шагов требует переход от (A,B) к (B,A). Этот процесс напоминает известную игру по превращению слова МУХА в слово СЛОН при помощи замены букв, только в данной ситуации всё намного проще.

Итак, мы приходим к выводу, что {d} -- решающая коалиция для любой пары. Тем самым доказана Лемма 2, но это ещё не даёт возможности заключить, что d -- диктатор.

В самом деле, каковы бы ни были кандидаты A, B, мы пока не можем гарантировать, что предпочтение одного из них другому экспертом d немедленно повлечёт за собой, что именно в таком порядке эти кандидаты будут располагаться в коллективном мнении -- ведь нам ещё требуется, чтобы все остальные эксперты высказались наоборот. Покажем, что мнение эксперта d относительно порядка следования A, B всегда будет достаточным для того, чтобы и в коллективном мнении было так же. В этом состоит содержание Леммы 3, утверждающей, что d -- диктатор.

Итак, вновь разобьём всех экспертов на три группы: пусть первая группа состоит только из d, который поставил A выше B; во вторую группу пусть войдут те, кто высказался так же про этих кандидатов, а в третьей группе пусть будут все эксперты, поставившие B выше A (вторая или третья группа могут оказаться пустыми). Как и ранее, рассмотрим кандидата C, отличного от A и B. Рассмотрим такое голосование, при котором только d поставил A выше C, и все эксперты поставили C выше B:

1). .... A ..... C ..... B .....
2) ..... C ..... A ..... B .....
3) ..... C ..... B ..... A .....

Тогда в коллективном мнении A стоит выше C в силу того, что {d} -- решающая коалиция относительно A, C. По Принципу Единогласия, С в коллективном мнении опережает B. Следовательно, A в коллективном мнении расположен выше B, и для этого оказалось достаточным, чтобы так их расположил эксперт d.

Итак, d на самом деле является диктатором. Лемма 3 доказана, и вместе с ней доказана теорема Эрроу.

Теорема Эрроу (также известна как «Парадокс Эрроу», англ. Arrow’s paradox) - теорема о невозможности «коллективного выбора». Сформулирована американским экономистом Кеннетом Эрроу в 1951 году.

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

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

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

ТЕОРЕМА НЕВОЗМОЖНОСТИ ЭРРОУ

(Arrow\"s impossibility theorem) Теорема, согласно которой в экокомической модели, включающей нескольких человек, голосование большинством голосов отнюдь не всегда порождает равновесную ситуацию. Пусть три лица, 1, 2 и 3, последовательно ранжируют по степени предпочтения три ситуации, А, В и С. Если лицо 1 ставит ситуации в порядке А, В, С, лицо 2 – В, С, А, а лицо 3 – С, А, В, то при принятии нестратегического решения большинством голосов оказывается, что ситуация А предпочтительнее ситуации В, В предпочтительнее С, а С предпочтительнее А. Заметим, однако, что в данной теореме ничего не говорится о неизбежности столь парадоксального положения и даже о его вероятности, а всего лишь утверждается, что оно возможно в принципе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство теоремы Эрроу

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

≻i - предпочтения i-го агента; [≻"] - профиль предпочтений (кортеж, элементами которого являются предпочтения всех агентов);

W: Ln → L - функция общественного благосостояния; ≻W - коллективные предпочтения.

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

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

Парето эффективность

W парето эффективна, если для любых исходов o1, o2 ∈ O, ∀i (o1 ≻i o2) ⇒ (o1 ≻W o2)

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

W независима от посторонних альтернатив, если для любых исходов o1, o2 ∈ O и для любых двух профилей предпочтений [≻"] и [≻"] ∈ Ln, ∀i (o1 ≻i" o2 ⇔ o1 ≻i" o2) ⇒ (o1 ≻W([≻"]) o2 ⇔ o1 ≻W([≻"]) o2)

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

Считаем, что для W отсутствует диктатор, если не существует такого i, что ∀ o1, o2 ∈ O (o1 ≻i o2 ⇒ o1 ≻W o2)

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

Если |O| ≥ 3, то любая Парето эффективная, независящая от посторонних альтернатив функция общественного благосостояния W имеет диктатора.

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

Этап 1. Утверждение

Если каждый агент помещает исход b в самый верх или самый низ своего списка предпочтений, то и в ≻W исход b тоже будет либо вверху, либо внизу списка.

Возьмем произвольный профиль [≻] такой, что в нем для всех агентов i исход b расположен либо вверху, либо внизу списка предпочтений ≻i. Теперь допустим, что наше утверждение неверно, т.е. существуют такие a,c ∈ O, что a ≻W b и b ≻W c. Изменим тогда профиль [≻] так, чтобы для всех агентов выполнялось c ≻i a, не изменяя при этом ранжирования остальных исходов. Обозначим полученный профиль [≻"]. Так как после такой модификации исход b для каждого агента все равно останется либо на самой верхней, либо на самой нижней позиции в списке его предпочтений, то из независимости W от посторонних альтернатив можно заключить, что и в новом профиле a ≻W b и b ≻W c. Следовательно, в силу транзитивности ≻W получаем a ≻W c. Но мы предположили, что для всех агентов c ≻i a, тогда в силу парето эффективности должно быть c ≻W a. Полученное противоречие доказывает утверждение.

Этап 2. Утверждение

Существует агент, который является центральным в том смысле, что, изменив свой голос, он может переместить исход b из самой нижней позиции в списке ≻W в самую верхнюю позицию в этом списке.

Рассмотрим любой профиль предпочтений, в котором все агенты расположили исход b в самом низу своего списка предпочтений ≻i. Ясно, что и в ≻W исход b находится на самой нижней позиции. Пусть все агенты начали по очереди переставлять исход b с самой нижней на самую верхнюю позицию в своих списках предпочтений, не меняя при этом ранжирования остальных исходов. Пусть n* - агент, который переставив таким образом b, изменил ≻W. Обозначим [≻1] - профиль предпочтений как раз до того, как n* переместил b, а [≻2] - профиль предпочтений сразу же после того, как n* переместил b. Таким образом, в [≻2] исход b изменил свою позицию в ≻W, при этом для всех агентов b находится либо на самой верхней, либо на самой нижней позиции ≻i. Следовательно, в силу утверждения, доказанного на Этапе 1, в ≻W исход b занимает самую верхнюю позицию.

Этап 3. Утверждение

, не включающими в себя b.

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

Этап 4. Утверждение

n* - диктатор над всеми парами .

Рассмотрим какой-нибудь исход с. В силу Этапа 2 существует некоторый центральный агент n** для этого исхода, он же является диктатором для всех пар , где, в частности, A = a, B = b. Но n* и сам может менять ранжирование в ≻W (это рассматривалось на Этапе 2). Следовательно, можно заключить, что n** совпадает с n*. Доказательство завершено.