by falcao

О МАНИПУЛЯЦИИ ОБЩЕСТВЕННЫМ МНЕНИЕМ

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

      Эксперт A
        1. водка
        2. пиво
        3. вино

      Эксперт B
        1. пиво
        2. вино
        3. водка

      Эксперт C
        1. вино
        2. водка
        3. пиво
Здесь не важно, отражает ли реальную ситуацию мнение этих экспертов. Кто-то из них мог лоббировать те или иные интересы. Важно то, как эти мнения можно интерпретировать.

Вот, допустим, выступает "водочный король". Он утверждает, что, по данным опроса, первое место заняла водка. Конечно, это так. Водка популярнее пива, так как два эксперта из трёх - A и C (т.е. большинство) придерживаются такого мнения. Пиво же популярнее вина по мнению экспертов A и B. Поэтому именно водка занимает первое место.

Но вот на авансцену выходит "пивной король". Эксперты A и B сказали, что пиво популярнее вина. А вино популярнее водки по мнению большинства экспертов - так думают B и C. Так что пиву - нет альтернативы.

Уже возникает противоречие, но тут выходит всеми забытый "винный король". Он говорит: что за дела? Вино стоит выше водки - это признают двое из трёх, B и C. А водка главнее пива - об этом свидетельствуют мнения A и C.

О чём говорит этот простой пример? Не о том ли, что "мнение большинства" (по мало-мальски сложным вопросам) - это некая умственная фикция, которой ничто не соответствует в реальности, но которая может служить средством манипуляции?

Один, довольно знаменитый, математический результат о невозможности объективной выработки "коллективного мнения" - это так называемая "Теорема Эрроу о диктаторе". (Кеннет Эрроу - лауреат премии по экономике шведского банка, 1972 год) Любопытно, что для понимания как формулировки, так и доказательства никаких специальных знаний не требуется.

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

ТЕОРЕМА ЭРРОУ О ДИКТАТОРЕ (ФОРМУЛИРОВКА)

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

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

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

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

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

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

Смысл теоремы можно истолковать так.

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

Допустим, что нарушается Принцип Единогласия.

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

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

Любая из таких ситуаций может породить сомнения в справедливости обработки результатов, вызывая споры. Лишь предоставление диктаторских функций одному из экспертов может нас гарантированно избавить от этого.

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

В любом случае, видно, что принцип независимости запрещает довольно естественные вещи.

Например, одно дело когда A и B в чьем-то рейтинге стоят рядом, и совсем другое если между ними еще сто человек. А принцип независимости это никак не учитывает.

Принцип Независимости, конечно, можно подвергать той или иной критике. Но в Вашем примере от ситуации, когда A и B стоят рядом, можно по шагам перейти к ситуации, когда их разделяет 100 человек. Из соображений "дискретной непрерывности" ясно, что на каком-то из шагов вердикт относительно рассматриваемых кандидатов поменяется. Такая перемена вряд ли может быть разумно обоснована - например, A и B разделяло 12 человек, а потом между ними вставили 13-го. И вдруг 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 доказана, и вместе с ней доказана теорема Эрроу.

    QED

    flaass
    Попробую упростить.

    1. Что значит, "способ обработки"? Это одна N-арная булева функция: для пары кандидатов А,В и N мнений экспертов она выдает "общее мнение". Принцип независимости влечет, что эта функция корректно определена, принцип единогласия - что она сохраняет единогласное мнение. Очевидно так же, что она антисимметрична (просто поменяем местами А и В).

    2. Для одного или двух экспертов единогласная и антисимметричная функция единственна - и такая, как нам надо, т.е. диктаторская.

    3. Итак, надо лишь показать, как для любой не-диктаторской функции от трех и более переменных найти N упорядочений трех кандидатов, которые при применении этой функции дают замкнутый цикл.

    Это и делается в доказательстве, но явное произнесение этих трех вещей может прояснить ситуацию.

    migmit
    Пусть A - некоторое подмножество экспертов. Пусть при некотором выборе из двух кандидатов x и y эксперты из множества A высказались за x, а остальные - за y. Если в результате будет выбран x - то множество A будем называть решающим. Систему всех решающих множеств обозначим через F. Зная F, мы знаем какой выбор сделает комитет экспертов при выборе из двух кандидатов; согласно принципу независимости, этого достаточно для определения, какой выбор они сделают при выборе из многих кандидатов.

    Далее:

    1) Для любого множества экспертов система F содержит либо его, либо дополнение к нему. Это прямо следует из определения решающего множества.

    2) F замкнуто относительно бинарных пересечений. Действительно, пусть A и B - решающие множества. Рассмотрим трёх кандидатов x, y и z. Пусть теперь:

  • эксперты из A ∩ B упорядочат их как x y z
  • эксперты из A\B - как z x y
  • эксперты из B\A - как y z x
  • а все остальные - как z y x
  • Тогда:

  • кандидата x предпочли кандидату y все эксперты из A и только они - значит, x будет в итоге предпочтён y.
  • Аналогично, кандидата y предпочли z все эксперты из B и только они - значит, y будет предпочтён z.
  • Следовательно, x будет предпочтён z - но так решили только эксперты из пересечения A и B. Значит, это пересечение принадлежит F.

    3) F вместе с каждым множеством содержит все большие его.
    Действительно, если A принадлежит F, а B - нет, причём B содержит A, то по пункту 1 F содержит дополнение B, а по пункту 2 - пересечение A с дополнением B - то есть, пустое множество. По принципу единогласия, пустое множество решающим быть не может.

  • 2 + 3 есть в точности определение фильтра,
  • а 1 гарантирует, что он является ультрафильтром.
  • Вот, собственно, и доказательство теоремы Эрроу (ибо на конечном множестве неглавных ультрафильтров нет).

    falcao
    Первоначально услышанное мной доказательство именно на языке ультрафильтров и было изложено. Конечно, в таком виде оно выглядит короче. Но я имел в виду популярное доказательство, доступное в принципе и школьникам. Если перевести с одного языка на другой, то как раз что-то такое и получится.

    В пункте 2 у Вас рассмотрены не все случаи. Те упорядоченные пары, для которых коалиции A и B решающие, у Вас имеют ровно один общий элемент. Нужно ещё охватить случаи

  • A(x,y) & B(x,y)
  • A(x,y) & B(y,x)
  • A(x,y) & B(z,t)
  • migmit
    Зачем? Я просто привожу пример "входных данных" для чёрного ящика. Мне не нужно рассматривать ДРУГОЙ пример.

    falcao
    Этого я не понял. Какое у Вас определение решающего множества? Я воспринял его так: A называется решающим, если существуют такие x,y, что из условия "все эксперты из A проголосовали за x, а остальные за y" следует, что в коллективном мнении x стоит выше y. Я обозначаю этот факт в виде A(x,y). Когда Вы доказываете пункт 2, то A и B - решающие. Но относительно каких пар? Вы доказываете, что если A(x,y) и B(y,z), то С(x,z), где C =A ^ B.

    Кстати, и в пункте 1 Вы выводите из A(x,y), что неверно D(y,x), где D - дополнение для A. Но почему D не может оказаться решающим для другой пары? Может быть, я определение не так понял?

    migmit
    Решающее - не бывает относительно чего-то. Оно вообще - решающее.

    Дело в том, что если A(x,y), то A(z,t) для любых z и t: если все эксперты из A и только они выскажутся за z против t - то выбран будет z. Ибо процедура голосования от личностей кандидатов не зависит, она зависит только от мнений экспертов.

    >> Вы доказываете, что если A(x,y) и B(y,z), то С(x,z), где C=A ^ B
    Правильно. И это означает, что коль скоро A и B решающие, то и C - тоже.

    >> Кстати, и в пункте 1 Вы выводите из A(x,y), что неверно D(y,x), где D - дополнение для A. Но почему D не может оказаться решающим для другой пары? Может быть, я определение не так понял?
    Гррр. Если все эксперты из D и только они выскажутся за кандидата z против t, то эксперты из A и только они выскажутся за t против z. А поскольку A - решающее, то выбран будет t. Значит, D - не решающее.

    falcao
    ОК. То есть определение решающего множества у Вас, стало быть, такое: A решающее, если A(x,y) для любой пары кандидатов. Тогда с доказательством пункта 2 проблем нет.

    > Ибо процедура голосования от личностей кандидатов не зависит, она зависит только от мнений экспертов.
    Вот эту мысль я не понял. Откуда следует, что из A(Петя,Вася) следует A(Федя,Коля)? Допустим, что все эксперты из A предпочли Петю Васе и Федю Коле, а все эксперты из дополнения D поступили наоборот. В коллективном мнении Петя оказался лучше Васи, а Коля - лучше Феди. Почему так не может быть? То есть при таком определении возникают трудности с доказательством пункта 1.

    migmit
    Прежде всего: обозначение A(x,y) мне не нравится. Давайте обозначим через (A) следующее утверждение: если в выборах принимают участие только два кандидата, эксперты из множества A высказались за первого, а эксперты из дополнения A - за второго, то выбран будет первый. Замечу, что здесь не учитываются личности кандидатов; я считаю, что результат голосования зависит ТОЛЬКО от того, как высказались эксперты, но не от имени кандидата, цвета его волос и т.п. Иначе говоря, процедура голосования - "чёрный ящик" со входами - голосами экспертов, и выходом - "мнением коллектива". Других входов у чёрного ящика нет. Тогда (A) и означает как раз, что A - решающее множество. По принципу независимости, тот же результат "соревнования" между x и y будет иметь место и в том случае, когда в выборах принимают участие другие кандидаты.

    falcao
    Обозначение A(x,y) вполне корректно. Рассматривать случай, когда в выборах принимает участие только два кандидата, мы не можем, так как число кандидатов заранее фиксируется. Машина не должна уметь обрабатывать мнения о неполном числе кандидатов. Такое можно было бы позволить, но это привело бы к более слабому утверждению.

    Ввиду принципа независимости, в этом даже нет необходимости, и потому предикат можно определить и так. Но главное не в этом. Вы просто неявно принимаете дополнительную аксиому, которой нет в условии. Можно было бы назвать её Принципом Инвариантности. Это означает, что если мы переименуем кандидатов, т.е. заменим i-го кандидата на кандидата с номером s(i) в мнениях всех экспертов, где s -- некоторая подстановка, то и в коллективном мнении должна осуществиться ровно такая же подстановка. Именно это подразумевается, когда говорится, что ничего не зависит от имени или цвета волос кандидата. Я не спорю, что такая аксиома соответствует требованиям здравого смысла. Но она сильно упрощает задачу. Если её принять, то Ваше доказательство, безусловно, проходит.

    У Эрроу было 4 аксиомы. Одна говорила о том, что машина должна уметь обрабатывать любые мнения. Это в данной мной формулировке упрятано в понятие всюду определённой функции. Второй и третьей аксиомами были единогласие и независимость, а четвёртой -- отсутствие "диктаторов". Заключением теоремы было утверждение о невозможности построения требуемой функции. Инвариантности относительно перестановок, которая сильно упрощает доказательство, в оригинале не было.

    Помимо математических соображений, есть и ещё одно. Машина "заточена" под данное конкретное голосование. Всем известен список и конретных экспертов, и конкретных кандидатов. Создатели машины могут принимать во внимание что угодно вплоть до того, что эксперт номер i подкуплен кандидатом номер j. Им важно лишь создать и опубликовать такую функцию обработки, чтобы избежать споров определённого типа. Отсутствие инвариантности таких споров породить не может, так как оцениваемые кандидаты заведомо не равны, и это все знают.