Bayes-Spiel

Grundidee und Definition

Ein Bayes-Spiel, auch bayessches oder bayesianisches Spiel, ist ein spieltheoretisches Spiel mit unvollständiger Information. Mindestens ein Spieler kennt nicht alle für das Spiel entscheidenden Informationen über die anderen Spieler, insbesondere möglicherweise deren Auszahlungsfunktionen. Das Spiel ist daher zunächst nicht vollständig analysierbar. Die Spieler müssen Vermutungen über die Strategien und Entscheidungen der anderen in Form von Wahrscheinlichkeitsverteilungen, sogenannten beliefs, bilden.

Nach Harsanyis Modell werden Bayes-Spiele als Spiele mit imperfekter Information dargestellt. Dabei kennt mindestens ein Spieler nicht jede zuvor getroffene Entscheidung anderer Spieler oder der Natur. Zufallsentscheidungen werden durch einen zusätzlichen Spieler namens Natur modelliert, der vor allen anderen handelt. Bei Kartenspielen kann beispielsweise die zufällige Kartenverteilung als erster Zug der Natur aufgefasst werden. Schach ist dagegen ein Spiel mit perfekter Information.

Formal wird ein Bayes-Spiel als G = <N; <Tᵢ; Sᵢ; uᵢ; pᵢ>ᵢ∈N> beschrieben. N ist die Menge der Spieler. Tᵢ bezeichnet die möglichen Typen von Spieler i; tᵢ ist der von der Natur gewählte Typ und t₋ᵢ bezeichnet die Typen aller anderen Spieler. Sᵢ ist die Menge der möglichen Strategien von Spieler i, sᵢ eine gewählte Strategie und s₋ᵢ die Strategien der anderen. Die Auszahlungsfunktion uᵢ(sᵢ; s₋ᵢ; tᵢ; t₋ᵢ) hängt von allen gewählten Strategien und Typen ab. pᵢ bezeichnet die beliefs des Spielers i. Ein Gleichgewicht besteht aus den Strategien aller Spieler und ihren beliefs. Eine Strategie legt für jeden möglichen Typ eine Menge von Aktionen fest.

Satz von Bayes als Grundlage

Der Satz von Bayes dient dazu, bedingte Wahrscheinlichkeiten zu berechnen, also Wahrscheinlichkeiten unter der Voraussetzung, dass ein bestimmtes Ereignis bereits eingetreten ist:

P(Aᵢ|B) = [P(B|Aᵢ) · P(Aᵢ)] / P(B).

Dabei bedeutet P(Aᵢ|B) die Wahrscheinlichkeit von Aᵢ unter der Bedingung B. Ausgangspunkt ist P(Aᵢ|B) = P(Aᵢ ∩ B) / P(B). Da P(Aᵢ ∩ B) = P(B|Aᵢ) · P(Aᵢ) gilt, erhält man die Bayes-Formel.

Anschaulich wird der Anteil der zu B führenden Fälle betrachtet, die zugleich über Aᵢ führen. In Bayes-Spielen werden damit beliefs nach einer beobachteten Handlung, einem Signal oder einem Zufallsergebnis aktualisiert. Die nachträgliche Wahrscheinlichkeit eines Typs hängt also sowohl von seiner ursprünglichen Wahrscheinlichkeit als auch davon ab, wie wahrscheinlich das beobachtete Ereignis bei diesem Typ war.

Nicht-sequentielle Spiele und bayessches Nash-Gleichgewicht

Sequentielle Spiele bestehen aus mehreren Runden; die Auszahlung eines Spielers ist die Summe seiner Auszahlungen in den einzelnen Runden. Sind Strategiemengen und Auszahlungsfunktionen in jeder Runde gleich, spricht man von einem wiederholten Spiel. Das ist jedoch keine notwendige Bedingung für ein sequentielles Spiel. Für nicht-sequentielle Spiele wird üblicherweise die Normalform verwendet, während die Extensivform für nicht-sequentielle und sequentielle Spiele geeignet ist.

Das bayessche Nash-Gleichgewicht ist eine Strategiekombination, sofern sie existiert, bei der kein Spieler seine erwartete Auszahlung durch einen Strategiewechsel erhöhen kann. Jeder Spieler berücksichtigt dabei seine beliefs über die Wahrscheinlichkeitsverteilung der Strategien der anderen. Das Konzept entspricht dem Nash-Gleichgewicht bei perfekter und vollständiger Information.

Im Freizeitbeispiel wählen zwei Arbeitskollegen gleichzeitig zwischen Kino und Schwimmbad. Spieler 1 bevorzugt das Kino, Spieler 2 das Schwimmbad. Beide verbringen ihre Freizeit aber lieber mit einem Freund als mit einem Feind. Spieler 1 ist entweder Freund oder Feind, kennt seinen eigenen Typ, und Spieler 2 kennt ihn nicht. Bei Freunden bringt der Besuch derselben Einrichtung eine Auszahlung von 3; bei Feinden bringt das Meiden desselben Ortes eine Auszahlung von 3. Zusätzlich gibt es eine Auszahlung von 2 für die jeweils bevorzugte Freizeitbeschäftigung. Die Typenverteilung ist common knowledge und gleichverteilt: P(Freund) = P(Feind) = 1/2.

Es gibt zwei bayessche Nash-Gleichgewichte: ([Kino, Schwimmbad]; Kino) mit P(Freund|Kino) = P(Feind|Schwimmbad) = 1 sowie ([Schwimmbad, Kino]; Schwimmbad) mit P(Feind|Kino) = P(Freund|Schwimmbad) = 1. In der ersten Schreibweise geben die beiden Einträge für Spieler 1 seine Handlung als Freund beziehungsweise als Feind an; der letzte Eintrag bezeichnet die Handlung von Spieler 2.

Sequentielle Spiele und perfekt bayessches Gleichgewicht

Signalspiele sind eine besondere Form sequentieller Bayes-Spiele und werden meist in einer Variante der Extensivform dargestellt. Stochastische Bayes-Spiele modellieren sequentielle Bayes-Spiele mit Umgebungszuständen und zufälligen Zustandsübergängen.

Das perfekt bayessche Gleichgewicht erweitert das teilspielperfekte Gleichgewicht auf Spiele mit unvollständiger Information. Eine Kombination aus Strategien und beliefs ist ein perfekt bayessches Gleichgewicht, wenn drei Bedingungen erfüllt sind: Für jede Informationsmenge müssen beliefs angegeben werden können, die jedem Knoten dieser Menge eine Wahrscheinlichkeit zuordnen. Jeder Spieler muss angesichts seiner beliefs und der Strategien der Gegner rational handeln; die Strategien müssen also zu teilspielperfekten Ergebnissen führen. Außerdem werden die beliefs auf dem Gleichgewichtspfad mit dem Satz von Bayes bestimmt. Diese drei Forderungen definieren streng genommen nur ein schwach perfektes bayessches Gleichgewicht; für ein perfekt bayessches Gleichgewicht ist eine weitere Bedingung erforderlich.

Im Bier-Quiche-Spiel ist Spieler 1 entweder Softie oder Macho. Die Natur bestimmt den Typ, der nur Spieler 1 bekannt ist. Beide kennen die Verteilung P(Softie) = 0,1 und P(Macho) = 0,9. Als Softie erhält Spieler 1 für Quiche 1 und für Bier 0, als Macho umgekehrt. Spieler 1 bestellt Bier oder Quiche. Spieler 2 beobachtet nur diese Bestellung als Signal und kann sich anschließend duellieren. Er möchte sich nur mit einem Softie duellieren. Spieler 1 erhält für kein Duell immer 2. Spieler 2 erhält 1, wenn er einen Softie duelliert oder ein Duell mit einem Macho vermeidet; sonst erhält er 0.

Spieler 1 hat die Strategien [Bier, Bier], [Quiche, Quiche], [Bier, Quiche] und [Quiche, Bier]. Spieler 2 hat [Duell, Duell], [Kein Duell, Kein Duell], [Duell, Kein Duell] und [Kein Duell, Duell], wobei die Einträge die Reaktionen auf die möglichen Signale bezeichnen.

Es gibt zwei perfekt bayessche Gleichgewichte: ([Quiche, Quiche]; [Duell, Kein Duell]) mit P(Softie|Quiche) = 0,1 und ([Bier, Bier]; [Kein Duell, Duell]) mit P(Softie|Bier) = 0,1. Im ersten Fall folgt dies aus P(Softie|Quiche) = [P(Quiche|Softie) · P(Softie)] / P(Quiche) = (1 · 0,1) / 1 = 0,1. Cho und Kreps erweitern den Gleichgewichtsbegriff um das sogenannte intuitive Kriterium. Es schließt das erste dieser beiden Gleichgewichte aus.

Belief-Anpassung im wiederholten Münzspiel

Ein weiteres Beispiel zeigt die wiederholte Anpassung von beliefs. Ein Spieler wettet auf das Ergebnis einer möglicherweise manipulierten Münze. Eine richtige Vorhersage bringt 1, eine falsche 0. Die Natur wählt gleichwahrscheinlich einen der Typen Immer Kopf (IK), Faire Münze (FM) oder Immer Zahl (IZ). Zu Beginn lauten die beliefs für (IK; FM; IZ) daher (1/3; 1/3; 1/3). Kopf und Zahl haben zunächst dieselbe erwartete Auszahlung, sodass der Spieler zufällig auf Kopf oder Zahl setzt.

Fällt Kopf (K), aktualisieren sich die beliefs zu P(IK|K) = 2/3, P(FM|K) = 1/3 und P(IZ|K) = 0. Fällt Zahl (Z), ergeben sich P(IK|Z) = 0, P(FM|Z) = 1/3 und P(IZ|Z) = 2/3. Für weitere Runden werden die beliefs nach demselben Verfahren angepasst; die Wahrscheinlichkeiten P(K) und P(Z) verändern sich nach jedem Wurf.

Unter der Annahme, dass im ersten Wurf Kopf gefallen ist, gilt P(K) = 5/6 und P(Z) = 1/6. Insgesamt setzt der Spieler zunächst zufällig auf Kopf oder Zahl. Danach setzt er so lange auf das Ergebnis der ersten Runde, bis das Gegenteil eintritt. Tritt das Gegenteil ein, handelt es sich mit Sicherheit um eine faire Münze; ab diesem Zeitpunkt wählt der Spieler seine Strategie wieder zufällig.