Lineare Optimierung (Spieltheorie)

Die lineare Optimierung w​ird im Rahmen d​er Spieltheorie z​ur Ermittlung optimal gemischter Strategien genutzt. Das Verfahren i​st insbesondere b​ei sehr komplizierten Nullsummenspielen anwendbar u​nd garantiert darüber hinaus b​ei Spielen m​it mehr a​ls zwei Personen u​nd einer Vielzahl möglicher Strategien d​ie Ermittlung v​on Gleichgewichten.[1]

Vorgehen

Zweipersonenspiele, d​ie eine endliche Spieldauer aufweisen, können n​ach John v​on Neumann u​nd Oskar Morgenstern a​uf folgende Normalform gebracht werden: [2]

	S1	S2	${\displaystyle \ldots }$	Sn-1	Sn
Z1	a1,1	a1,2	${\displaystyle \ldots }$	a1,n-1	a1,n
Z2	a2,1	a2,2	${\displaystyle \ldots }$	a2,n-1	a2,n
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \ddots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$
Zm-1	am-1,1	am-1,2	${\displaystyle \ldots }$	am-1,n-1	am-1,n
Zm	am,1	am,2	${\displaystyle \ldots }$	am,n-1	am,n

Die Menge ${\displaystyle Z_{1},\ldots ,Z_{m}}$ sind die Strategien des Zeilenspielers Z. Die Menge ${\displaystyle S_{1},\ldots ,S_{n}}$ sind die Strategien des Spaltenspielers S.

Die Auszahlungsmatrix mit den Werten ${\displaystyle a_{i,j}(i=1,\ldots ,m;j=1,\ldots ,n)}$ 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 ${\displaystyle a_{1,1}}$ und S die Auszahlung ${\displaystyle -a_{1,1}}$ .

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 ${\displaystyle Z_{i}(i=1,\ldots ,m)}$ wählt, werden im Folgenden mit ${\displaystyle p_{i}(p_{i}\geq 0,\sum _{i=1}^{m}p_{i}=1)}$ und die Wahrscheinlichkeiten, mit der S die Strategien ${\displaystyle S_{j}(j=1,\ldots ,n)}$ spielt mit ${\displaystyle q_{j}(q_{j}\geq 0,\sum _{j=1}^{n}q_{j}=1)}$ bezeichnet. Mit der Verteilung der Wahrscheinlichkeiten ${\displaystyle \!\ {p}}$ über ${\displaystyle {Z_{1},\ldots ,Z_{m}}}$ erhält Z seine gemischte Strategie und mit der Verteilung der Wahrscheinlichkeiten ${\displaystyle \!\ {q}}$ über ${\displaystyle {S_{1},\ldots ,S_{n}}}$ erhält S seine gemischte Strategie. Der erwartete Gewinn ${\displaystyle \!\ {E}}$ des Zeilenspielers ergibt sich folgendermaßen:

${\displaystyle \operatorname {E} (p,q)=\sum _{i=1}^{m}\sum _{j=1}^{n}p_{i}q_{j}a_{ij}}$ . 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 ${\displaystyle \!\ {a_{*}}}$ die obere Auszahlungsschranke des Zeilenspielers und ${\displaystyle \!\ {a^{*}}}$ die untere Auszahlungsschranke des Spaltenspielers dar.

${\displaystyle a_{*}={\underset {p}{\mathrm {max} }}\,{\underset {S_{j}}{\mathrm {min} }}\,\operatorname {E} (p,S_{j})}$

${\displaystyle a^{*}={\underset {q}{\mathrm {min} }}\,{\underset {Z_{i}}{\mathrm {max} }}\,\operatorname {E} (q,Z_{i})}$

Der Maximierungsspieler Z findet seine optimale Strategie ${\displaystyle \!\ {p^{0}}}$ durch die Lösung des folgenden Problems:

maximiere ${\displaystyle \!\ {a_{*}}}$

so dass ${\displaystyle a_{*}\leq \sum _{i=1}^{m}a_{ij}p_{i}\qquad (j=1,\ldots ,n)}$ und

${\displaystyle \sum _{i=1}^{m}p_{i}=1}$ und

${\displaystyle \quad p_{i}\geq 0\qquad (i=1,\ldots ,m)}$

Der Minimierungsspieler S hat auf der Suche nach der optimalen Strategie ${\displaystyle \!\ {q^{0}}}$ folgendes Problem zu lösen:

minimiere ${\displaystyle \!\ {a^{*}}}$

so dass ${\displaystyle a^{*}\geq \sum _{j=1}^{n}a_{ij}q_{j}\qquad (i=1,\ldots ,m)}$ und

${\displaystyle \sum _{j=1}^{n}q_{j}=1}$ und

${\displaystyle \quad q_{j}\geq 0\qquad (j=1,\ldots ,n)}$

Gilt ${\displaystyle \!\ {a_{*}}={a^{*}}}$ , so ergibt sich ein gemischter Wert ${\displaystyle \!\ {W}}$ . Diesen Wert können sich beide Spieler nur aufgrund der Kenntnis der Auszahlungsmatrix durch Wahl der gemischten Minimax-Strategie ${\displaystyle \!\ {p^{0}}}$ und ${\displaystyle \!\ {q^{0}}}$ jederzeit garantieren. Es wird vorausgesetzt, dass der Wert des Spiels ${\displaystyle \!\ {W}}$ 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 ${\displaystyle x_{i}={\frac {p_{i}}{a_{*}}}(i=1,\ldots ,m)}$ und ${\displaystyle y_{j}={\frac {q_{j}}{a^{*}}}(j=1,\ldots ,n)}$ führt durch Einsetzen in die oben ermittelten Gleichungen zu den finalen linearen Optimierungsproblemen.

Für den Zeilenspieler ergibt sich folgendes Optimierungsproblem ${\displaystyle \!\ {L_{1}}}$ :

${\displaystyle \!{\frac {1}{a}}_{*}=\sum _{i=1}^{m}x_{i}}$ zu minimieren unter den Nebenbedingungen ${\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}\geq 1;\qquad x_{i}\geq 0\qquad (i=1,\ldots ,m;j=1,\ldots ,n)}$

Für den Spaltenspieler ergibt sich folgendes Optimierungsproblem ${\displaystyle \!\ {L_{2}}}$ :

${\displaystyle \!{\frac {1}{a}}*=\sum _{j=1}^{n}y_{j}}$ zu maximieren unter den Nebenbedingungen ${\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}\leq 1;\qquad y_{j}\geq 0\qquad (i=1,\ldots ,m;j=1,\ldots ,n)}$

Die Lösung der Aufgabe erfolgt über das Simplex-Verfahren. Da ${\displaystyle L_{1}}$ und ${\displaystyle L_{2}}$ zueinander duale Programme darstellen, reicht es aus, ${\displaystyle L_{1}}$ oder ${\displaystyle L_{2}}$ zu lösen, um die Strategien für beide Spieler zu ermitteln. Die Ergebnisse für ${\displaystyle x_{i}}$ und ${\displaystyle y_{j}}$ können aus dem entwickelten Simplex-Endtableau abgelesen werden und ermöglichen ohne viel Aufwand die Ermittlung des Spielwertes ${\displaystyle W}$ und der optimal gemischten Strategien ${\displaystyle p^{0}}$ und ${\displaystyle q^{0}}$ .

Beispiel

Das Vorgehen z​ur Bestimmung d​er optimal gemischten Strategien s​oll anhand d​es Knobelspiels Schere, Stein, Papier verdeutlicht werden. Das Zwei-Personen-Nullsummenspiel w​eist folgende Auszahlungsmatrix auf:

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

Für d​as gegebene Spiel l​iegt kein Sattelpunkt i​n reinen Strategien vor. Die Lösung d​es Problems erfolgt m​it Hilfe d​er linearen Optimierung u​nd der Ermittlung d​er Wahrscheinlichkeitsverteilungen.

Da für d​as weitere Vorgehen positive Werte d​er Auszahlungsmatrix vorausgesetzt werden, erfolgt d​ie Addition e​iner Konstanten. Dies führt n​icht zu e​iner Änderung d​er optimalen Strategien, sondern n​ur zu e​iner Änderung d​er Erwartungswerte. Nach Lösung d​es Optimierungsproblems m​uss diese Konstante wieder abgezogen werden. In d​em gewählten Beispiel führt d​ie Addition v​on 2 z​u dem gewünschten Ergebnis.

So entsteht aus der Ausgangsmatrix ${\displaystyle A={\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix}}\ \Rrightarrow \ A^{\prime }={\begin{pmatrix}2&1&3\\3&2&1\\1&3&2\end{pmatrix}}}$

Daraus entwickeln s​ich die folgenden Optimierungsprobleme:

Zeilenspieler:

minimiere ${\displaystyle {\frac {1}{a_{*}}}=\sum _{i=1}^{3}x_{i}\ }$ so dass

${\displaystyle {\begin{alignedat}{3}2x_{1}&+&3x_{2}&+&x_{3}\geq 1\\x_{1}&+&2x_{2}&+&3x_{3}\geq 1\\3x_{1}&+&x_{2}&+&2x_{3}\geq 1\end{alignedat}}}$

${\displaystyle x_{i}\geq 0;\ i=1,2,3}$

Spaltenspieler:

maximiere ${\displaystyle {\frac {1}{a^{*}}}=\sum _{j=1}^{3}y_{j}\ }$ so dass

${\displaystyle {\begin{alignedat}{3}2y_{1}&+&y_{2}&+&3y_{3}\leq 1\\3y_{1}&+&2y_{2}&+&y_{3}\leq 1\\y_{1}&+&3y_{2}&+&2y_{3}\leq 1\end{alignedat}}}$

${\displaystyle y_{j}\geq 0;\ j=1,2,3}$

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

${\displaystyle x_{1}=x_{2}=x_{3}={\frac {1}{6}}\qquad y_{1}=y_{2}=y_{3}={\frac {1}{6}}}$

Für ${\displaystyle {\frac {1}{a_{*}}}=\sum _{i=1}^{m}x_{i}}$ lässt sich der Wert ${\displaystyle {\frac {1}{2}}}$ ermitteln.

Aufgrund der Beziehungen ${\displaystyle x_{i}={\frac {p_{i}}{a_{*}}};\quad y_{j}={\frac {q_{j}}{a^{*}}}}$ ergeben sich die optimalen Strategien ${\displaystyle \ p^{*}}$ und ${\displaystyle q^{*}}$ .

${\displaystyle p_{i}^{*}=2\cdot {\frac {1}{6}}={\frac {1}{3}}\qquad q_{j}^{*}=2\cdot {\frac {1}{6}}={\frac {1}{3}}}$

Die optimale gemischte Strategie des Zeilenspielers lautet: ${\displaystyle \ p_{i}^{*}=\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}$

Die optimale gemischte Strategie des Spaltenspielers lautet: ${\displaystyle \ q_{j}^{*}=\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}$

Der Wert des Spiels mit der Auszahlungsmatrix ${\displaystyle A^{\prime }}$ beträgt ${\displaystyle a_{*}=a^{*}=W^{\prime }=2}$ . Für die Ausgangsmatrix ${\displaystyle A}$ ergibt sich der Spielwert durch Subtraktion der Konstanten und damit ist ${\displaystyle W=W^{\prime }-2=0}$ .

Gilt für ein Spiel ${\displaystyle W=0}$ , so wird dieses Spiel als fair bezeichnet.

Die ermittelten optimalen Strategien für das Spiel ${\displaystyle A^{\prime }}$ stellen aufgrund der Äquivalenz gleichzeitig optimale Strategien für das Spiel ${\displaystyle A}$ dar.[5]

Um d​en optimalen Gewinn z​u erlangen, müssen b​eide Spieler j​ede der möglichen Strategien m​it einer Wahrscheinlichkeit v​on 33,33 % spielen u​nd diese d​amit zufällig gleich o​ft anwenden.[6]

Belege

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

• 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.