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

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

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

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

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

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

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

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

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

Полнота 

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

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

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

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

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

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

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

Для N≥2 и n≥3 не существует системы голосования, которая отвечает всем пяти условиям.

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

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

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

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

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

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

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

Для N≥2 и n≥3 не существует системы голосования, которая отвечает всем четырём условиям.

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

К:Википедия:Статьи без источников (тип: не указан)

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

• <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>[\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)</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>с</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> и есть диктатор.

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

См. также

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

Ссылки

• [ecsocman.hse.ru/data/2010/05/22/1213970517/13_04_06.pdf Теорема о невозможности в задаче пропорционального представительства]
• [web.archive.org/web/20040902034619/www.svasiljev.boom.ru/arrow.htm Кардиналистское голосование: Путь преодоления парадоксов социального выбора]

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

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


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