Теорема Ауманна о согласии: согласие ни при чем (ч.1)

Что если я скажу вам, что вторая по известности среди рационалистов математическая теорема - является наиболее неверно понимаемой? Причем до такой степени, что относительно ее сути заблуждались Элиезер Юдковский, Скотт Ааронсон и сам автор теоремы Роберт Ауманн. Звучит дико, и я сам был озадачен в свое время не меньше вашего (и до сих пор сильно озадачен), но позвольте мне объясниться. Прежде чем пояснять, почему же все эти уважаемые (и отнюдь не чуждые математике) люди, действительно ошибаются, я расскажу, в чем же на самом деле суть теоремы Ауманна.

Общее знание

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

• все в этой группе знают, что небо синее;
• все знают, что все знают, что небо синее;
• все знают, что все знают, что все знают, что небо синее;
• ... и так далее до бесконечности.

Важно отметить, что даже если всем известно, что небо синее, но хотя бы один человек в группе не уверен, что всем остальным этот факт известен - общего знания о синеве неба в группе нет. И вообще, если хоть на одном этапе из этого бесконечного ряда утверждений у кого-то возникает сомнение в знаниях остальных - общего знания о факте нет.

Чтобы точнее понять суть этого понятия, рассмотрим конкретный пример того, как формируется приближение к общему знанию. Пусть у нас есть группа из двух людей - Алиса и Боб, и есть коробка, в которой находится чайник. Вот как факт о том, что в коробке находится чайник, по шагам приближается к общему знанию между Алисой и Бобом:

• Алиса открыла коробку и увидела, что там чайник ⇒ Алиса знает, что в коробке был чайник;
• Боб в этот момент увидел Алису через приоткрытую дверь ⇒ Боб знает, что Алиса знает, что в коробке чайник [для простоты здесь и далее не будем раскрывать, что Боб знает, что в коробке чайник; это делается в точности аналогично, но с отставанием на один шаг];
• В момент открытия коробки Алиса заметила Боба в зеркале ⇒ Алиса знает, что Боб знает, что Алиса знает, что в коробке чайник;
• Боб заметил, как Алиса пристально посмотрела через зеркало прямо на него ⇒ Боб знает, что Алиса знает, что Боб знает, что Алиса знает, что в коробке чайник;
• Алиса заметила, как Боб смутился, поймав ее взгляд ⇒ Алиса знает, что Боб знает, что Алиса знает, что Боб знает, что Алиса знает, что в коробке чайник...
• Далее мне становится труднее продолжать расписывать эту красочную сцену, но в теории это можно делать до бесконечности (и не забываем, что начиная со второго шага между Алисой и Бобом начинает распространяться знание, что Боб знает, что в коробке чайник).

Конечно, на практике довольно сложно создать абсолютно точное общее знание (Алиса могла не заметить реакции Боба на ее взгляд и предположить, что тот думает, что остался незамеченным ⇒ наличие чайника в коробке больше не является общим знанием). Однако, хорошим приближением будет являться "факт X был четко и недвусмысленно озвучен при полном собрании всей группы людей". Уже начиная с этого можно строить практические выводы, основанные на наличии достаточно приличного подобия общего знания.

Теорема Ауманна

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

Итак, сформулируем (сравнительно строго) теорему для группы из двух агентов (на N агентов она расширяется тривиально).

• Рассмотрим двух агентов - Алису и Боба, между которыми является общим знанием тот факт, что оба они идеальные байесианцы.
• Пусть вся известная им двоим информация о некой (для простоты - изолированной от прочих) области знаний также является общим знанием между ними (т.е. ранее они в явном виде обменялись всей этой информацией, сделав ее общим знанием; при этом честность обоих в момент обмена информацией также являлась общим знанием).
• Теперь Алиса и Боб хотят поставить дополнительные эксперименты, чтобы получить новую информацию об этой области знаний (у каждого из них свой собственный набор экспериментов, которые могут частично совпадать, но могут быть полностью различны); суть и все возможные исходы каждого из экспериментов (но не реальный исход, который определится лишь в будущем и пока не известен ни одному из них) также являются общим знанием между ними.
• Обменявшись указанной выше информацией, Алиса и Боб разъехались в разные концы мира; каждый из них провел целиком всю свою серию экспериментов; в результате каждому стало известно что-то, чего может не знать второй (хотя с точки зрения всезнающего внешнего наблюдателя может оказаться, что какой-то факт известен им обоим, хотя сами они могут об этом не догадываться). При этом ключевым моментом является то, что с того момента, как они разъехались, и до самого конца применения теоремы включительно (и, если желаете, вообще на веки вечные) Алиса и Боб не обменялись ни единым битом информации ни прямо, ни косвенно, и вообще никак не общались и ни разу не встречались.
• В озвученных условиях Теорема Ауманна и свойства общего знания теперь говорят нам, что Алиса - после проведения своих экспериментов (в результате которых она открыла для себя множество новых фактов) - не знает, каковы результаты экспериментов Боба; однако, она может определить (зная о сути экспериментов Боба и имея в виду всё прочее их общее знание), какие из этих новых фактов все же являются их новым общим знанием. Точно так же и Боб в состоянии определить, какие из ставших доступных ему новых фактов являются общим знанием (при условии, что Алиса независимо от него также довела до конца всю серию своих экспериментов). Наконец - важнейший вывод: этот набор фактов (новое общее знание), до которого дошел каждый из них, у них обоих в точности совпадает; при этом, естественно, все выводы, которые опираются лишь на "старое общее знание"+"новое общее знание" (и ни на какие иные факты) у них также совпадут, и по сути тоже будут являться частью нового общего знания (хотя со своей стороны каждый может добавить еще что-то содержательное - например, пользуясь фактами, которыми владеет эксклюзивно).
• Вообще-то, на этом всё содержательно интересное в теореме как таковой заканчивается. Правда, если вспомнить общую формулу теоремы "Пусть A, B и C. Если в этих условиях верно X, то верно Y" - то это была часть "Пусть". Для полноты описания упомянем также тривиальнейшую часть "Если-То". А именно. Обозначим весь текущий массив общего знания Алисы и Боба (в момент "после проведения обоими их экспериментов") за ОЗ. Если не только фактически полученные результаты экспериментов, но и ни один мыслимый результат ни одного из их экспериментов (лишь бы только такой результат не противоречил ОЗ) не мог бы дать о некоем факте Ф никакой новой информации сверх той, что была получена об Ф на основе только лишь ОЗ, то тогда все апостериорные выводы Алисы и Боба относительно Ф с неизбежностью совпадут (и вообще-то, будут являться частью этого общего знания).
• Наш вывод можно приложить не только к эпистемологии, но и к совместным действиям и получить уже чуть менее тривиальные результаты. Действительно, несложно действовать скоординированно с другими агентами, если вы заранее синхронизировали свое знание с ними (в частности, ваш совместный план действий); если вы позже узнали что-то новое - хорошо бы обсудить это знание (иначе может получиться "кто в лес, кто по дрова", а мы хотели бы действовать максимально скоординированно для получения наилучшего результата). Тривиальное следствие из теоремы Ауманна, тем не менее говорит нам о том, что иногда ничего обсуждать не требуется. Хотя Алиса и Боб обладают принципиально разным набором информации и не имеют возможности ей обменяться, они, тем не менее, способны действовать совместно в довольно широких пределах - так, как будто бы они подробно обсудили все факты из их нового общего знания и следующие из них выводы, и приняли решение совместно действовать на их основе (хотя и утаив друг от друга все прочие результаты своих экспериментов).

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

Итак. Город Бердичев. Шеф и Коллега расследуют убийство. У них есть ровно четверо подозреваемых: три маленькие бабушки из дома престарелых - Агата, Барбара и Клэр, а также один бывший спецназовец, двухметровый шкаф Дональд. Точно известно, что убийца - один из этих четверых.

Наши братья пилоты разбирают личные дела всех четырех подозреваемых и видят, что телосложение всех бабушек очень похоже, телосложение же Дональда разительно отличается. При этом в медицинских картах сказано, что Агата имеет первую группу крови, Барбара и Клэр - вторую, Дональд - третью; четвертой нет ни у кого. Агата, Барбара и Клэр живут в одном доме престарелых на севере Бердичева, Дональд - в загородном доме на юге. Во второй половине дня все четверо всегда находятся у себя дома.

И вот в разгар работы, после того, как вся вышеупомянутая информация была подробно обсуждена нашими героями, в комнату входит Карбофос и заявляет: "Мы нашли свидетеля, который видел силуэт убийцы, входящего в квартиру жертвы. Кроме того, на месте преступления найдена кровь убийцы, мы отправили ее на судмедэкспертизу".

"Что будем делать, Шеф?" - спрашивает Коллега. "Будем брать! - отвечает Шеф. - Но сначала, Коллега, съездите-ка к экспертам и узнайте группу крови убийцы, а я съезжу опрошу свидетеля. В пять часов вечера встречаемся на месте. Если это Дональд, то придется вызывать группу захвата." После этого Шеф и Коллега разъехались по делам.

Далее мы в нашем рассказе будем для определенности считать, что убийца - Агата. Что же произошло далее, и о чем думали Шеф и Коллега?

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

Теперь проследим за мыслями Коллеги. Итак, он подумал следующее: "Я знаю, что убийца - Агата; она имеет телосложение бабушки; значит, Шефу сказали, что убийца имеет телосложение бабушки, и теперь это все, что ему известно о личности убийцы. Теперь я знаю, что убийца - Агата, и знаю, что Шеф знает, что убийца - одна из бабушек."

Шеф же подумает так: "Я знаю, что это - либо Агата (первая группа крови), либо Барбара (вторая группа), либо Клэр (снова вторая группа), но точно не Дональд (не третья группа). Значит, эксперты могли сказать Коллеге, что кровь была либо первой группы, либо второй; но точно не третьей. Я не знаю точно, что сказали эксперты, но Коллега либо знает, что убийца - Агата, либо знает, что убийца - одна из двоих: Барбара либо Клэр. В любом случае, он уж наверняка знает, что убийца - одна из бабушек. Большего я не могу сказать с уверенностью. Так что я знаю, что это одна из бабушек, и Коллега точно знает, что это одна из бабушек (на самом деле, ему известно даже больше, но что именно - я не знаю)."

Коллега, определив со своей стороны совершенно точно, что же сказал Шефу свидетель (даром что Коллеги там и вовсе не было, и со свидетелем он никогда не общался!), может в точности восстановить приведенный выше ход рассуждений Шефа. Теперь Коллега знает, что Шеф знает, что Коллега знает, что убийца - одна из бабушек. Аналогично и Шеф понимает, что Коллега в курсе, что Шеф знает, что убийца - одна из бабушек.

На этом этапе их общее знание стабилизируется. Теперь, хотя Шеф и Коллега после своего отъезда не обмолвились ни словом, у них есть общее знание, что убийца - одна из бабушек. В пять часов вечера они оба подъедут к дому престарелых на севере Бердичева, и ни один из них не озаботится вызовом группы захвата или хотя бы звонком другому: "Это не спецназовец, группа захвата не нужна, не пытайтесь ее позвать" - они оба прекрасно знают, что это абсолютно излишне. Конечно, в пять часов Коллега обрадует Шефа тем, что они стопроцентно установили личность убийцы, но собраться в одном месте и не вызывать группу захвата они смогут и без этого.

Напоследок хочется подчеркнуть разницу между "общим знанием", "индивидуальным знанием" и "объединенным знанием". Для этого немного модифицируем наш пример - пусть первая группа крови будет не только у Агаты, но и у Дональда (а у Барбары и Клэр - все так же вторая). Тогда (при условии, что убийца - по-прежнему Агата) у Шефа индивидуальное знание будет "убийца либо Агата, либо Барбара, либо Клэр", а у Коллеги - "убийца либо Агата, либо Дональд". Их общее знание при этом не изменится ни на йоту по сравнению с тем, что было утром: "убийца - либо Агата, либо Барбара, либо Клэр, либо Дональд". Действительно, Коллега подумает: "ну это либо Агата, либо Дональд, но кто именно - я не знаю; значит, я не представляю, какое телосложение у убийцы, и, стало быть, что скажет о нем Шефу свидетель; если это Агата - то телосложение бабушки, и тогда Шеф будет думать, что это Агата, либо Барбара, либо Клэр; если это Дональд - то телосложение спецназовца, и Шеф будет знать, что это Дональд; короче, я понятия не имею, что думает Шеф". У Шефа будет аналогичная проблема, но уже очевидно, что он и подавно не знает, что думает Коллега о том, что думает сам Шеф (помимо того, что им было известно с самого начала). Так что Шеф, конечно, знает, что группу захвата вызывать не надо, и нужно ехать в дом престарелых, а вот Коллега - нет; для совместных действий им придется пообщаться. Конечно, после того, как они объединят свои знания, то они надежно установят то, что не было известно ни одному из них: что убийца - именно Агата, и никто иной.

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

Конечно, когда два агента явным образом обменялись знаниями друг с другом, их объединенное знание становится также и общим (они ведь оба в курсе, что оба владеют объединенным знанием, и что второй тоже в курсе этого - ну и так далее). А вот три агента, встречаясь лишь попарно, могут обладать одинаковым и максимально полным объединенным знанием, но это не обязательно будет общим знанием (если, например, Боб и Чарли встретились и полностью обменялись своими знаниями, но у Алисы нет об этом общего знания хотя бы с одним из них).

Итак, теорема Ауманна вовсе не о том, что два рационалиста ни при каких условиях не могут согласиться не соглашаться (это-то - вообще тривиальный факт). Она о том, что при некоторых условиях два рационалиста не имеют возможности не согласиться. Т.е. речь идет не о ситуации, когда Алиса говорит: "Я считаю, что А", а Боб говорит: "А я считаю, что Б. Странно, мы вроде оба нормальные рационалисты. Давай кракситься" и Алиса отвечает: "Давай." Нашим случаем скорее будет вот что: Алиса говорит: "Я считаю, что В, и ты тоже", а Боб отвечает: "Ну да, это очевидно."

Вы понимаете ее неправильно

Итак, теперь мы более-менее разобрались, в чем суть теоремы Ауманна: в некоем квазиобмене информацией и возможности скоординированных действий на ее основе без реального обмена информацией. И что, такие светлые умы, как Юдковский, Ааронсон и Ауманн понимали ее как-то иначе? Представьте себе, да (и, похоже, далеко не только они)! На этот случай существует доказательство, и уж самое надежное! И вам оно сейчас будет предъявлено.

Итак, начнем с Элиезера Юдковского. В эссе "Байесианское дзюдо" он пересказывал свой диалог на званом обеде:

— Ну, гм, видимо нам придётся остаться при своих мнениях на этот счёт. «Согласиться не соглашаться» — в таких случаях говорят англичане.

— На самом деле, так нельзя. Есть теорема из области рациональности — теорема Ауманна о согласии — которая говорит о том, что два рационалиста не могут согласиться не соглашаться. Если два человека не соглашаются друг с другом, то хотя бы один из них должен быть в чем-то неправ.

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

Ну ладно, с этой формулировкой всё понятно. Она содержит в принципе корректное и эпистемически полезное утверждение, потому и разлетелась как "простое объяснение сути теоремы". Ее распространенность - это, пожалуй, хорошо; то, что она служит затычкой для любопытства для тех, кто хочет понять, что означает теорема Ауманна - плохо. Впрочем, шансы на альтернативное развитие событий были невелики - во-первых, потому, что третье же предложение статьи Ауманна под названием (sic!) "Aggreeing to Disagree" гласит: "Вкратце, люди с одинаковыми приорами не могут согласиться не соглашаться"; во-вторых, потому, что если вы попытаетесь понять смысл статьи и доказательства теоремы до последней запятой, то ваша реакция вполне может оказаться такой: "(╯ ° □ °) ╯ (┻━┻), дайте мне уже простое объяснение, и я пойду." (пользуясь случаем, хочу поблагодарить Михаила Дегтярева, который в свое время помог мне пробиться через загадочные места этой статьи - думаю, сам я едва ли смог бы распутать эту загадку)

Кстати, в статье приводится еще несколько формулировок теоремы, ни одна из которых не является корректной. Конечно, возникает закономерный вопрос: откуда я тогда вообще выкопал корректную формулировку, если она нигде не приводится? Ну, я восстановил ее по тексту доказательства (и положил: формулировкой теоремы Ауманна является мало-мальски нетривиальный результат, который без особых натяжек доказывается приведенным доказательством). Несколько напоминает работу одного суперкомпьютера (частью которого я тоже являюсь); только там искали вопрос на ответ "42"...

Итак, не вдаваясь в детали (их рассмотрение я отложу до второй статьи), я заявляю здесь, что в доказательстве речь идет именно об индивидуально вычисляемом общем знании, а вовсе не о полученном в результате коммуникации объединенном знании.

В то же время, одна из формулировок в статье Aggreeing to Disagree гласит: "Если два человека имеют одинаковые приоры, и их постериоры для данного события A являются общим знанием, то эти постериоры должны быть равны". Ну, часть про одинаковые приоры действительно относится к сути теоремы; заключение о том, что в условиях теоремы должно следовать равенство постериоров, тоже в общем-то верно; отсутствие упоминания о том, что еще должно быть общим знанием (из существенного - набор экспериментов) - ну ладно, не страшно, это была только полуформальная формулировка; но что, черт возьми, означает оборот "постериоры являются общим знанием"?! Вот на простом человеческом языке, в формате "Алиса сказала Бобу, что..."?

Конечно, далее в статье говорится: "если два человека говорят друг другу их постериоры и доверяют друг другу, то постериоры являются общим знанием". Но давайте представим себе эту картину. Алиса говорит Бобу: "мои постериоры относительно события А - 33%". Хорошо, с этого момента ее постериоры являются их общим знанием. Ровно до того момента, как Боб скажет: "а мои постериоры до того, как ты это сказала, были равны 70%, но теперь равны 50%". В этот момент Алиса получает новую информацию ("хм, а Боб-то что-то знает такое про событие А, чего не знаю я - определенно стоит оценить вероятность как более высокую, чем я считала!") и обновляет свои постериоры - и до того момента, пока она не откроет рот, ее новые постериоры становятся неизвестны Бобу. И так далее - когда один сообщает второму свои постериоры - этот второй их меняет, и они становятся неизвестны первому (в любой момент общим знанием является очередная итерация постериоров лишь одного из двоих).

В конце статьи Ауманн предлагает подход к разрешению этой проблемы. А именно, пишет он, пусть наши два агента будут по очереди сообщать друг другу обновленные значения своих постериоров; тогда в конце концов последовательность постериоров каждого сойдется, причем обе последовательности сойдутся к одному и тому же числу. Вообще говоря, это интересное утверждение, но, во-первых, оно не имеет прямого отношения к теореме Ауманна (т.к. включает в себя процесс обмена информацией), а во-вторых, не является, на мой взгляд, настолько очевидным, чтобы приводить его без доказательства (доказательство "это следует из приведенной теоремы", увы, не пройдет).

Скотт Ааронсон пошел по такому же пути (последовательного обмена информацией между двумя агентами) и в результате даже доказал собственную теорему о скорости сходимости двух последовательностей. Это - еще более примечательный математический результат; оттого забавно, как он вырос из неверного понимания сути теоремы Ауманна. В статье Аарносона "Общее знание и теорема Ауманна" мы также видим, как он последовательно обсуждает ситуацию обмена информацией и постепенного увеличения индивидуального знания агентов до уровня объединенного знания.

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

Заключение

Итак, я рассказал вам о своем понимании теоремы Ауманна, а именно: какое не вполне тривиальное математическое утверждение доказывается в т.н. "доказательстве теоремы Ауманна" из оригинальной статьи Ауманна. Также я указал на то (или, вернее, основательно так прошелся по теме), что многие признанные авторитеты в области математики (и вообще очень большое количество людей) понимают значение теоремы совершенно неправильно. Озадачен ли я последним фактом? Еще как (причем уже больше двух лет)! Однако, я до сих пор не могу придумать более изящного способа натягивания совы на глобус, нежели тот, к которому пришел я (и который еще бы, желательно, допускал трактовки Юдковского, Ааронсона и Ауманна).

Свое собственное мнение вы можете составить прочитав как минимум статью Ауманна и исследовав его формулировку и доказательство - пожалуй, с уже приведенными мной пояснениями это будет проще, чем без оных. Однако, через некоторое время верифицировать мою правоту будет еще проще - во второй статье я планирую расписать весь необходимый математический формализм и затем аккуратно сформулировать и доказать теорему Ауманна в том виде, в котором это и должно быть сделано.