Min-Max-Theorem

Aus Wiwiwiki.net
Zur Navigation springenZur Suche springen

Das Min-Max-Theorem ist ein Satz in der Spieltheorie zur Lösung eines Zwei-Personen-Nullsummenspiels. Es formalisiert das Verhalten der Spieler (unter der Annahme, dass der Gewinn des einen, der Verlust des anderen ist) durch Minimierung der maximalen Auszahlung des Gegners den eigenen Verlust zu minimieren (Minimax), und das Minimum der eigenen Auszahlung zu maximieren (Maximin). Das Min-Max-Theorem besagt, dass jedes Zwei-Personen-Nullsummenspiel mit endlicher Anzahl an Strategien ein Gleichgewicht in reinen oder gemischten Strategien besitzt. Es wird als Hauptsatz der Spieltheorie bezeichnet und wurde erstmals 1928 von John von Neumann formuliert und bewiesen.[1]


Einordnung

John von Neumann formalisierte und bewies das Min-Max-Theorem erstmals 1928 in seiner Analyse „Zur Theorie der Gesellschaftsspiele“. Dadurch legte er die Grundlage der modernen Spieltheorie.[2] Beim Min-Max-Theorem wird unterstellt, das die Spieler aufgrund von Unwissenheit hinsichtlich der Strategiewahl des Mitspielers sehr pessimistische Erwartungen haben. Das bedeutet, man erwartet vom Mitspieler das Verhalten, welches einem selbst am meisten schadet. In Folge dessen bedienen sich die Spieler bei der Wahl ihrer Entscheidung dem Maximin-Kriterium (Maximin-Regel). Dabei betrachtet der Spieler, welche Auszahlung bei den jeweiligen Strategien im schlechtesten Fall zu erwarten ist und wählt jene Strategie, bei der die minimale Auszahlung am größten (maximal) ist.[3] Somit maximiert der Spieler seine minimale erwartete Auszahlung und minimiert demnach den maximal zu erwarteten Verlust. Diese Strategie wird als Maximin-Strategie bezeichnet. Der Mitspieler wird sich daraufhin nach dem Minimax-Kriterium verhalten, welches die umgekehrte Bedingung erfüllt. Er wählt die Minimax-Strategie. In reinen Strategien ist die daraus resultierende Kombination die sogenannte Maximinlösung und wird auch als Sattelpunkt bezeichnet.[4] Die Kombination von Maximin- und Minimax-Strategien führt bei gemischten Strategien dazu, dass kein Spieler seine Position durch Veränderung seiner Strategie gegenüber dem Mitspieler verbessern kann.[5] Dies bildet einen Spezialfall des Nash-Gleichgewichts für Zwei-Personen-Nullsummenspiele.[6]

Zur Ermittlung dieser Gleichgewichtsstrategie wird in sehr komplexen Nullsummenspielen die lineare Optimierung genutzt.

Häufig findet man die Bezeichnung Minimax statt Maximin. Die Verwendung von Minimax als Synonym ist jedoch streng genommen unlogisch, da man das Maximum minimieren würde.[7]

Spieltheoretische Formulierung

Der Hauptsatz für 2-Personen-Nullsummenspiele in einem Matrixspiel (A,B,G) beinhaltet:


A = (a1 , a2, ...am) die Menge der reinen Strategien von Spieler A


B = (b1, b2, ...bn) die Menge der reinen Strategien von Spieler B


G =(ai, bj) = Gi,j = der Gewinn, wenn Spieler Strategie ai und bj wählen


Wählen beide Spieler ihre gemischte Strategie unabhängig voneinander so resultiert daraus für Spieler A der mittlere Gewinn G‘(x,y), mit


G'(x,y) = xiyj * Gij

Die daraus resultierende Matrix (X,Y,G‘) nennt man gemischte Erweiterung. [8]


Die gemischte Erweiterung (X, Y, G‘) eines jeden Zwei-Personen-Nullsummenspiels mit endlichen (reinen) Strategieräumen A und B besitzt einen Wert v sowie für jeden Spieler mindestens eine (gemischte) Gleichgewichtsstrategie x* bzw. y* mit der der Wert v garantiert werden kann.


Für Spieler A existiert eine Gleichgewichtsstrategie:


x* = (x*1,...x*i,...x*m) mit x*i 0 und x*i = 1


so dass:


Formel


Für Spieler B existiert eine Gleichgewichtsstrategie:


y* = (y*1,...y*j,...y*m) mit y*j 0 und y*j = 1


so dass:


[9]


somit gilt allgemein:


Allgemeine Vorgehensweise

Ein 2-Personen-Nullsummenspiel in Matrixform kann folgendermaßen dargestellt werden (Bimatrix):

Spieler B:
s1B s2B sn-1B snB
Spieler A:
s1A u1,1 u1,2 u1,n-1 u1,n
s2A u2,1 u2,2 u2,n-1 u2,n
sm-1A um-1,1 um-1,2 um-1,n-1 um-1,n
smA um,1 um,2 um,n-1 um,n

Spieler A ist der Zeilenspieler und Spieler B der Spaltenspieler. Das Spiel wird aus Sicht des Spielers A betrachtet, wobei im Strategievektor s = (sA,sB) die Zeile durch sA und die Spalte sB= sA bezeichnet wird. In den Matrixzellen steht die Auszahlung uA(s) = -uB(s), so dass die Auszahlungen des Spielers A gleich dem Verlust des Spielers B entspricht. Spieler A wählt aufgrund seiner pessimistischen Erwartungen bezüglich des Verhaltens seines Mitspielers, diejenige Zeile, in der das Zeilenminimum maximal ist. (Maximin-Kriterium). Bei dieser Strategie sA , maximiert er somit seine minimal zu erwartende Auszahlung. (Maximin-Strategie) Die Optimierungsregel für Spieler A lautet folglich:

Unabhängig von der Strategiewahl des Spielers B, garantiert sich Spieler A dadurch das maximal mögliche Auszahlungsminimum. In dem strikt kompetitiven Spiel wird Spieler B daraufhin jene Spalte wählen, in der das Spaltenmaximum minimal ist um seine Verluste zu minimieren. (Minimax-Kriterium) Diese Strategie sB (Minimax-Strategie) erfüllt somit genau die inverse Bedingung der Strategie sA des Spielers A. Die Optimierungsregel dafür lautet also:


Folglich kann Spieler B durch seine Minimax-Strategie sB die Auszahlung des Spielers A auf maximal diesen Betrag begrenzen. Unabhängig davon was Spieler A unternimmt. Somit gilt:


[10]


Die Kombination dieser beiden optimalen Strategien sA und sB für ein endliches Zwei-Personen-Nullsummenspiel ergeben einen gemeinsamen Wert v. Dieser wird als Gleichgewicht oder Sattelpunkt bezeichnet. Daraus ergibt sich der Hauptsatz:

= v


Man bezeichnet den Wert v auch allgemein als Wert des Spiels. Wenn dieser gleich 0 ist wird das Spiel als fair bezeichnet.[11]

Sofern beide Spieler rational spielen, kann Spieler A eine Minimalauszahlung erwarten. Spieler B kann hingegen bewirken, dass Spieler A nicht mehr als die Minimalauszahlung gewinnt.[12]

Beispiele

Betrachtet wird die folgende Bimatrix mit den Spielern A(riel) und B(ob).

Spieler B(ob)
   s1B  s2B   s3B min uA (sA,sB)

  sB

(Zeilenminimum)

Spielerin A(riel) s1A 5 3 7 3
s2A 6 4 9 4
s3A 3 2 1 1
max uA (sA,sB)

  sA

(Spaltenmaximum)

6 4 9

(Eigene Darstellung in Anlehnung an: Rieck, Christian (2015): S. 335.)

Die Zeilenspielerin A(riel) wählt zuerst. Danach der Spaltenspieler B(ob). Beide Spieler gehen der pessimistischen Annahme nach, dass der jeweils andere ihm maximalen Schaden zufügen möchte. Unter dieser Annahme maximieren beide. A(riel) durchsucht die Zeilen nach dem Minimum, und wählt jene Zeile in der das Minimum am höchsten ist. Damit sie sich die maximale minimale Auszahlung garantieren kann. In dem Fall wählt sie Strategie s2A. B(ob) hingegen durchsucht jede Spalte nach dem Maximum. Er wird jedoch folglich immer das minimale Maximum nehmen, welches A(riel) durch die Wahl der Zeile vorgegeben wurde. Um sicherzustellen das A(riel) die geringste mögliche Auszahlung erhält. Er wählt also jene Spalte in der das Maximum am niedrigsten ist. In dem Fall ist das die Strategie s2B. Durch die Kombination der beiden Strategie entsteht der Sattelpunkt (Gleichgewicht) in u2,2. Angenommen es gäbe mehrere gleichhohe Zeilenminima oder Spaltenmaxima, kann der Sattelpunkt nicht eindeutig bestimmt werden. Dann können die Spieler auf gemischte Strategien ausweichen.[13] Dazu wird im Folgenden ein Tennisspiel betrachtet In der Bimatrix stellen die Werte anstatt Auszahlungen, Erfolgsquoten für jede reine Strategien der beiden Kontrahenten A(riel) und B(ob) dar. Nach dem Motto: „Lady’s First“ schlägt Spielerin A(riel) als erstes auf.

Spieler B(ob):
Vorhand Rückhand
Spielerin A(riel): Vorhand 50 80
Rückhand 90 20

(Eigene Darstellung in Anlehnung an: Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): S. 223.)

Da die Interessen der beiden Spieler genau entgegengesetzt sind, wird Spieler B(ob) versuchen, den Ball erfolgreich zu retournieren und die maximale Erfolgsquote seiner Gegnerin zu minimieren (Minimax-Strategie). Mit diesem Vorwissen wird Spielerin A(riel) versuchen, ihre eigene Minimum-Erfolgsquote zu maximieren (Maximin-Strategie).

In diesem Beispiel beträgt die Minimum-Erfolgsquote von Spielerin A(riel) für jede ihrer reinen Strategien in der Zeile Vorhand 50 und Rückhand 20. Das Maximum dieser Minima (Maximin) beträgt folglich 50 und garantiert ihr den größtmöglichen Erfolg, wenn sie zu 100% auf die Vorhand spielt, insofern Spieler B(ob) in seinen eigenen Interessen so gut wie möglich retourniert. A(riel) würde die Strategie Vorhand wählen. Die Maximum-Erfolgsquote von B(ob) für jede seiner Strategien beträgt in Spalte Vorhand 90 und Rückhand 80. Das Minimum dieser Maxima (Minimax) beträgt 80 und garantiert ihm den größtmöglichen Erfolg, insofern A(riel) in ihrem eigenen Interesse so gut wie möglich retourniert. B(ob) würde die Rückhand wählen.

Spieler B(ob):
Vorhand Rückhand Zeilenminimum
Spielerin A(riel): Vorhand 50 80 50

(Maximin)

Rückhand 90 20 20
Spaltenmaximum 90

80

(Minimax)

(Eigene Darstellung in Anlehnung an: Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): S. 223.)

Die Minimax- und Maximin-Werte der beiden Tennisspieler sind unterschiedlich: Maximin Spielerin A (50%) < Minimax Spieler B (80 %).

Dementsprechend besitzt dieses Spiel keinen Sattelpunkt (Gleichgewicht) in reinen Strategien. Da die richtige Position nicht mehr vorhersagbar ist, kann jeder der beiden Spieler seine Position durch Mischen der reinen Strategien Vorhand und Rückhand verbessern und die Erfolgsquote des Gegners schwächen,.

Die Strategiekombinationen, die sich für die beiden Spieler aus dem Mix ihrer reinen Strategien ergeben, werden zunächst aus der Perspektive von Spielerin A(riel) betrachtet. Sie spielt Vorhand mit einer Wahrscheinlichkeit von p und folglich Rückhand mit einer Wahrscheinlichkeit von (1-p). Der p-Mix ergibt, für jede der reinen Strategien von Spieler B(ob), den zu erwartenden Erfolg der Spielerin A(riel) für ihre gemischte Strategie.

Spieler B(ob):
Vorhand Rückhand Zeilenminimun
Spielerin A(riel): Vorhand 50 80 50
Rückhand 90 20 20
p-Mix 50p+90 (1-p) 80p+20 (1-p) min = ?

(Eigene Darstellung in Anlehnung an: Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): S. 223.)

Wenn Spieler B(ob) Vorhand spielt, entspricht die Erfolgsquote der Spielerin A(riel) 50p+90 (1-p) und bei Rückhand 80p+20 (1-p). Die Wahrscheinlichkeit p berechnet sich daraus wie folgt:

50p+90 (1-p) = 80p+20 (1-p)

70 (1-p) = 30p

70 = 100p

P = 0,7 à erwartete Erfolgsquote: 50*0,7+90 (1-0,7) = 62

Nun werden die Strategiesets aus der Perspektive des Spielers B(ob) betrachtet. Er spielt Vorhand mit der Wahrscheinlichkeit q und Rückhand folglich mit der Wahrscheinlichkeit (1-q). Der q-Mix gibt, für jede der reinen Strategien von Spielerin A(riel), den zu erwartenden Erfolg des Spielers B(ob) für seine gemischte Strategie an.

Spieler B(ob):
Vorhand Rückhand q-Mix
Spielerin A(riel): Vorhand 50 80 50q + 80 (1 - q)
Rückhand 90 20 90q + 20 (1 - q)
Spaltenmaximum 90 80 min = ?

(Eigene Darstellung in Anlehnung an: Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): S. 223.)

Wenn A(riel) also Vorhand spielt, entspricht die Erfolgsquote von B(ob)

50q+80 (1-q) und bei Rückhand 90q+20 (1-q). Die Wahrscheinlichkeit q beträgt somit:

50q+80 (1-q) = 90q + 20 (1-q)

60 (1-q) = 40q

60 = 100q

q = 0,6 à erwartete Erfolgsquote: 50*0,6+80 (1-0,6) = 62 Die Spielerin A(riel) konnte folglich durch das Mixen von reinen Strategien ihre Maximin von 50% auf 62% steigern. Spieler B(ob) konnte durch das das Nutzen seiner gemischten Strategie sein Minimax von 80% auf 62% senken. Wenn beide Spieler ihre optimale gemischte Strategie gegeneinander spielen, so entspricht der Maximin der Spielerin A(riel), dem Minimax des Spielers B(ob). In Folge dessen kann sich kein Spieler gegenüber dem anderen besser stellen.[14]

Kritik

Trotz der großen Bekanntheit des Min-Max-Theorems wird ihm heutzutage eine eher geringe Bedeutung beigemessen. Das liegt daran das es lediglich auf Zwei-Personen-Nullsummenspiele anwendbar ist. Bereits bei Zwei-Personen-Nichtnullsummenspielen ist im Allgemeinen nicht vom Gegenspieler ein Maximinverhalten zu erwarten. Denn man weiß, dass dieser immer sein Eigeninteresse verfolgt. Folglich kann man sich in seine Position hineindenken, um sein Verhalten zu prognostizieren. Diese strategische Denkweise würde in der Regel zu einem anderen Resultat als die Maximinlösung führen.[15] Bei Mehrpersonenspielen müsste man davon ausgehen, das alle Spieler an Verfolgungswahn leiden und denken die Mitspieler haben sich gegen einen verbündet. Dann würde man im Ergebnis zum Nash-Gleichgewicht kommen. Jedoch ist davon auszugehen, dass mindestens ein Spieler sein Verhalten ändert und maximiert um zu versuchen sich besser zu stellen.[16]

Da sich ökonomische Probleme in der Regel nicht durch Zwei-Personen-Nullsummenspiele beschreiben lassen, findet das Theorem in der modernen Spieltheorie und Praxis nur noch geringe Anwendung.

Anwendung

Das Min-Max-Theorem bildet die Grundlage für den Minimax-Algorithmus. Dessen Varianten wie die Alpha-Beta-Suche bildendas Kernelement von Schachcomputern oder Simulationen verschiedener Brettspiele wie „Dame“,

Mühle“, „Vier gewinnt“.

Die auf dem Theorem basierende Maximin-Regel fand in John Rawls „Theorie zur Gerechtigkeit“ auch in der Philosophie Anwendung

JEL Klassifikation

C7 Spieltheorie und Verhandlungstheorie

C72 Nicht kooperative Spiele

Siehe auch

Literatur

  • Bühlmann, Hans; Loeffel, Hans; Nievergelt Erwin (1975): Entscheidungs- und Spieltheorie, Berlin: Springer Verlag. ISBN 978-3-540-07462-5
  • Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): Games of Strategy, 3.Auflage, London/New York: Norton Verlag. ISBN 978-0-393-93112-9
  • Dresher, Melvin (1961): Strategische Spiele, Theorie und Praxis, Zürich: Verlag Industrielle Organisation. ISBN: B0062EVXYA
  • Hillier, Frederick S.; Liebermann, Gerald J. (1996): Operations Research, 5.Auflage, Verlag Oldenbourg. ISBN 978-3-486-23987-4.
  • Holler, Manfred J.; Illing, Gerhard (2008): Einführung in die Spieltheorie, 7.Auflage, Berlin: Springer-Verlag. ISBN 978-3-540-69372-7
  • Rieck, Christian (2006): Spieltheorie: Eine Einführung, Eschborn: Rieck Verlag, ISBN 3-924043-91-4
  • Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. ISBN 3-924043-91-4
  • Sauer, Tomas (2017): Spieltheorie, Berlin: Logos. ISBN 978-3-8325-4472-0
  • von Neumann, John (1928): Zur Theorie der Gesellschaftsspiele, Mathematische Annalen Nr. 100. Digizeitschrift

Einzelnachweise

  1. Sauer, Tomas. (2017): Spieltheorie, Berlin: Logos.  S.27. ISBN 978-3-8325-4472-0
  2. von Neumann, John (1928): Zur Theorie der Gesellschaftsspiele, Mathematische Annalen Nr. 100, S. 295–320. Digizeitschrift
  3. Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. S.64, ISBN 3-924043-91-4
  4. Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. S.335, ISBN 3-924043-91-4
  5. Hillier, Frederick S.; Liebermann, Gerald J. (1996): Operations Research, 5.Auflage, Verlag Oldenbourg, S. 360. ISBN 978-3-486-23987-4
  6. Rieck, Christian (2006): Spieltheorie: Eine Einführung, Eschborn: Rieck Verlag, S. 291. ISBN 3-924043-91-4
  7. Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. S.64, ISBN 3-924043-91-4
  8. Bühlmann, Hans; Loeffel, Hans; Nievergelt, Erwin (1975): Entscheidungs- und Spieltheorie, Berlin: Springer Verlag, S. 180, ISBN 978-3-540-07462-5
  9. Bühlmann, Hans; Loeffel, Hans; Nievergelt, Erwin (1975): Entscheidungs- und Spieltheorie, Berlin: Springer Verlag, S. 183, ISBN 978-3-540-07462-5
  10. Dresher, Melvin (1961): Strategische Spiele, Theorie und Praxis, Zürich: Verlag Industrielle Organisation. S.14/15 ISBN: B0062EVXYA
  11. Sauer, Tomas (2017): Spieltheorie, Berlin: Logos.  S.27. ISBN: 978-3-8325-4472-0
  12. Dresher, Melvin (1961): Strategische Spiele, Theorie und Praxis, Zürich: Verlag Industrielle Organisation. S. 15 ISBN: B0062EVXYA
  13. Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. S. 334/335, ISBN 3-924043-91-4
  14. Dixit, Avinash K.; Skeath, Susan; Reiley, David H. (2009): Games of Strategy, 3.Auflage, London/New York: Norton Verlag, S. 222/223. ISBN 978-0-393-93112-9
  15. Holler, Manfred J.; Illing, Gerhard (2008): Einführung in die Spieltheorie, 7.Auflage, Berlin: Springer-Verlag, S.55, ISBN 978-3-540-69372-7
  16. Rieck, Christian (2015): Spieltheorie – Eine Einführung, 14. Überarbeitete Auflage, Eschborn: Rieck Verlag. S. 336, ISBN 3-924043-91-4