Sattelpunkt

Aus Wikiludia
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Definition

Sei  f : X \times Y \to  \mathbb R eine Funktion von zwei Variablen x und y, dann heißt ein Punkt  (x^*,\ y^*) ein Sattelpunkt der Funktion f , falls

  f(x,\ y^*)\le f(x^*,\ y^*)\le f (x^*,\ y)\qquad  \forall x, y \in X \times Y

Zusammenhang zwischen Sattelpunkt und Nash-Gleichgewicht

Die Strategiekombination (\tilde s^{1*},\ \tilde s^{2*}) eines (endlichen) Zweipersonen-Nullsummen-Spiels ist ein Nash-Gleichgewicht:\Leftrightarrow (\tilde s^{1*} , \tilde s^{2*}) ist ein Sattelpunkt der Funktion u.
In der Menge der gemischten Strategien  \exists mindestens ein Sattelpunkt.

Beweis

Aus der Nash-Gleichgewicht Definition folgt:
 \tilde u^1(\tilde s^{1*},\ \tilde s^{2*})\ge\tilde u^1(\tilde s^{1},\ \tilde s^{2*}) und \tilde u^2(\tilde s^{1*},\ \tilde s^{2*})\ge\tilde u^2(\tilde s^{1*},\ \tilde s^{2}).
Aus der Beziehung u2 = − u1 = − u folgt schließlich die Sattelpunkteigenschaft des Strategiepaares (\tilde s^{1*},\ \tilde s^{2*}) (auch Sattelpunktstrategie genannt) bezüglich der reinen oder gemischten Strategien:
\tilde u(\tilde s^1,\ \tilde s^{2*})\le\tilde u(\tilde s^{1*},\ \tilde s^{2*})\le\tilde u(\tilde s^{1*},\ \tilde s^{2})\qquad  \forall \tilde s^i \in \tilde S^i.
Es ist uns bekannt, dass in gemischten Strategien immer ein Nash-Gleichgewicht existiert und somit nach dem oben gezeigten auch ein Sattelpunkt.

Minmax-Darstellung für Sattelpunktstrategien

Sei eine stetige Funktion  f : X \times Y \to  \mathbb R gegeben, wobei  X\subseteq \mathbb R^{n_1} und  Y\subseteq \mathbb R^{n_2} kompakte Mengen sind.

Notwendig und hinreichend für die Existenz eines Sattelpunktes der Funktion  \,f ist die Gültigkeit der folgenden Gleichung:

max_xmin_y \,f(x,y)=min_ymax_x \, f(x,y).

Beweis

  • Notwendige Bedingung:

(x^*\,,y^*) sei ein Sattelpunkt der Funktion \,f, d.h.:
 f\,(x,\,y^*)\le f\,(x^*,\,y^*)\le f\,(x^*,\,y)\qquad  \forall x,\,y.
Dann folgt: max_x f\,(x,\,y^*)\le f\,(x^*,\,y^*)\le min_y f\,(x^*,\,y).
Nun kann man die linke Seite der Gleichung weiter verkleinern und die rechte Seite weiter vergrößern:
min_y max_x f\,(x,\,y)\le f\,(x^*,\,y^*)\le max_x min_y f\,(x,\,y)
\Rightarrow min_y max_x f\,(x,\,y)\le max_x min_y f\,(x,\,y)
Da allgemein gilt: max_x f(x,y)\ge min_y f(x,y)\qquad  \forall x,\,y
\Rightarrow min_y max_x f\,(x,\,y)\ge max_x min_y f\,(x,\,y). Daraus folgt schließlich die Gleichheit wie oben behauptet.

  • Hinreichende Bedingung:

Es gelte nun:  max_x min_yf\,(x,y)= min_y max_x f\,(x,y).
Man nehme die beiden äußeren Extrema für die Werte x * bzw.y * an. Dann gilt:
 max_x min_yf\,(x,y)=  max_x f\,(x,y^*)\ge f\,(x^*,\,y^*)
min_y max_x f\,(x,y)=min_y f\,(x^*,y)\le f\,(x^*,\,y^*) .
Dann folgt: min_y max_x f\,(x,y)=min_y f\,(x^*,y)\le f\,(x^*,\,y^*) \le max_x f\,(x,y^*)=max_x min_yf\,(x,y).
Wegen der Gleichheit der beiden äußeren Größen folgt überall Gleichheit und somit auch  f(x,y^*) \le max_x f(x,y^*)=f(x^*,y^*)=min_y f(x^*,y)\le f(x^*,y). Dies wäre die Sattelpunktdefinition.

Sattelpunkte in reinen Strategien

Man sieht anhand der folgenden Überlegungen, dass die Minmax-Darstellung für Sattelpunktstrategien intuitiv einleuchtend ist.

  • Überlegung des ersten Spielers: Wählt er die j-te Strategie, dann gewinnt er mindestens min_ku_{jk}=min_kU(s_j^1,s_k^2),unabhängig von der Strategie die der zweite Spieler wählt.Seine Schlußfolgerung:er wird diejenige Strategie j wählen, die ihm die Auszahlung  max_j min_k \,u_{jk} liefert.
  • Überlegung des zweiten Spielers: Wählt er die k-te Strategie, dann verliert er höchstens max_ju_{jk}=max_jU(s_j^1,s_k^2).Seine Schlußfolgerung ist diejenige Strategie k zu wählen, die ihm den geringsten Verlust einbringt, nämlich min_kmax_j\,u_{jk}.

Frage:Sind die Funktionswerte aller Sattelpunkte gleich und können Sattelpunkte "gemischt" werden?

Der folgende Satz zeigt, dass beides zutrift:


Sei eine stetige Funktion  f:X\times Y\to \mathbb R gegeben, wobei  X\subseteq \mathbb R^{n_1} und  Y\subseteq \mathbb R^{n_2} kompakte Mengen sind.Ferner seien (\bar x,\bar y) und (\hat x,\hat y) zwei verschiedene Sattelpunkte der Funktion f. Dann sind auch (\hat x,\bar y) und  (\bar x,\hat y) Sattelpunkte der Funktion  \,f und es gilt:

 f(\bar x,\bar y)=f(\hat x,\hat y)=f(\bar x,\hat y)=f(\hat x,\bar y).

Beweis

Wir beweisen die Aussage durch direktes Nachprüfen:

f(\hat x,\bar y)\le f(\bar x,\bar y)\le f(\bar x,\hat y)\le f(\hat x,\hat y)\le f(\hat x,\bar y) \Rightarrow f(\bar x,\bar y)=f(\hat x,\hat y)=f(\hat x,\bar y)=f(\bar x,\hat y).
 (\bar x,\hat y) ist Sattelpunkt:  f(x,\hat y)\le f(\hat x,\hat y)=f(\bar x,\hat y)=f(\bar x,\bar y)\le f(\bar x,y).

Die Sattelpunkteigenschaft von (\hat x, \bar y) wird analog bewiesen.


Dieser Satz rechtfertigt die folgende Definition und zeigt, dass jedes Nash-Gleichgewicht eines Zweipersonen-Nullsummen-Spiels die gleiche Auszahlung für beide Spieler ergibt.

Definition

Sei (s1 * ,s2 * ) ein Nash-Gleichgewicht eines endlichen Zweipersonen-Nullsummen-Spiel Δ. Die Auszahlung  w(\Delta) =\hat{U}( s^{1*}, s^{2*}) an den ersten Spieler heißt auch Wert des Zweipersonen-Nullsummen-Spiels Δ.

Satz

Für die gemischte Erweiterung eines endlichen Spieles gilt folgende äquivalente Formulierung des Nash-Gleichgewichts. \tilde s^*=(\tilde s^{i*},\tilde s^{-i*}) ist genau dann ein Nash-Gleichgewicht, wenn für alle reinen Strategien s_j^i der Spieler i = 1,...,m gilt:

   \tilde U^i(s_j^i,\tilde s^{-i*}) \le \tilde U^i(\tilde s^*)          j=1,...,n_i \qquad i=1,...,m

Beweis

Notwendige Bedingung

Dies folgt unmittelbar aus der Definition des Nash-Gleichgewichts.

Hinreichende Bedingung

Wenn die Ungleichung aus dem Satz für alle reinen Strategien si des i-ten Spielers gilt, dann folgt für alle gemischten Strategien :  \tilde U^i(\tilde s^i,\tilde s^{-i*})=\sum_{j=1}^{n_i} \tilde U^i(s_j^i,\tilde s^{-i*})\tilde s_j^i \le \sum_{j=1}^{n_i} \tilde U^i(\tilde s^*) \tilde s_j^i =\tilde U^i(\tilde s^*)

Satz

Sei w(U) der Wert des Zweipersonen-Nullsummen-Spieles mit der Auszahlungsmatrix U = (ujk) für den ersten Spieler,dann gilt:

             max_jmin_ku_{jk} \le w(U) \le min_kmax_ju_{jk}

Beweis

Nach dem obigen Satz und der Eigenschaft eines Nullsummen-Spiels gilt:

 w \le \sum_{j=1}^{n_1}u_{jk}x_j \qquad k=1,...,n_2  \qquad (1)

 \sum_{k=1}^{n_2}u_{jk}y_k \le w \qquad j=1,...,n_1  \qquad  (2)

Aus (1) folgt w \le min_k max_j u_{jk}.

Aus (2) folgt  w \ge max_j min_k u_{jk}.

Satz

Die Strategiekombination (\tilde s^{1*},\tilde s^{2*}) ist genau dann ein Nash-Gleichgewicht eines Zweipersonen-Nullsummen-Spieles, wenn folgende Beziehungen gelten:

 U(\tilde s^{1*},\tilde s^{2*})=max_{\tilde s^1}min_{\tilde s^2} U(\tilde s^1,\tilde s^2)
 =max_{\tilde s^1}min_k U(\tilde s^1,s_k^2)=min_{\tilde s^2}max_{\tilde s^1}U(\tilde s^1,\tilde s^2)=min_{\tilde s^2}max_j U(s_j^1,\tilde s^2)

Beweis

Da die beste Antwort des ersten Spielers auf die Strategie  \tilde s^2 auch für eine reine Strategie angenommen wird, gilt:

max_{\tilde s^1}U(\tilde s^1,\tilde s^2)=max_j U(s_j^1,\tilde s^2)

und es kann auf beiden Seiten das Minimum genommen werden:

U(\tilde s^{1*},\tilde s^{2*})=min_{\tilde s^2}max_{\tilde s^1}U(\tilde s^1,\tilde s^2)=min_{\tilde s^2}max_j U (s_j^1,\tilde s^2)

Beim fehlenden Teil der Aussage des Satzes wird die beste Antwort des zweiten Spielers auf die Strategie  \tilde s^1 in gleicher Weise betrachtet:

max_{\tilde s^2}[-U(\tilde s^1,\tilde s^2)]=max_k[-U(\tilde s^1,s_k^2)] und es kann wieder auf beiden Seiten das Minimum genommen werden:

-U(\tilde s^{1*},\tilde s^{2*})=min_{\tilde s^1}max_{\tilde s^2}[-U(\tilde s^1,\tilde s^2)]=min_{\tilde s^1}max_k[-U(\tilde s^1,s_k^2)].

Wenn man jetzt das Minuszeichen vor das minmax rauszieht, so wird dieses zu maxmin und es folgt die Aussage des Satzes.

Aus dem Satz ergibt sich Folgendes:

Berechnung der Nash-Gleichgewichte als Sattelpunktstrategien

  • Problem des ersten Spielers

Die Berechnung von  w=max_{\tilde s^1} min_k \sum_{j=1}^{n_1}u_{jk} \tilde s^1_j ist äquivalent zum folgenden Optimierungsproblem (mit  x_j= \tilde s^1_j ):

 w \to max_x
 w \le \sum_{j=1}^{n_1}u_{jk}x_j \qquad k=1,...,n_2
 \sum_{j=1}^{n_1}x_j=1
 x_j \ge 0 \qquad \qquad j=1,...,n_1

Da ein Sattelpunkt der gemischten Erweiterung des Spielers existiert, hat dieses Optimierungsproblem immer eine Lösung.

  • Problem des zweiten Spielers

Die Berechnung von  w=min_{\tilde s^2} max_j \sum_{k=1}^{n_2}u_{jk}\tilde s^2_k ist äquivalent zum folgenden linearen Optimierungsproblem (mit  y_k=\tilde s^2_k):

 w \to min_y
 \sum_{k=1}^{n_2}u_{jk}y_k \le w \qquad j=1,...,n_1
 \sum_{k=1}^{n_2}y_k=1
 y_k \ge 0 \qquad \qquad k=1,...,n_2

Auch hier folgt aus der oben bewiesenen Existenz eines Sattelpunkts die Lösbarkeit dieser Optimierungsaufgabe.

Andere Darstellung der Optimierungsprobleme des 1. und des 2.Spielers

Zu jedem Zweipersonen-Nullsummen-Spiel kann ein strategisch äquivalentes Zweipersonen-Nullsummen-Spiel mit einem Spielwert > 0 konstruiert werden (Addition einer Konstanten zu den Auszahlungen ). Wenn nun der Spielwert w > 0 ist, dann kann bei den Optimierungsaufgaben durch w dividiert werden und es ergibt sich:

  • Problem des ersten Spielers

Sei \check x = \frac x w

 \sum_{j=1}^{n_1}\check x_j \to min
 \sum_{j=1}^{n_1} u_{jk} \check x_j \ge 1 \qquad k=1,...,n_2
 \check x_j \ge 0 \qquad \qquad j=1,...,n_1
  • Problem des zweiten Spielers

Sei \check y = \frac y w

 \sum_{k=1}^{n_2}\check y_k \to max
 \sum_{k=1}^{n_2} u_{jk}\check y_k \le 1 \qquad j=1,...,n_1
 \check y_k \ge 0 \qquad k=1,...,n_2

Beispiel

In einer (kleinen) Stadt sei die folgende Situation gegeben. Eine bestimmte Waare werde nur von zwei Kaufleuten angeboten. Die Kaufleute legen Anfang des Tages unabhängig voneinander den Preis fest. Sei festgelegt, dass eine Änderung des Preises erst am nächsten Tag möglich ist. Es werde angenommen, dass nur drei verschiedene Preise  p_1,\,p_2,\,p_3 (0<\,p_1<\,p_2<\,p_3) gewählt werden. Wenn der billigere Anbieter den Preis p1 hat, dann macht er um a1 Geldeinheiten mehr Gewinn als sein Konkurrent. Er macht um a2 Geldeinheiten mehr Gewinn, wenn p2 sein Preis ist. Beachte man außerdem noch, dass  0<\,a_1<\,a_2 . Jeder der beiden Kaufleute betrachtet den Mehrgewinn seines Konkurrenten als eigenen (fiktiven) Verlust. Es kann außerdem angenommen werden, dass bei gleichem Preis jeder an diesem Tag gleich viel Gewinn macht.


Die Auszahlungsmatrix für den ersten Kaufmann (Spieler) ist:

p_1 \quad p_2 \quad  p_3 Z-Min.
\quad p_1

\quad p_2

\quad p_3

 0  \,\qquad a_1 \quad a_1

-a_1 \quad 0 \quad a_2

-a_1  \, -a_2 \, 0

\,0

 \,-a_1

 \,-a_2

Sp.-Max. 0 \quad a_1 \quad a_2 \,a_2

Es folgt also:

 min\,max(0,\,a_1,\,a_2)=0 \qquad max\,min (0,-a_1,-a_2)=0

Weil beide Werte gleich sind, gibt es einen Sattelpunkt im Wert 0 und dieser Sattelpunkt ergibt sich für das Strategiepaar (p_1,\,p_1).

Siehe auch

Nullsummenspiel

Minimax-Prinzip

Meine Werkzeuge