Minimax-Theorem

Aus Wikiludia
Wechseln zu: Navigation, Suche

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

Inhaltsverzeichnis

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 fx + μ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) = gx + μy) + λa + μa = fx + μ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 y0 und der letzte nicht von x0 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 y0 geben mit f(x,y0) < a für alle x. Nach Lemma 3 gibt es damit aber ein x0 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 minifi(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 N1 und N2 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 = λp1 + μp2 mit \lambda,\mu \ge 0, λ + μ = 1 und 0 = λf1(p1) + μf1(p2) = f1(p). Nach Voraussetzung ist damit aber 0 > f2(p) = λf2(p1) + μf2(p2).

Wegen f1(p1) = − α1f2(p1) und f2(p2) = − α2f1(p2) haben wir also 0 = − α1λf2(p1) + μf1(p2) und 0 > λf2(p1) − α2μf1(p2). Multiplikation der ersten Beziehung mit α2 und Addition zur zweiten liefert nun 0 > λ(1 − α1α2)f2(p1), und wegen f2(p1) < 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 = fn 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 fn, 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 Ni als abgeschlossene Teilmengen eines Kompaktums kompakt sind.)

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

Beweis von Lemma 2

Ist eine der Mengen Ni 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 λ12. Für alle x\in N_1 gilt dann \frac{f_1(x)}{-f_2(x)} < c = \frac{\lambda_2}{\lambda_1}, also (da f2 auf N1 negativ ist) λ1f1(x) < − λ2f2(x) und damit λ1f1 + λ2f2 < 0 auf N1. Ebenso beweist man die Gültigkeit der Ungleichung auf N2, 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,y0) < a für alle x\in K.

Beweis von Lemma 3

Es genügt, die Behauptung für a = 0 zu beweisen, denn jedes fa 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 fi ist auf \mathcal O_{y_i} negativ. Also gibt es \lambda_1,\dots,\lambda_n\ge 0 mit \sum \lambda_i = 1 und
0 > λifi(x) = λif(x,yi) = f(x,λiyi)
iii
für alle x\in K. Also tut
y: = λiyi
i
das in der zweiten Aussage Gewünschte.
Meine Werkzeuge