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

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

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

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

Пример [ править ]

Головоломка [ править ]

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

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

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

Решение [ править ]

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

Доказательство [ править ]

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

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

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

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

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

Формализация [ править ]

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

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

${\ displaystyle E_ {G} \ varphi \ Leftrightarrow \ bigwedge _ {я \ 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 )}$${\displaystyle \psi }$${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$${\displaystyle \varphi }$

Эта синтаксическая характеристика получает семантическое содержание через так называемые структуры Крипке . Структура Крипке задается (i) набором состояний (или возможных миров) S , (ii) n отношениями доступности , определенными на , интуитивно представляющими, какие состояния агент я считаю возможными из любого данного состояния, и (iii) оценочной функцией присвоение значения истинности в каждом состоянии каждому примитивному предложению в языке. Семантика оператора знания задается тем, что он является истинным в состоянии 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}}$. Семантика для общего оператора знаний, то дается, принимая, для каждой группы агентов G , то рефлексивное и транзитивное замыкание из , для всех агентов I в G , называют такое отношение , и предусматривается , что верно в государственных е iff истинно во всех состояниях t, таких что .${\displaystyle R_{i}}$${\displaystyle R_{G}}$${\displaystyle C_{G}\varphi }$${\displaystyle \varphi }$${\displaystyle (s,t)\in R_{G}}$

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

В качестве альтернативы (но эквивалентно) общеизвестные знания можно формализовать с помощью теории множеств (это был путь, по которому лауреат Нобелевской премии Роберт Ауманн в своей основополагающей статье 1976 года). Мы начнем с множеством состояний S . Затем мы можем определить событие Е как подмножество множества состояний S . Для каждого агента i определите раздел на S , P _i . Этот раздел представляет состояние осведомленности агента в состоянии. В состоянии 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 .

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

${\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).}$

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

Приложения [ править ]

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

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

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

Ученые-информатики используют языки, включающие эпистемологическую логику (и общие знания), чтобы рассуждать о распределенных системах. Такие системы могут быть основаны на логике, более сложной, чем простая пропозициональная эпистемическая логика, см. Вулдридж « Рассуждения об искусственных агентах» , 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 
• JJ Ch. Мейер и У. ван дер Хук « Эпистемическая логика для компьютерных наук и искусственного интеллекта» , том 41, Кембриджские трактаты по теоретической информатике, Cambridge University Press, 1995. ISBN 0-521-46014-X 
• Решер, Николас (2005). Эпистемическая логика: обзор логики знания . Университет Питтсбурга Press . ISBN 978-0-8229-4246-7.. См. Главу 3.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-89943-7.. См. Раздел 13.4; скачать бесплатно онлайн .
• Гинтис, Герберт (2000) Развитие теории игр Princeton University Press. ISBN 0-691-14051-0 
• Гинтис, Герберт (2009) Границы разума Princeton University Press. ISBN 0-691-14052-9 
• Халперн, JY ; Моисей, Ю. (1990). «Знания и общие знания в распределенной среде». Журнал ACM . 37 (3): 549–587. arXiv : cs / 0006009 . DOI : 10.1145 / 79147.79161 . S2CID  52151232 .

Внешние ссылки [ править ]

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