Эффект эрроу заключается в том что. Теоремы эрроу и гиббарда-саттертуэйта

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

Канке В.А., Философия науки: краткий энциклопедический словарь, М., «Омега-Л», 2008 г., с. 309.

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому результат Эрроу называют «теоремой невозможности».

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

Можно заметить, что количество мнений, которые может высказать эксперт, равно 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*. Доказательство завершено.

Теорема Эрроу (также известна как «Парадокс Эрроу », англ. 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.

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

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

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

Рассмотрим различные формулировки теории:

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

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

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

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

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

Формулировка 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) - агент, который переставив таким образом b, изменил?W. Обозначим [?1] - профиль предпочтений как раз до того, как n* переместил b, а [?2] - профиль предпочтений сразу же после того, как n* переместил b. Таким образом, в [?2] исход b изменил свою позицию в?W, при этом для всех агентов b находится либо на самой верхней, либо на самой нижней позиции?i. Следовательно, в силу утверждения, доказанного на Этапе 1, в?W исход b занимает самую верхнюю позицию.

Этап 3. Утверждение. Выберем из пары любой элемент. Без потери общности, выберем 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. n* - диктатор над всеми парами .

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