Bayes-Spiel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Bayes-Spiel bezeichnet in der Spieltheorie ein Spiel mit unvollständiger Information, welches nach dem englischen Mathematiker Thomas Bayes benannt ist. Das Bayestheorem, mit dessen Hilfe man bedingte Wahrscheinlichkeiten berechnen kann, bildet die Grundlage für Lösungskonzepte dieser Spielart.

Bayes-Spiele sind als Spiele mit imperfekter Information modellierbar.

Definition[Bearbeiten]

In einem Spiel mit unvollständiger Information gibt es mindestens einen Spieler, welcher nicht sämtliche, für das Spiel entscheidende Informationen (i.A. Auszahlungsfunktionen) über die anderen Spieler besitzt. Bayes-Spiele sind damit a Priori nicht analysierbar. Es müssen Vermutungen über die Strategien und Entscheidungen der anderen Spieler in Form von Wahrscheinlichkeitsverteilungen (beliefs) aufgestellt werden.

Nach einem Modell von Harsanyi[1][2] werden Bayes-Spiele mit Hilfe solcher beliefs als Spiele mit imperfekter Information dargestellt und analysiert. In einem solchen Spiel gibt es mindestens einen Spieler, welchem nicht jede zuvor getroffene Entscheidung (sowohl anderer Spieler als auch Zufallsentscheidungen) bekannt ist. Für alle nicht von Spielern getroffenen Zufallsentscheidungen wird ein neuer Spieler (Natur genannt) eingeführt, der diese vor allen anderen Entscheidungen trifft. Somit können dieselben Lösungskonzepte wie bei Spielen mit imperfekter Information angewendet werden.

Beispielsweise ist in Kartenspielen die Verteilung der Karten zufällig und damit in den meisten Fällen unbekannt. Betrachtet man die Verteilung der Karten als ersten Zug des Spielers Natur, so haben die Spieler imperfekte Information über die bisher getroffenen Entscheidungen. Im Gegensatz dazu ist Schach ein klassisches Beispiel für Spiele mit perfekter Information.

Dabei gilt formal für ein Spiel G=<N;\; <T_i; \;S_i;\; u_i;\; p_i>_{i\in N}>:

  1. N bezeichnet die Menge der Spieler
  2. T_i bezeichnet die möglichen Typen des Spielers i. Dabei ist t_i der von der Natur gewählte Typ, t_{-i} sind die Typen aller anderen Spieler.
  3. S_i ist die Menge aller möglichen Strategien von Spieler i. Dabei ist s_i eine gewählte Strategie und s_{-i} sind die Strategien aller anderen Spieler.
  4. u_i(s_i;\;s_{-i};\;t_i;\;t_{-i}) ist die Auszahlungsfunktion für Spieler i. Diese ist abhängig von allen gewählten Strategien und Typen.
  5. p_i sind die beliefs des Spielers i.

Ein Gleichgewicht besteht aus der Strategie jedes Spielers und deren beliefs. Eine Strategie ist eine Menge von Aktionen für jeden möglichen Typ.

Mathematische Grundlagen (Bayestheorem)[Bearbeiten]

Graphische Veranschaulichung des Bayestheorems
Hauptartikel: Bayestheorem

Mit Hilfe des Bayestheorem (auch Satz von Bayes genannt) lassen sich bedingte Wahrscheinlichkeiten berechnen:

 P(A_i|B) \; = \; \frac {P(B|A_i) \cdot P(A_i)} {P(B)}

Dabei gilt für die Wahrscheinlichkeit von A_i bedingt B :

 \begin{align}
P(A_i|B) \; &= \; \frac {P(A_i \cap B)}{P(B) }\\ &= \;  \frac {\frac {P(A_i \cap B)}{P(A_i)} \cdot P(A_i)}{P(B)} \\ &= \; \frac {P(B|A_i) \cdot P(A_i)} {P(B)}
\end{align}

Anschaulich also - wie im Bild rechts - ist die Wahrscheinlichkeit, dass A_i (rot) eintrifft, unter dem Wissen dass B eingetroffen ist (gelber Bereich), gerade der Anteil des über A_i zu B führenden Astes an allen zu B führenden Ästen.

Nicht-sequentielle Spiele und sequentielle Spiele[Bearbeiten]

Sequentielle Spiele sind runden-basierte Spiele, bei denen die Auszahlungen der Spieler gerade die Summen der Auszahlungen der Spieler in jeder Runde sind. Sind in jeder Runde die Strategiemengen und Auszahlungsfunktionen identisch, spricht man auch von wiederholten Spielen. Dies ist jedoch keine Voraussetzung für sequentielle Spiele.

Je nach Spielart eignen sich unterschiedliche Darstellungsformen. Üblicherweise verwendet man die Normalform nur für nicht-sequentielle Spiele. Die Extensivform wird hingegen sowohl für nicht-sequentielle als auch für sequentielle Spiele benutzt.

Signalspiele bezeichnen eine besondere Art sequentieller Bayes-Spiele, die meist in einer Variante der Extensivform dargestellt werden.

Nicht-sequentielle Spiele[Bearbeiten]

Bayessches Nash-Gleichgewicht[Bearbeiten]

Beispiel 1: nicht sequentielles Bayes-Spiel mit Spielertypen

Das Bayessche Nash-Gleichgewicht bezeichnet eine Strategiekombination (falls vorhanden), bei der kein Spieler seine erwartete Auszahlung durch einen Strategiewechsel verbessern kann. Dabei muss er seine Vermutungen über die Wahrscheinlichkeitsverteilung (beliefs) für die Strategien der anderen Spieler berücksichtigen. Dieses Konzept ist analog zum Nash-Gleichgewicht im Fall von Spielen mit perfekter und vollständiger Information.

Beispiel[Bearbeiten]

In diesem Spiel planen zwei Arbeitskollegen ihre Freizeitbeschäftigung. Dabei stehen die Möglichkeiten Schwimmbad und Kino zur Wahl. Spieler 1 geht lieber in das Kino, Spieler 2 würde das Schwimmbad vorziehen. Natürlich verbringen beide ihre Freizeit lieber mit einem Freund als mit einem Feind. Allerdings weiß Spieler 2 nicht, wie sehr Spieler 1 ihn mag.

Spieler 1 ist entweder vom Typ Freund oder Feind und er selbst kennt seinen Typ. Die Auszahlungen sind abhängig von ihrem Verhältnis zueinander und der Wahl der Freizeitbeschäftigung: Sind sie Freunde und besuchen die gleiche Einrichtung, erhalten sie eine Auszahlung von 3. Sind sie Feinde möchten sie sich lieber meiden und erhalten eine Auszahlung von 3, wenn sie nicht am selben Ort sind. Zusätzlich erhalten sie die Auszahlung 2 für die bevorzugte Freizeitbeschäftigung.

Die Wahrscheinlichkeitsverteilung über die Typen von Spieler 1 ist common knowledge und gleichverteilt: P(Freund) = P(Feind) = 1/2. Da die Spieler gleichzeitig entscheiden (keine Absprache möglich), muss Spieler 2 Vermutungen über die Wahl von Spieler 1 aufstellen.

Es gibt 2 Bayessche Nash-Gleichgewichte, bei denen sich kein Spieler durch Abweichen von seiner Strategie besser stellen kann.

Im ersten Gleichgewicht mit ([Kino, Schwimmbad]; Kino) gilt gerade P(Kino|Freund)=1 und P(Schwimmbad|Feind)=1. Damit folgt nach Bayes P(Freund|Kino)=P(Feind|Schwimmbad)=1. Analoges Vorgehen im zweiten Gleichgewicht mit ([Schwimmbad, Kino]; Schwimmbad) liefert insgesamt:


\begin{align}
&([Kino, Schwimmbad]; &Kino)&; \text{ mit } P(Freund|Kino)= P(Feind|Schwimmbad)=1 \;) \\ 
&([Schwimmbad, Kino]; &Schwimmbad)&; \text{ mit } P(Feind|Kino)=P(Freund|Schwimmbad)=1 \;) \\ 
\end{align}

Sequentielle Spiele[Bearbeiten]

Perfektes Bayessches Gleichgewicht[Bearbeiten]

Das Perfekte Bayessche Gleichgewicht ist eine Weiterentwicklung des Teilspielperfekten Gleichgewichts für Spiele mit unvollständiger Information.

Eine Menge von Strategien und Vermutungen über Wahrscheinlichkeitsverteilungen (beliefs) nennt man Perfektes Bayessches Gleichgewicht, wenn folgende Voraussetzungen erfüllt sind:

  1. Jeder Spieler muss für jede Informationsmenge beliefs angeben können, welche jedem Knoten dieser Menge eine Wahrscheinlichkeit zuordnet.
  2. Jeder Spieler handelt, gegeben seiner beliefs und der Strategie der Gegner, rational. Das heißt die Strategien führen zu teilspielperfekten Ergebnissen.
  3. Die beliefs auf dem Gleichgewichtspfad werden mit Hilfe des Bayestheorem ermittelt.

Bemerkung: Diese Forderungen definieren streng genommen nur ein schwach perfektes bayessches Gleichgewicht. Für ein perfektes bayessches Gleichgewicht bedarf es einer weiteren Bedingung.

Beispiele[Bearbeiten]

Beispiel 1[Bearbeiten]
Beispiel 1: Bier-Quiche Spiel

Im sogenannten Bier-Quiche-Spiel (erstmals von Cho und Kreps behandelt[3]) gibt es zwei Spieler:

Spieler 1 ist entweder ein Softie oder ein Macho. Von welchem Typ Spieler 1 ist wird von der Natur vorgegeben und ist nur ihm selbst bekannt. Dabei kennen beide Spieler die Wahrscheinlichkeitsverteilung: P(Softie) = 0,1 und P(Macho) = 0,9. Er hat die Wahl zum Frühstück Bier oder Quiche zu bestellen. Als Softie erhält er durch Quiche eine Auszahlung von 1 und durch Bier 0, als Macho umgekehrt.

Spieler 2 trifft später Spieler 1 und hat die Möglichkeit sich zu duellieren. Er möchte sich jedoch nur duellieren, falls Spieler 1 ein Softie ist. Jedoch kennt Spieler 2 von Spieler 1 nicht den Typ, sondern nur dessen Frühstücksbestellung (Signal). Spieler 1 möchte in keinem Fall ein Duell und bekommt für kein Duell immer Auszahlung 2. Spieler 2 bekommt Auszahlung 1, falls er sich mit einem Softie duelliert oder das Duell mit einem Macho meidet. In allen anderen Fällen erhält er Auszahlung 0.

Die Graphik rechts veranschaulicht dieses Signalspiel mit aufaddierter Auszahlung.

Mögliche Strategien für Spieler 1 sind:

  1. Spiele Bier egal ob Macho oder Softie, kurz: [Bier,Bier],
  2. Spiele Quiche egal ob Macho oder Softie: [Quiche,Quiche] ,
  3. Spiele Bier als Macho und Quiche als Softie: [Bier,Quiche] und
  4. Spiele Quiche als Macho und Bier als Softie: [Quiche,Bier].

Mögliche Strategien für Spieler 2 sind:

  1. Spiele immer Duell, egal welches Signal, kurz: [Duell,Duell],
  2. Spiele immer Kein Duell, egal welches Signal: [Kein Duell,Kein Duell],
  3. Spiele Duell, falls Signal Bier, sonst Kein Duell: [Duell,Kein Duell] und
  4. Spiele Kein Duell, falls Signal Bier, sonst Duell: [Kein Duell,Duell].

Es gibt zwei Perfekte Bayessche Gleichgewichte:

Im ersten Gleichgewicht mit ([Quiche, Quiche]; [Duell, Kein Duell]), gilt P(Quiche|Softie) = P(Quiche|Macho) = 1. Mit dem Bayestheorem ergibt sich gemäß Forderung 3 der belief von Spieler 2:

P(Softie|Quiche) =\frac{P(Quiche|Softie) \cdot P(Softie)}{P(Quiche)}=\frac{1\cdot 0,1}{1}=0,1.

Analog ergibt sich im zweiten Gleichgewicht ([Bier, Bier]; [Kein Duell, Duell]) die beliefs P(Softie|Bier) = 0,1 .

Insgesamt gilt also:


\begin{align}
&((&[Quiche&, Quiche]&;\;[Duell,Kein \;  Duell])&;\; P(Softie|Quiche) =0,1)\text{ und}\\ 
&((&[Bier&, Bier]&;\;[Kein \; Duell, Duell])&;\; P(Softie|Bier) =0,1)
\end{align}

Beide Gleichgewichte erfüllen zwar die Bedingungen an ein Perfektes Bayessches Gleichgewicht, Cho und Kreps erweitern aber den Gleichgewichtsbegriff um eine weitere Forderung. Im Allgemeinen wird diese intuitives Kriterium genannt und sorgt dafür, dass das erste Gleichgewicht ausgeschlossen wird[4].

Beispiel 2[Bearbeiten]

Dieses Beispiel veranschaulicht, wie beliefs im Laufe eines wiederholten Spiels mit Hilfe des Bayestheorems angepasst werden. Es gibt nur einen Spieler, der auf das Ergebnis eines eventuell manipulierten Münzwurfs wettet. Eine richtige Voraussage bringt eine Auszahlung von 1, ansonsten 0. Die möglichen Münztypen werden von der Natur vorgegeben und sind gleich wahrscheinlich: Immer Kopf (IK), Faire Münze (FM) und Immer Zahl (IZ).

In der ersten Runde setzt der Spieler seine beliefs entsprechend der Wahrscheinlichkeitsverteilung der Typen auf (1/3; 1/3; 1/3) für (IK; FM; IZ). Zunächst bringt Strategie Kopf dieselbe erwartete Auszahlung wie Strategie Zahl. Der Spieler setzt also beliebig auf Kopf oder Zahl und wirft anschließend die Münze. Bevor er ein weiteres Mal setzt, passt er seine beliefs mit Hilfe des Bayestheorems an:

Kopf (K) wird geworfen:

Änderung der beliefs in Abhängigkeit vom Ereignis


\begin{align}
P(IK|K)&=\frac{P(K|IK)\cdot P(IK)}{P(K)}&&= \frac{1 \cdot 1/3}{1/2}&&= \frac{2}{3}  \\
P(FM|K)&=\frac{P(K|FM)\cdot P(FM)}{P(K)}&&=\frac{1/2 \cdot 1/3}{1/2}&&=\frac{1}{3} \\
P(IZ|K)&=\frac{P(K|IZ)\cdot P(IZ)}{P(K)}&&= \frac{0 \cdot 1/3}{1/2}&&=0   \\
\end{align}

Zahl (Z) wird geworfen:


\begin{align}
P(IK|Z)&=\frac{P(Z|IK)\cdot P(IK)}{P(Z)}&&=  \frac{0 \cdot 1/3}{1/2}&&=0   \\  
P(FM|Z)&=\frac{P(Z|FM)\cdot P(FM)}{P(Z)}&&=\frac{1/2 \cdot 1/3}{1/2}&&=\frac{1}{3} \\
P(IZ|Z)&=\frac{P(Z|IZ)\cdot P(IZ)}{P(Z)}&&= \frac{1 \cdot 1/3}{1/2}&&=  \frac{2}{3}  \\ 
\end{align}

Geht das Spiel weiter, werden die beliefs wie oben angepasst. Dabei ist nur zu beachten, dass sich die Wahrscheinlichkeiten P(K) beziehungsweise P(Z) nach jedem Wurf ändern. Unter der Annahme, dass im ersten Wurf Kopf gefallen ist, gilt:


\begin{align}
P(K)&= P(IK|K)\cdot P(IK)+P(FM|K)\cdot P(FM)+P(IZ|K)\cdot P(IZ)=2/3 \cdot 1 + 1/3 \cdot  1/2 + 0 \cdot 0= 5/6 \text{ und} \\
P(Z)&=1-P(K)=1/6
\end{align}

Insgesamt setzt der Spieler also im ersten Zug zufällig (gleichverteilt) auf Kopf oder Zahl. Danach wird er solange auf das Ergebnis der ersten Runde setzten, bis das Gegenteilige eintritt. Sofern dieser Fall überhaupt irgendwann eintritt, wird er ab diesem Zeitpunkt seine Strategie wieder zufällig wählen, da es sich mit Sicherheit um eine faire Münze handelt.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  1.  Robert Gibbons: A Primer in Game Theory. Financial Times, Harlow 1992, ISBN 978-0-7450-1159-2.
  2.  Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, ISBN 978-0-262-06141-4.
  3.  John A. Hartigan: Bayes Theory. Springer, New York, Heidelberg 1983, ISBN 3-540-90883-8.

Einzelnachweise[Bearbeiten]

  1.  John C. Harsanyi: Games with Incomplete Information Played by "Bayesian" Players Part I. The Basic Model. In: Management Science. 14, Nr. 3, INFORMS, 1967.
  2.  Drew Fudenberg, Jean Tirole: Game Theory. The MIT Press, Cambridge, Massachusetts 1991, ISBN 978-0-262-06141-4. S.209 ff.
  3.  In-Koo Cho and David M. Kreps: Signaling Games and Stable Equilibria. In: The Quarterly Journal of Economics. 102, Nr. 2, 1987, S. 183-187 (online, abgerufen am 24. Januar 2012).
  4.  In-Koo Cho and David M. Kreps: Signaling Games and Stable Equilibria. In: The Quarterly Journal of Economics. 102, Nr. 2, 1987, S. 185 (online, abgerufen am 24. Januar 2012).