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

редактировать

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

Общие знания это особый вид знаний для группы агентов. Общеизвестно, что p в группе агентов G, когда все агенты в G знают p, все они знают, что они знают p, все они знают, что все они знают, что они знают p, и так далее до бесконечности.

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

Философ Стивен Шиффер в своей книге 1972 года «Значение, независимо разработанной». понятие, которое он назвал «взаимным знанием», которое функционирует очень аналогично «общему знанию» Льюиса и Фриделя 1969 года.

Содержание

1 Пример
- 1.1 Головоломка
- 1.2 Решение
  - 1.2.1 Доказательство
2 Формализация
- 2.1 Модальная логика (синтаксическая характеристика)
- 2.2 Теоретические множества (семантическая характеристика)
3 Приложения
4 См. Также
5 Примечания
6 Ссылки
7 Дополнительная литература
8 Внешние ссылки

Пример

Головоломка

Идея общеизвестного часто вводится некоторым вариантом головоломок :

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

В какой-то момент на остров приходит посторонний, созывает всех людей на острове и делает следующее публичное объявление: «По крайней мере, у одного из вас голубые глаза». Кроме того, всем известно, что посторонний правдив, и все знают, что все это знают и т. Д.: Общеизвестно, что он правдив, и, таким образом, становится общеизвестным, что есть по крайней мере один островитянин, у которого есть голубые глаза. Проблема: если предположить, что все люди на острове абсолютно логичны и что это тоже общеизвестно, каков конечный результат?

Решение

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

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

Решение можно увидеть с помощью индуктивного аргумента. Если k = 1 (то есть есть ровно один голубоглазый человек), этот человек распознает, что у него только голубые глаза (увидев только зеленые глаза у других), и уйдет на рассвете. Если k = 2, на рассвете никто не уйдет. Два голубоглазых человека, видя только одного человека с голубыми глазами, которого никто не покинул на 1-й заре (и, следовательно, k>1), уйдут на второй заре. Индуктивно можно предположить, что никто не уйдет при первых k - 1 рассвете тогда и только тогда, когда будет не менее k голубоглазых людей. Те, у кого голубые глаза, видя k - 1 голубоглазых среди других и зная, что должно быть не менее k, решат, что у них должны быть голубые глаза, и уйдут.

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

Для k = 2 это просто знания «первого порядка». Каждый голубоглазый человек знает, что есть кто-то с голубыми глазами, но каждый голубоглазый не знает, что другой голубоглазый обладает такими же знаниями.

Для k = 3 это знания «второго порядка». Каждый голубоглазый знает, что второй голубоглазый знает, что у третьего голубоглазые, но никто не знает, что есть третий голубоглазый человек с такими знаниями, пока посторонний не сделает свое заявление.

В целом: для k>1 это знания "(k - 1) -го порядка". Каждый голубоглазый человек знает, что второй голубоглазый знает, что третий голубоглазый знает, что... (повторите для всего k - 1 уровней) у k-го человека голубые глаза, но никто не знает, что есть «k-й» голубоглазый человек с такими знаниями, пока посторонний не сделает свое заявление. Таким образом, понятие общего знания имеет ощутимый эффект. Знание того, что все знают, имеет значение. Когда публичное заявление постороннего (факт, уже известный всем, если k = 1, тогда один человек с голубыми глазами не узнает до объявления) становится общеизвестным, голубоглазые люди на этом острове в конечном итоге делают вывод о своем статусе и уходят..

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

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

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

EG φ ⇔ ⋀ i ∈ GK i φ, {\ displaystyle E_ {G } \ varphi \ Leftrightarrow \ bigwedge _ {i \ in G} K_ {i} \ varphi,}

E_G \ varphi \ Leftrightarrow \ bigwedge_ {i \ in G} K_i \ varphi,

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

C φ ⇔ ⋀ i = 0 ∞ E i φ {\ displaystyle C \ varphi \ Leftrightarrow \ bigwedge _ {i = 0} ^ {\ infty} E ^ {i} \ varphi}

C \ varphi \ Leftrightarrow \ bigwedge_ {i = 0} ^ \ infty E ^ i \ varphi

Однако есть одна сложность. Языки эпистемической логики обычно финитны, тогда как аксиома выше определяет общее знание как бесконечное соединение формул, а не правильно сформированную формулу языка. Чтобы преодолеть эту трудность, можно дать общеизвестное определение с фиксированной точкой. Интуитивно общеизвестные знания рассматриваются как фиксированная точка «уравнения» $CG φ = φ ∧ EG (CG φ) {\ displaystyle C_ {G} \ varphi = \ varphi \ wedge E_ {G} (C_ { G} \ varphi)}$ $C_G \ varphi = \ varphi \ wedge E_G (C_G \ varphi)$ . Таким образом, можно найти формулу $ψ {\ displaystyle \ psi}$ $\ psi$ , предполагающую $EG (φ ∧ CG φ) {\ displaystyle E_ {G} (\ varphi \ wedge C_ {G} \ varphi)}$ $E_G (\ varphi \ wedge C_G \ varphi)$ , из которого, в пределе, мы можем вывести общеизвестные сведения о $φ {\ displaystyle \ varphi}$ $\ varphi$ .

Эта синтаксическая характеристика получает семантическое содержание через так- называется структурами Крипке. Структура Крипке задается (i) набором состояний (или возможных миров) S, (ii) n отношениями доступности $R 1,…, R n {\ displaystyle R_ {1}, \ dots, R_ {n }}$ $R_1, \ dots, R_n$ , определенный на $S × S {\ displaystyle S \ times S}$ $S \ times S$ , интуитивно представляющий, какие состояния агент i считает возможными из любого данного состояния, и (iii) функция оценки $π {\ displaystyle \ pi}$ $\ pi$ , присваивающая значение истинности в каждом состоянии каждому примитивному предложению в языке. Семантика оператора знаний задается тем, что $K i φ {\ displaystyle K_ {i} \ varphi}$ $K_i \ varphi$ истинно в состоянии s, если $φ {\ displaystyle \ varphi}$ $\ varphi$ истинно во всех состояниях t, таких что $(s, t) ∈ R i {\ displaystyle (s, t) \ in R_ {i}}$ $(s, t) \ in R_i$ . Таким образом, семантика для оператора общих знаний задается путем взятия для каждой группы агентов G рефлексивного и транзитивного замыкания для $R i {\ displaystyle R_ {i}}$ $R_ {i}$ , для всех агентов i в G, вызвать такое отношение $RG {\ displaystyle R_ {G}}$ $R_ {G}$ и указать, что $CG φ { \ displaystyle C_ {G} \ varphi}$ $C_G \ varphi$ истинно в состоянии s, если и только если $φ {\ displaystyle \ varphi}$ $\ varphi$ истинно во всех состояниях t, таких что $(s, t) ∈ RG {\ displaystyle (s, t) \ in R_ {G}}$ $(s, t) \ in R_G$ .

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

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

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

K i (e) = {s ∈ S ∣ P i (s) ⊂ e} {\ displaystyle K_ {i} (e) = \ { s \ in S \ mid P_ {i} (s) \ subset e \}}

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

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

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

E (e) = ⋂ я K я (e) {\ displaystyle E (e) = \ bigcap _ {i} K_ {i} (e)}

E (e) = \ bigcap_i K_i (e)

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

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

C (e) = \ bigcap_ {n = 1} ^ {\ infty} E ^ n (e).

Можно легко увидеть эквивалентность синтаксическому подходу, описанному выше: рассмотрим Aumann структура, как только что определено. Мы можем определить соответствующую структуру Крипке, взяв (i) то же пространство S, (ii) отношения доступности $R i {\ displaystyle R_ {i}}$ $R_ {i}$ , которые определяют классы эквивалентности, соответствующие разбиениям $P i {\ displaystyle P_ {i}}$ $P_ {i}$ , и (iii) функция оценки, которая дает значение, истинное для примитивного предложения p во всех и только состояниях s, таких что $s ∈ E p {\ displaystyle s \ in E ^ {p}}$ $s \ in E ^ p$ , где $E p {\ displaystyle E ^ {p}}$ $E ^ p$ - событие Aumann структура, соответствующая примитивному предложению p. Нетрудно увидеть, что функция универсальной доступности $RG {\ displaystyle R_ {G}}$ $R_ {G}$ , определенная в предыдущем разделе, соответствует тончайшему общему укрупнению разделов $P i { \ displaystyle P_ {i}}$ $P_ {i}$ для всех $i ∈ G {\ displaystyle i \ in G}$ $i \ in G$ , что является конечной характеристикой общеизвестных знаний, также данной Ауманом в Статья 1976 г.

Приложения

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

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

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

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

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

См. Также

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

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

Примечания

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

Ссылки

Дополнительная литература

Роберт Ауманн (1976) «Соглашаясь не соглашаться» Annals of Statistics 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) Конвенция: философское исследование Oxford: Blackburn. ISBN 0-631-23257-5
JJ Ch. Мейер и У ван дер Хук «Эпистемическая логика для информатики и искусственного интеллекта», том 41, Кембриджские трактаты по теоретической информатике, 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) Game Theory Evolving Princeton University Press. ISBN 0-691-14051-0
Гинтис, Герберт (2009) Границы разума, Princeton University Press. ISBN 0-691-14052-9
Halpern, J. Y. ; Моисей, Ю. (1990). «Знания и общие знания в распределенной среде». Журнал ACM. 37(3): 549–587. arXiv : cs / 0006009. doi : 10.1145 / 79147.79161. S2CID 52151232.

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

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