Common Knowledge

Aus Wikiludia
Wechseln zu: Navigation, Suche

Das Konzept common knowledge, zu deutsch gemeinsames Wissen, hat erstmals Aumann im Jahre 1976 mathematisch formuliert. Bei der Analyse eines Spieles ist es wichtig zu definieren, was als gemeinsames Wissen allen Spielern gleichermassen bekannt ist und was jeder einzelne Spieler über das Wissen der anderen weiß.

Inhaltsverzeichnis

Wissensmodell

Um gemeinsames Wissen formal beschreiben zu können muss zunächst ein Wissensmodell für den einzelnen Spieler definiert werden.

Die Menge aller Zustände

Mit Ω bezeichnet man die Menge aller Zustände.

Mögliche Interpretationen:

  • Ein Zustand  \omega \in \Omega beschreibt die Umstände, die der Entscheidungsträger in einem bestimmten Entscheidungsproblem für relevant hält.
  • Ein Zustand  \omega \in \Omega beschreibt die ganze Welt mit den Informationen und Überzeugungen des Entscheidungsträgers, sowie seinen Handlungen.

Die Informationsfunktion

Definition: (partitionierende) Informationsfunktion

  • Eine Informationsfunktion für die Menge Ω von Zuständen ist eine Funktion  P: \Omega \rightarrow \mathcal{P}(\Omega) , die jedem Zustand  \omega \in \Omega eine nichtleere Teilmenge von Zuständen  P(\omega) \subseteq \Omega zuordnet.
  • Eine Informationsfunktion P für die Menge Ω aller Zustände heißt partitionierend, wenn es eine Partition von Ω gibt, so dass für jedes  \omega \in \Omega gilt, dass P(ω) jenes Element der Partition ist, welches ω enthält.

Interpretation: Im Zustand  \omega \in \Omega ist der Entscheidungsträger davon überzeugt, dass sich der tatsächliche Zustand in der Menge  P(\omega) \subseteq \Omega befindet. Ist die Informationsfunktion sogar partitionierend, gilt  \omega \in P(\omega) und dann ist der Entscheidungsträger nicht nur davon überzeugt, sondern weiß sogar, dass sich der tatsächliche Zustand in P(ω) befindet.

Lemma

Eine Informationsfunktion ist partitionierend \Leftrightarrow (P1)  \omega \in P(\omega) für jedes  \omega \in \Omega

(P2)  \overline{\omega} \in P(\omega) \Rightarrow P(\overline{\omega})=P(\omega)

Beweis:
\Rightarrow Folgt direkt.
\Leftarrow Es gilt also, dass P die Eigenschaften (P1) und (P2) erfüllt.

Wenn  P(\omega)\cap P(\overline{\omega})\neq \emptyset und  \overline{\overline{\omega}} \in P(\omega)\cap P(\overline{\omega}) , also  \overline{\overline{\omega}} \in P(\omega) \ \wedge \ \overline{\overline{\omega}} \in P(\overline{\omega}) .
Wegen (P2) gilt:  P(\overline{\overline{\omega}})=P(\omega) \ \wedge \ P(\overline{\overline{\omega}})=P(\overline{\omega}) . Also ist  P(\omega)=P(\overline{\omega})
Wegen (P1) gilt:  \cup_{\omega \in \Omega} P(\omega) = \Omega
Also ist P partitionierend.

Interpretation:

  • (P1) besagt, dass ein Entscheidungsträger niemals den tatsächlichen Zustand ω aus der Menge der plausiblen Zustände P(ω) ausschließt.
  • (P2) besagt, dass ein Entscheidungsträger die (Un-)Vereinbarkeit von Zuständen verwendet, um Rückschlüsse auf den tatsächlichen Zustand zu machen:
  1. Sei  \overline{\omega} \in P(\omega) und man nehme an es gebe einen Zustand  \overline{\overline{\omega}} \in P(\overline{\omega}) mit  \overline{\overline{\omega}} \not \in P(\omega) . Dann gilt nach (P2):  P(\omega) \neq P(\overline{\omega}) \Rightarrow \overline{\omega} \not \in P(\omega) . Wenn also ω der Zustand ist, kann der Entscheidungsträger begründen, dass der tatsächliche Zustand nicht  \overline{\omega} sein kann, weil  \overline{\overline{\omega}} mit seiner Information unvereinbar ist.
  2. Es gebe einen Zustand  \overline{\overline{\omega}} \in P(\omega) mit  \overline{\overline{\omega}} \not \in P(\overline{\omega}) . Dann gilt nach (P2):  P(\omega) \neq P(\overline{\omega}) \Rightarrow \overline{\omega} \not \in P(\omega) . Wenn also ω der Zustand ist, kann der Entscheidungsträger begründen, dass der tatsächliche Zustand nicht  \overline{\omega} sein kann, weil  \overline{\overline{\omega}} mit seiner Information vereinbar ist.

Bemerkung: Im Normalfall geht man davon aus, dass das Tupel (Ω,P) die Bedingungen (P1) und (P2) erfüllt, die Informationsfunktion P also partitionierend ist.

Die Wissensfunktion

Definition: (bekanntes) Ereignis

  • Sei Ω die Menge der Zustände.
Eine Teilmenge  E \subseteq \Omega nennt man Ereignis.
  • Sei P eine Informationsfunktion und  \omega \in \Omega .
Ein Ereignis E heißt einem Entscheidungsträger bekannt, wenn für ihn im Zustand ω gilt:  P(\omega) \subseteq E .
Man sagt dann auch, dass der Entscheidungsträger das Ereignis E kennt.

Interpretation/Bezeichnung: Das Wort 'bekannt' stammt daher, dass ein Entscheidungsträger, für den  P(\omega) \subseteq E gilt, im Zustand ω weiß (beziehungsweise im Fall einer nicht partitionierenden Informationsfunktion, 'meint zu wissen' oder 'davon übereugt ist'), dass der tatsächliche Zustand ein Zustand aus dem Ereignis E ist.

Definition: Wissensfunktion

Seien eine Informationsfunktion P, sowie ein Ereignis  E \subseteq \Omega gegeben.
Dann wird durch  K: \mathcal{P}(\Omega) \rightarrow \mathcal{P}(\Omega) ,  K(E)=\{\omega \in \Omega | P(\omega) \subseteq E\} die zu P zugehörige Wissensfunktion K des Entscheidungsträgers definiert.

Interpretation: Für jedes Ereignis  E \subseteq \Omega ist die Menge  K(E) \ die Menge aller Zustände in denen der Entscheidungsträger E kennt.

Bemerkungen:

  1. Jede Wissensfunktion K erfüllt die folgenden Bedingungen:
    • (K1)  K(\Omega)=\Omega \ (Der Entscheidungsträger weiß, dass ein Zustand aus Ω eingetreten ist)
    • (K2)  E \subseteq F \Rightarrow K(E) \subseteq K(F)
    • (K3)  K(E) \cap K(F) = K(E \cap F) (Wenn der Entscheidungsträger E und F kennt, kennt er auch  E \cap F )
  2. Wenn die zugrundelegende Informationsfunktion P zusätzlich noch die Bedingung (P1) erfüllt, erfüllt die Wissensfunktion K folgende zusätzlichen Eigenschaft:
    • (K4)  K(E) \subseteq E (Axiom des Wissens)
  3. Wenn die zugrundelegene Informationsfunktion P jetzt sogar partitionierend ist, d.h. (P1) und (P2) erfüllt sind, erfüllt die Wissensfunktion K folgende zusätzlichen Eigenschaften:
    • (K5)  K(E) \subseteq K(K(E)) (Axiom der Transparenz)
    • (K6)  \Omega \setminus K(E) \subseteq K(\Omega \setminus K(E)) (Axiom der Weisheit)

Gemeinsames Wissen

Wenn in einem Zustand jeder Spieler das Ereignis kennt und außerdem...

  • jeder Spieler weiß, dass jeder Mitspieler es kennt, und
  • jeder Spieler weiß, dass alle Mitspieler wissen, dass jeder Mitspieler es kennt, und
  • jeder Spieler weiß, dass alle Mitspieler wissen, dass alle Mitspieler wissen, dass jeder Mitspieler es kennt, und
  • jeder Spieler weiß, dass alle Mitspieler wissen, dass alle Mitspieler wissen, dass alle Mitspieler wissen, dass jeder Mitspieler es kennt, und
  • ...

so spricht man von gemeinsamen Wissen.

Man kann nun das oben beschriebene Wissensmodell für die formale Beschreibung des Begriffs 'gemeinsames Wissen' verwenden.
Der Einfachheit halber wird der Begriff hier nur für zwei Spieler definiert. Er lässt sich aber problemlos, ganz analog, auf eine höhere Anzahl von Spielern erweitern.

Definition: gemeinsames Wissen bei zwei Spielern

Seien die Menge Ω von Zuständen, sowie die Wissensfunktionen K1 bzw. K2 von Spieler 1 bzw. Spieler 2 gegeben.
Ein Ereignis  E \subseteq \Omega heißt gemeinsames Wissen (common knowledge) zwischen Spieler 1 und Spieler 2 im Zustand  \omega \in \Omega , wenn ω in jeder Menge der unendlichen Folge  K_1(E) \ ,  K_2(E) \ ,  K_1(K_2(E)) \ ,  K_2(K_1(E)) \ ,  K_1(K_2(K_1(E))) \ ,  K_2(K_1(K_2(E))),... \ enthalten ist.

Definition: offensichtliches Ereignis

In einem Spiel mit n Spielern seien für die Menge der Zustände Ω die Informationfunktionen P1,...,Pn gegeben.
Ein Ereignis  F \subseteq \Omega heißt offensichtliches Ereignis unter den Spielern 1,...,n, wenn für alle  \omega \in F gilt:  P_i(\omega) \subseteq F für i = 1,...,n.

Interpretation: Ein Ereignis F ist offensichtlich unter n Spielern, wenn alle n Spieler es kennen.

Lemma

Für die Menge Ω von Zuständen sei P1 bzw. P2 die partitionierende Informationsfunktion von Spieler 1 bzw. Spieler 2. Weiter sei K1 bzw. K2 die zu P1 bzw. P2 gehörige Wissensfunktion und  E \subseteq \Omega ein Ereignis. Dann sind äquivalent:

  • (A) Ki(E) = E für i = 1,2.
  • (B) E ist unter den Spielern 1 und 2 offensichtlich.
  • (C) E ist eine Vereinigung von Elementen der Partition, die durch Pi, für i = 1,2 induziert wird.

Beweis:
(A) \Rightarrow (B): Nach (A) gilt für i = 1,2:  K_i(E)=\{\omega \in \Omega | P_i(\omega) \subseteq E\}=E .

Also gilt für jedes  \omega \in E :  P_1(\omega) \subseteq E \ \wedge \ P_2(\omega) \subseteq E \Rightarrow (B)

(B) \Rightarrow (C): Nach (B) gilt für i = 1,2:  \forall \ \omega \in E: \omega \in P_i(\omega) \subseteq E .

Also gilt für i = 1,2:  E=\cup_{\omega \in E} P_i(\omega) und somit ist das Ereignis E eine Vereinigung von Elementen der Partitionen P1 und P2  \quad \Rightarrow (C)

(C) \Rightarrow (A): Folgt direkt.

Satz

Sei Ω eine endliche Menge von Zuständen, P1 bzw. P2 partitionierende Informationsfunktion von Spieler 1 bzw. Spieler 2. Weiter sei K1 bzw. K2 die zu P1 bzw. P2 gehörige Wissensfunktion.
Dann gilt im Zustand  \omega \in \Omega :
Ein Ereignis  E \subseteq \Omega ist gemeinsames Wissen zwischen Spieler 1 und 2.  \Leftrightarrow Es existiert ein unter den Spielern 1 und 2 offensichtliches Ereignis F mit  \omega \in F \subseteq E .

Beweis:
 \Rightarrow : Sei also im Zustand  \omega \in \Omega das Ereignis  E \subseteq \Omega gemeinsames Wissen zwischen Spieler 1 und Spieler 2.

Dann ist für jedes  i \in \{1,2\} mit  i \neq j :  E \supseteq K_i(E) \supseteq K_j(K_i(E)) \supseteq K_i(K_j(K_i(E))) \supseteq ... und ω ist Element jeder dieser Mengen.
Folglich sind alle diese Mengen nichtleer und da Ω endlich ist, gibt es zwei aufeinanderfolgende Mengen für die Gleichheit gilt. Definiere diese Menge als  F:=K_i(K_j(K_i(...K_i(E)...))) \ . Für F gilt also nun auch:  K_j(F)=K_j(K_i(K_j(K_i(...K_i(E)...))))=F \ .
Übersicht:
 \begin{matrix} 
& =:F & = & K_j(F) & \supseteq & K_i(K_j(F))=K_i(F) & (1) \\
E \supseteq ... \supseteq & \overbrace{\underbrace{K_i(K_j(K_i(...K_i(E)...)))}} & \supseteq & \overbrace{\underbrace{K_j(K_i(K_j(K_i(...K_i(E)...))))}} & \supseteq & \overbrace{\underbrace{K_i(K_j(K_i(K_j(K_i(...K_i(E)...)))))}} & \supseteq & ... \\
& =:K_i(G) & = & K_j(K_i(G))& \supseteq & K_i(K_j(K_i(G)))=K_i(K_i(G)) & (2)
\end{matrix}

Wegen (1) gilt:  K_i(F) \subseteq F
Da die Informationsfunktionen partitionierend sind, gilt für die Wissensfunktionen das Axiom der Tranzparenz (K5):  K(E) \subseteq K(K(E)) .
Insbesondere also:  F = K_i(G) \subseteq K_i(K_i(G)) = K_i(F)
Insgesamt folgt:  K_i(F)=F \
Nach obigem Lemma ( (A)  \Rightarrow (B) ) ist F ein offensichtlich Ereignis unter den Spielern 1 und 2. Dann gilt nach Definition:  \omega \in F \subseteq E .

 \Leftarrow : Es existiere also im Zustand  \omega \in \Omega ein unter Spieler 1 und Spieler 2 offensichtliches Ereignis F mit  \omega \in F \subseteq E .

Sei  i \in \{1,2\} mit  i \neq j .
Nach obigem Lemma ( (B)  \Rightarrow (A) ) ist:  F=K_i(F)=K_i(K_j(F))=K_i(K_j(K_i(F)))=... \ Also ist F gleich jeder Menge der Form  K_i(K_j(K_i(...K_i(F)...)) \
Für jede Wissensfunktion gilt (K2):  A \subseteq B \Rightarrow K(A) \subseteq K(B) \quad \forall\ B \subseteq \Omega
Folglich:
 \begin{matrix}
\omega \in F \subseteq E \Rightarrow & \underbrace{K_i(F)} & \subseteq \ K_i(E) \ \Rightarrow & \underbrace{K_j(K_i(F))} & \subseteq \ K_j(K_i(E)) \ \Rightarrow & \underbrace{K_i(K_j(K_i(F)))} & \subseteq \ K_i(K_j(K_i(E))) \ \Rightarrow \ ...\\
& =F & & =F  & & =F 
\end{matrix}
Somit ist ω in jeder Menge der Form  K_i(K_j(K_i...K_i(E)...)) \ enthalten und folglich ist die Menge E per Definition gemeinsames Wissen.

Beispiele

Ausgangssituation A

Seien  \Omega = \{\omega_1,\dots,\omega_{10}\} \ und P1 bzw. P2 partitionierende Informationsfunktion von Spieler 1 bzw. Spieler 2. Weiter sei K1 bzw. K2 die zu P1 bzw. P2 gehörige Wissensfunktion.
Die durch die Informationsfunktionen induzierten Partitionen seien:
 \mathcal{P}_1=\{\{\omega_1,\omega_2\},\{\omega_3, \omega_4\},\{\omega_5, \omega_6\},\{\omega_7, \omega_8, \omega_9\}, \{\omega_{10}\}\}
 \mathcal{P}_2=\{\{\omega_1\},\{\omega_2,\omega_3\}, \{\omega_4,\omega_5\}, \{\omega_6\},\{\omega_7, \omega_8\}, \{\omega_9, \omega_{10}\}\}

Beispiel A1

Untersucht wird, ob das Ereignis  E_1=\{\omega_1, \omega_2, \omega_3, \omega_4, \omega_5\} \ gemeinsames Wissen zwischen Spieler 1 und Spieler 2 ist.

Lösung mittels Definition:
Es gilt:

  •  K_1(E_1)=K_1(\{\omega_1, \omega_2, \omega_3, \omega_4, \omega_5\})= \{\omega_1, \omega_2, \omega_3, \omega_4 \} ,\ weil  P_1(\omega_5)=\{\omega_5,\omega_6\} \not \in E_1
  •  K_2(K_1(E_1))=K_2(\{\omega_1, \omega_2, \omega_3, \omega_4 \})=\{\omega_1, \omega_2, \omega_3\} ,\ weil  P_2(\omega_4)=\{\omega_4,\omega_5\} \not \in K_1(E_1)
  •  K_1(K_2(K_1(E_1)))=K_1(\{\omega_1, \omega_2, \omega_3\})=\{\omega_1, \omega_2\} ,\ weil  P_1(\omega_3)=\{\omega_3,\omega_4\} \not \in K_2(K_1(E_1))
  •  K_2(K_1(K_2(K_1(E_1))))=K_2(\{\omega_1, \omega_2\})=\{\omega_1\} ,\ weil  P_2(\omega_2)=\{\omega_2,\omega_3\} \not \in K_1(K_2(K_1(E_1)))
  •  K_1(K_2(K_1(K_2(K_1(E_1)))))=K_1(\{\omega_1\})=\emptyset , weil  P_1(\omega_1)=\{\omega_1,\omega_2\} \not \in K_2(K_1(K_2(K_1(E_1))))

Da  K_1(K_2(K_1(K_2(K_1(E_1))))) \ leer ist, kann das Ereignis E1 in keinem Zustand  \omega \in \Omega gemeinsames Wissen zwischen Spieler 1 und Spieler 2 sein.

Lösung mittels Satz:
Da das Ereignis E1 kein zwischen den beiden Spielern offensichtliches Ereignis  F \subseteq E_1 enthält, kann es in keinem Zustand  \omega \in \Omega gemeinsames Wissen zwischen Spieler 1 und Spieler 2 sein.

Beispiel A2

Untersucht wird, ob das Ereignis  E_2=\{\omega_1, \omega_2, \omega_3, \omega_4, \omega_5, \omega_6\} \ gemeinsames Wissen zwischen Spieler 1 und Spieler 2 ist.

Lösung mittels Definition:
Es gilt:
 K_1(E_2)=K_2(E_2)=E_2 \
Somit ist  E_2=K_1(E_2)=K_2(E_2)=K_1(K_2(E_2))=K_2(K_1(E_2))=K_1(K_2(K_1(E_2)))=K_2(K_1(K_2(E_2)))=... \ .
Sei  i \in \{1,2\} mit  i \neq j . Dann ist jedes  \omega \in E_2 auch in jeder Menge der Form  K_i(K_j(K_i(...(E_2)...))) \ enthalten, und deshalb ist E2 in jedem Zustand  \omega \in E_2 gemeinsames Wissen zwischen Spieler 1 und Spieler 2.

Lösung mittels Satz:
Da das Ereignis E2 ein zwischen den beiden Spielern offensichtliches Ereignis ist, ist es in jedem Zustand  \omega \in E_2 gemeinsames Wissen zwischen Spieler 1 und Spieler 2.



Ausgangssituation B

Seien  \Omega = \{\omega_1,\dots,\omega_{10}\} \ und P1 bzw. P2 partitionierende Informationsfunktion von Spieler 1 bzw. Spieler 2. Weiter seien K1 bzw. K2 die zu P1 bzw. P2 gehörige Wissensfunktion.
Die durch die Informationsfunktionen induzierten Partitionen seien:
 \mathcal{P}_1=\{\{\omega_1, \omega_2\}, \{\omega_3, \omega_4\}, \{\omega_5\}, \{\omega_6, \omega_7\}, \{\omega_8, \omega_9, \omega_{10}\}\}
 \mathcal{P}_2=\{\{\omega_1, \omega_2, \omega_3\}, \{\omega_4\}, \{\omega_5, \omega_6\}, \{\omega_7, \omega_8\}, \{\omega_9, \omega_{10}\}\}

Beispiel B1

Untersucht wird, ob das Ereignis  F=\{\omega_1, \omega_2, \omega_3, \omega_4, \omega_5, \omega_6, \omega_7, \omega_8, \omega_9\} \ gemeinsames Wissen zwischen Spieler 1 und Spieler 2 ist.

Lösung mittels Definition:
Es gilt:

  •  K_1(F)=K_1(\{\omega_1,\dots,\omega_9\})=\{\omega_1,\dots,\omega_7\} ,\ weil  P_1(\omega_8)=P_1(\omega_9)=\{\omega_8,\omega_9,\omega_{10}\} \not \in F \
  •  K_2(K_1(F))=K_2(\{\omega_1,\dots,\omega_7\})=\{\omega_1,\dots,\omega_6\} ,\ weil  P_2(\omega_7)=\{\omega_7,\omega_8\} \not \in K_1(F)
  •  K_1(K_2(K_1(F)))=K_1(\{\omega_1,\dots,\omega_6\})=\{\omega,\dots,\omega_5\} ,\ weil  P_1(\omega_6)=\{\omega_6,\omega_7\} \not \in K_2(K_1(F))
  •  K_2(K_1(K_2(K_1(F))))=K_2(\omega,\dots,\omega_5\})=\{\omega_1,\dots,\omega_4\} ,\ weil  P_2(\omega_5)=\{\omega_5,\omega_6\} \not \in K_1(K_2(K_1(F)))
  •  K_1(K_2(K_1(K_2(K_1(F)))))=K_1(\{\omega_1,\dots,\omega_4\})=\{\omega_1,\dots,\omega_4\} \
  •  K_2(K_1(K_2(K_1(K_2(K_1(F))))))=K_2(\{\omega_1,\dots,\omega_4\})=\{\omega_1,\dots,\omega_4\} \
  •  K_i(K_j(K_i(K_j(K_i(\dots(F)\dots)))))=\{\omega_1,\dots,\omega_4\} ,\ für jedes weitere Folgenglied, wobei  i \in \{1,2\} und  i \neq j .

Außerdem gilt:

  •  K_2(F)=K_2(\{\omega,\dots,\omega_9\})=\{\omega_1,\dots,\omega_8\} ,\ weil  P_2(\omega_9)=\{\omega_9,\omega_{10}\} \not \in F
  •  K_1(K_2(F))=K_1(\{\omega_1,\dots,\omega_8\})=\{\omega_1,\dots,\omega_7\} ,\ weil  P_1(\omega_8)=\{\omega_8,\omega_9,\omega_{10}\} \not \in K_2(F)
  •  K_2(K_1(K_2(F)))=K_2(\{\omega_1,\dots,\omega_7\})=K_2(K_1(F)) ,\ dann analog siehe zweite Zeile oben.


Also ist das Ereignis F nur in den Zuständen  \omega_1,\omega_2,\omega_3 \ und  \omega_4 \ gemeinsames Wissen zwischen Spieler 1 und 2.
Das Ereignis F ist nicht gemeinsames Wissen zwischen Spieler 1 und 2 in den Zuständen  \omega_5,\omega_6,\omega_7,\omega_8,\omega_9,\omega_{10} \ .

Lösung mittels Satz:
Da das Ereignis  G:=\{\omega_1,\dots,\omega_4\} ein zwischen den beiden Spielern offensichtliches Ereignis ist, ist das Ereignis F in den Zuständen  \omega_1,\omega_2,\omega_3 \ und  \omega_4 \ gemeinsames Wissen zwischen Spieler 1 und Spieler 2.

Quellen

Meine Werkzeuge