Satz von Kuhn

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Der Satz von Kuhn

Der Satz von Kuhn ist ein fundamentaler Satz über extensive Spiele mit vollkommener Erinnerung. Er besagt nämlich, dass Verhaltensstrategien und gemischte Strategien für die Beschreibung und Lösung der Spiele äquivalent sind. Für die Formulierung des Satzes müssen jedoch zunächst die Begriffe "vollkommene Erinnerung" und "äquivalent" definiert werden.


Vollkommene Erinnerung:

Definition: Ein extensives Spiel hat vollkommene Erinnerung (perfect recall), falls jeder Spieler an jeder seiner Informationsmengen weiß, welche Züge er im bisherigen Spielverlauf an welchen Informationsmengen gewählt hat.

Alternativ: Ein extensives Spiel hat vollkommenes Erinnerungsvermögen, wenn alle eigenen vorangegangen Züge bekannt sind.

(Vgl.: Erinnerungsvermögen)

Äquivalenz zweier Strategien:

Definition: Zwei Strategien eines Spielers heißen äquivalent, falls es für die Realisationswahrscheinlichkeiten von Endpunkten keinen Unterschied macht, ob bei gegebenen Strategien der anderen Spieler die eine oder die andere Strategie von diesem Spieler gewählt wird.

Formulierung des Satzes von Kuhn:


Satz.
G sei ein extensives Spiel mit vollkommener Erinnerung. Dann existiert zu jeder gemischten Strategie \ X_i eine zu \ X_i äquivalente Verhaltensstrategie \ \beta und umgekehrt.


Beweis.

von rechst nach links

Beweisskizze.

Wir bewiesen, dass der Satz gilt für alle Spiele in denen es keine Knoten \ v,u gibt, so dass es ein Pfad von \ v bis \ u gibt, und \ v und \ u gehören zur selben Informationsmenge von Spieler \ i. (Alle Spiele mit vollkommener Erinnerung erfüllen diese Definition.)


Sei \ J_i=(I_i^1,...,1_i^k) die Informationspartitionierung von Spieler \ i, und sei \ \beta=(\beta^1,...,\beta^k) eine Verhaltensstrategie. Wir definieren eine gemischten Strategie \ X_i=(X_i^1,...,X_i^N) für Spieler \ i. Jede reine Strategie \ A_i^l definiert eine Aktion \ A_i^l(I_i^j) für jede Informationsmenge \ I_i^j. Wir setzen die Wahrscheinlichkeit \ X_i^l von \ A_i^l auf

\ A_i^l= \prod_{I_i^j \in J_i} \beta^j(A_i^l(I_i^j))



von links nach rechts

Sei \ X_i eine gemischten Strategie für Spieler \ i. Sei \ \pi_i(v) die Summe der Wahrscheinlichkeiten (nach \ X_i), dass Spieler \ i eine reine Strategie spielt, unter der \ v erreichbar ist.

Sei \ v,u zwei Knoten in der Selben Informationsmenge \ I_i^j. Da \ S vollkommener Erinnerung hat, gilt \ \pi(v)=\pi(u). Für jede reine Strategie \ A_i wird Aktion \ a in \ v genau dann gewählt, wenn sie auch in \ u gewählt wird. Sei \ v^',u^' die Nachfolger von \ v bzw. \ u, die durch Aktion \ a erreicht werden.

Dann gilt \ \pi_i(v^')=\pi_i(u^').

Wir definieren eine Verhaltensstrategie \ \beta=(\beta^1,..., \beta^k) für Spieler \ i. Sei \ v \in I_i^j und \ v^' der Nachfolger von \ v, der mit Aktion \ a erreicht wird. Dann setzen wir \ \beta^j(a)=\pi_i(v^')/\pi_i(v). .

(wie wir \ \beta^j(a) definieren, wenn \ \pi_i(v)=0 ist unwichtig.)

Sei \ A_{-i} ein reines Strategieprofil für die Gegner. Sei \ w ein Blatt von \ T. Wenn \ w unter \ A_{-i} nicht erreichbar ist die Wahrscheinlichkeit, dass \ w erreicht wird 0 unabhängig von der Strategie von Spieler \ i. Nehmen wir also an, dass \ w erreichbar ist unter \ A_{-i}. Wenn der Pfad nach \ w eine Aktion von Spieler \ i enthält, die von \ X_i Wahrscheinlichkeit 0 gegeben wird, hat sie auch unter \ \beta Wahrscheinlichkeit 0. Sei \ v_o,v_1,...,v_n,w die Knoten auf dem Pfad nach \ w. Dann ist die Wahrscheinlichkeit, dass \ w erreicht wird unter Strategieprofil \ (A_i{-i}, \beta)


\ \pi_i(v_1)/\pi_i(v_0) * \pi_i(v_2)/\pi_i(v_1)***\pi_i(w)/\pi_i(v_n)


Da \ v_0 die Wurzel ist gilt \ \pi_i(v_0)=1 Also ist die Wahrscheinlichkeit oben genau \ \pi_i(w), die Wahrscheinlichkeit von \ w unter \ (A_{-i},X_i).

Alternative Formulierung des Satzes von Kuhn:

Satz.
Sei G ein Spiel mit vollkommener Erinnerung. Dann gilt: Für zwei beliebige gemischte Strategien in Δ(Sk), die verhaltensäquivalent sind, sind auch auszahlungsäquivalent.

Beweis:

Für jeden Knoten x in G, sei p(x) das Produkt aller Wahrscheinlichkeiten der Alternativen an den Wahrscheinlichkeitsknoten, die auf dem Weg von dem Ursprung bis x liegen (wobei p(x)=1, falls es keinen solchen Knoten gibt.). Für alle Spieler k sei Bk(x) die Menge aller Strategien von Spieler k, in denen alle nötigen Züge enthalten sind, um Knoten x zu erreichen. Also gilt, dass B_k(x) \subset S_k genau die Teilmenge mit s_k \in B_k(x) ist, äquivalent dazu ist, dass wenn es für jeden Informationszustand i \in I_k und jeden Zug d_i \in D_i einen Ast auf dem Weg von dem Ursprung zu dem Knoten x gibt, der eine Alternative mit Bezeichnung di an einem Entscheidungsknoten für Spieler k mit Informationszustand i ist, dann muss sk(i) = di gelten. Nun sei außerdem: B(x)= \times B_k(x)

Nun gilt: P(x | s) = p(x), wenn s \in B(x) und P(x | s) = 0, wenn s \notin B(x)

Nun: Sei: τ in \times \Delta (S_k) Sei: σ Verhaltensstrategieprofil in \times_k \times_i \Delta(D_i), mit i \in I_k Dabei ist σ die Darstellung von τ als Verhaltensstrategie Sei: Für jeden Knoten x sei \hat{P} (x|\tau) die Wahrscheinlichkeit bezüglich τ (D.h. alle Spieler verhalten sich nach dem Strategieprofil τ x zu erreichen.) D.h. also: \hat{P} (x|\tau)=\Sigma_s (\Pi_k \tau_k (s_k)) P(x|s)= p(x) \Pi_k (\Sigma_{s_{k}\in B_{k}(a)}\tau_k(s_k))

Nun ist zu zeigen: \hat{P} (x|\tau)= \overline{P} (x|\sigma) (i), wobei \overline{P} (x|\sigma) das Produkt aller Wahrscheinlichkeiten bezüglich σ auf dem Weg von dem Ursprung bis x ist. (i) stimmt offensichtlich für den Ursprungsknoten, da \hat{P} (x|\tau)= \overline{P} (x|\sigma)=1

Nun folgt der Beweis per Induktion: Angenommen \hat{P} (y|\tau)= \overline{P} (y|\sigma) ist wahr am Knoten y. Sei nun x der Knoten, der direkt auf y folgt.

Nun gibt es zwei Fälle:

Fall 1: y ist ein Wahrscheinlichkeitsknoten (d.h. die Entscheidung ist für einen Zweig ist durch Wahrscheinlichkeiten determiniert) und der Alternativzweig von y zu x hat die Wahrscheinlichkeit q. \Rightarrow Nach Definition von \overline{P} gilt \overline{P} (y|\tau)= q \overline{P} (y|\sigma) und es gilt \hat{P} (y|\tau)= \Sigma_s (\Pi_k \tau_k (s_k))P(x|s)= \Sigma_s (\Pi_k \tau_k(s_k))q P(y|s)=q \hat{P} (y|\tau) \Rightarrow (i) stimmt.


Fall 2: y gehört zu Spieler k mit Informationszustand r, der Alternativzweig von y zu x wird durch den Zug dr beschrieben. \Rightarrow \overline{P} (x|\sigma) = \sigma_{j.r} (d_r) \overline{P} (y|\sigma) Außerdem gilt: p(x) = p(y) und \forall i \neq j : B_k(x)=B_k(y) Außerdem gilt: Da G vollkommene Erinnerung hat: \Rightarrow B_j(y)=S_{j}^{*}(r) und B_j(x)=S_{j}^{**}(d_r, r)

Also gilt: \hat{P} (x|\tau)= p(x)\Pi_k(\Sigma_{s_k \in B_k(x)} \tau_k (s_k))= p(y) \sigma_{j.r} (d_r) \Pi_k (\Sigma_{s_k \in B_k(y)} \tau_k (s_k)) = \sigma_{j.r} (d_r) \hat{P} (y|\tau), da  \sigma_{j.r} (d_r)(\Sigma_{s_j \in $S_{j}^{*} (r)} \tau_j (s_j))= \Sigma_{s_j \in S_{j}^{**}(d_r, r)} \tau_j (s_j). wobei σj.r die Zug-Wahrscheinlichkeit für Spieler j mit Informationszustand r ist.

Nach Induktionsvorraussetzung gilt (i) für alle Knoten. Wegen (i) hängt die Wahrscheinlichkeitsverteilung über den Auszahlungen nur von den Darstellungen als Verhaltensstrategien ab. Also müssen auch die erwarteten Auszahlungen gleich sein.

Für jeden Spieler k und jedes Verhaltensstrategieprofil σ in \times_k \times_i \Delta (D_i) definiere vk(σ) die erwartete Auszahlung von k wenn alle j ihre Strategie σj benutzen. \Rightarrow v_k(\sigma)=\Sigma_{x \in \Omega} \overline{P} (x|\sigma) w_k(x), wobei Ω die Menge der terminalen Knoten ist und wk(x) die Auszahlung von Spieler k an den terminalen Knoten. Für τ in \times \Delta (S_k) erfüllt die erwartete Auszahlung uk(τ) in der Normal-Darstellung: u_i(\tau)= \Sigma_{x \in \Omega} \hat{P} (x|\tau) w_k(x) Also: Wenn σ Darstellung als Verhaltensstrategie von τ \Rightarrow v_k(\sigma)=u_k(\tau)

Und somit die Behauptung!

Quelle: Game Theory: Analysis of Conflict (Roger B. Myerson)

Satz

(Satz von Zermelo)
Jedes endliche extensive Spiel mit perfekter Information hat ein teilspielperfektes Gleichgewicht.

Beweis: Sei Γ = (N,H,P,ui) ein endliches extensive Spiel mit perfekter Information. Konstruire ein teilspielperfektes Gleichgewicht durch Induktion über die Länge l(Γ(h)) für alle Teilspiele Γ(h). Konstruire parallel dazu Funktionen t_i:H \to \R für alle Spieler i \in N so, dass ti(h) die Auszahlung für Spieler i in einem teilspielperfekten Gleichgewicht im Teilspiel Γ(h) angibt.
Falls l(Γ(h)) = 0, dann ist ti(h) =ui(h) für alle i\in N. Sei ti(h) für alle h \in H mit l(\Gamma(h))\le k bereits definiert. Betrachte nun h*\in H mit l(Γ(h * )) = k + 1 und P(h*)=i.

                        O
                        :
                        :
                        O h*
                     /  |  \
                 a1 / a2 | a3 \
                   /    |    \
                  /     |     \
                 O      O      O
                /\      /\     /\
               /__\    /__\   /__\


Für alle a \in A(h*) ist l(\Gamma(h*,a)) \le k. Setze si(h * ):= \text {argmax} _{a\in A(h*)} </math>ti(h * ,a) und tj(h * ): = tj(h * ,si(h * )) für alle j \in N. Induktiv erhalten wir dabei ein Strategieprofil s, das die Schritt-Abweichungs-Eigenschaft erfüllt. Mit dem Lemma folgt, dass das s ein teilspielperfektes Gleichgewicht ist.
Lemma:
(Ein-Schritt-Abweichung). Sei Γ = (N,H,P,ui) ein extensives Spiel mit perfekter Information und endlichem Horizont. Das Strategieprofil s* ist ein teilspielperfektes Gleichgewicht von Γ genau dann wenn für jeden Spieleri \in N und jede Historie h\in H mit P(h) = i gilt: u_{i|h}(O_h(s*_{-i|h},s*_{i|h}) \ge u_{i|h}(O_h(s*_{-i|h},s_i)) für jede Strategie si des Spielers i im Teilspiel Γ(h), die sich von s * i | h nur in der Aktion unterscheidet, die direkt nach der initialen Historie von Γ(h) vorgeschrieben wird.
Beweis:
Falls s* ein teilspielperfektes Gleichgewicht ist, gilt die Eigenschaft natürlich. Angenommen, s* ist kein teilspielperfektes Gleichgewicht. Dann existieren eine Historie h und ein Spieler i so, dass es eine profitable Abweichung si in Γ(h) gibt. Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass die Anzahl der Historien h' mit der Eigenschaft, dass s_i(h') \not= s*_{i|h}(h') ist, höchstens so groß wie die Länge der längsten Historie in Γ(h) ist. Diese Annahme ist erlaubt, da es zu jeder profitablen Abweichung si von s * i | h eines Spielers i eine profitable Abweichung \tilde s_i(h') dieses Spielers gibt, bei der alle Historien h' mit \tilde s_i(h') \not= s*_{i|h}(h') auf einem Pfad des Spielbaumes liegen. Betrachte dazu etwa die folgende Visualisierung, wobei s * 1 | h = AGILN und s * 2 | h= CF:

                          0 p(h)=1
                         / \
                    A  /     \ B
                     /         \
                  2 0           0 2  
                C  / \ D    E  /  \F
                 /     \      /     \
             1  0     1 0  1 0     1 0
             G /\ H  I /\K  L/\M    N/\O
              /  \    /  \  /  \    /  \
             0    0  0   0 0    0  0    0


Angenommen, s1 = BHKMO ist eine profitable Abweichung von Spieler 1. Dann ist auch \tilde s_1= BGILO eine profitable Abweichung.\tilde s_1 unterscheidet sich aber nur an zwei Historien vons * 1 | h, während die längste Historie in Γ(h) die Länge drei hat. Wegen des endlichen Horizonts von math>\Gamma</math> ist diese Anzahl der Historien h' mit der Eigenschaft, dass s_i(h') \not= s*_{i|h}(h') ist, endlich. Wähle also eine profitable Abweichung si in Γ(h) so, dass die Anzahl der Historien h' mit s_i(h') \not= s*_{i|h}(h') minimal ist. Sei dann h* die längste Historie inΓ(h)) mit s_i(h') \not= s*_{i|h}(h'). Dann ist die initiale Historie in Γ(h,h * ) die einzige, an der sich si | h * von s * i | (h,h * ) unterscheidet. Außerdem ist si | h * eine profitable Abweichung in Γ(h,h * ), da wir gefordert haben, dass h* die längste Historie in Γ(h) mit s_i(h') \not= s*_{i|h}(h') ist, d.h. Γ(h,h * ) ist das gesuchte Teilspiel.

Meine Werkzeuge