Általános ismeretek

A közös tudás olyan helyzetben játszódik le, amikor egy bizonyos csoportból minden egyén tud egy bizonyos esemény bekövetkezéséről, ennek a tudásnak a jelenlétéről a csoport többi tagja között, a tudás jelenlétéről a tudás jelenlétéről stb. a végtelenségig [1] . Az általános tudás fogalma először a filozófiai irodalomban David Kellogg Lewisnál (1969) merült fel. Az általános tudás definícióját egyúttal Morris Friedell szociológus adta meg [2] . Egy matematikai ( halmazelméleti ) értelmezést végzett 1976-ban Robert Aumann , aki egy episztemikus játékelmélet felépítésével foglalkozott . Az 1980-as évek óta a számítástechnikai kutatók érdeklődnek a koncepció iránt . A közös tudás sok logikai rejtvény alapját képezi, amelyeket különösen John Horton Conway [3] tanulmányozott .

A közös tudás a kölcsönös tudás gyengébb fogalmához kapcsolódik . Az általánostól eltérően a kölcsönös egy esemény bekövetkezésének tudatát jelenti, de más feltétel nem szab a résztvevők tudásának. Így a közös tudás mindig kölcsönös (a fordítva nem igaz).

Formalizálás

Modális logika (szintaktikai jellemző)

Közös tudás definiálható multimodális logikai rendszerekre , ahol a modális operátorokat episztemikusan értelmezik . A multimodális rendszerek a propozíciós logika kiterjesztései a G ágensek egy csoportjával és a K i modális operátorokkal ( i = 1, ..., n ). A K i φ kifejezés jelentése "az i ügynök tudja, hogy φ". Ezután meg kell határoznia egy E G operátort , amely megfelel a "G csoportban mindenki tudja, hogy" helyzetnek:

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

Ha a kifejezést jelöljük , megkapjuk az általános tudás axiómáját $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

Itt jön egy komplikáció. Az episztemikus logika nyelve véges számú objektumon működik, míg az általános tudás axiómája végtelen számú képlet konjunkcióját tartalmazza. Ezért az episztemikus logika nyelvén a képlet nem jól formált . A problémát úgy oldjuk meg, hogy a kifejezést fix pontban határozzuk meg. Az általános tudás a kifejezés fix pontja . Ezután találhat egy képletet , amely feltételezi , hogy a határértékben általános ismereteket ad . $C_{G}\varphi =\varphi \wedge E_{G}(C_{G}\varphi )$ $\psi$ $E_{G}(\varphi \wedge C_{G}\varphi )$ $\varphi$

Ez a szintaktikai jellemző a Kripke-modell szemantikával van felruházva . A modellt (i) egy S állapothalmaz , (ii) n -en definiált átmeneti reláció adja , (iii) egy címkéző függvény . A szemantika megalkotásához először meg kell állapítani, hogy egy s állapotban mi igaz akkor és csak akkor, ha minden t állapotra igaz , hogy . A közismereti operátor szemantikáját egy reflexív és tranzitív lezárás hozza létre a G -beli összes i ágensre (az eredményül kapott relációt jelöléssel jelöljük ), feltéve, hogy ez akkor és csak akkor igaz az s állapotban , ha minden t állapotban igaz , . ${\displaystyle R_{1},\dots ,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}$

Halmazelmélet (szemantikai jellemző)

Az általános tudás egy alternatív, de egyenértékű formalizálását ad Robert Aumann a halmazelmélet szempontjából . Létezik egy S állapothalmaz . Ennek részhalmazait eseményeknek nevezzük. Minden egyes i - hez egy S - Pi partíció van meghatározva . A felosztás az egyén egy bizonyos állapotú tudásának jellemzésére szolgál. Az s állapotban az i egyed tudja, hogy az s -t tartalmazó P i partíció egyik eleme, a P i ( s ) halmazban szereplő állapotok közül néhány (de nem melyik) keletkezett . Ebben a modellben a téves tudás lehetősége kizárt.

A tudásfüggvény meghatározása a következő:

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

Vagyis K i ( e ) azoknak az állapotoknak a halmaza, amelyekben az egyén tud az e esemény bekövetkezéséről . K i ( e ) az e részhalmaza .

Ekkor a "mindenki tud e előfordulásáról" operátort a következőképpen definiáljuk

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

Mint a modális logika esetében, az E függvényt iteratívan alkalmazzuk, és . A megosztott tudás függvény így néz ki: $E^{1}(e)=E(e)$ $E^{n+1}(e)=E(E^{n}(e))$

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

A megközelítések egyenértékűsége könnyen kimutatható. Adott egy Aumann modell, akkor meghatározható a megfelelő Kripke modell. Ehhez (i) meg kell adni ugyanazt az S állapotkészletet , (ii) meg kell adni a partícióknak megfelelő ekvivalencia osztályokat meghatározó átmeneti relációkat , (iii) meg kell adni egy címkéző függvényt, amely az "igaz" értéket rendeli hozzá. p állítás akkor és csak akkor, ha az s állapotok olyanok, hogy hol van a p állításnak megfelelő esemény az Aumann-modellből . Könnyen belátható, hogy az utolsó részben definiált függvény felel meg a partíciók legjobb általános durvításának mindenki számára , ami a köztudat legfőbb jellemzője (Aumann is megadta 1976-ban). $R_i$ $P_{i}$ ${\displaystyle s\in E^{p))$ $E^{p}$ $R_{G}$ $P_{i}$ $i\in G$

Példák

Az általános tudás fogalma a koszos gyerekek problémájának példáján tárható fel . K kék szemű ember él a szigeten, mindenki másnak zöld szeme van. Kezdetben egyik lakos sem tudja a szeme színét. A törvény szerint, ha egy szigetlakó felismeri a szeme színét, másnap napkeltekor el kell hagynia a szigetet. A szigeten mindenki ismeri a többiek szemszínét, nincsenek fényvisszaverő felületek, és soha nem esik szó a szemszínről.

Egyszer egy külföldi érkezik a szigetre, összegyűjti a sziget lakóit, és nyilvános bejelentést tesz, mondván: "Legalább egyikőtöknek kék szeme van." Mindenki tudja, hogy ez a külföldi mindig igazat mond, és köztudomásúvá válik az az információ, hogy legalább egy szigetlakónak kék szeme van. A kérdés az: ha feltesszük, hogy a sziget minden lakója logikus, és ez is köztudott, mi lesz a vége az ügynek?

A válasz: a bejelentést követő k-adik hajnalban minden kék szemű elhagyja a szigetet. A megoldás indukcióval történhet. Ha k=1, vagyis pontosan egy kék szemű ember van a szigeten, akkor ez azonnal rájön, hogy egyedül neki van kék szeme, mivel csak zöld szeműek vannak a környéken, és először elhagyja a szigetet. hajnal. Ha k = 2, akkor senki sem hagyja el a szigetet az első hajnalban, de ők ketten, akik csak egy kék szemű embert látnak körül, és tudják, hogy senki sem hagyta el a szigetet az első hajnalban (és ezért k>1) hagyja el a szigetet a második hajnalban. Könnyű indukcióval bizonyítani, hogy akkor és csak akkor és csak akkor hagyja el senki a szigetet az első k-1 hajnal után, ha legalább k kék szemű ember van a szigeten, és minden kék szemű ember elhagyja a szigetet a k-adik hajnal, ha pontosan k van belőlük.

Ebben a forgatókönyvben az a legérdekesebb, hogy k>1-re a külföldi csak azt mondja el a szigetlakóknak, amit már tudnak: hogy vannak köztük kékszeműek. Az a fontos, hogy mielőtt ez a tény elhangzott, nem volt köztudott.

Példa arra a problémára, amely jól illusztrálja, hogy megbízható kommunikációs csatorna esetén lehetetlen a közös tudás elérésének lehetősége a két általános probléma . Két hadsereg készül a város megrohanására, mindegyiket saját tábornok vezeti. E seregek táborai két dombon helyezkednek el, amelyeket völgy választ el egymástól. A tábornokok közötti kommunikáció egyetlen módja az, hogy hírnököket küldenek üzenetekkel a völgyön keresztül. De a völgyet elfoglalja az ellenség, és bármelyik hírvivőt el lehet fogni. A probléma az, hogy a tábornokok előzetesen (kommunikáció közben) alapvető döntést hoztak a támadásról, de nem egyeztek meg a támadás pontos időpontjában. A probléma összetettsége abban rejlik, hogy nem lehet kidolgozni egy algoritmust a garantált üzenetküldéshez.

Jegyzetek

↑ Osborne, Martin J. és Ariel Rubinstein . Játékelmélet tanfolyam . Cambridge, MA: MIT, 1994. Nyomtatás.
↑ Morris Friedell, "On the Structure of Shared Awareness", Behavioral Science 14 (1969): 28–39.
↑ Ian Stewart. I Know That You Know That... // Math Hysteria (angol) . – Oxford University Press , 2004.

Linkek

Jurij Usztinovszkij. A bölcsekről és a hűtlen feleségekről . Elemek (2012. július 30.). (határozatlan)

Játékelmélet
Alapfogalmak	Kölcsönös és közös tudás Játékos A hitek hierarchiája Irracionális erősítés Stratégia ( dominancia ) Fordított indukció
A játékok típusai	Egyidejű , szekvenciális és ismétlődő Nem együttműködő és együttműködő Teljes , hiányos , tökéletes és tökéletlen információkkal _ Normál és kiterjesztett formában _ Ellentétes Differenciális Sztochasztikus A nemek harca Szarvasvadászat
Megoldási koncepciók	Kockázati dominancia Korrelált egyensúly Remegő kéz egyensúlya Nash egyensúly A részjáték tökéletes egyensúlya Racionalizálhatóság Szekvenciális egyensúly erős egyensúly Saját mérleg Evolúciósan stabil stratégia Epszilon-egyensúly Pareto hatékonyság Sejtmag
Játékpéldák	A fogoly dilemmája Az "El Farol" bár feladata Bertrand modell Cournot modell Stackelberg modell Orlyanka A megosztott erőforrások tragédiája sólymok és galambok
Episztemikus játékelmélet Mechanizmus tervezés Tisztességes felosztás