Invarianz

Aus Wikiludia
Wechseln zu: Navigation, Suche

Im Beispiel Matching Pennies (Zwei Spieler wählen gleichzeitig Kopf oder Zahl. Spieler I gewinnt, wenn seine Vermutung stimmt, andernfalls gewinnt Spieler II) scheint es keinen Grund zu geben, Kopf anstatt Zahl zu wählen. Tatsächlich ist das Problem dasselbe, wenn wir die Namen von Kopf und Zahl auswechseln. In anderen Worten ist das Problem invariant unter dem Austausch der Namen der reinen Strategien. In diesem Artikel erläutern wir den Begriff Invarianz. Wir definieren dann den Begriff einer invarianten Strategie und zeigen, dass in der Suche nach einer Minimax-Strategie ein Spieler seine Aufmerksamkeit auf invariante Strategien legen sollte. Der Gebrauch dieses Ergebnisses vereinfacht die Suche nach Minimax-Strategien in vielen Spielen. So gibt es im beispielhaften Spiel Matching-Pennies nur eine invariante Strategie, entweder Kopf oder Zahl zu nehmen, mit einer Wahrscheinlichkeit von 50%. Deshalb gilt hier das Prinzip der Minimax-Strategie.


Inhaltsverzeichnis


Definition

Invariantes Spiel

Sei \ G = (X,Y,A) ein endliches Spiel und g:X\rightarrow Y eine injektive Abbildung. 
Das Spiel \ G heißt invariant unter \ g, wenn \forall x \in X  ein eindeutiges x' \in X  existiert, so dass:
A(x,y) = A(x', g(y)) ~~ \forall y \in Y. 

Die Bedingung, dass \ x' eindeutig ist, ist nicht einschränkend, denn gäbe es einen weiteren Punkt x'' \in X, so dass

A(x,y) = A(x'', g(y))~~ \forall y \in Y, dann würde

A(x', g(y)) = A(x'', g(y))~~ \forall y \in Y gelten und jede injektive Abbildung auf einer endlichen Menge auch surjektiv ist, folgt

 A(x',y) = A(x'', y)~~ \forall y \in Y. Also haben beide Strategien die selbe Auszahlung, daher kann eine von ihnen ohne Änderung des Problems gestrichen werden.

Ohne Einschränkung der Allgemeinheit setzen wir voraus, dass alle Duplikate solcher reinen Strategien entfernt wurden. D.h.

A(x',y) = A(x'',y) ~~ \forall y \in Y \Longrightarrow x'= x''

A(x,y') = A(x,y'') ~~ \forall x \in X \Longrightarrow y'= y''.

Das \  x' aus der Definition hängt nur von \ g und  \ x ab. Wir definieren  x':=\bar{g}(x) .

Die Abbildung  \bar{g} ist injektiv (also auch surjektiv) auf \ X, weil wenn  \ \bar{g}(x_{1}) = \bar{g}( x_{2}) gilt, folgt:

 A(x_{1},y) = A(\bar{g}(x_{1}), g(y)) = A(\bar{g}(x_{2}), g(y)) = A(x_{2},y) ~~  \forall y \in Y \Longrightarrow x_{1}= x_{2},

was die Behauptung bestätigt. Zudem existiert die Inverse \ g^{-1} von \ g, definiert durch:\ g^{-1}(g(x)) = g( g^{-1}(x)) = x.

Invariante Strategie

Sei \ G = (X,Y,A) ein endliches, unter der Abbildung g:Y\rightarrow Y invariantes Spiel. 
Die gemischte Strategie q:x\rightarrow [0,1], mit \sum\limits_{x\in X}^{}q(x)=1  von Spieler1 heißt invariant unter \ g, wenn \forall x \in X  gilt: \ q(x)=q(g(x)). Spieler 2 analog.

Theorem

Wenn ein endliches Spiel \  G=(X,Y,A)  unter einer Menge \ \mathcal{G}  von Abbildungen invariant ist, das heißt   \forall g \in \mathcal{G}  gilt:  \ g  ist invariant, exisitieren invariante optimale Strategien für die Spieler.

Beweis:

Es genügt zu zeigen, dass Spieler 2 eine invariante optimale Strategie hat. Weil das Spiel endlich ist, existiert eine Auszahlung  \ V und eine optimale gemischte Strategie \   q^{*} für Spieler 2.

Das soll bedeuten dass,

\sum\limits_{y\in Y}^{} A(x,y)q^{*}(y)\leq V , \forall x\in X (\ *)

Wir müssen zeigen, dass eine invariante Strategie \tilde{q} exisitiert, die die selbe Bedingung erfüllt.

Sei N=\left|\mathcal{G}\right| die Anzahl der Elemente von \mathcal{G} .

\tilde{q}(y) := \frac{1}{N} \sum\limits_{g\in \mathcal{G}} ^{}q^{*}(g(y))

Dann ist \ \tilde{q} invariant, weil für jedes \  g' \in \mathcal{G}gilt:

\tilde{q} (g'(y)) = \frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} q^{*}(g(g'(y))=

\tilde{q} (g'(y))= \frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} q^{*}g(y))=\tilde{q}(y) weil die Anwendung von g' auf \ Y=\{1,2,...,n\} nur die Elemente von Y vertauscht. Außerdem erfüllt \tilde{q} (\ *), weil

\sum\limits_{y\in Y}^{} A(x,y)\tilde{q}(y) = \sum\limits_{y\in Y}^{}  A(x,y)\frac{1}{N}  \sum\limits_{g\in \mathcal{G}}^{} q^{*}(g(y))=

  • \frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} \sum\limits_{y\in Y}^{} A(x,y)q^{*}(g(y))=
  • \frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} \sum\limits_{y\in Y}^{} A(\tilde{g}(x),g(y))q^{*}(g(y))=
  • \frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} \sum\limits_{y\in Y}^{} A(\tilde{g}(x),y)q^{*}(y)\leq\frac{1}{N} \sum\limits_{g\in \mathcal{G}}^{} V=V.

q.e.d.

Im Beispiel Matching-Pennies gilt: \ X=Y=\{1,2\} und \ A(1,1)=A(2,2)=1 und \ A(1,2)=A(2,1)=-1

Das Spiel \ G=(X,Y,A) ist invariant unter der Menge \mathcal{G} =\{e,g\}, in der \ e die Identitätsabbildung ist und für \ g gilt: \ g(1)=2 und \ g(2)=1.

Die gemischte Strategie \ (q(1),q(2)) ist invariant unter \mathcal{G}, wenn \ q(1)=q(2). Aus \ q(1)+q(2)=1 folgt, dass q(1)=q(2)=\frac{1}{2} die einzige invariante Strategie für Spieler 2 ist. Außerdem erfüllt es die Minimaxgleichung.

Schere-Stein-Papier ist invariant unter der Menge \mathcal{G}=\{e,g,g^{2}\}, wo \ g(Papier)=Schere, \ g(Schere)=Stein und \ g(Stein)=Papier ist.

Die einzige invariante, also auch minimax, Strategie ist \frac{1}{3} für jeweils Schere, Stein und Papier.

Beispiele

Oberst-Blotto-Spiele

Meine Werkzeuge