Minimax-Theorem

Aus Wikiludia

Das Minimax-Theorem (v. Neumann 1928) besagt: Jedes endliche Zweipersonen-Nullsummenspiel besitzt ein Nash-Gleichgewicht in gemischten Strategien.

Inhaltsverzeichnis

1 Genaue Formulierung des Theorems
2 Beweis des Minimax-Theorems
3 Beweis des Satzes
4 Einige Lemmata

Genaue Formulierung des Theorems

Es seien $S_1 = \{ 1,\dots,n \},S_2 = \{1,\dots,m\}$ die Strategiemengen eines endlichen Zweipersonen-Nullsummenspieles, und es sei $u:S_1\times S_2\to\mathbb R$ die Auszahlungsfunktion des ersten Spielers. Beim Übergang zu gemischten Strategien erhalten wir ein neues Nullsummenspiel mit den Strategieräumen $\tilde S_1 = \Delta_n$ und $\tilde S_2 = \Delta_m$ , wobei $\Delta_k := \{(x_1,\dots,x_k)^T\in\mathbb R^k : x_i \ge 0, \sum x_i = 1\}$ der k-dimensionale Einheitssimplex ist, und der Auszahlungsfunktion $\tilde u: \Delta_n \times \Delta_m \to \mathbb R$ des ersten Spielers, die gegeben ist durch $\tilde u((x_1,\dots,x_n), (y_1,\dots,y_m)) = \sum_{i=1}^n \sum_{j=1}^m x_i y_j u(i,j) = x^T A y$ mit $x = (x_1,\dots,x_n)^T \in \mathbb R^n, y = (y_1,\dots,y_m)^T\in\mathbb R^m, A = (u(i,j))_{i,j} \in \mathbb R^{n\times m}$ .

Das Minimax-Theorem lautet nun: In der beschriebenen Situation gilt $\min_{y\in\Delta_m} \max_{x\in\Delta_n} \tilde u(x,y) = \max_{x\in\Delta_n} \min_{y\in\Delta_m} \tilde u(x,y)$ . Nach dem Minimax-Prinzip ist das äquivalent zur Existenz eines Nash-Gleichgleichgewichtes im durch Übergang zu gemischten Strategien erhaltenen Spiel.

Beweis des Minimax-Theorems

Wir geben einen einfachen Beweis des Minimax-Theorems von Hellmuth Kneser (1952) und beginnen dazu mit einer

Definition (konvex-linear)

Es seien V,W reelle Vektorräume, $K\subset V$ konvex und $f:K\to W$ eine Abbildung. $f$ heißt konvex-linear, wenn $f (λ x + μ y) = λ f (x) + μ f (y)$ für alle $x,y\in K$ und alle $\lambda,\mu\ge 0$ mit $λ + μ = 1$ gilt.

Bemerkung 1

Offenbar sind Einschränkungen linearer Abbildungen auf konvexe Mengen konvex-linear. Das gleiche gilt aber auch für affin-lineare Funktionen: ist nämlich $f = g + a$ mit $g:V\to W$ linear und $a\in W$ konstant, so ist $λ f (x) + μ f (y) = g (λ x + μ y) + λ a + μ a = f (λ x + μ y)$ wegen $λ + μ = 1$ .

Satz (Kneser 1952)

Es seien V,W reelle Vektorräume mit beliebigen Topologien, und es seien $K\subset V$ und $L\subset W$ nichtleer, konvex und kompakt. Ist $f:K\times L\to\mathbb R$ stetig und in beiden Argumenten konvex-linear, so gilt $\max_{x\in K} \min_{y\in L} f(x,y) = \min_{y\in L} \max_{x\in K} f(x,y).$

Bemerkung 2

Das Minimax-Theorem in der oben angegebenen Form folgt unmittelbar aus dem Satz von Kneser: denn in $\mathbb R^k$ mit der Standardtopologie sind die Einheitssimplizes $Δ k$ konvex und (nach dem Satz von Heine-Borel) kompakt, und die Auszahlungsfunktion $\tilde u$ ist als Einschränkung einer Bilinearform stetig und in beiden Argumenten konvex-linear.
Der Satz von Kneser läßt sich ohne Mühe verallgemeinern zur Aussage: ist $f$ in beiden Argumenten konvex-linear und im ersten Argument oberhalbstetig, so gilt $\sup_{x\in K} \inf_{y\in L} f(x,y) = \inf_{y\in L} \max_{x\in K} f(x,y).$
Im Satz ist nur die Ungleichung $\ge$ nichttrivial. Die andere kann man ganz allgemein und ohne alle Voraussetzungen so einsehen: für jedes Paar $(x_0,y_0)\in K\times L$ gilt $\inf_{y\in Y} f(x_0, y) \le f(x_0,y_0) \le \sup_{x\in X} f(x,y_0)$ , und da der erste Ausdruck nicht von $y 0$ und der letzte nicht von $x 0$ abhängt, folgt daraus $\sup_{x\in X} \inf_{y\in Y} f(x,y) \le \inf_{y\in Y} \sup_{x\in X} f(x,y)$ .

Beweis des Satzes

Die Existenz der im Satz auftretenden Minima und Maxima ist eine elementare Übung in mengentheoretischer Topologie, die wir in einem eigenen Artikel ausführen.

Wie bemerkt, ist die Ungleichung $\le$ trivial, wir müssen also nur $\ge$ zeigen. Dazu setzen wir $a := \min_{y\in Y} \max_{x\in X} f(x,y)$ . Dann gibt es zu jedem $y\in Y$ ein $x\in X$ mit $f(x,y) \ge a$ , also kann es kein $y 0$ geben mit $f (x, y 0) < a$ für alle $x$ . Nach Lemma 3 gibt es damit aber ein $x 0$ mit $f(x_0,y) \ge a$ für alle $y$ , also $\min_{y\in Y} f(x_0, y) \ge a$ und damit $\max_{x\in X} \min_{y\in Y} f(x,y) \ge a = \min_{y\in Y} \max_{x\in X} f(x,y)$ , was zu beweisen war.

Einige Lemmata

Das Lemma 1 ist eine (auch an sich interessante) allgemeine Aussage über konvex-lineare Funktionen auf Kompakten Mengen. Lemma 2 ist ein Hilfsmittel zum Beweis von Lemma 1. Lemma 3 schließlich ist das Hauptlemma für den Beweis des Satzes von Kneser und hat auch an sich, bezogen auf die Situation der Nullsummenspiele in gemischten Strategien, eine interessante Deutung: zu jeder vorgegebenen Auszahlung $a\in\mathbb R$ kann entweder Spieler 1 eine Strategie wählen, die ihm stets mindestens einen Ertrag von $a$ sichert, oder aber Spieler 2 kann eine Strategie wählen, die ihm einen Ertrag von mehr als $- a$ garantiert.

Lemma 1

Es sei V ein reeller Vektorraum mit einer beliebigen Topologie und $K\subset V$ nichtleer, kompakt und konvex. Es sei $n\ge 1$ und $f_1,\dots,f_n:K\to\mathbb R$ konvex-lineare stetige Funktionen mit der Eigenschaft $min i f i (x) < 0$ für alle $x\in K$ . Dann gibt es eine konvexe Linearkombination $f = \sum_{i=1}^n \lambda_i f_i$ mit $\lambda_i \ge 0$ , $\sum \lambda_i = 1$ und $f (x) < 0$ für alle x.

Beweis von Lemma 1

Zunächst bemerken wir, daß wir die Normierungsbedingung $\sum\lambda_i = 1$ fallenlassen können: denn eine ohne diese Bedingung gewonnenen Linearkombination kann nicht $\lambda_1 = \dots = \lambda_n = 0$ erfüllen, also können wir durch den Übergang $\lambda_i \to \lambda'_i = \lambda_i / \sum_j \lambda_j$ die gewünschte Normierung erreichen. Wir beweisen die Behauptung nun durch Induktion nach n.

Der Fall $n = 1$

Hier ist die Behauptung klar.

Der Fall $n = 2$

Wir setzen $N_i := \{x\in K : f_i(x) \ge 0\}$ . Nach Lemma 2 müssen wir nur zeigen: sind $N 1$ und $N 2$ beide nichtleer, so gilt $α 1 α 2 < 1$ mit $\alpha_1 := \max_{x\in N_1} \frac{f_1(x)}{-f_2(x)},\quad \alpha_2 := \max_{x\in N_2} \frac{f_2(x)}{-f_1(x)}$ . Seien also $p_i\in N_i$ mit $\frac{f_1(p_1)}{-f_2(p_1)} = \alpha_1$ und $\frac{f_2(p_2)}{-f_1(p_2)} = \alpha_2$ . Dann ist $f_1(p_1) \ge 0 > f_1(p_2)$ , also gibt es eine konvexe Linearkombination $p = λ p 1 + μ p 2$ mit $\lambda,\mu \ge 0$ , $λ + μ = 1$ und $0 = λ f 1 (p 1) + μ f 1 (p 2) = f 1 (p)$ . Nach Voraussetzung ist damit aber $0 > f 2 (p) = λ f 2 (p 1) + μ f 2 (p 2)$ .

Wegen $f 1 (p 1) = - α 1 f 2 (p 1)$ und $f 2 (p 2) = - α 2 f 1 (p 2)$ haben wir also $0 = - α 1 λ f 2 (p 1) + μ f 1 (p 2)$ und $0 > λ f 2 (p 1) - α 2 μ f 1 (p 2)$ . Multiplikation der ersten Beziehung mit $α 2$ und Addition zur zweiten liefert nun $0 > λ(1 - α 1 α 2) f 2 (p 1)$ , und wegen $f 2 (p 1) < 0$ und $\lambda\ge 0$ folgt daraus $1 - α 1 α 2 > 0$ , also $α 1 α 2 < 0$ wie behauptet.

Induktionsschritt

Es sei nun $n > 2$ und $N := \{f_n \ge 0\}$ . Ist $N$ leer, so können wir $f = f n$ setzen und sind fertig. Andernfalls ist $N$ konvex (denn eine konvexe Linearkombination nichtnegativer Werte ist nichtnegativ), und wir können die Induktionsvoraussetzung anwenden auf die $n - 1$ Funktionen ${f_1}_{|N},\dots,{f_{n-1}}_{|N}$ , so daß wir nichtnegative Zahlen $λ' i$ erhalten mit $\sum_{i=1}^{n-1} \lambda'_i = 1$ , so daß $f'(x) := \sum_{i=1}^{n-1} \lambda'_i f_i(x)$ für alle $x\in N$ negativ ist.

Wenden wir nun den Fall $n = 2$ an auf $f'$ und $f n$ , so erhalten wir $\mu_1,\mu_2 \ge 0$ mit $μ 1 + μ 2 = 1$ , so daß $0 > \mu_1 f'(x) + \mu_2 f_n(x) = \sum_{i=1}^{n-1} \mu_1 \lambda'_i f_i(x) + \mu_2 f_n(x)$ stets gilt, also tun $λ i : = μ 1 λ' i$ für $1\le i < n$ und $λ n : = μ 2$ das Gewünschte.

Lemma 2

Es sei X ein kompakter topologischer Raum und $f_1,f_2:X\to\mathbb R$ stetige Funktionen. Die Mengen $N_i := \{f_i \ge 0\}$ , $i = 1,2$ seien disjunkt, und es sei $\max_{x\in N_1} \frac{f_1(x)}{-f_2(x)} \cdot \max_{x\in N_2} \frac{f_2(x)}{-f_1(x)} < 1$ . (Falls eine der Mengen leer ist, entfällt diese Bedingung; ansonsten sind die auftretenden Maxima definiert, weil die $N i$ als abgeschlossene Teilmengen eines Kompaktums kompakt sind.)

Dann gibt es $\lambda_1,\lambda_2 \ge 0$ mit $λ 1 + λ 2 > 0$ und $λ 1 f 1 + λ 2 f 2 < 0$ stets.

Beweis von Lemma 2

Ist eine der Mengen $N i$ leer, so ist die Behauptung trivial. Andernfalls können wir nach Voraussetzung ein $c > 0$ wählen mit $c > \max_{x\in N_1} \frac{f_1(x)}{-f_2(x)}$ und $\frac 1c > \max_{x\in N_2} \frac{f_2(x)}{-f_1(x)}$ . Schreibe $c = \frac{\lambda_2}{\lambda_1}$ mit positiven Zahlen $λ 1,λ 2$ . Für alle $x\in N_1$ gilt dann $\frac{f_1(x)}{-f_2(x)} < c = \frac{\lambda_2}{\lambda_1}$ , also (da $f 2$ auf $N 1$ negativ ist) $λ 1 f 1 (x) < - λ 2 f 2 (x)$ und damit $λ 1 f 1 + λ 2 f 2 < 0$ auf $N 1$ . Ebenso beweist man die Gültigkeit der Ungleichung auf $N 2$ , und außerhalb von $N_1\cup N_2$ ist sie stets erfüllt.

Bemerkung

Man kann leicht zeigen, daß die Voraussetzungen von Lemma 2 sogar notwendig sind für die Existenz einer Linearkombination wie angegeben.

Lemma 3

Unter den Voraussetzungen des Satzes von Kneser ist für jedes $a\in\mathbb R$ eine der folgenden Aussagen erfüllt:

Es gibt ein $x_0\in K$ mit $f(x_0, y) \ge a$ für alle $y\in L$ .
Es gibt ein $y_0\in L$ mit $f (x, y 0) < a$ für alle $x\in K$ .

Beweis von Lemma 3

Es genügt, die Behauptung für $a = 0$ zu beweisen, denn jedes $f - a$ erfüllt ebenfalls die gemachten Voraussetzungen. Angenommen, die erste Aussage gelte nicht. Zu jedem $y\in L$ setze $\mathcal O_y := \{x\in K : f(x,y) < 0\}.$ Dann bilden die $\mathcal O_y$ eine offene Überdeckung von K: denn nach Voraussetzung gibt es zu jedem $x\in K$ ein $y\in L$ mit $f (x, y) < 0$ , also $x\in \mathcal O_y$ . Da K kompakt ist, gibt es $y_1,\dots,y_n\in L$ mit $K = \bigcup_{i=1}^n \mathcal O_{y_i}$ .

Die Funktionen $f_i:K\to\mathbb R, x\mapsto f(x,y_i)$ erfüllen damit die Voraussetzungen von Lemma 1, denn

f i

ist auf $\mathcal O_{y_i}$ negativ. Also gibt es $\lambda_1,\dots,\lambda_n\ge 0$ mit $\sum \lambda_i = 1$ und

0 > \sum λ i f i (x) = \sum λ i f (x, y i) = f (x, \sum λ i y i) i i i

für alle $x\in K$ . Also tut

y : = \sum λ i y i i

das in der zweiten Aussage Gewünschte.

0 >	∑	λ_if_i(x) =	∑	λ_if(x,y_i) = f(x,	∑	λ_iy_i)
	i		i		i

Minimax-Theorem

Inhaltsverzeichnis

Genaue Formulierung des Theorems