Словник / Спільне знання
Два генерали стоять на двох пагорбах, між ними долина з ворогом. Удвох вони переможуть, поодинці загинуть. Домовитися можна лише через гінців, а гінця можуть перехопити. Генерали обмінюються підтвердженнями: «отримав», «отримав твоє "отримав"»… Здається, після десятка таких листів сумнівів не лишиться. Але й тисяча підтверджень не дає того, що їм насправді потрібно.
Шар «На пальцях» приховано на всіх задачах.
Генерал A посилає гінця: «Атакуємо на світанку». Генерал B відповідає своїм гінцем: «Отримав». A відповідає: «Отримав твоє "отримав"». І так далі, по черзі. Кожного гінця ворог може перехопити, і тоді відправник про це не дізнається.
Після скількох доставлених гінців генерал може атакувати й бути певним, що не опиниться в бою сам?
Перевірте самі. Гінці бігають туди й назад, доки котрогось не перехоплять. Кожен генерал атакує, якщо отримав щонайменше k гінців, адресованих йому. Оберіть k і шанс, що ворог перехопить гінця, і зіграйте тисячі ночей.
Ліворуч генерал A, праворуч B, час іде вниз. Пунктирна стрілка з хрестиком — перехоплений гінець, на ньому обмін закінчується. Число біля стрілки — скільки разів «знає, що» вже стоїть у ланцюжку.
Хоч скільки гінців у плані, хтось відправляє останнього й не знає, чи той дійшов. Щоб дізнатися, потрібне ще одне підтвердження, а з ним та сама біда. Тому вимога «більше підтверджень» не рятує: вона лише робить спільну атаку рідшою. А в ті ночі, коли генерал усе-таки йде в бій, ризик опинитися самому лишається тим самим, що й шанс утратити одного гінця.
Кожен доставлений гінець додає до ланцюжка одне «знає, що». Перший: B знає план. Другий: A знає, що B знає. Третій: B знає, що A знає, що B знає. Генералам же потрібно, щоб усі ці поверхи були збудовані одразу, до нескінченності. Це й називають спільним знанням, і гінці його не дають ніколи.
Троє друзів нудьгують на вечірці. Кожен піде, лише якщо піде компанія: стирчати у дверях самому ніяково. Ви знаєте, що таксі чекає біля входу. Як донести це так, щоб вони пішли разом? Спробуйте шепотіти кожному окремо, а потім просто скажіть уголос.
Факт є спільним знанням групи, якщо його знає кожен, кожен знає, що всі його знають, кожен знає, що всі знають, що всі знають, і так без кінця. Звучить як гра слів, але різниця цілком практична. Коли треба діяти разом і ніхто не хоче бути першим, мало, щоб кожен знав. Треба, щоб кожен був певен, що інші теж певні.
Найпростіший спосіб створити спільне знання — сказати щось публічно, коли всі бачать, що всі чують. Ланцюжок приватних повідомлень, хоч який довгий, цього не замінить.
Шар «Строго» приховано на всіх задачах.
Кожен знає факт, але може думати, що решта не знає. Скажімо, кожному колезі окремо сказали, що завтра свято. Чи прийде завтра хтось на роботу «про всяк випадок», бо не певен щодо інших?
Те саме оголосили на загальних зборах. Нового факту ніхто не почув, але тепер кожен знає, що знають усі, і що всі знають і це. Вдома лишаться всі.
Класичний приклад — казка Андерсена «Нове вбрання короля» (1837). Кожен у натовпі бачить, що король голий, але мовчить: а раптом інші бачать вбрання? Хлопчик вигукує те, що всі й так бачили. Нового він не повідомив нічого, проте після його слів кожен знає, що й інші це бачать, і натовп сміється разом.
Здається, тисяча поверхів «знає, що» — це майже нескінченність, і поводитися люди мають майже так, ніби знання спільне. Економіст Аріель Рубінштейн 1989 року показав, що це не так. У його «грі з електронною поштою» комп'ютери двох гравців автоматично пересилають підтвердження, доки якийсь лист не загубиться. Для раціональних гравців результат такий самий, наче листів не було зовсім: хоч скільки підтверджень надійшло, жоден не ризикує.
Чому так, видно в симуляції генералів. Генерал B отримав рівно k гінців, і більше ніхто не прийшов. Можливо, перехопили його власну відповідь, і тоді A теж має k гінців і атакує. А можливо, ще раніше перехопили гінця, якого A мав надіслати, і тоді A отримав лише k − 1 і чекає. Обидва варіанти майже однаково ймовірні, тож на самій межі генерал B вгадує, ніби кидає монетку.
P(B сам | B отримав рівно k) = 1 / (2 − p)
Тут p — шанс утратити гінця. При p = 10% це 1/1,9 ≈ 52,6%, тобто навіть трохи гірше за монетку, і від k це не залежить. Зіграйте ночі в симуляції вище, і тут з'являться ваші числа.
Рубінштейн довів, що з таких «монеток» і складається рівновага: якщо на межі ризикувати не варто, то не варто й на крок вище, а тоді й ще на крок, і так до будь-якої кількості листів.
Шар «Глибше» приховано на всіх задачах.
E¹φ = «кожен знає φ», Ek+1φ = E(Ekφ), Cφ = E¹φ ∧ E²φ ∧ E³φ ∧ …
Ekφ — це k поверхів «усі знають, що». Спільне знання Cφ вимагає всіх поверхів одночасно. Його можна задати й без нескінченного ряду, як нерухому точку: Cφ рівносильне E(φ ∧ Cφ). Тобто факт є спільним знанням, коли всі знають і сам факт, і те, що він спільне знання. Саме так працює публічна заява: почувши її, кожен знає, що всі інші почули її разом із ним.
У мові можливих світів Ауман описав це так: подія є спільним знанням, якщо вона правдива в кожному світі, до якого можна дійти будь-яким ланцюжком «а раптом він думає, що…».
P(доставлено рівно n гінців) = (1 − p)n · p
B отримує непарні гінці, A парні. За правилом «атакувати після k» B атакує, коли доставлено щонайменше 2k − 1 гінців, а A — щонайменше 2k. Тому:
разом = (1 − p)2k · сам = p · (1 − p)2k−1 · сам, коли хтось атакував = p
Остання частка не залежить від k зовсім. Більший k лише зменшує шанс атакувати взагалі: при p = 10% і k = 10 генерали атакують разом лише в 12,2% ночей, а ризик для того, хто пішов у бій, лишається 10%. Щоб він зник, k має бути нескінченним, тобто генерали мають мати спільне знання.
Варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші.
Знижка вигідна кав'ярні, хоч би що зробила сусідня, але коли знижують обидві, кожна заробляє втричі менше, ніж якби обидві тримали ціну.
Набір стратегій, у якому нікому не вигідно змінити свою, поки інші не змінюють своїх.
У дилемі в'язня обидва зраджують, хоча мовчати вигідніше обом: рівновага не означає найкращий результат.
Розв'язування гри з кінця: спершу останній хід, потім передостанній, і так до першого.
У грі-стоніжці логіка велить забрати копійки на першому ж ході, хоча, граючи довше, обидва отримали б сотні, і живі люди так майже не роблять.