Теорема Эрроу о диктаторе (формулировка)

Теорема Эрроу о  диктаторе (формулировка)

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

Эта теорема была доказана в начале 50-х годов. Я  о ней впервые узнал при  замечательных обстоятельствах. Было это 19 августа 1991 года в Барнауле. Мы приехали туда на алгебраическую конференцию. Туда же прибыл мой бывший однокурсник  из Тбилиси. Мы сидели в гостиничном  номере, пили привезённое им из Грузии вино и смотрели по телевизору пресс-конференцию  Янаева. Я находился в состоянии  полной эйфории, так как был несказанно обрадован созданием ГКЧП (я воспринимал  эту меру как отстранение от власти горе-реформатора Горбачёва подобно  тому, как был в своё время смещён Хрущёв). Надо сказать, что все собравшиеся  также разделяли мои чувства. Под это дело моим сокурсником  и была очень кстати рассказана Теорема  Эрроу о диктаторе.  

Надо сказать, что  этот математический результат довольно специальный, поэтому в общеобразовательные  университетские курсы он не входил. Я уже на протяжении многих лет  рассказываю эту теорему студентам, читая спецкурс по дискретной математике. (Кстати, я несколько дней назад  принимал у них по этой дисциплине экзамен, с чем и была связана  задержка с размещением этого  поста. Билет с теоремой Эрроу  достался двум студентам, которые получили "5" и "4".) 

Итак, вот сама теорема. Думаю, что формулировку понять должно быть весьма легко. 

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

Принцип Единогласия. Если каждый эксперт считает, что  кандидат A лучше кандидата B, то и  в коллективном мнении A должен стоять выше B. 

Принцип Независимости. Расположение любых двух кандидатов A, B в коллективном мнении зависит  только от того, в каком порядке  эксперты расположили этих кандидатов и не зависит от того, как относительно них расположены другие кандидаты. Иными словами, если ни один из экспертов не менял своего мнения о том, кто из кандидатов A, B лучше или хуже другого, то и в коллективном мнении порядок следования этих кандидатов не должен измениться. 

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

Смысл теоремы можно  истолковать так. Предположим, что  создана некая процедура обработки  мнений экспертов. Можно считать, что  она реализована в виде "чёрного  ящика", и любой желающий может  протестировать её на предмет того, насколько она справедлива, вводя  в неё те или иные "мнения" и получая итоговый результат  обработки последних. Допустим, что  нарушается Принцип Единогласия. Тогда  мы можем столкнуться с такой  ситуацией, что во всех мнениях A стоит  выше B, а машина почему-то выдала вердикт, что B выше A. Если нарушается Принцип  Независимости, то при нескольких сеансах  тестирования может оказаться, что  мы заведомо не меняли в мнениях  экспертов порядок следования A и B, а в коллективном мнении этот порядок  вдруг ни с того, ни с сего поменялся. Любая из таких ситуаций может  породить сомнения в справедливости обработки результатов, вызывая  споры. Лишь предоставление диктаторских функций одному из экспертов может  нас гарантированно избавить от этого. 

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

Теорема Эрроу о  диктаторе (доказательство)

 Ниже идёт доказательство  теоремы, сформулированной в предыдущей  записи.  

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

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

2) ..... C ..... A ..... B .....

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 доказана, и вместе с ней доказана теорема  Эрроу.