Теорема Эрроу о диктаторе (формулировка)
Как я обещал в предыдущей своей записи, приступаю к изложению Теоремы Эрроу о диктаторе. Никаких предварительных знаний для понимания как формулировки, так и доказательства не требуется. Формулировку я излагаю здесь, а доказательство идёт под "катом" в следующем отдельном посте. (Оно довольно длинное, поэтому может потребоваться некоторый запас терпения, чтобы его прочитать и понять.)
Эта теорема была доказана в начале 50-х годов. Я о ней впервые узнал при замечательных обстоятельствах. Было это 19 августа 1991 года в Барнауле. Мы приехали туда на алгебраическую конференцию. Туда же прибыл мой бывший однокурсник из Тбилиси. Мы сидели в гостиничном номере, пили привезённое им из Грузии вино и смотрели по телевизору пресс-конференцию Янаева. Я находился в состоянии полной эйфории, так как был несказанно обрадован созданием ГКЧП (я воспринимал эту меру как отстранение от власти горе-реформатора Горбачёва подобно тому, как был в своё время смещён Хрущёв). Надо сказать, что все собравшиеся также разделяли мои чувства. Под это дело моим сокурсником и была очень кстати рассказана Теорема Эрроу о диктаторе.
Надо сказать, что этот математический результат довольно специальный, поэтому в общеобразовательные университетские курсы он не входил. Я уже на протяжении многих лет рассказываю эту теорему студентам, читая спецкурс по дискретной математике. (Кстати, я несколько дней назад принимал у них по этой дисциплине экзамен, с чем и была связана задержка с размещением этого поста. Билет с теоремой Эрроу достался двум студентам, которые получили "5" и "4".)
Итак, вот сама теорема. Думаю, что формулировку понять должно быть весьма легко.
Пусть имеется некоторое количество экспертов и некоторое количество кандидатов. Каждый эксперт высказывает своё мнение о кандидатах, располагая их в некотором порядке, т.е. распределяя по местам. Требуется построить процедуру обработки мнений экспертов для выработки коллективного мнения, т.е. определить итоговое распределение мест, наилучшим образом отражающее мнения экспертов. При этом процедура должна удовлетворять следующим двум разумным требованиям:
Принцип Единогласия. Если каждый эксперт считает, что кандидат A лучше кандидата B, то и в коллективном мнении A должен стоять выше B.
Принцип Независимости. Расположение любых двух кандидатов A, B в коллективном мнении зависит только от того, в каком порядке эксперты расположили этих кандидатов и не зависит от того, как относительно них расположены другие кандидаты. Иными словами, если ни один из экспертов не менял своего мнения о том, кто из кандидатов A, B лучше или хуже другого, то и в коллективном мнении порядок следования этих кандидатов не должен измениться.
Предположим, что один из экспертов является диктатором, т.е. за коллективное мнение всегда принимается мнение этого эксперта. Тогда легко понять, что оба требуемых условия выполнены. Теорема Эрроу утверждает, что если кандидатов три или более, то не существует никаких других способов обработки, удовлетворяющих обоим Принципам, кроме назначения диктатором одного из экспертов. (Если кандидатов всего два, то возможны и другие способы обработки.)
Смысл теоремы можно истолковать так. Предположим, что создана некая процедура обработки мнений экспертов. Можно считать, что она реализована в виде "чёрного ящика", и любой желающий может протестировать её на предмет того, насколько она справедлива, вводя в неё те или иные "мнения" и получая итоговый результат обработки последних. Допустим, что нарушается Принцип Единогласия. Тогда мы можем столкнуться с такой ситуацией, что во всех мнениях A стоит выше B, а машина почему-то выдала вердикт, что B выше A. Если нарушается Принцип Независимости, то при нескольких сеансах тестирования может оказаться, что мы заведомо не меняли в мнениях экспертов порядок следования A и B, а в коллективном мнении этот порядок вдруг ни с того, ни с сего поменялся. Любая из таких ситуаций может породить сомнения в справедливости обработки результатов, вызывая споры. Лишь предоставление диктаторских функций одному из экспертов может нас гарантированно избавить от этого.
Конечно, следует оговорить, что делать из этой теоремы какие-либо радикальные выводы вряд ли основательно. Тем не менее, она заставляет задуматься о пределах применимости такого понятия как "коллективное мнение".
Эта теорема была доказана в начале 50-х годов. Я о ней впервые узнал при замечательных обстоятельствах. Было это 19 августа 1991 года в Барнауле. Мы приехали туда на алгебраическую конференцию. Туда же прибыл мой бывший однокурсник из Тбилиси. Мы сидели в гостиничном номере, пили привезённое им из Грузии вино и смотрели по телевизору пресс-конференцию Янаева. Я находился в состоянии полной эйфории, так как был несказанно обрадован созданием ГКЧП (я воспринимал эту меру как отстранение от власти горе-реформатора Горбачёва подобно тому, как был в своё время смещён Хрущёв). Надо сказать, что все собравшиеся также разделяли мои чувства. Под это дело моим сокурсником и была очень кстати рассказана Теорема Эрроу о диктаторе.
Надо сказать, что этот математический результат довольно специальный, поэтому в общеобразовательные университетские курсы он не входил. Я уже на протяжении многих лет рассказываю эту теорему студентам, читая спецкурс по дискретной математике. (Кстати, я несколько дней назад принимал у них по этой дисциплине экзамен, с чем и была связана задержка с размещением этого поста. Билет с теоремой Эрроу достался двум студентам, которые получили "5" и "4".)
Итак, вот сама теорема. Думаю, что формулировку понять должно быть весьма легко.
Пусть имеется некоторое количество экспертов и некоторое количество кандидатов. Каждый эксперт высказывает своё мнение о кандидатах, располагая их в некотором порядке, т.е. распределяя по местам. Требуется построить процедуру обработки мнений экспертов для выработки коллективного мнения, т.е. определить итоговое распределение мест, наилучшим образом отражающее мнения экспертов. При этом процедура должна удовлетворять следующим двум разумным требованиям:
Принцип Единогласия. Если каждый эксперт считает, что кандидат A лучше кандидата B, то и в коллективном мнении A должен стоять выше B.
Принцип Независимости. Расположение любых двух кандидатов A, B в коллективном мнении зависит только от того, в каком порядке эксперты расположили этих кандидатов и не зависит от того, как относительно них расположены другие кандидаты. Иными словами, если ни один из экспертов не менял своего мнения о том, кто из кандидатов A, B лучше или хуже другого, то и в коллективном мнении порядок следования этих кандидатов не должен измениться.
Предположим, что один из экспертов является диктатором, т.е. за коллективное мнение всегда принимается мнение этого эксперта. Тогда легко понять, что оба требуемых условия выполнены. Теорема Эрроу утверждает, что если кандидатов три или более, то не существует никаких других способов обработки, удовлетворяющих обоим Принципам, кроме назначения диктатором одного из экспертов. (Если кандидатов всего два, то возможны и другие способы обработки.)
Смысл теоремы можно истолковать так. Предположим, что создана некая процедура обработки мнений экспертов. Можно считать, что она реализована в виде "чёрного ящика", и любой желающий может протестировать её на предмет того, насколько она справедлива, вводя в неё те или иные "мнения" и получая итоговый результат обработки последних. Допустим, что нарушается Принцип Единогласия. Тогда мы можем столкнуться с такой ситуацией, что во всех мнениях A стоит выше B, а машина почему-то выдала вердикт, что B выше A. Если нарушается Принцип Независимости, то при нескольких сеансах тестирования может оказаться, что мы заведомо не меняли в мнениях экспертов порядок следования A и B, а в коллективном мнении этот порядок вдруг ни с того, ни с сего поменялся. Любая из таких ситуаций может породить сомнения в справедливости обработки результатов, вызывая споры. Лишь предоставление диктаторских функций одному из экспертов может нас гарантированно избавить от этого.
Конечно, следует оговорить, что делать из этой теоремы какие-либо радикальные выводы вряд ли основательно. Тем не менее, она заставляет задуматься о пределах применимости такого понятия как "коллективное мнение".