Všeobecné znalosti

Společné poznání se odehrává v situaci, kdy každý jedinec z určité skupiny ví o výskytu určité události, o přítomnosti těchto znalostí mezi ostatními členy skupiny, o přítomnosti znalostí o přítomnosti znalostí atd. ad infinitum [1] . Pojem obecných znalostí se poprvé objevil ve filozofické literatuře u Davida Kellogga Lewise (1969). Definici obecných znalostí podal ve stejné době sociolog Morris Friedell [2] . Matematickou ( množinově teoretickou ) interpretaci provedl v roce 1976 Robert Aumann , který se zabýval konstrukcí epistemické teorie her . Od 80. let 20. století se o tento koncept začali zajímat výzkumníci počítačových věd . Všeobecná znalost je základem mnoha logických hádanek, kterými se zabýval zejména John Horton Conway [3] .

Společné poznání souvisí se slabším pojetím vzájemného poznání . Na rozdíl od obecného, vzájemné implikuje povědomí o výskytu události, ale na znalost účastníků nejsou kladeny žádné další podmínky. Společné poznání je tedy vždy vzájemné (opak neplatí).

Formalizace

Modální logika (syntaktická charakteristika)

Společné znalosti lze definovat pro multimodální logické systémy , kde jsou modální operátory interpretovány epistemicky . Multimodální systémy jsou rozšířením výrokové logiky s přidáním skupiny agentů G a modálních operátorů K i (s i = 1, ..., n ). Výraz K i φ znamená „agent i ví, že φ“. Dále je potřeba definovat operátor E G , který bude odpovídat situaci „každý ve skupině G to ví“:

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

Označením výrazu jako pro , získáme obecný znalostní axiom $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

Zde nastává komplikace. Jazyk epistemické logiky operuje na konečném počtu objektů, zatímco axiom obecných znalostí obsahuje konjunkci nekonečného množství formulí. Proto, v jazyce epistemické logiky, vzorec není dobře vytvořený . Problém je vyřešen definováním pojmu z hlediska pevného bodu. Obecná znalost je pevným bodem vyjádření . Pak můžete najít vzorec , který předpokládá , že v limitu dá obecnou znalost . $C_{G}\varphi =\varphi \wedge E_{G}(C_{G}\varphi )$ $\psi$ $E_{G}(\varphi \wedge C_{G}\varphi )$ $\varphi$

Tato syntaktická charakteristika je obdařena sémantikou využívající Kripkeho model . Model je dán (i) množinou stavů S , (ii) n přechodovými vztahy definovanými na , (iii) označovací funkcí . Abychom sestrojili sémantiku, musíme nejprve říci, co je pravdivé ve stavu s právě tehdy, když to platí pro všechny stavy t takové, že . Sémantika běžného znalostního operátoru je vytvořena reflexivním a tranzitivním uzávěrem pro všechny agenty i v G (výsledný vztah se označí jako ) za předpokladu, že to platí ve stavu s právě tehdy, když je pravdivé ve všech stavech t tak, že . ${\displaystyle R_{1},\tečky ,R_{n))$ $S\times S$ $\pi$ $K_{i}\varphi$ $\varphi$ ${\displaystyle (s,t)\in R_{i))$ $R_i$ $R_{G}$ $C_{G}\varphi$ $\varphi$ $(s,t)\in R_{G}$

Teorie množin (sémantická charakteristika)

Alternativní, ale ekvivalentní formalizaci obecných znalostí uvádí Robert Aumann v podmínkách teorie množin . Existuje množina stavů S . Jeho podmnožiny se nazývají události. Pro každé jednotlivé i je definován oddíl S - P i . Dělení slouží k charakterizaci znalostí jedince v určitém stavu. Ve stavu s individuální i ví, že vznikl některý (ale ne který) ze stavů zahrnutých v množině P i ( s ), která je prvkem dělení P i obsahujícím s . V tomto modelu je vyloučena možnost chybných znalostí.

Znalostní funkce je definována takto:

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

To znamená, že K i ( e ) je soubor stavů, ve kterých jedinec ví o výskytu události e . K i ( e ) je podmnožinou e .

Potom je operátor "každý ví o výskytu e " definován jako

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

Stejně jako v případě modální logiky se funkce E aplikuje iterativně a . Funkce sdílených znalostí vypadá takto: $E^{1}(e)=E(e)$ $E^{n+1}(e)=E(E^{n}(e))$

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

Ekvivalenci přístupů lze snadno prokázat. Vzhledem k Aumannovu modelu lze určit odpovídající Kripkeho model. K tomu je nutné (i) specifikovat stejnou množinu stavů S , (ii) specifikovat přechodové vztahy definující třídy ekvivalence odpovídající oddílům , (iii) specifikovat označovací funkci, která přiřadí hodnotu "true" tvrzení p právě tehdy, jsou-li stavy s takové, že , kde je událost z Aumannova modelu odpovídající tvrzení p . Je snadné vidět, že funkce definovaná v poslední sekci odpovídá nejlepšímu celkovému zdrsnění oddílů pro všechny , což je hlavní charakteristika obecných znalostí (také poskytnutých Aumannem v roce 1976). $R_i$ $P_{i}$ ${\displaystyle s\in E^{p))$ ${\displaystyle E^{p))$ $R_{G}$ $P_{i}$ $i\in G$

Příklady

Pojem všeobecných znalostí lze odhalit na příkladu problému špinavých dětí . Na ostrově žije k modrookých lidí, všichni ostatní mají oči zelené. Zpočátku nikdo z obyvatel nezná barvu svých očí. Podle zákona, pokud ostrovan pozná barvu svých očí, musí ostrov opustit při východu slunce následující den. Každý na ostrově zná barvu očí všech ostatních, nejsou zde žádné reflexní plochy a o barvě očí se nikdy nediskutuje.

V určitém okamžiku na ostrov přijede cizinec, shromáždí obyvatele ostrova a učiní veřejné oznámení: "Alespoň jeden z vás má modré oči." Každý ví, že tento cizinec vždy říká pravdu a informace, že alespoň jeden ostrovan má modré oči, se stává všeobecně známou. Otázka zní: pokud předpokládáme, že všichni obyvatelé ostrova jsou logičtí a je to také všeobecně známo, jak celá záležitost skončí?

Odpověď zní: k-tého úsvitu po oznámení všichni modroocí opustí ostrov. Řešení lze provést indukcí. Pokud k=1, to znamená, že na ostrově je právě jeden modrooký člověk, pak si tento člověk okamžitě uvědomí, že on jediný má modré oči, protože kolem jsou jen zelenookí lidé, a ostrov opustí jako první. svítání. Pokud k = 2, pak nikdo neopustí ostrov při prvním úsvitu, ale tito dva, když kolem sebe vidí pouze jednoho modrookého člověka a vědí, že nikdo neopustil ostrov při prvním úsvitu (a tedy k>1), budou opustit ostrov za druhého svítání. Indukcí lze snadno dokázat, že po prvních úsvitech k-1 nikdo neopustí ostrov, pokud a pouze v případě, že na ostrově bude alespoň k modrookých lidí, a že všichni modroocí opustí ostrov na k-tý úsvit, pokud je jich přesně k.

V tomto scénáři je nejzajímavější, že pro k>1 cizinec řekne ostrovanům jen to, co už vědí: že jsou mezi nimi modroocí lidé. Důležité je, že než byla tato skutečnost vyslovena, nebyla všeobecně známá.

Příkladem problému ilustrujícího nemožnost dosáhnout obecných znalostí v případě spolehlivého komunikačního kanálu je problém dvou generálů . Dvě armády, každá vedená svým vlastním generálem, se připravují na útok na město. Tábory těchto armád se nacházejí na dvou kopcích oddělených údolím. Jediný způsob, jak komunikovat mezi generály, je poslat posly se zprávami přes údolí. Údolí je ale obsazeno nepřítelem a kteréhokoli z poslů lze zachytit. Problém je v tom, že generálové o přepadení učinili zásadní rozhodnutí předem (dokud probíhala komunikace), ale nedohodli se na přesném čase přepadení. Složitost problému spočívá v nemožnosti vyvinout algoritmus pro garantované zasílání zpráv.

Poznámky

↑ Osborne, Martin J. a Ariel Rubinstein . Kurz teorie her . Cambridge, MA: MIT, 1994. Tisk.
↑ Morris Friedell, „On the Structure of Shared Awareness,“ Behavioral Science 14 (1969): 28–39.
↑ Ian Stewart. I Know That You Know That... // Math Hysteria (anglicky) . — Oxford University Press , 2004.

Odkazy

Jurij Ustinovský. O mudrcích a nevěrných manželkách . Živly (30. července 2012). (neurčitý)

Herní teorie
Základní pojmy	Vzájemná a společná znalost Hráč Hierarchie vír Iracionální zesílení strategie ( dominance ) Reverzní indukce
Typy her	Simultánní , sekvenční a opakující se Nekooperativní a kooperativní S úplnými , neúplnými , dokonalými a nedokonalými informacemi V normální i rozšířené podobě Antagonistický Rozdíl Stochastické Bitva pohlaví Lov na jelena
Koncepce řešení	Riziková dominance Korelovaná rovnováha Rovnováha třesoucí se ruky Nashova rovnováha Dokonalá rovnováha podhry Racionalizovatelnost Sekvenční vyvážení silná rovnováha Vlastní bilance Evolučně stabilní strategie Epsilon-rovnováha Paretova účinnost Jádro
Příklady her	Vězňovo dilema Úkol baru "El Farol" Model Bertrand Cournotův model Stackelbergův model Orlyanka Tragédie sdílených zdrojů jestřábi a holubice
Epistemická teorie her Konstrukce mechanismu Spravedlivé rozdělení