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

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

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

Эта концепция была впервые представлена ​​в философской литературе Дэвидом Келлогом Льюисом в его исследовании «Конвенция» (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}$

Пример

Головоломка

Идея общих знаний часто вводится с помощью некоторых вариантов индукционных головоломок (например, детской головоломки Muddy ): ^[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=1, тогда один человек с голубыми глазами не узнает, пока не будет объявлено) становится общеизвестным, голубоглазые люди на этом острове в конечном итоге делают вывод о своем статусе и покидают . ${\displaystyle E_{G}^{k-1}[\exists x\!\in \!G(Bl_{x})]}$

В частности:

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

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

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

Общему знанию может быть дано логическое определение в мультимодальных логических системах, в которых модальные операторы интерпретируются эпистемически . На пропозициональном уровне такие системы являются расширением пропозициональной логики . Расширение состоит из введения группы агентов G и n модальных операторов K _i (с i = 1, ...,  n ) с предполагаемым значением «агент i знает». Таким образом, K _i (где – формула логического исчисления) читается как «агент, которого я знаю ». Мы можем определить оператор EG с предполагаемым значением «каждый в группе 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 , Pi _. Этот раздел представляет состояние знаний агента в состоянии. Интуитивно, если два состояния s ₁ и s ₂ являются элементами одной и той же части разбиения агента, это означает, что s ₁ и s ₂ неотличимы для этого агента. В общем, в состоянии s агент i знает _, что одно из состояний в Pi ( s ) получено, но не знает, какое именно. (Здесь Pi ( s ) обозначает уникальный элемент Pi _, содержащий _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 , отношения доступности , которые определяют классы эквивалентности, соответствующие разбиениям , и функцию оценки, такую, что она дает значение, истинное для примитивного предложения 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), придерживающихся льюизианского, конвенционалистского подхода к языку.

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

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

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

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

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

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

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

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

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

Примечания

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

Рекомендации

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

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

• Ауманн, Роберт (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 Tracts in Theoretical Computer Science, 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 г.)