Minimax-Prinzip

Aus Wikiludia
Wechseln zu: Navigation, Suche

Das Minimax-Prinzip ist eine äquivalente Formulierung des Begriffs Nash-Gleichgewicht für Zweipersonen-Nullsummenspiele. Es besagt im Grunde, dass bei einem Zweipersonen-Nullsummenspiel die Maximinstrategie zum Nash-Gleichgewicht führt.

Es sei Γ ein Zweipersonen-Nullsummenspiel mit den Strategiemengen S1,S2 und den Auszahlungsfunktionen u1 = u und u2 = − u. Dann gilt:

  • Γ besitzt genau dann ein Nash-Gleichgewicht, wenn \min_{s_2\in S_2} \max_{s_1\in S_1} u(s_1,s_2) = \max_{s_1\in S_1} \min_{s_2\in S_2} u(s_1,s_2) gilt, und diese gemeinsame Zahl nennt man dann den Wert W(Γ) des Spiels.
  • Im Fall, daß Γ ein Nash-Gleichgewicht besitzt, gilt: eine Strategie (s_1^*,s_2^*)\in S_1\times S_2 ist genau dann ein Nash-Gleichgewicht, wenn u(s_1^*, s_2) \ge W(\Gamma) für alle s_2\in S_2 sowie u(s_1, s_2^*) \le W(\Gamma) für alle s_1\in S_1 ist.

Folgerungen

Aus dem Minimax-Prinzip erhält man sofort als Folgerungen:

  • Für jedes Nash-Gleichgewicht (s_1^*, s_2^*) von Γ ist die Auszahlung gerade der Wert des Spiels, u(s_1^*, s_2^*) = W(\Gamma).
  • Spielt der Spieler i eine Strategie, die Teil eines Nash-Gleichgewichtes ist, so ist es für i kein Nachteil, wenn der andere Spieler j\neq i nicht auf ein Nash-Gleichgewicht hin spielt. Anders gesagt: spielt Spieler 1 eine Strategie, die Teil eines Nash-Gleichgewichtes ist, so ist ihm eine Auszahlung von mindestens W(Γ) garantiert; analog ist Spieler 2 bei geschicktem Spiel eine Auszahlung von mindestens W(Γ) garantiert. Die Entscheidung eines Spielers für eine zu einem Nash-Gleichgewicht gehörige Strategie stellt also wesentlich schwächere Anforderungen an die Rationalität des Gegners als bei anderen Spielen.
  • Die Menge der Nash-Gleichgewichte von Γ ist entweder leer oder ein Quader G_1 \times G_2 \subset S_1 \times S_2 mit nichtleeren Mengen G1,G2. Insbesondere kann also für Nullsummenspiele das Phänomen nicht auftreten, daß beide Spieler Strategien spielen, die Komponenten verschiedener Nash-Gleichgewichte sind, so daß das resultierende Strategieprofil kein Nash-Gleichgewicht ist.

Beweis des Minimax-Prinzips

Im Artikel Nullsummenspiel:Zwei Personen.


Das Minimax-Theorem

Das zuerst 1928 von John von Neumann bewiesene Minimax-Theorem besagt nun: Für jedes endliche Zweipersonen-Nullsummenspiel ist nach Übergang zu gemischten Strategien die Minimaxgleichung erfüllt, und jedes endliche Zweipersonen-Nullsummenspiel besitzt ein Nash-Gleichgewicht in gemischten Strategien.

Meine Werkzeuge