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

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

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

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

Пример

Головоломка

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

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

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

Решение

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

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

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

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

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

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

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

В частности:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Ученые-компьютерщики используют языки, включающие в себя эпистемическую логику (и общеизвестные знания), чтобы рассуждать о распределенных системах. Такие системы могут основываться на логике, более сложной, чем простая пропозициональная эпистемическая логика, см. Wooldridge Reasoning about Artificial Agents , 2000 (в которой он использует логику первого порядка, включающую эпистемические и темпоральные операторы) или van der Hoek et al. «Эпистемическая логика переменного времени».

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

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

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

См. также

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

Примечания

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

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

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

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

• Вандершраф, Питер; Силлари, Джакомо. «Общие знания» . В Залте, Эдвард Н. (ред.). Стэнфордская энциклопедия философии .
• Сообщение в блоге профессора Теренса Тао (февраль 2008 г.)
• Карр, Карим. «В долгосрочной перспективе мы все мертвы» , «В долгосрочной перспективе мы все мертвы II» в The Twofold Gaze. Подробное описание проблемы голубоглазого островитянина с решением.
• Physics.harvard.edu «Проблема зеленоглазых драконов», архивировано 1 декабря 2014 г. в Wayback Machine , «Решение зеленоглазых драконов», архивировано 1 декабря 2014 г. в Wayback Machine (сентябрь 2002 г.)