Lineare Optimierung (Spieltheorie)

Instrument der Spieltheorie zur Ermittlung optimal gemischter Strategien

Die lineare Optimierung wird im Rahmen der Spieltheorie zur Ermittlung optimal gemischter Strategien genutzt. Das Verfahren ist insbesondere bei sehr komplizierten Nullsummenspielen anwendbar und garantiert darüber hinaus bei Spielen mit mehr als zwei Personen und einer Vielzahl möglicher Strategien die Ermittlung von Gleichgewichten.[1]

Vorgehen

Bearbeiten

Zweipersonenspiele, die eine endliche Spieldauer aufweisen, können nach John von Neumann und Oskar Morgenstern auf folgende Normalform gebracht werden:[2]

S1 S2   Sn-1 Sn
Z1 a1,1 a1,2   a1,n-1 a1,n
Z2 a2,1 a2,2   a2,n-1 a2,n
            
Zm-1 am-1,1 am-1,2   am-1,n-1 am-1,n
Zm am,1 am,2   am,n-1 am,n

Die Menge   sind die Strategien des Zeilenspielers Z. Die Menge   sind die Strategien des Spaltenspielers S.

Die Auszahlungsmatrix mit den Werten   beschreibt sämtliche Auszahlungen des Zeilenspielers. Wenn in Nullsummenspielen der Zeilenspieler die reine Strategie 1 wählt und der Spaltenspieler die reine Strategie 1, so bekommt Z die Auszahlung   und S die Auszahlung  .

Nach dem Min-Max-Theorem sollten beide Spieler ihre Strategie so wählen, dass die eigenen maximalen Verluste minimiert werden. Kann mit Hilfe des Min-Max-Kriteriums kein Sattelpunkt und damit keine für jeden Spieler optimale reine Strategie ermittelt werden, empfiehlt es sich, die jeweiligen Strategien zu mischen. Um die eigenen Auszahlungen zu maximieren, muss die Auswahl der Strategien zufällig mit bestimmten Wahrscheinlichkeiten erfolgen.[3] „Würfelt“ ein Spieler seine Strategie gemäß dieser Wahrscheinlichkeitsverteilung zufällig aus, ist ihm die bestmögliche Gewinnerwartung sicher, die er haben kann, wenn er seine Strategie unabhängig von der seines Gegners wählt.

Die Wahrscheinlichkeiten, mit der Z die Strategien   wählt, werden im Folgenden mit   und die Wahrscheinlichkeiten, mit der S die Strategien   spielt mit   bezeichnet. Mit der Verteilung der Wahrscheinlichkeiten   über   erhält Z seine gemischte Strategie und mit der Verteilung der Wahrscheinlichkeiten   über   erhält S seine gemischte Strategie. Der erwartete Gewinn   des Zeilenspielers ergibt sich folgendermaßen:

 . Umgekehrt verliert der Spaltenspieler genau diesen Erwartungswert.

Für das weitere Vorgehen ist es notwendig, das Min-Max-Theorem und dessen Idee auf gemischte Strategien auszuweiten. Es gilt, diejenige gemischte Strategie zu spielen, die das Minimum des erwarteten Gewinns maximiert bzw. das Maximum des erwarteten Verlustes minimiert.[4] Anders ausgedrückt, stellen   die obere Auszahlungsschranke des Zeilenspielers und   die untere Auszahlungsschranke des Spaltenspielers dar.

 

 

Der Maximierungsspieler Z findet seine optimale Strategie   durch die Lösung des folgenden Problems:

maximiere  

so dass   und

  und

 


Der Minimierungsspieler S hat auf der Suche nach der optimalen Strategie   folgendes Problem zu lösen:

minimiere  

so dass   und

  und

 

Gilt  , so ergibt sich ein gemischter Wert  . Diesen Wert können sich beide Spieler nur aufgrund der Kenntnis der Auszahlungsmatrix durch Wahl der gemischten Minimax-Strategie   und   jederzeit garantieren. Es wird vorausgesetzt, dass der Wert des Spiels   größer 0 ist. Dies ist immer dann gesichert, wenn die Auszahlungsmatrix nur positive Elemente enthält. Wenn dies nicht der Fall ist, kann es durch die Addition einer genügend großen einheitlichen Konstante erreicht werden. Nach Beendigung der Rechnung wird diese Konstante wieder abgezogen.

Die Einführung der neuen Variablen   und   führt durch Einsetzen in die oben ermittelten Gleichungen zu den finalen linearen Optimierungsproblemen.

Für den Zeilenspieler ergibt sich folgendes Optimierungsproblem  :

  zu minimieren unter den Nebenbedingungen  

Für den Spaltenspieler ergibt sich folgendes Optimierungsproblem  :

  zu maximieren unter den Nebenbedingungen  

Die Lösung der Aufgabe erfolgt über das Simplex-Verfahren. Da   und   zueinander duale Programme darstellen, reicht es aus,   oder   zu lösen, um die Strategien für beide Spieler zu ermitteln. Die Ergebnisse für   und   können aus dem entwickelten Simplex-Endtableau abgelesen werden und ermöglichen ohne viel Aufwand die Ermittlung des Spielwertes   und der optimal gemischten Strategien   und  .

Beispiel

Bearbeiten

Das Vorgehen zur Bestimmung der optimal gemischten Strategien soll anhand des Knobelspiels Schere, Stein, Papier verdeutlicht werden. Das Zwei-Personen-Nullsummenspiel weist folgende Auszahlungsmatrix auf:

Schere Stein Papier
Schere 0 −1 1
Stein 1 0 −1
Papier −1 1 0

Für das gegebene Spiel liegt kein Sattelpunkt in reinen Strategien vor. Die Lösung des Problems erfolgt mit Hilfe der linearen Optimierung und der Ermittlung der Wahrscheinlichkeitsverteilungen.

Da für das weitere Vorgehen positive Werte der Auszahlungsmatrix vorausgesetzt werden, erfolgt die Addition einer Konstanten. Dies führt nicht zu einer Änderung der optimalen Strategien, sondern nur zu einer Änderung der Erwartungswerte. Nach Lösung des Optimierungsproblems muss diese Konstante wieder abgezogen werden. In dem gewählten Beispiel führt die Addition von 2 zu dem gewünschten Ergebnis.

So entsteht aus der Ausgangsmatrix  

Daraus entwickeln sich die folgenden Optimierungsprobleme:

Zeilenspieler:

minimiere   so dass

 
 


Spaltenspieler:

maximiere   so dass

 
 


Die beiden linearen Programme können mit Hilfe des Simplex-Verfahrens gelöst werden. Für das gewählte Beispiel ergeben sich folgende Werte:

 

Für   lässt sich der Wert   ermitteln.

Aufgrund der Beziehungen   ergeben sich die optimalen Strategien   und  .

 

Die optimale gemischte Strategie des Zeilenspielers lautet:  

Die optimale gemischte Strategie des Spaltenspielers lautet:  

Der Wert des Spiels mit der Auszahlungsmatrix   beträgt  . Für die Ausgangsmatrix   ergibt sich der Spielwert durch Subtraktion der Konstanten und damit ist  .

Gilt für ein Spiel  , so wird dieses Spiel als fair bezeichnet.

Die ermittelten optimalen Strategien für das Spiel   stellen aufgrund der Äquivalenz gleichzeitig optimale Strategien für das Spiel   dar.[5]

Um den optimalen Gewinn zu erlangen, müssen beide Spieler jede der möglichen Strategien mit einer Wahrscheinlichkeit von 33,33 % spielen und diese damit zufällig gleich oft anwenden.[6]

  1. Avinash K. Dixit/Barry J. Nalebuff: Spieltheorie für Einsteiger. Strategisches Know-how für Gewinner. Schaeffer-Poeschel Verlag, Stuttgart, 1997, S. 175.
  2. John von Neumann/Oskar Morgenstern: Spieltheorie und wirtschaftliches Verhalten, Physica-Verlag, Würzburg, 1967, S. 93.
  3. Hans-Jürgen Zimmermann: Operations Research, Vieweg+Teubner Verlag, Braunschweig/Wiesbaden, 2005, S. 38.
  4. Frederick S. Hillier/Gerald J. Liebermann: Operations Research, Oldenbourg, 1996, S. 360.
  5. Hans-Jürgen Zimmermann: Operations Research, Vieweg+Teubner Verlag, Braunschweig/Wiesbaden, 2005, S. 37.
  6. Karl Manteuffel/Dieter Stumpe: Spieltheorie, Vieweg+Teubner Verlag, Leipzig, 1997, S. 32.

Literatur

Bearbeiten
  • John von Neumann, Oskar Morgenstern: Spieltheorie und wirtschaftliches Verhalten. Physica-Verlag, Würzburg, 1967.
  • Hans-Jürgen Zimmermann: Operations Research, Vieweg+Teubner Verlag, Braunschweig/Wiesbaden 2005, ISBN 978-3528032104.
  • Avinash K. Dixit, Barry J. Nalebuff: Spieltheorie für Einsteiger. Strategisches Know-how für Gewinner. Schaeffer-Poeschel Verlag, Stuttgart 1997, ISBN 3-7910-1239-8.
  • Frederick S. Hillier, Gerald J. Liebermann: Operations Research, Oldenbourg, 1996, ISBN 978-3486239874.
  • Karl Manteuffel, Dieter Stumpe: Spieltheorie, Vieweg+Teubner Verlag, Leipzig 1997, ISBN 978-3322007247.