Nash-Gleichgewicht:Berechnung in gemischten Strategien

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Vorausgehende Definitionen

Zu einem Spiel in Normalform (M,S,u) mit M=\{1,\ldots,N\}, S=S_1 \times S_2
\times \ldots \times S_N, S_i = (s_i^1, \ldots s_i^{m_i}) endlich, u =
(u_i)_{i \in M}, u_i : S \rightarrow \mathbb R ist eine gemischte Strategie eines Spielers i eine Wahrscheinlichkeitsverteilung über dessen Strategiemenge Si:


\Delta S_i = \Delta(S_i) := \left\{ \sigma_i \mathrm{ ist  Wahrscheinlichkeitsverteilung} \right\}

das heißt \sigma_i = (p_1^i, \ldots p_{m_i}^i), mit p_j^i \in [0,1] \subset \mathbb R
\wedge \sum p_j^i = 1 \ \forall{1 \leq j \leq m_i}

Ein Nash-Gleichgewicht ist eine Strategiekombinationen (\sigma_1^*,\ldots,\sigma_n^*), für die gilt: \forall \sigma_i \in
\Delta S_i : u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(\sigma_i, \sigma_{-i}^*)

Allgemeine Betrachtung von gemischten Strategien

In gemischten Strategien hat ein Spieler die Möglichkeit alle reinen Strategien mit einer gewissen Wahrscheinlichkeit zu spielen. Dies beinhaltet die Möglichkeit manche reinen Strategien mit der Wahrscheinlickeit 0 zu spielen, also gar nicht. Eine gemischte Strategie ist somit eine Auswahl und Gewichtung der reinen Strategien untereinander. Dabei bringt es dem Spieler keinen Nutzen zwei reine Strategien zu mischen (also beide mit einem Gewicht 0 < p < 1 zu versehen), wenn eine der beiden Strategien in jeder Situation besser ist als die andere z.B. weil die eine Strategie die andere dominiert. Andererseits ist es auch nicht von Vorteil eine Strategie in der Auswahl wegzulassen (sie mit Gewicht p=0 zu versehen), wenn diese in manchen Situationen besser ist als eine andere gewählte Strategie.

Suchvarianten

Um Nash-Gleichgewichte in gemischten Strategien zu finden gibt es mehrere mögliche Vorgehensweisen.

Kombinatorische Suche von Nash-Gleichgewichten

Sucht man nach Nash-Gleichgewichten in gemischten Strategien, so muss man alle Kombinationen von gemischten Strategien aller Spieler miteinander vergleichen. Um diese Menge an Kombinationen systematisch zu untersuchen klassifiziert man die gemischten Strategien eines Spielers in Klassen von Kombinationen, die die gleichen reinen Strategien verwenden (p > 0) bzw weglassen (p = 0) und vergleicht diese mit den Klassen der Strategien der anderen Spieler.

Jedes Element \kappa \in \mathfrak{P}(S_i) \setminus \emptyset der Potenzmenge der reinen Strategien eines Spielers entspricht so einer Klasse und lässt sich durch ein Polynom darstellen: P(\kappa) = x_1s_1 + \ldots + x_Ms_M, wobei M:=\|\kappa\|<N und alle in κ nicht vorkommenden Strategien \bar
\kappa := S_i \setminus \kappa fehlen in diesem Polynom.

Es gilt nun den Raum K := \mathfrak{P}(S_1) \times \ldots \times
\mathfrak{P}(S_N) auf Nash-Gleichgewichte zu untersuchen. Für jedes k=(k_1,\ldots,k_N) \in K gilt es nun die in der allgemeinen Betrachtung genannten Eigenschaften einer sinnvollen Strategiekombination zu prüfen. Dazu hält man alle ki fest und prüft für dieses \kappa := k_i \subset S_i = (\kappa_1, \ldots,
\kappa_M), ob

  1. alle in der Kombination vorkommenden Strategien den gleichen Nutzen haben  \forall_{j,l \leq M, j \neq l} u_i(\kappa_j, P(k_{-i})) = u_i(\kappa_l, P(k_{-i}))
  2. alle nicht in der Kombination vorkommenden Strategien schlechter sind  \forall_{j \leq M} \forall_{\bar \kappa \in S_i \setminus \kappa} u_i(\kappa_j, P(k_{-i})) > u_i( \bar \kappa, P(k_{-i}))

Dabei ist P(k_{-i}) = \prod_{t \in k_{-i}} P(t) und wie üblich k_{-i} = (k_1,
\ldots, k_{i-1}, k_{i+1}, \ldots, k_N).

Diese Eigenschaften muss man für alle k \in K und alle ki in k prüfen um potentielle Nash-Gleichgewichte zu identifizieren. Führen die (Un-) Gleichungen zu einem Widerspruch, so kommt diese Kombination von Strategieklassen nicht für ein Nash-Gleichgewicht in Frage. Führen die (Un-) Gleichungen zu keinem Widerspruch, so ergibt sich eine Belegung für die Faktoren der Polynome für die noch die Bedingung für ein Nash-Gleichgewicht zu prüfen ist:


\forall \sigma_i \in
\Delta S_i : u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(\sigma_i, \sigma_{-i}^*)

Meine Werkzeuge