Falcão (falcao) wrote,
Falcão
falcao

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

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

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

Можно заметить, что количество мнений, которые может высказать эксперт, равно 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 доказана, и вместе с ней доказана теорема Эрроу.
Tags: математика
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 8 comments