Теорема Ауманна - вторая после теоремы Байеса по популярности математическая теорема среди рационалистов. Однако, какие бы то ни было объяснения ее сущности (а тем более - подробные и исчерпывающие) встречаются, на мой взгляд, непозволительно редко. Лично мне не хватило даже достаточно обстоятельной статьи Скотта Ааронсона "Общее знание и теорема Ауманна", чтобы понять хотя бы точную математическую формулировку теоремы (чтение оригинальной статьи Ауманна помогало, но не сильно). В конечном итоге, основательно расспросив Михаила Дегтярева в слаке русскоязычного lesswrong-сообщества, я смог составить более-менее пристойное представление о сути теоремы. Однако ряд связанных с ней моментов по-прежнему ставил меня в тупик.
В конечном итоге я написал довольно большую статью с изложением своего тогдашнего понимания теоремы Ауманна и своего понимания недостаточного понимания ее другими. Среди персон, неправильно понимавших теорему, были упомянуты Элиезер Юдковский, Скотт Ааронсон и сам Роберт Ауманн, что было довольно смелым заявлением. После публикации меня закономерно спросили: а точно ли прав именно я, а не вышеупомянутые умные люди?
В ходе дальнейших моих разбирательств в этой теме я, похоже, наконец понял всё то, из-за чего чувствовал себя немало озадаченным ранее. И в этой статье я планирую восстановить справедливость и аргументированно указать, в чем все эти люди были правы (в большинстве принципиальных вопросов), а в чем - не очень (в меньшинстве сугубо второстепенных). И, конечно, в чем был прав и неправ я сам в моей первой статье.
Данный текст представляет собой математическое изложение теоремы Ауманна и некоторых более поздних результатов, а также их интерпретацию (замечу, что в чем-то эта интерпретация вполне согласуется с той, что была представлена в прошлой статье, а в чем-то - значительно ее расширяет). В дальнейшем я ориентируюсь в первую очередь на читателя, знакомого с математикой по крайней мере на уровне первого курса математического факультета, хотя описания результатов простым человеческим языком тоже будет в изобилии. К сожалению, подробно разъяснить, что такое сигма-алгебра или разбиение множества, у меня нет никакой возможности - текст и так получится очень объемным. Но, надеюсь, данная статья станет очередным важным шагом в деле донесения знания об этой интересной теореме до все более и более широкой публики.
Обычно при обсуждении вероятностного пространства $\{ \Omega, \mathcal B, p \}$ принято называть $\Omega$ множеством (пространством) элементарных исходов. При обсуждении байесовских агентов мы будем подразумевать под ним пространство миров (где каждый элемент $\omega$ - это полное описание мира во всем его многообразии). В принципе можно провести некоторую параллель между пространством возможных миров и бесконечномерным (или, возможно, просто страшномногомерным) фазовым пространством.
В этой концепции понятие "информация" означает способность отличать одни миры от других. Зададим на $\Omega$ отношение эквивалентности вида "миры, которые мы не можем отличить друг от друга" (подразумевается, что мы можем провести как наблюдения невооруженным взглядом, чтобы отличить миры с синим небом от миров с зеленым небом, так и более сложные эксперименты, чтобы отличить миры с квантовой гравитацией, описываемой теорией струн от миров с квантовой гравитацией, описываемой теорией петлевой квантовой гравитации). Отношение эквивалентности задает на $\Omega$ разбиение; элементы разбиения (классы эквивалентности) - это совокупность миров, которые мы не можем отличить от миров, лежащих в том же классе, но зато надежно отличаем от миров, лежащих в любом другом классе. При этом чем меньше элемент разбиения, тем меньше неопределенность (какой конкретно мир из возможных реализуется на самом деле), и тем больше информации. Элемент разбиения $\{\omega\}$ отражает абсолютно полную информацию, когда мы знаем о мире буквально всё; элемент разбиения $\Omega$ отражает полное отсутствие информации - мы не можем сказать о мире вообще ничего и не можем указать ни на один из возможных миров, который заведомо не реализуется в реальности.
Скажем, в примере с Шефом и Коллегой из прошлой статьи (где Шеф знал только телосложение убийцы, а Коллега - группу крови) пространство элементарных исходов выглядело как $\Omega = \{1, 2, 3, 4\}$ а разбиения - соответственно $\mathcal P_1 = \{\{1, 2, 3\},\{4\}\}$ и $\mathcal P_2 = \{ \{ 1 \}, \{ 2, 3 \}, \{ 4 \} \}$. А вот если бы у Братьев Пилотов не было бы заранее списка подозреваемых, а была бы возможность узнать рост преступника с точностью до сантиметра, то разбиение выглядело бы как $\{ \{ 54 \}, \{ 55 \},... \{251 \} \}$ (с учетом рекордов роста взрослых людей).
Оговоримся, что в дальнейшем мы будем рассматривать только элементы разбиения ненулевой меры. Если же нам попадутся элементы нулевой меры (т.е. с нулевой вероятностью), то будем считать, что мы заранее удалим их из $\Omega$ либо произвольным образом объединим с другими элементами. С практической точки зрения это разумно, т.к. с одной стороны, мы почти никогда не попадем в событие нулевой вероятности; с другой, при попытке оперировать такими событиями, в некоторых случаях нам пришлось бы столкнуться с неопределенностью вида 0/0.
При этом если в рамках какой-то конкретной задачи мы можем сказать, что наше пространство элементарных исходов выглядит как $\Omega=\{1, 2, 3, 4, 5, 6\}$, причем $p(1)=p(2)=p(3)=p(4)=p(5)=p(6)=\frac{1}{6}$ (классическая задача с честным шестигранным игральным кубиком), то в терминологии пространства миров мы будем говорить о разбиении $\Omega$ на классы эквивалентности $\{ "миры,\ где\ кубик\ выпадает\ единицей", ... "миры,\ где\ кубик\ выпадает\ шестеркой" \}$, при этом мера каждого класса эквивалентности также будем равна $\frac{1}{6}$.
Как было упомянуто в предыдущей статье, по определению некоторый факт является общим знанием между N агентами, если этот факт известен каждому агенту; при этом каждому агенту известно, что этот факт известен всем; каждому агенту известно, что каждому агенту известно, что факт известен всем - и так далее до бесконечности. Рассмотрим теперь, как формализовать это определение в терминах пространства миров.
Пусть у нас есть пространство возможных миров $\Omega$, зафиксирован реальный мир $\omega$ и есть два агента - Алиса и Боб. Познавательные возможности Алисы и Боба представлены конечными разбиениями на $\Omega$ - $\mathcal P_1 = \{ P_1^1, ... P_1^m \}$ и $\mathcal P_2 = \{ P_2^1, ... P_2^n \}$ соответственно (бесконечные разбиения мы не будем рассматривать, т.к. реальные агенты чисто физически за время существования Вселенной не смогут отделить друг от друга бесконечное число возможных миров, например, за счет измерения какой-то вещественнозначной величины с бесконечной точностью). В таком случае информация (знания, известные факты) для Алисы - это элемент разбиения $\mathbf P_1(\omega) \in \mathcal P_1$, содержащий $\omega$; для Боба - элемент его разбиения $\mathbf P_2(\omega) \in \mathcal P_2$. Естественно, конкретное значение $\omega$ ни одному из них не известно - они только знают, что реальный мир находится "где-то здесь" (среди множества миров из соответствующего элемента разбиения).
В дальнейшем в рамках разговора об общем знании и теореме Ауманна мы также будем предполагать, что эти разбиения (но не конкретные элементы $\mathbf P_1$ и $\mathbf P_2$ - да, здесь и далее я часто буду опускать $\omega$ там, где это можно безболезненно сделать) являются между Алисой и Бобом общим знанием в неформальном смысле (т.е. они оба знают, что они оба знают,... что их разбиения именно таковы). Это важно, т.к. в противном случае поломается вся логика и вычисления - невозможно знать, что думает твой визави о твоем знании, если ты не уверен, что он знает твое разбиение и способен по нему что-то высчитать.
Итак, как же формализуется понятие общего знания? Вообще-то об информации о мире, известной Бобу, Алиса знает немногое - только то, какую информацию он в принципе способен получить (его разбиение). Однако о самом мире ей кое-что известно: она знает, что реальный мир $\omega$ находится где-то внутри $\mathbf P_1$. Исходя из этого она уже может предположить кое-что о том, что известно Бобу. Посмотрим для примера на следующую картинку.
Красными линиями здесь обозначено разбиение Алисы, зелеными - разбиение Боба (левая вертикальная черта - это красная и зеленая линия; будем считать, что у обоих агентов левый элемент разбиения один и тот же). $\mathbf P_1$ здесь - четвертый слева "прямоугольник", $\mathbf P_2$ - нечто напоминающее треугольник посередине.
Где конкретно находится реальный мир $\omega$, Алиса не знает, так что тут могут быть разные варианты. Она может предположить, что реальный мир находится где-то в районе точки A - и в этом случае Боб будет знать, что реальность - это где-то в элементе $P_2^A$. Либо же реальный мир может оказаться где-то в районе точки B - и тогда Боб будет знать $P_2^B$. Опять же, по мнению Алисы, мир может находиться в районе точки C (кстати, мы-то с вами знаем, что именно это предположение верно), и в таком случае Бобу будет известно $P_2^C$ (на самом деле так и есть). Наконец, Алиса заканчивает перебирать варианты на районе точки D, что будет означать знание Боба $P_2^D$.
