Общепринятое знание

[Gortaur]

Общепринятое знание - это то, что можно получить путем рассуждений "Я знаю, что ты знаешь, что я знаю ..." Используется в теории игр да и вообще интересный объект.

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

Далее идет семантическа формализация через теорию множеств которая немного приятнее - но там отсутствуют намеки на формулировки через неподвижную точку. Есть ли такая формулировка при описании ОЗ через теорию множеств и вообще, что можно посмотреть по данной теме краткого и полезного (знаю, что прошу много - но для любой области есть такие статьи/литература). Можно на английском.

[beroal]

Gortaur в сообщении #447552 писал(а):

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

Наверное, хотели написать уравнение $C_G\phi \leftrightarrow E_G(C_G\phi\land\phi)$.

Кстати, вы разбирались, почему там жалуются на бесконечную коньюнкцию? IMHO ошибка в формуле: $C\phi:=\bigwedge_{i = 1}^\infty E^n\phi$.

[Gortaur]

Да, теперь больше похоже на уравнение для неподвижной точки.

Про бесконечную конъюнкцию без понятия - пишут, что тогда задача не является well formed. Может, в этой логике данные выражения некорректны. А почему Вы думаете, что ошибка в этой формуле?

[epros]

Да, любопытная тема. Формализация понятия "стратегии" в теории игр всегда оставляло у меня впечатление, что там с логикой что-то не так. Суть в том, что понятие стратегии игрока включает в себя "информацию о стратегиях других игроков". Получается замкнутый круг: стратегия определяется через стратегию, т.е. с формальной точки зрения понятие стратегии не определено.

В качестве выхода из этой ситуации можно предложить понятие о "стратегии n-ого уровня":
1) Стратегия 0-ого уровня - это правило выбора игроком хода без учёта стратегий противников.
2) Стратегия (n+1)-ого уровня - это правило выбора игроком хода с учётом стратегий противников n-ого уровня.
Но у такого подхода есть большой недостаток: Непонятно, на каком уровне стратегии имеет смысл остановиться. Вроде бы, чем больше, тем круче

Другой "выход" из ситуации заключается в том самом "общем знании". Т.е. мы как бы сразу перескакиваем на "стратегию бесконечного уровня": Какой бы уровень стратегии ни был у противников, нам их стратегии известны и мы выбираем свой ход, учитывая их. Разумеется, противникам тоже всё известно о нашей стратегии. Это приводит нас к идее равновесия по Нэшу: решение находится в седловой точке.

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

[Gortaur]

epros
Реальность-то тут при чем Если серьезно, то просто изучается предельный случай, потому что по игроку не поймешь, какой глубины (измеренной в уровнях стратегий $n$) его мышление. Например, шахматы - по идее, эквилибриум Нэша для одного из игроков вообще не садиться играть, если оба они обладают бесконечным уровнем мышления, но у Homo Sapiens Sapiens пока думалки не хватает.

Насчет формального определения стратегии - у меня похожий вопрос возник, после того, как я прочитал этот Ответ. Здесь пользователь JDH требует, что уже существовало общепринятое знание - что навело на вопрос: чего достаточно для того, чтобы это общепринятое знание было?

1. Я знаю свои стратегии.
2. Я знаю стратегии других игроков.
3. Я знаю, что каждый из них знает о своих стратегиях и о моих.
4. Я знаю, что они знают 1+2+3.

Это необходимо - и по-моему, этого недостаточно.

[beroal]

Gortaur в сообщении #449545 писал(а):

А почему Вы думаете, что ошибка в этой формуле?

Раз жалуются на бесконечную конъюнкцию, одна из конъюнкций должна быть бесконечной. В Википедии сейчас та формула означает, что косвенность знания уровня $\leq n$, это подозрительно.

[Gortaur]

beroal
Не совсем понял, можете объяснить?

[beroal]

Gortaur в сообщении #449627 писал(а):

beroal
Не совсем понял, можете объяснить?

Вряд ли, я и сам плохо понимаю. Я высказал лишь догадки.

[epros]

Gortaur в сообщении #449578 писал(а):

Реальность-то тут при чем

Ну, уважаю я её дюже. Вроде как задачу, не имеющую отношения к реальности, даже и рассматривать как-то неинтересно: всегда остаётся подозрение, что ЛЮБОЕ её решение приемлемо (обо задача-то нереальная, какая разница?), а значит в каком-то смысле - правильно.

Gortaur в сообщении #449578 писал(а):

Насчет формального определения стратегии - у меня похожий вопрос возник, после того, как я прочитал этот Ответ. Здесь пользователь JDH требует, что уже существовало общепринятое знание - что навело на вопрос: чего достаточно для того, чтобы это общепринятое знание было?

Вот именно, что определение этого common knowledge какое-то мутное. Пункты я бы сформулировал несколько иначе. Например, так:

1) Каждый игрок знает платёжную матрицу каждого игрока (= каждый игрок знает как игроки будут ходить, если узнают ходы остальных).
2) Каждый игрок знает, что каждый игрок знает платёжную матрицу каждого игрока (= каждый игрок знает, что каждый игрок знает как игроки будут ходить, если узнают ходы остальных).
3) Каждый игрок знает, что каждый игрок знает, что каждый игрок знает платёжную матрицу каждого игрока (= каждый игрок знает, что каждый игрок знает, что каждый игрок знает как игроки будут ходить, если узнают ходы остальных).
...

Common khowledge лежит где-то в конце этой цепочки, то бишь в бесконечности, а значит, как я понимаю, оное недостижимо.

Обладая только (1), нельзя прийти к равновесию Нэша. Здесь мы знаем, как бы ходили все игроки, "если бы знали", но мы не знаем, как они будут ходить без всяких "если". Эту задачу можно смоделировать в терминах вероятностной логики. Для этого нужно предположить, что игроки не знают ходы остальных, т.е. полагают распределение по их ходам равномерным. Отсюда каждый игрок может рассчитать оптимальный (в среднем) для себя ход. Т.е. решение на уровне стратегии (1) уже есть, но это отнюдь не седловая точка.

На каком уровне стратегии мы придём к равновесию Нэша? Я так полагаю, что где-то в пределе может быть и придём, но это ещё нужно доказать... По-моему, отделываться здесь словами про common knowledge не совсем корректно.

[Gortaur]

Расчитать оптимальный он-то может, только тут вся теория игр перетекает в вопрос, какое распределение ему использовать для ходов игроков. Без (2) и других уровней это просто задача оптимального выбора, потому что информация о соперниках нулевая. Получается, что для годной теории игр изначально предполагается существование common knowledge.

[epros]

Вот именно, всё упирается в распределение для ходов других игроков. И ни на каком уровне "знания о знании о знании" без этого распределения задача, строго говоря, не решится. А common knowledge, по-моему, это какое-то надувательство:
- Во-первых, непонятно что это такое. Конечную цепочку "знания о знании о знании" определить можно, но бесконечную цепочку таких определений невозможно рассматривать как определение (по крайней мере, в рамках сколько нибудь разумной логики).
- Во-вторых, не очевидно, что в отсутствие распределений для ходов других игроков бесконечная цепочка "знания о знании о знании" (в отличие от конечной) приведёт к какому-то решению.

С моей точки зрения корректное решение заключается в том, чтобы заложить некое априорное распределение ходов других игроков (например, равномерное), а потом посмотреть, каково будет решение на n-ом уровне стратегии. В этом случае и вопрос о предельном случае $n \to \infty$, соответствующем "common knowledge", приобретает смысл. Очевидно, что если в задаче есть точка равновесия Нэша, то именно в ней будет решение для предельного случая.

Кстати, если седловой точки нет, то тоже получается интересно. Например, в игре чёт-нечет (один загадывает, другой отгадывает) равновесной стратегией для обоих игроков будет "выбирать наугад с равной вероятностью". Она же совпадает со стратегией бесконечного уровня.

[Gortaur]

Любопытный факт, что всю эту цепочку упрощает следующая ситуация. Все игроки собираются вместе - и им при всех говорят о правилах игры. Тогда достаточно сказать 1 раз - common knowledge появится. Если же давать информацию каждому по отдельности, то здесь нужно бесконечное число действий для того же результата. Несколько напоминает синхронизацию.

[epros]

Хм, я не уверен. Даже если каждый слышал, что каждый слышал, это ещё не доказывает, что каждый услышал и понял именно то, что было сказано. Формально говоря, переход на каждый следующий уровень "знания о знании" требует дополнительной аксиомы. Т.е. то, что "я и оппонент знаем правила", можно заложить аксиоматически, но из этого не следует, что "я и оппонент знаем, что мы оба знаем правила", а значит последнее придётся закладывать как отдельную аксиому. Если первую аксиому можно считать результатом наблюдения за тем, как игроки прослушали правила, то вторую аксиому можно рассматривать как предположение о наличии у игроков определённого уровня мыслительной активности.

[В.О.]

Мне тоже эта тема весьма интересна. В принципе, ссылки в википедии есть.
http://levine.sscnet.ucla.edu/archive/refs4512.pdf
http://www.kgt.bme.hu/targyak/hagyomany ... umann1.pdf
Можно потихоньку разбирать и здесь пересказывать. Может кто чего умного подскажет.

В википедии есть один неприятный момент. Утверждается, что после публичного выступления пришельца возникло общее знание. When the outsider's public announcement (a fact already known to all) becomes common knowledge, the blue-eyed people on this island eventually deduce their status, and leave.
Однако в смысле того определения, которое там сформулировано, общего знания не возникло.
Общее знание это некий бесконечный процесс. Для существования предела нужно что-то вроде топологии. Впрочем, нужно сначала почитать статьи.
И еще. В 1973 г. В А. Лефевр написал книгу "Конфликтующие структуры". Там тоже обсуждается рефлексия высоких порядков и т.п. Можно было бы сравнить подходы.