Nullsummenspiel:unendliche Strategiemengen

Aus Wikiludia
Wechseln zu: Navigation, Suche

Als Ergänzung zu den endlichen Zweipersonen-Nullsummenspiele beschäftigt sich dieser Artikel mit den unendlichen Spielen, d.h. Spiele mit zwei Spielern, wobei jeder unendlich viele Strategien zur Verfügung hat. Es wird außerdem noch ein besonderer Fall unendlicher Spiele (Spiele auf dem Einheitsquadrat) näher betrachtet und analysiert.

Inhaltsverzeichnis

Definition

Sei uij die erwartete Auszahlung von Spieler 1 an Spieler 2, wenn der 1.Spieler die reine Strategie i und der 2.Spieler die reine Strategie j wählt. Eine gemischte Strategie für den ersten Spieler ist eine Folge x = (x1,x2,...) reeller Zahlen, wobei folgendes gilt:

 (1)\quad \sum_{i=1}^\infty x_i=1

 (2)\quad x_i\ge 0 .

Analog definiert man die gemischte Strategie für den 2.Spieler als eine Folge y = (y1,y2,...) wobei für yi auch (1) und (2) gelten soll.

Die Auszahlungsfunktion der gemischten Strategie (x,y) wird dann folgendermaßen definiert:

 A(x,y)=\sum_{i,j=1}^\infty x_i u_{ij} y_j\qquad (3)

(falls diese unendliche Reihe konvergiert).

Probleme

Bei Spielen mit abzählbar vielen Strategien können folgende Schwierigkeiten aufweisen:

  • Die Reihe (3) konvergiert nicht.
  • Die Reihen
\sum_{i=1}^\infty \sum_{j=1}^\infty x_i u_{ij} y_j und
 \sum_{j=1}^\infty \sum_{i=1}^\infty x_i u_{ij} y_j

besitzen verschiedene Grenzwerte.

  • Die Menge der gemischten Strategien muss außerdem nicht notwendig kompakt sein, d.h. Maxima und Minima müssen nicht unbedingt existieren.


Folgendes Beispiel soll diese Schwierigkeiten verdeutlichen:


Beispiel mit abzählbar unendlicher Strategienmenge

Gegeben seien die zwei Spieler 1 und 2.
Die Auszahlungsfunktionen der beiden Spieler seien gegeben durch:

u_{i\,j} = 1 für  i\,>\,j
u_{i\,j} = -1 für  i\,<\,j
u_{i\,j} = 0 für  i\,=\,j

und

v_{i\,j}=-u_{i\,j}, wobei i,j natürliche Zahlen seien.

Wir können die Auszahlung auch als halbunendliche Matrix schreiben in der Form:


\begin{pmatrix}0&-1&-1&...&-1\\+1&0&-1&...&-1\\...&+1&0&-1&...\\ ...&...&+1&0&-1\\+1&...&...&...&...\end{pmatrix}


Beobachtung:

Das Spiel hat keinen Spielwert (Wert des Spiels) in reinen Strategien.
Begründung:
Wir bestimmen das Minimum der einzelnen Spalten. Man erkennt, dass für alle Spalten das Minimum -1 beträgt. Folglich gilt

 \max_{n}\min_{m}u_{n\,m}=-1

Die Bestimmung der Maxima der einzelnen Zeilen der Matrix liefert -1, folglich

 \min_{m}\max_{n}u_{n\,m}=+1


Behauptung

Die gemischte Erweiterung hat keinen Spielwert.
Wir sagen etwas präziser:


\inf_{y}\sup_{x} U_{xy} = +1

\sup_{x}\inf_{y} U_{xy} = -1


Spiele auf dem Einheitsquadrat

Beschreibung

Spiele auf dem Einheitsquadrat sind ein wichtiger Typ der unendlichen Spiele, bei dem die Spieler ein Kontinuum von reinen Strategien haben, die als Punkte im Intervall [0,1] dargestellt werden. Anders formuliert: Die reine Strategie eines Spielers ist eine reelle Zahl auf diesem Intervall. Die reellwertige Auszahlungsfunktion ist auf dem Einheitsquadrat [0,1]x[0,1] definiert, mit Werte in \mathbb R. Eine gemischte Strategie ist eine Wahrscheinlichkeitsverteilung auf der Menge der reinen Strategien. Sie kann durch eine Verteilungsfunktion charakterisiert werden, die eine reelwertige Funktion ist, die auf dem Intervall [0,1] definiert wird und die folgende Eigenscgaften erfüllt:

  • F(0)=0
  • F(1)=1
  • Gilt  x>y \Rightarrow F(x)\ge F(y)

F(x) entspricht der Wahrscheinlichkeit, dass die Zahl aus dem Intervall [0,x] gegriffen wird.

Die Wahrscheinlichkeit, dass die Zahl aus dem Intervall (a,b] gegriffen wird, ist dann :  F(b)-F(a)\ge 0

  •  x \neq 0 \,\Rightarrow \,F(x)=\lim_{z \to x \,und \,z>x} F(z) (F ist rechtsstetig).

Wenn der 1. Spieler die reine Strategie  x \in [0,1] wählt und der 2.Spieler sich dagegen für die gemischte Strategie G entscheidet, so ist die Auszahlung durch folgendes Integral gegeben ( Stieltjes - Integral ) :

 E(x,G)=\int\limits_0^1 A(x, y) dG(y)

Die Funktion G wird auch Gewichtsfunktion genannt, da sie regelt wie stark A an unterschiedlichen Stellen gewichtet wird.

Es gilt dasselbe auch im umgekehrten Fall,d.h. falls Spieler 2 die reine Strategie wählt und Spieler 1 dafür die gemischte.

Wählen jedoch beide die gemischte Strategie liefert dies:

 E(F,G)=\int\limits_0^1 \int\limits_0^1 A(x, y)dF(x)dG(y)

Wenn die beiden Integralle existieren, dann gilt natürlich :

 E(F,G)=\int\limits_0^1 E(F,y)dG(y)=\int\limits_0^1 E(x,G)dF(x)

Optimale Strategien und Werte des Spiels

Wir definieren

 w_1=\sup_F \inf_y E(F,y) und
 w_2=\inf_G \sup_x E(x,G).

Wir stellen uns jetzt zwei Fragen:

  1. Gilt  \,w_1=\,w_2 \,?
  2. Kann man  \sup\inf bzw. \inf\sup durch \,max\,min bzw. \,min\,max ersetzen?


Wenn man beide Fragen mit "Ja" beantworten kann, dann gibt es optimale Strategien.

Wenn man dagegen nur die erste Frage beantwortet werden, dann besitzt das Spiel zwar ein Wert (w = w1 = w2) aber keine optimale Strategie. Es besitzt dann aber sogenannte ε-optimale Strategien, d.h. zu jedem vorgegebenen ε > 0 existieren gemischte Strategien F und G für Spieler 1 und 2 so, dass gilt:

 \,E(F,y)> w-\epsilon

für alle x,y aus [0,1].


Die folgenden zwei Sätze zeigen, dass es für die Spiele über dem Einheitsquadrat mit stetiger Auszahlungsfunktion A(x,y) (Kern des Spiels) optimale Strategien gibt.


Satz

Ist der Kern A(x,y) stetig, dann können \sup\inf und  \inf\sup durch \,max\,min bzw.  \,min\,max ersetzt werden. Weil aber die Menge aller Abbildungen von [0,1] nach [0,1] kompakt ist bezüglich der Topologie der punktweisen Konvergenz, enthält die Folge (F1,F2,...) eine konvergente Teilfolge. Setze den zugehörigen Grenzwert als F0.

Beweis

A(x,y) ist stetig. Es folgt, dass  E(F,y)=\int\limits_0^1 A(x,y)dF(x) für jedes F eine stetige Funktion fon y ist. Das Intervall [0,1] ist kompakt, d.h. E(F,y) nimmt das Minimum auf dieses Intervall an. Also kann man zunächst \sup\inf durch \sup\,min ersetzen. Nach Definition von w1 existiert zu jedem  n\in  N eine Verteilungsfunktion Fn für die folgendes gilt:  \min_y E(F_n, y)> w_1-\frac 1n . F0 erfüllt alle Eigenschaften die beim Grenzübergang erhalten bleiben. Man erhält:

 F_0^*(x)=\begin{cases}

  0,  \qquad wenn \quad x=0\\
  \lim_{z \to x, z>x},\qquad wenn \quad 0<x<1\\
  1, \qquad wenn \quad x=1
\end{cases}

Diese Strategie unterscheidet sich höchstens an den Unstetigkeitsstelle von F0. Da F0 und  F_0^* Verteilungsfunktionen sind, ist die Menge ihrer Unstetigkeitsstellen höchstens abzählbar, so dass \forall y gilt:

 \int\limits_0^1 A(x,y)dF_0^*(x)=\int\limits_0^1 A(x,y)dF_0(x)

A(x,y) ist gleichmäßig stetig (wegen der Stetigkeit von A(x,y) und der Kompaktheit des Einheitsquadrats). Daraus folgt, dass F0 Grenzwert einer konvergenten Teilfolge der Fn ist, d.h.

 \int\limits_0^1 A(x,y)dF_0(x)=\lim_{n\to \infty}\int\limits_0^1 A(x,y)dF_n(x)

Dieser Grenzwert ist aber für alle Werte von y mindestens gleich w1, und damit gilt:  \min_y E(F_0^*, y)\ge w_1


Man zeigt analog, dass \inf\sup durch \,min\,max ersetzt werden kann.

Satz

Ist der Kern A(x,y) stetig, dann gilt w1 = w2.

Beweis

Man betrachte die (n+1)x(n+1) Matrix  A_n=(a_{ij}^n)=A(\frac in,\frac jn) wobei  n\in \N und i,j = 0,1,...,n

Das Spiel mit der Matrix An habe den Wert vn und seien  r_n=(r_0^n,...,r_n^n) bzw.  s_n= (s_0^n,...,s_n^n) die optimalen Strategien für Spieler 1 bzw. Spieler 2. Wegen A(x,y) stetig und [0,1] kompakt folgt A(x,y) gleichmäßig stetig. D.h., zu jedem ε > 0 gibt es δ > 0 derart, dass gilt:

 \sqrt{(x-x')^2+(y-y')^2}<\delta \Rightarrow |A(x,y)-A(x',y')|<\epsilon

Wähle nun n so gross, dass  \frac 1n < \delta . Sei Fn folgendermaßen definiert:

 F_n(x)=\sum_{i=0}^{[nx]} r_i^n mit [nx] die größte ganze Zahl, die nicht größer als nx ist.

Für beliebiges y setzen wir j=[ny]. Es gilt offenbar  E(F_n,\frac jn)=\sum_{i=0}^n a_{ij}^n r_i^n \ge v_n und wegen  |y-\frac jn|=|y-\frac {[ny]}n|<|y-\frac {ny-1}n|=|\frac 1n|<\delta auch |A(x,y)-A(x,\frac jn)|<\epsilon und schließlich

|\int\limits_0^1 ( A(x,y)-A(x,\frac jn)) dF_n(x)|=|E(F_n,y)-E(F_n,\frac jn)|<\epsilon

Also gilt  \forall y \, E(F_n, y)>v_n-\epsilon und damit w1 > vn − ε.

Ganz ähnich zeigt man w2 < vn + ε.

Die beiden Ungleichungen liefern w_2-\epsilon <v_n \Rightarrow w_1>v_n-\epsilon >w_2-\epsilon-\epsilon=w_2-2\epsilon.

Uns ist aber bekannt, dass  w_1 \le w_2 und da wir ε beliebig gewählt haben folgt schließlich w1 = w2.

Bemerkung

An diesem Bewies ist es erstens bemerkenswert, dass  w= \lim_{n \to \infty} v_n und zweitens die Tatsache, dass die Strategien Fn die optimale Strategie belibieg genau approximieren. Folglich approximieren die Matrixspiele An das kontinuierliche Spiel A(x,y).

Wenn der Kern "sehr glatt" ist, erreicht man eine gute Approximation schon mit sehr kleinen n. Anderersetis braucht man sehr grosse n für eine gute Annäherung, wenn sich der Kern nicht entsprechend wohlverhält. Die Methoden, die meist zur Lösung von Matrixspielen herangezogen werden sind in der Regel nicht schnell genug für die Behandlung von großen Spielen, wie z.B. 100x100. Daher wäre es besser, diese Spiele mit analytischen Modellen zu lösen. Leider existiert aber kein derartiges Verfahren. Die Entwicklung einer solchen Methode ist eines der noch ausstehenden Probleme der Spieltheorie. Ausserdem wäre es von Interesse, ein Verfahren zu entwickeln, mit dem entscheiden werden kann, ob die optimale Strategie F eines Spiels eine Treppenfunktion ist, d.h., ob eine eindeutige Zahl von reinen Strategien ausreicht, oder ob eine stetige Verteilung notwendig ist.

Meine Werkzeuge