Общеизвестно (логика)

Заявление о том, что игроки знают и также знают, что другие игроки знают (до бесконечности)

Общие знания — это особый вид знаний для группы агентов . Общие знания о p существуют в группе агентов G , когда все агенты в G знают p , все они знают, что они знают p , все они знают, что они все знают, что они знают p , и так далее до бесконечности . ^[1] Это можно обозначить как . ${\displaystyle C_{G}p}$

Впервые это понятие было введено в философскую литературу Дэвидом Келлогом Льюисом в его исследовании Convention (1969). Социолог Моррис Фриделл определил общее знание в статье 1969 года. ^[2] Впервые ему была дана математическая формулировка в теоретико-множественной структуре Робертом Ауманном (1976). Ученые-компьютерщики стали интересоваться предметом эпистемической логики в целом и общим знанием в частности, начиная с 1980-х годов. ^[1] Существует множество головоломок, основанных на этом понятии, которые были тщательно исследованы такими математиками, как Джон Конвей . ^[3]

Философ Стивен Шиффер в своей книге 1972 года «Значение » независимо разработал понятие, которое он назвал « взаимным знанием » ( ), которое функционирует совершенно аналогично понятию «общее знание» Льюиса и Фриделя 1969 года. ^[4] Если достоверное объявление сделано публично , то оно становится всеобщим знанием; Однако, если оно передается каждому агенту в частном порядке, оно становится взаимным знанием, но не общим знанием. Даже если тот факт, что «каждый агент в группе знает p » ( ), передается каждому агенту в частном порядке, это все еще не общее знание: . Но, если любой агент публично объявляет о своем знании p , то становится общим знанием, что он знает p (а именно ). Если каждый агент публично объявляет о своем знании p , p становится общим знанием . ${\displaystyle E_{G}p}$ ${\displaystyle E_{G}p}$ ${\displaystyle E_{G}E_{G}p\not \Rightarrow C_{G}p}$ ${\displaystyle a}$ ${\displaystyle C_{G}K_{a}p}$ ${\displaystyle C_{G}E_{G}p\Rightarrow C_{G}p}$

Пример

Головоломка

Идея общего знания часто вводится с помощью некоторых вариантов индукционных головоломок (например, головоломки «Чумазые дети» ): ^[2]

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

В какой-то момент на остров прибывает посторонний, собирает всех людей на острове и делает следующее публичное заявление : «По крайней мере, у одного из вас голубые глаза». Более того, посторонний всем известен как правдивый, и все знают, что все это знают, и так далее: общеизвестно, что он правдив, и, таким образом, становится общеизвестным, что есть по крайней мере один островитянин с голубыми глазами ( ). Проблема: найти конечный результат, предполагая, что все люди на острове полностью логичны (знания каждого участника подчиняются схемам аксиом эпистемической логики ) и что это тоже общеизвестно. ${\displaystyle C_{G}[\exists x\!\in \!G(Bl_{x})]}$

Решение

Ответ заключается в том, что на k -м рассвете после объявления все голубоглазые люди покинут остров.

Доказательство

Решение можно увидеть с помощью индуктивного аргумента. Если k  = 1 (то есть есть ровно один голубоглазый человек), человек поймет, что у него одного голубые глаза (увидев только зеленые глаза у других) и уйдет на первом рассвете. Если k  = 2, никто не уйдет на первом рассвете, и бездействие (и подразумеваемое отсутствие знания у каждого агента) будет замечено всеми, что затем также станет общим знанием ( ). Два голубоглазых человека, видя только одного человека с голубыми глазами, и что никто не ушел на первом рассвете (и, таким образом, что k  > 1; а также что другой голубоглазый человек не думает, что все, кроме него самого, не голубоглазые , поэтому другой голубоглазый человек ), уйдут на втором рассвете. Индуктивно можно рассудить, что никто не уйдет на первых k  − 1 рассветах, если и только если есть по крайней мере k голубоглазых людей. Те, у кого голубые глаза, увидев k  − 1 голубоглазых людей среди остальных и зная, что должно быть по крайней мере k , рассудят, что у них должны быть голубые глаза, и уйдут. ${\displaystyle C_{G}[\forall x\!\in \!G(\neg K_{x}Bl_{x})]}$ ${\displaystyle \neg K_{a}[\forall x\!\in \!(G-a)(\neg Bl_{x})]}$ ${\displaystyle \exists x\!\in \!(G-a)(Bl_{x})}$

При k  > 1 сторонний наблюдатель сообщает жителям острова только то, что они уже знают: что среди них есть голубоглазые люди. Однако до того, как этот факт будет объявлен, он не является общеизвестным , а является взаимным знанием .

При k  = 2 это просто знание «первого порядка» ( ). Каждый голубоглазый человек знает, что есть кто-то с голубыми глазами, но каждый голубоглазый человек не знает, что другой голубоглазый человек имеет то же самое знание. ${\displaystyle E_{G}[\exists x\!\in \!G(Bl_{x})]}$

При k  = 3 это знание «второго порядка» ( ). Каждый голубоглазый человек знает, что второй голубоглазый человек знает, что у третьего человека голубые глаза, но никто не знает, что есть третий голубоглазый человек с этим знанием, пока посторонний не сделает своего заявления. ${\displaystyle E_{G}E_{G}[\exists x\!\in \!G(Bl_{x})]=E_{G}^{2}[\exists x\!\in \!G(Bl_{x})]}$

В общем: для k  > 1, это знание "( k  − 1)-го порядка" ( ). Каждый голубоглазый человек знает, что второй голубоглазый человек знает, что третий голубоглазый человек знает, что... (повторите для всего k  − 1 уровней) у k -го человека голубые глаза, но никто не знает, что есть " k -й" голубоглазый человек с этим знанием, пока посторонний не сделает своего заявления. Поэтому понятие общего знания имеет ощутимый эффект. Знание того, что все знают, имеет значение. Когда публичное заявление постороннего (факт, уже известный всем, если только k = 1, тогда единственный человек с голубыми глазами не узнает до объявления) становится общеизвестным, голубоглазые люди на этом острове в конечном итоге делают вывод о своем статусе и уходят. ${\displaystyle E_{G}^{k-1}[\exists x\!\in \!G(Bl_{x})]}$

В частности:

1. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$является свободным (т.е. известным до утверждения постороннего) тогда и только тогда, когда . ${\displaystyle i+j\leq k}$
2. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$, с уходящим днем, из которого никто не уходит, подразумевает следующий день . ${\displaystyle E_{G}^{i-1}[|G(Bl_{x})|\geq j+1]}$
3. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$для достигается, таким образом, тогда и только тогда, когда оно достигается для . ${\displaystyle j\geq k}$ ${\displaystyle i+j>k}$
4. Посторонний дает за . ${\displaystyle E_{G}^{i}[|G(Bl_{x})|\geq j]}$ ${\displaystyle i=\infty ,j=1}$

Формализация

Модальная логика (синтаксическая характеристика)

Общим знаниям можно дать логическое определение в многомодальных логических системах, в которых модальные операторы интерпретируются эпистемически . На пропозициональном уровне такие системы являются расширениями пропозициональной логики . Расширение состоит из введения группы G агентов и n модальных операторов K i ₍ где i = 1, ...,  n ) с предполагаемым значением «агент i знает». Таким образом, K _i (где — формула логического исчисления) читается как «агент i знает ». Мы можем определить оператор E _G с предполагаемым значением «все в группе G знают», определив его с помощью аксиомы ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

${\displaystyle E_{G}\varphi \Leftrightarrow \bigwedge _{i\in G}K_{i}\varphi ,}$

Сокращая выражение с помощью и определяя , общее знание можно затем определить с помощью аксиомы ${\displaystyle E_{G}E_{G}^{n-1}\varphi }$ ${\displaystyle E_{G}^{n}\varphi }$ ${\displaystyle E_{G}^{0}\varphi =\varphi }$

${\displaystyle C\varphi \Leftrightarrow \bigwedge _{i=0}^{\infty }E^{i}\varphi }$

Однако есть сложность. Языки эпистемической логики обычно конечны , тогда как аксиома выше определяет общее знание как бесконечное соединение формул, следовательно, не является хорошо сформированной формулой языка. Чтобы преодолеть эту трудность, можно дать определение общего знания с фиксированной точкой . Интуитивно общее знание мыслится как фиксированная точка «уравнения» . Здесь — это Алеф-ноль . Таким образом, можно найти формулу, подразумевающую , из которой в пределе мы можем вывести общее знание о . ${\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi }$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \psi }$ ${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$ ${\displaystyle \varphi }$

Из этого определения видно, что если является общеизвестным, то является также общеизвестным ( ). ${\displaystyle E_{G}\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle C_{G}E_{G}\varphi \Rightarrow C_{G}\varphi }$

Эта синтаксическая характеристика получает семантическое содержание через так называемые структуры Крипке . Структура Крипке задается набором состояний (или возможных миров) S , n отношений доступности , определенных на , интуитивно представляющих то, какие состояния агент i считает возможными из любого заданного состояния, и функцией оценки, присваивающей значение истинности , в каждом состоянии, каждому примитивному предложению в языке. Семантика Крипке для оператора знания задается условием, что является истинным в состоянии s тогда и только тогда, когда является истинным во всех состояниях t таких, что . Семантика для оператора общего знания, таким образом, задается взятием для каждой группы агентов G , рефлексивного (модальная аксиома T ) и транзитивного замыкания (модальная аксиома 4 ) из , для всех агентов i в G , называемого таким отношением , и условием, что является истинным в состоянии s тогда и только тогда, когда является истинным во всех состояниях t таких, что . ${\displaystyle R_{1},\dots ,R_{n}}$ ${\displaystyle S\times S}$ ${\displaystyle \pi }$ ${\displaystyle K_{i}\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle (s,t)\in R_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{G}}$ ${\displaystyle C_{G}\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle (s,t)\in R_{G}}$

Теоретико-множественная (семантическая характеристика)

Альтернативно (но эквивалентно) общие знания могут быть формализованы с использованием теории множеств (это был путь, выбранный лауреатом Нобелевской премии Робертом Ауманн в его основополагающей статье 1976 года). Начиная с множества состояний S . Затем событие E может быть определено как подмножество множества состояний S . Для каждого агента i , определите раздел на S , P _i . Этот раздел представляет состояние знаний агента в состоянии. Интуитивно, если два состояния s ₁ и s ₂ являются элементами одной и той же части раздела агента, это означает, что s ₁ и s ₂ неразличимы для этого агента. В общем случае, в состоянии s , агент i знает, что одно из состояний в P _i ( s ) достигается, но не какое именно. (Здесь P _i ( s ) обозначает уникальный элемент P _{i ,} содержащий s . Эта модель исключает случаи, в которых агенты знают вещи, которые не являются истинными.)

Функцию знаний K теперь можно определить следующим образом:

${\displaystyle K_{i}(e)=\{s\in S\mid P_{i}(s)\subset e\}}$

То есть, K _i ( e ) — это множество состояний, в которых агент будет знать, что происходит событие e . Это подмножество e .

Подобно приведенной выше формулировке модальной логики, оператор для идеи «все знают» может быть определен как e .

${\displaystyle E(e)=\bigcap _{i}K_{i}(e)}$

Как и в случае с модальным оператором, мы будем итерировать функцию E , и . Используя это, мы можем затем определить функцию общего знания, ${\displaystyle E^{1}(e)=E(e)}$ ${\displaystyle E^{n+1}(e)=E(E^{n}(e))}$

${\displaystyle C(e)=\bigcap _{n=1}^{\infty }E^{n}(e).}$

Эквивалентность с синтаксическим подходом, описанным выше, легко увидеть: рассмотрим структуру Ауманна, как только что определенную. Мы можем определить соответствующую структуру Крипке, взяв то же пространство S , отношения доступности , которые определяют классы эквивалентности, соответствующие разделам , и функцию оценки, такую, что она дает значение true для примитивного предложения p во всех и только состояниях s таких, что , где — событие структуры Ауманна, соответствующее примитивному предложению p . Нетрудно увидеть, что функция доступности общих знаний, определенная в предыдущем разделе, соответствует наилучшему общему огрублению разделов для всех , что является финитной характеристикой общих знаний, также данной Ауманн в статье 1976 года. ${\displaystyle R_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle s\in E^{p}}$ ${\displaystyle E^{p}}$ ${\displaystyle R_{G}}$ ${\displaystyle P_{i}}$ ${\displaystyle i\in G}$

Приложения

Общие знания были использованы Дэвидом Льюисом в его новаторском игровом теоретико-конвенциональном описании конвенции. В этом смысле общие знания являются концепцией, которая по-прежнему остается центральной для лингвистов и философов языка (см. Clark 1996), поддерживающих льюисовское, конвенционалистское описание языка.

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

Концепция общего знания является центральной в теории игр . В течение нескольких лет считалось, что предположение об общем знании рациональности для игроков в игре является фундаментальным. Оказывается (Aumann and Brandenburger 1995), что в играх с двумя игроками общее знание рациональности не требуется как эпистемическое условие для стратегий равновесия Нэша .

Специалисты по информатике используют языки, включающие эпистемическую логику (и общие знания), чтобы рассуждать о распределенных системах. Такие системы могут быть основаны на логике, более сложной, чем простая пропозициональная эпистемическая логика, см. Wooldridge Reasoning about Artificial Agents , 2000 (в которой он использует логику первого порядка, включающую эпистемические и временные операторы) или van der Hoek et al. "Alternating Time Epistemic Logic".

В своей книге 2007 года « Суть мысли: язык как окно в человеческую природу » Стивен Пинкер использует понятие общего знания для анализа вида косвенной речи, используемой в намёках.

В популярной культуре

В комедийном фильме « Горячий свинец и холодные ноги » есть пример цепочки логики, которая разрушается общим знанием. Денверский парень говорит своим союзникам, что Рэттлснейк в городе, но что у него [Кида] есть «преимущество»: «Он здесь, и я знаю, что он здесь, и он знает, что я знаю, что он здесь, но он не знает, что я знаю, что он знает, что я знаю, что он здесь». Таким образом, оба главных героя знают главный факт (Рэтлснейк здесь), но это не «общеизвестно». Обратите внимание, что это верно, даже если Кид ошибается: возможно, Рэттлснейк знает , что Кид знает, что он знает, что он знает, цепочка все равно рвется, потому что Кид этого не знает. Спустя несколько мгновений Рэттлснейк сталкивается с Кидом. Мы видим, как Кид понимает, что его тщательно выстроенное «преимущество» рухнуло в общее знание.

Смотрите также

• Философский портал

• Глобальная игра
• Взаимное знание (логика)
• Множественное невежество
• Охота на оленя
• Стивен Шиффер
• Задача двух генералов о невозможности установления общих знаний по ненадежному каналу

Примечания

1. ↑ См. учебники «Рассуждения о знаниях» Фейгина, Хэлперна, Мозеса и Варди (1995) и «Эпистемическая логика для компьютерных наук» Мейера и ван дер Хука (1995).
2. ^ Структурно идентичную задачу предлагает Герберт Гинтис (2000); он называет ее «Женщины Севитана».

Ссылки

1. Осборн, Мартин Дж. и Ариэль Рубинштейн . Курс теории игр . Кембридж, Массачусетс: MIT, 1994. Печать.
2. Моррис Фриделл, «О структуре общего сознания», Behavioral Science 14 (1969): 28–39.
3. Ян Стюарт (2004). «Я знаю, что ты знаешь, что...». Математическая истерия . OUP.
4. Стивен Шиффер, Значение , 2-е издание, Oxford University Press, 1988. Первое издание было опубликовано OUP в 1972 году. Обсуждение концепций Льюиса и Шиффера см. в книге Рассела Дейла, Теория значения (1996).

Дальнейшее чтение

• Ауманн, Роберт (1976) «Согласие с несогласием» Анналы статистики 4(6): 1236–1239.
• Ауманн Роберт и Адам Бранденбургер (1995) «Эпистемические условия для равновесия Нэша» Econometrica 63 (5): 1161–1180.
• Кларк, Герберт (1996) Использование языка , Cambridge University Press ISBN 0-521-56745-9 
• Фейгин, Рональд; Халперн, Джозеф; Моисей, Йорам; Варди, Моше (2003). Рассуждения о знаниях . Кембридж: MIT Press . ISBN 978-0-262-56200-3..
• Льюис, Дэвид (1969) Конвенция: Философское исследование Оксфорд: Блэкберн. ISBN 0-631-23257-5 
• Дж. Дж. Ч. Мейер и В. ван дер Хук Эпистемическая логика для компьютерных наук и искусственного интеллекта , том 41, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995. ISBN 0-521-46014-X 
• Решер, Николас (2005). Эпистемическая логика: обзор логики знания . Издательство Питтсбургского университета . ISBN 978-0-8229-4246-7.. См. Главу 3.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Многоагентные системы: алгоритмические, игровые и логические основы. Нью-Йорк: Cambridge University Press . ISBN 978-0-521-89943-7.. См. раздел 13.4; можно бесплатно загрузить онлайн.
• Гинтис, Герберт (2000) Развитие теории игр . Издательство Принстонского университета. ISBN 0-691-14051-0 
• Гинтис, Герберт (2009) Границы разума Издательство Принстонского университета. ISBN 0-691-14052-9 
• Halpern, JY ; Moses, Y. (1990). «Знание и общие знания в распределенной среде». Журнал ACM . 37 (3): 549–587. arXiv : cs/0006009 . doi :10.1145/79147.79161. S2CID  52151232.

Внешние ссылки

• Вандершраф, Питер; Силлари, Джакомо. «Общее знание». В Zalta, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Запись в блоге профессора Теренса Тао (февраль 2008 г.)
• Карр, Карим. "In the Long Run We Are All Dead", "In the Long Run We Are All Dead II" в The Twofold Gaze. Подробное описание проблемы голубоглазого островитянина с решением.
• physics.harvard.edu "Проблема зеленоглазых драконов" Архивировано 01.12.2014 на Wayback Machine , "Решение зеленоглазых драконов" Архивировано 01.12.2014 на Wayback Machine (сентябрь 2002 г.)