Lineare Optimierung (Spieltheorie)

Lineare Optimierung (Spieltheorie)

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]

Inhaltsverzeichnis

Vorgehen

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

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

Die Menge Z_1, \ldots, Z_m sind die Strategien des Zeilenspielers Z. Die Menge S_1, \ldots, S_n sind die Strategien des Spaltenspielers S.

Die Auszahlungsmatrix mit den Werten 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 a1,1 und S die Auszahlung a1,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 Strategie ermittelt werden, empfiehlt es sich die jeweiligen Strategien zu mischen. Um die eigenen Auszahlungen zu erhöhen, muss die Auswahl der Strategien zufällig 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 Z_i (i = 1,\ldots, m) wählt, werden im Folgenden mit p_i ( p_i \geq 0,\sum_{i=1}^m p_i = 1) und die Wahrscheinlichkeiten, mit der S die Strategien S_j (j = 1,\ldots, n) spielt mit q_j ( q_j \geq 0,\sum_{j=1}^n q_j = 1 ) bezeichnet. Mit der Verteilung der Wahrscheinlichkeiten \!\ {p} über {Z_1, \ldots, Z_m} erhält Z seine gemischte Strategie und mit der Verteilung der Wahrscheinlichkeiten \!\ {q} über {S_1, \ldots, S_n} erhält S seine gemischte Strategie. Der erwartete Gewinn \!\ {E} des Zeilenspielers ergibt sich folgendermaßen:

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 \!\ {a_*} die obere Auszahlungsschranke des Zeilenspielers und \!\ {a^*} die untere Auszahlungsschranke des Spaltenspielers dar.


a_* = \underset{p}{max}  \underset {S_j}{min}  \ E(p, S_j)

a^* = \underset{q}{min}  \underset {Z_i}{max}  \ E(q, Z_i)

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

maximiere \!\ {a_*}

so dass a_* \leq \sum_{i=1}^m a_{ij}p_i \qquad (j = 1,\ldots, n) und

\sum_{i=1}^m p_i = 1 und

\quad p_i \geq 0 \qquad (i = 1,\ldots, m)


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

minimiere \!\ {a^*}

so dass a^* \geq \sum_{j=1}^n a_{ij}q_j \qquad (i = 1,\ldots, m) und

\sum_{j=1}^n q_j = 1 und

\quad q_j \geq 0 \qquad (j = 1,\ldots, n)

Gilt \!\ {a_*}= {a^*}, so ergibt sich ein gemischter Wert \!\ {W}. Diesen Wert können sich beide Spieler nur aufgrund der Kenntnis der Auszahlungsmatrix durch Wahl der gemischten Minimax-Strategie \!\ {p^0} und \!\ {q^0} jederzeit garantieren. Es wird vorausgesetzt, dass der Wert des Spiels \!\ {W} größer 0 ist. Falls dies nicht der Fall ist, so kann durch die Addition einer genügend großen einheitlichen Konstante strikt positive Elemente der Auszahlungsmatrix erreicht werden. Nach Beendigung der Rechnung wird diese Konstante wieder abgezogen.

Die Einführung der neuen Variablen x_i = \frac {p_i} {a_*} (i = 1,\ldots, m) und y_j = \frac {q_j} {a^*} (j = 1,\ldots, n) führt durch Einsetzen in die oben ermittelten Gleichungen zu den finalen linearen Optimierungsprogrammen.

Für den Zeilenspieler ergibt sich folgendes Optimierungsproblem \!\ {L_1}:

\!\frac 1a_* = \sum_{i=1}^m x_i zu minimieren unter den Nebenbedingungen \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 \!\ {L_2}:

\!\frac 1a* = \sum_{j=1}^n y_j zu maximieren unter den Nebenbedingungen \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 \!\ {L_1} und \!\ {L_2} zueinander duale Programme darstellen, reicht es aus \!\ {L_1} oder \!\ {L_2} zu lösen, um die Strategien für beide Spieler zu ermitteln. Die Ergebnisse für \!\ {x_i} und \!\ {y_j} können aus dem entwickelten Simplex-Endtableau abgelesen werden und ermöglichen ohne viel Aufwand die Ermittlung des Spielwertes \!\ {W} und der optimal gemischten Strategien \!\ {p^0} und \!\ {q^0}.

Beispiel

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 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 sich die folgenden Optimierungsprobleme:

Zeilenspieler:

minimiere \!\frac 1a_* = \sum_{i=1}^3 x_i

so dass


  \begin{alignat}{3}
    2x_1 &+ & 3x_2 &+ & 1x_3 \geq 1\\
    x_1 &+ & 2x_2 &+ & 3x_3 \geq 1\\
    3x_1 &+ &  x_2 &+ & 2x_3 \geq 1
  \end{alignat}


x_i \geq 0, i = 1, \ldots, 3


Spaltenspieler:

maximiere \!\frac {1}{a^*} = \sum_{j=1}^3 y_j

so dass


  \begin{alignat}{3}
    2y_1 &+ & 1y_2 &+ & 3y_3 \leq 1\\
    3y_1 &+ & 2y_2 &+ & y_3 \leq 1\\
    1y_1 &+ & 3y_2 &+ & 2y_3 \leq 1
  \end{alignat}


y_j \geq 0, j = 1, \ldots, 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:

x_1 = x_2 = x_3 = \frac {1}{6} \qquad y_1 = y_2 = y_3 = \frac {1}{6}


Für \!\frac 1a_* = \sum_{i=1}^m x_i lässt sich der Wert \!\frac {1}{2} ermitteln.


Aufgrund der Beziehungen x_i = \frac {p_i}{a_*} ; \qquad y_j = \frac {q_j}{a^*} ergeben sich die optimalen Strategien \!\ {p^0} und \!\ {q^0}

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: p^*_i = \left( \frac{1}{3},\frac{1}{3}, \frac{1}{3} \right)

Die optimale gemischte Strategie des Spaltenspielers lautet: q^*_j = \left( \frac{1}{3},\frac{1}{3}, \frac{1}{3} \right)

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

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


Die ermittelten optimalen Strategien für das Spiel \!\ {A^\prime} stellen aufgrund der Äquivalenz gleichzeitig optimale Strategien für das Spiel \!\ {A} 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]

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.

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lineare Optimierung — Bei linearen Optimierungsproblemen ist die Menge der zulässigen Punkte (braun) durch lineare Ungleichungen (Hyperebenen) eingeschränkt. Die Lineare Optimierung oder Lineare Programmierung ist eines der Hauptverfahren des Operations Research und… …   Deutsch Wikipedia

  • Lineare Programmierung — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Optimierung (Mathematik) — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines – meist komplexen – Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme… …   Deutsch Wikipedia

  • Lineare partielle Information — (LPI) ist eine lineare Modellierungsmethode für die praxisnahen Entscheidungen, die auf zuvor unscharfen Informationen basieren. Die Theorie wurde 1970 von Edward Kofler in Zürich entwickelt. Begriffsbildungen, Eigenschaften, Vorstellungen oder… …   Deutsch Wikipedia

  • Globale Optimierung — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Duales Problem — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Linear programming — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Lineares Programm — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Primales Problem — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Einsatzforschung — Operations Research (auch operational research, kurz OR) bzw. Unternehmensforschung (Unternehmen im Sinne von operation) ist ein Teilgebiet der Angewandten Mathematik, das sich mit der Optimierung bestimmter Prozesse oder Verfahren beschäftigt.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”