Bayes-Spiel

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Bayes-Spiele

Dieser Artikel behandelt Spiele mit unvollständiger Information, die oft auch Bayes-Spiele genannt werden, da sie auf dem Bayes'schen Wahrscheinlichkeitsbegriff beruhen. Bei Spielen mit vollständiger Information hingegen sind alle spielrelevanten Informationen G = {S1,...,Sn,u1,...,un} gemeinsames Wissen. Daher haben alle Spieler denselben Informationsstand. Im Fall von unvollständiger Information ist mindestens ein Aspekt nicht gemeinsames Wissen, d.h. es existiert private Information und daher Informationsasymmetrie. In der Regel ist die Auszahlungsfunktion ui private Information von Spieler i.


Definition

Ein Spiel im Sinne der Spieltheorie, in dem einem oder mehreren Spielern nicht alle für das Spiel relevanten Informationen über andere Spieler bekannt sind (z.B. Nutzen / Payoff) - d.h. die Spielinformation ist unvollständig - wird als Bayes- oder Bayes’sches Spiel bezeichnet. Es ist eine Variante von Spielen in extensiver Form


Einführung

Bayes-Spiele - d.h. Spiele mit unvollständiger Information - wurden erstmal in 1967 von John C. Harsanyi modelliert. Er hat gezeigt, dass sie sich ohne Schwierigkeiten in Spiele mit vollständiger, aber unvollkommener oder imperfekter Information überführen lassen. Davor hat man geglaubt, dass Spiele mit unvollständiger Information überhaupt nicht analysiert werden können. Aufgrund ihrer realitätsnahen Eigenschaften finden Bayes-Spiele viele Anwendungen: z.B. bei Modellierung von Auktionen (keiner weiß, wie viel die anderen Auktionsteilnehmer bereit sind zu bieten), aber auch bei vielen Spielen, die für wirtschaftswissenschaftliche Überlegungen modelliert werden (s. dazu die Projektarbeit Spieltheorie in Finance).

Unter Bedingungen von Bayes-Spielen lassen sich die Lösungskonzepte, die für Spiele mit vollständiger Information entwickelt wurden, nicht direkt anwenden. Nach Erkenntnissen von John C. Harsanyi kann man jedoch solche Spiele als die mit vollständiger, aber unvollkommener / imperfekter Information sehen. So gesehen, ist die Unterscheidung in Spiele mit imperfekter und solche mit unvollständiger Information heute unwesentlich: Spiele mit unvollständiger Information sind Spiele, in denen die Spieler imperfekte Information über die Spielzüge der Natur (als einem Dummy-Spieler) besitzen. Die Natur "wählt" für jeden einzelnen Spieler  i \in M = \{1,...,n\} aus der Spielermenge M gewisse Eigenschaften, die seine Mitspieler nicht beobachten können. Sie sind unsicher darüber, welche konkreten Eigenschaften Spieler i aufweist, die auch als sein Typ bezeichnet werden.
Den Typ eines Spielers i kann man als Zufallsvariable auffassen, deren Realisierung nur von i selbst beobachtbar ist. Die Menge aller für Spieler i denkbaren Charakteristika (die Menge aller für ihn möglichen Typen) werde mit Ti bezeichnet. Die Mitspieler sind unsicher darüber, welche konkreten Eigenschaften t_i \in T_i der Spieler i aufweist. Darüber bilden sich nur bestimmte Wahrscheinlichkeitsvorstellungen, während i selbst natürlich weiß von welchem Typ er ist; ti beschreibt also einen möglichen Zustand der privaten Information des Spielers i. Diese private Information kann aus der Kenntnis der eigenen Präferenzen und Fähigkeiten bestehen, sie kann aber auch seine subjektive Wahrscheinlichkeitseinschätzung über unsichere Ereignisse einschließen.
Jeder Spieler hat gewisse Vorstellungen darüber mit welcher Wahrscheinlichkeit die Natur eine bestimmte Kombination ti der Typen aller Gegenspieler wählt. Sei  (T, \mathcal P (T), \mathbb P ) ein Wahrscheinlichkeitsraum, dann rechnet ein Spieler vom Typ ti damit, dass mit der (bedingten) Wahrscheinlichkeit  \mathbb P(t_{-i} | t_i) gerade die Kombination ti von Gegenspielern festgelegt wurde. Jeder Spieler hat eine Wahrscheinlichkeitsverteilung über die Menge der Typen seiner Gegenspieler Ti = (T1,...,Ti − 1,Ti + 1,...,Tn). Dabei liefert die Kenntnis des eigenen Typs oft auch gewisse Informationen über die Mitspieler.
Die Beschreibung eines Spiels unvollständiger Information erfordert also sowohl eine exakte Angabe aller denkbaren Kombinationen von Typen der Spieler, als auch die Spezifizierung der subjektiven Wahrscheinlichkeitseinschätzungen aller Spieler.

Es wird angenommen, dass die Menge der Wahrscheinlichkeitsverteilungen von Typen anderer Spieler ein gemeinsames Wissen ist. Diese Verteilungen lassen sich als bedingte Wahrscheinlichkeiten mit der Bayes'sche Regel berechnen, wenn man eine gemeinsame Ausgangsverteilung über alle Züge der Natur unterstellt.


Typologisierung

Es werden mögliche Ausprägungen des unbekannten Merkmals, z.B. der Auszahlungsfunktion, festgelegt.

  • Spieler i kann z.B. vom Typ t1,t2,... sein.
  • Es sei Ti der (diskrete oder stetige) Typenraum von Spieler i mit t_i \in T_i.
  • Spieler i kennt seinen eigenen Typ. Die anderen Spieler müssen Erwartungen bezüglich des Typs von Spieler i bilden.
    • Beispiel: Ein Bieter in einer Auktion kennt die Wertschätzung nicht, die ein anderer Bieter i dem auktionierten Gegenstand entgegenbringt. Er weiß aber, dass diese Wertschätzung im Intervall [0,1000] liegt, also ist Ti = [0,1000].
  • Die anderen Spieler k ordnen den möglichen Typen t_i \in T_i,  i \in M \setminus \{k\} subjektive Wahrscheinlichkeiten zu.

Die Vermutungen bzw. Erwartungen eines Spielers i bezüglich des Typs eines oder mehrerer anderer Spieler, die sog. beliefs, sind gemäß dem Wahrscheinlichkeitsbegriff nach Bayes subjektiv.

  • Apriori-Erwartungen: liegen vor Beginn des Spiels vor (prior).
  • Aposteriori-Erwartungen: werden im Spielverlauf aus den Apriori-Erwartungen, den realisierten (beobachteten)

Spielzügen und den bedingten Wahrscheinlichkeiten gebildet (posterior), mit denen die Spielertypen bestimmte Spielzüge durchführen. Die Erwartungen sind dann zwar weiterhin subjektiv, jedoch stets konsistent mit den Beobachtungen.

  • Produkt der Typenräume aller anderen Spieler: T_{-i} = \times_{j \neq i}  T_j
  • Typkonfiguration aller anderen Spieler: t_{-i} \in T_{-i}
  • Wahrscheinlichkeitsbeurteilung von Spieler i vom Typ ti bezüglich einer Typkonfiguration der anderen Spieler: p_i (t_{-i} | t_i), \ t_i \in T_i

Dies ist eine bedingte Wahrscheinlichkeit, weil die Erwartung vom eigenen Typ ti , d.h. von seinen privaten Informationen abhängen kann.

  • Die Strategiewahl von i hängt von seinem eigenen Typ ti sowie von seinen Vermutungen über ti ab.


Auszahlungsfunktion

Die tatsächliche Auszahlung für Spieler i hängt von den gewählten Strategien und von den tatsächlichen Typen der Spieler ab. Dabei hängen die Strategien ihrerseits von den Typen ab:

ui = ui(s1(t1),...,sn(tn),t1,...,tn)

Notation: si(ti) = s1(t1),...,si − 1(ti − 1),si + 1(ti + 1),...,sn(tn)) Also lässt sich ui schreiben als: ui = ui(si(ti),si(ti),ti,ti)


Erwartungsbildung

Die tatsächlich realisierte Auszahlung ui = ui(si(ti),si(ti),ti,ti) kann Spieler i aber nicht bestimmen, weil er die Typkonfiguration ti nicht kennt.


E[u_i (s_i(t_i), s_{-i}(t_{-i}), t_i, t_{-i})] = \sum_{t_{-i}} p_i(t_{-i} | t_{i}) u_i (s_i(t_i), s_{-i}(t_{-i})

Ein rationaler Spieler i maximiert seine erwarteten Auszahlungen. Das setzt allerdings Überlegungen bezüglich des gleichgewichtigen Verhaltens der anderen Spieler voraus.

Nash-Gleichgewicht

Ein Bayes-Nash-Gleichgewicht liegt vor, wenn jeder Spieler jeden Typs jeweils seine Beste Antwort wählt, d.h. diejenige, die seinen (subjektiv) erwarteten Nutzen maximiert. Das Gleichgewicht hängt demnach von den Erwartungen pi aller Spieler jeden Typs ab.

Zur Definition des Gleichgewichts siehe: Bayes-Gleichgewicht.

Eigenschaften des Bayes-Nash-Gleichgewichts:

  • Die Optimalität der Strategiewahl aller Spieler ist lediglich ex ante gegeben. D.h. es besteht vor dem Ausspielen der Strategien

kein Anreiz für einen Spieler, von seiner Strategie abzuweichen. Unter Berücksichtigung der durch die beobachteten Spielzüge offenbarten Informationen müssen ex post die ursprünglichen Strategieentscheidungen nicht mehr optimal sein.

  • Aufgrund der realisierten Strategien werden sich im Allgemeinen die Einschätzungen über den Typ der anderen

Spieler pi(ti | ti) ändern! Es werden Aposteriori-Wahrscheinlichkeiten gebildet.


Verfeinerung der Apriori-Wahrscheinlichkeiten mit Common Priors

Die Wahrscheinlichkeitseinschätzungen der Spieler (priors) sollen auf "objektiven Grundlagen" beruhen.

Common prior: p(t1,...,tn) = p(ti,ti)

Die Bezeichnung "common" suggeriert, dass diese Wahrscheinlichkeiten gemeinsames Wissen darstellen. Basierend auf den common priors ist die totale (unbedingte) Wahrscheinlichkeit, dass Spieler pi vom Typ ti ist, gegeben durch:


p(t_i) = \sum_{t_{-i}} p(t_i, t_{-i})

Nun wenden wir das Bayes-Theorem an und erhalten für p(ti,ti):


p(t_{-i} | t_i) = \frac{p(t_{-i} | t_i) p(t_i)}{p(t_i)} = \frac{p(t_{-i}, t_i)}{p(t_i)} = \frac{p(t_1, ..., t_n)}{\sum_{t_{-i}} p(t_i, t_{-i})}

Wenn also die priors p(t1,...,tn) gemeinsames Wissen sind, dann kann jeder Spieler jede beliebige bedingte Erwartung bezüglich der Typkonfiguration bestimmen. Ansonsten nimmt man alle Typkonfigurationen als gleichwahrscheinlich an, sodass auch alle bedingten Wahrscheinlichkeiten identisch sind.


Beispiel 1 -- Gemeinsame Information

t21 t22 \sum
t11 0.2 0.4 p(t11) = 0.6
t12 0.1 0.3 p(t12) = 0.4
\sum p(t21) = 0.3 p(t22) = 0.7 1


Angenommen, Spieler 1 ist vom Typ t11. Seine Erwartungen sind dann gegeben durch: p(t_{21}|t_{11}) = \frac{0.2}{0.6} = \frac{1}{3} und p(t_{22}|t_{11}) = \frac{0.4}{0.6} = \frac{2}{3}

Gemäß dem Konzept der Common Priors seien hier die Wahrscheinlichkeitsverteilung der möglichen Typkonfigurationen p(t_i, t_j), \ i,j = 1,2, d.h. die obige Matrix, gemeinsames Wissen.


Beispiel 2 -- Einfache Auktion

Setting:

  • Zwei Bieter i = 1,2
  • Wertschätzung vi für das auktionierte Gut ist private Information
  • Typologisierung: t_i = v_i \in [0, 1] = T_i
  • Erwartungen: v_i \sim U[0, 1] (Gleichverteilung auf dem Einheitsintervall)
  • Strategievariable ist das Gebot bi
  • Rationalität erfordert b_i \leq v_i

Die Auszahlungsfunktion sei: 
u_i (b_i , b_j) = \begin{cases}v_i - b_i, falls \ b_i > b_j \\\frac{v_i - b_i}{2}, falls \ b_i = b_j \\0, sonst\end{cases}

Nun berechnen wir die erwartete Auszahlung 
E[u_i] = p(b_i > b_j) \cdot (v_i - b_i) + \underbrace{p(b_i = b_j)}_{=0} \cdot \frac{v_i - b_i}{2} + p(b_i < b_j) \cdot 0 =  p(b_i > b_j) (v_i - b_i)

Wie oben erwähnt erfordert ein rationales Gebot b_j \leq v_j bzw. b_j = \alpha \cdot v_j, \ \alpha \in (0, 1).

p(b_i > b_j) = p(b_i > \alpha \cdot v_j) = p(\frac{b_i}{\alpha} > b_j) = \frac{b_i}{\alpha}, da vj gleichverteilt auf (0,1) ist.

Wir setzen dieses Ergebnis in den erwarteten Gewinn ein uund optimieren diesen:


E[u_i(b_i, b_j)] = (v_i - b_i) \frac{b_i}{\alpha}


\frac{\partial E[u_i]}{\partial b_i} = \frac{v_i}{\alpha} - 2 \frac{b_i}{\alpha} := 0 \Rightarrow b_i^* = \frac{v_i}{2}

Demnach gilt für das optimale Gebot b_i^*: \alpha = \frac{1}{2}, also \frac{b_i}{\alpha} \in [0,1].

Quellen

Ausblick

Für weitere Informationen, zahlreiche Beispiele und verwandte Themen siehe folgende Projektarbeiten (alle bald fertig):

...und Artikel:

Alle relevanten Definitionen sind unter folgenden Artikeln erfasst:


Literatur

Meine Werkzeuge