Gemischte Strategie

Definition: Gegeben ist ein Spiel in Normalform mit n Spielern {1, ..., n}, S = S1 x S2 x ... x Sn , ui : S → R Voraussetzung |Si | = mi endlich, dann ist Si = {si1, ..., simi } die Menge der reinen Strategien des Spielers i. Jede Wahrscheinlichkeitsverteilung über diese reinen Strategien ist eine gemischte Strategie: Δ Si = Δ(Si) := {(p1i, ..., pmii ) ∈ Rmi : Σ pji = 1 & pji ≥ 0} pji bzw. σij bezeichnet dabei die Wahrscheinlichkeit mit der sij gewählt wird. Im allgemeinen wird eine gemischte Strategie mit σi(p) = (p1i, ..., pmii) dargestellt. Falls für mindestens zwei j die Bedingung 0 < σij < 1 erfüllt ist, liegt eine echte gemischte Strategie vor.

Beispiel: Gegeben sei ein 2 Personenspiel mit folgender Auszahlungsmatrix:

Spieler 1 \ 2	Strategie 1	Strategie 2
Strategie 1	1,   –1	–2,   2
Strategie 2	–2,   2	3,   –3

Dieses Spiel scheint auf dem ersten Blick ein faires Spiel zu sein. Falls die möglichen Strategiekombinationen (1,1),(1,2),(2,1),(2,2) – in Klammern steht die jeweilige Strategie des jeweiligen Spielers - gleichhäufig auftreten, ist die Gewinnerwartung eines jeden Spielers gleich Null. Allerdings ist dieses Spiel nicht gerecht wie gleich aufgezeigt wird. Dabei geht man davon aus, dass beide Spieler jeweils eine gemischte Strategie wählen:

Spieler 1 wählt mit Wahrscheinlichkeit p die Strategie 1 und mit Wahrscheinlichkeit (1-p) die Strategie 2.
Spieler 2 verhält sich analog: Er wählt mir Wahrscheinlichkeit q die Strategie 1 und mit Wahrscheinlichkeit (1-q) die Strategie 2.
Daraus ergeben sich folgende zu erwartende Auszahlungen an die Spieler:

u₁ = 8pq – 5p – 5q + 3                         u₂ = – 8pq + 5p + 5q – 3

Wir erhalten die Nash-Gleichgewichte: p^* = 5/8, q^* = 5/8.

Falls Spieler 2 die Strategie q = q^* = 5/8 wählt, kann Spieler 1 jede beliebige Strategie wählen. Durchschnittlich wird er auf lange Sicht gesehen mindestens pro Spiel einen Verlust von 1/8 hinnehmen müssen, denn:

u₁(σ₁(p^*), σ₂(q^*)) = –1/8                     u₂(σ₁(p^*), σ₂(q^*)) = 1/8

Definition: si ∈ Si ist beste Antwort auf s-i ∈ S-i, wenn: ui(si, s-i) ≥ ui(si', s-i)   ∀si' ∈ Si = sup{ ui(si,s-i): si' ∈ Si} ∈ R   bi(s-i) := {si ∈ Si : si beste Antwort auf s-i} ⊂ Si Aber: Si kompakt und ui stetig   ⇒ bi(si) ≠ Ø

Beispiel: Cournot-Oligopol: Gegeben: n Firmen mit gleichem Produkt. Zusammengefasst: b(s) := (b₁(s_-1), ..., b_n(s_-n)) ^_⊂ S
s ^_∈S, b: S ^_→ S beste Antwort-Korrespondenz. Konkret:
Mit der Preisfunktion p(s) = P – (s₁ + ... + s_n), wobei s_i = Produktionsmenge des Unternehmen i und P den vorhandenen Marktpreis repräsentieren, ergibt sich die Gewinnfunktion u_i(s) = p(s)s_i - cs_i mit Fixkosten c. Die Gewinnfunktion ist zu Maximieren:
^_∂u_i(s) / ^_∂s_i = 0     ^_⇒   0 = P – c – Σ_j=1,j≠i(s_j) – 2s_i               2s_i = P – c – Σ_j≠i(s_i)
Beste Antwort:   b_i = ½ (P – c – Σ_j≠i(s_i))                     Maximum, da ^_∂u_i / ^_∂2s_i(b_i) < 0

Satz: s* ist Nash-Gleichgewicht   ⇔ ∀i ∈{1,...,n}: si* ∈ bi(s-i)   ⇔ s* ∈ b(s*)

Beweis: s^* ist Nash - Gleichgewicht   _^⇔ ∀i u_i(s^*, s_-i) _^≥ u_i(s_i, s_-i) _^⇔ ∀i u_i(s^*, s_-i) _^≥ u_i(s_i', s_-i)
∀i _^∈{1,...,n}: s_i^{* _∈} b_i(s_-i)  _^⇔ ∀i   s^{* _∈} {s_{i ^∈} S_i: u_i(s_i, s_-i) _^≥ u_i(s_i', s_-i)} _^⇔ ∀i u_i(s^*, s_-i) _^≥ u_i(s_i', s_-i)
s^{* _∈} b(s^*)  _^⇔ s^{* _∈} {s^{* _∈} S_i: u_i(s^*, s_-i) _^≥ u_i(s_i', s_-i)} _^⇔ ∀i u_i(s^*, s_-i) _^≥ u_i(s_i', s_-i)

Beste Antwort in gemischten Strategien: Ein weiterer interessanter Aspekt, im Bezug auf die beste Antwort, ist in einem Spiel mit gemischten Strategien gegeben. Ein Spieler wählt eine gemischte Strategie als beste Antwort auf die gemischte Strategie der Anderen.
Die Gleichung

u_i(σ_i,σ_-i) ^_≡ E_σi(u_i(s_i,σ_-i)) ^_≡ Σ_{si∈ Si} u_i(s_i,σ_-i)σ_i(s_i)

stellt den erwarteten Gewinn des Spielers i, bzgl. seiner Strategie σ_i und den anderen Strategien σ_-i der Mitspieler dar.

Definition: Die beste Antwort in einer gemischten Strategie bi: Δ S-i → Δ Si ist definiert durch: bi(σ-i) = {σi ∈ Δ Si: ui(σi, σ-i) ≥ ui(σi', σ-i)   ∀σi' ∈ Δ (Si)} Für jedes σ-i ∈ Δ S-i, ist ui*(σi) = max{ui(si, σi): si ∈ Si}

Korollar: Falls die Bedingungen σi(si) > 0 und ui(si, σ-i) = ui*(σi) erfüllt sind folgt: σi ∈ bi(σ-i)

Beweis: Angenommen die Bedingung u_i(s_i, σ_-i) = u_i^*(σ_-i) und σ_i(s_i) > 0 seien erfüllt, dann ergibt sich mit Σ_{si ^∈ Si} σ_i(s_i) = 1 und σ_i(s_i) ^_≥ 0 für jedes s_{i ^∈} S_i: u_i(σ_i, σ_-i) ^_≡ Σ_{si ^∈ Si} u_i(s_i, σ_-i) σ_i(s_i) = Σ_{si ^∈ Si} u_i^*(σ_-i) σ_i(s_i) = u_i^*(σ_-i) Σ_{si ^∈ Si} σ_i(s_i) = u_i^*(σ_-i). Andererseits muss für jede gemischte Strategie σ_i^- gelten: u_i(σ_i^-, σ_-i) ^_≡ Σ_{si ∈ Si} u_i(s_i,σ_-i) σ_i^-(s_i) ^_≤ Σ_{si ∈ Si} u_i^*(σ_-i) σ_i^-(s_i) = u_i^*(σ_i^-). Aufgrund dessen folgt, falls die Bedingungen σ_i(s_i) > 0 und u_i(s_i, σ_-i) = u_i^*(σ_-i) erfüllt sind: u_i(σ_i, σ_-i) = u_i^*(σ_-i) ^_≥ u_i(σ_i^-, σ_-i) für alle σ_i^{- _∈} Δ S_i. Das wiederum Bedeutet das σ_{i ^∈} b_i(σ_-i) ist.

Bemerkung: Dasselbe Ergebnis kann auch über einen Widerspruchsbeweis erzielt werden. Betrachte dazu die Strategie s_i^* die zusätzlich die Bedingungen σ_i(s_i^*) > 0 und u_i(s_i^*, σ_-i) < u_i^*(σ_-i) erfüllt. Wähle weiter eine Strategie s_i^- mit der Eigenschaft u_i(s_i^-, σ_-i) = u_i^*(σ_-i). Dann folgt aufgrund von

u_i(σ_i, σ_-i) = Σ_{si ∈ Si} u_i(s_i, σ_-i) σ_i(s_i) = u_i(s_i^*, σ_-i) σ _i(s_i^*) + Σ_si≠si* u_i(s_i, σ_-i) σ_i(s_i) ^_≤
≤ u_i(s_i^*, σ_-i) σ_i(s_i^*) + Σ_si≠si* u_i^*(σ_-i) σ_i(s_i) < u_i^*(σ_-i) σ_i(s_i^*) + u_i^*(σ_-i) Σ_si≠si* σ_i(s_i) =
= u_i^*(σ_-i)(σ_i(s_i^*) + Σ_si≠si* σ_i(s_i)) = u_i^*(σ_-i) = u_i(s_i^*, σ_-i)

dass σ_{i ^∉} b_i(σ_-i) ist.