Lineare Programmierung

From Wiwiwiki.net
Jump to navigationJump to search

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

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

S1 S2 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ldots} Sn-1 Sn
Z1 a1,1 a1,2 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ldots} a1,n-1 a1,n
Z2 a2,1 a2,2 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ldots} a2,n-1 a2,n
Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \vdots} Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \vdots} Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \vdots}  Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ddots} Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \vdots} Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \vdots}
Zm-1 am-1,1 am-1,2 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ldots} am-1,n-1 am-1,n
Zm am,1 am,2 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \ldots} am,n-1 am,n

Die Menge Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle Z_1, \ldots, Z_m} sind die Strategien des Zeilenspielers Z. Die Menge Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle S_1, \ldots, S_n} sind die Strategien des Spaltenspielers S.

Die Auszahlungsmatrix mit den Werten Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a_{1,1}} und S die Auszahlung Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\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 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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle Z_i (i = 1,\ldots, m)} wählt, werden im Folgenden mit Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle p_i ( p_i \geq 0,\sum_{i=1}^m p_i = 1)} und die Wahrscheinlichkeiten, mit der S die Strategien Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle S_j (j = 1,\ldots, n)} spielt mit Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle q_j ( q_j \geq 0,\sum_{j=1}^n q_j = 1 )} bezeichnet. Mit der Verteilung der Wahrscheinlichkeiten Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {p}} über Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle {Z_1, \ldots, Z_m}} erhält Z seine gemischte Strategie und mit der Verteilung der Wahrscheinlichkeiten Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {q}} über Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle {S_1, \ldots, S_n}} erhält S seine gemischte Strategie. Der erwartete Gewinn Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {E}} des Zeilenspielers ergibt sich folgendermaßen:

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a_*}} die obere Auszahlungsschranke des Zeilenspielers und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a^*}} die untere Auszahlungsschranke des Spaltenspielers dar.


Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a_* = \underset{p}{max} \underset {S_j}{min} \ E(p, S_j)}

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a^* = \underset{q}{min} \underset {Z_i}{max} \ E(q, Z_i)}


Der Maximierungsspieler Z findet seine optimale Strategie Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {p^0}} durch die Lösung des folgenden Problems:

maximiere Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a_*}}

so dass Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a_* \leq \sum_{i=1}^m a_{ij}p_i \qquad (j = 1,\ldots, n)} und

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \sum_{i=1}^m p_i = 1} und

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \quad p_i \geq 0 \qquad (i = 1,\ldots, m)}


Der Minimierungsspieler S hat auf der Suche nach der optimalen Strategie Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {q^0}} folgendes Problem zu lösen:

minimiere Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a^*}}

so dass Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle a^* \geq \sum_{j=1}^n a_{ij}q_j \qquad (i = 1,\ldots, m)} und

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \sum_{j=1}^n q_j = 1} und

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \quad q_j \geq 0 \qquad (j = 1,\ldots, n)}


Gilt Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a_*}= {a^*}} , so ergibt sich ein gemischter Wert Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {W}} . Diesen Wert können sich beide Spieler nur aufgrund der Kenntnis der Auszahlungsmatrix durch Wahl der gemischten Minimax-Strategie Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {p^0}} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {q^0}} jederzeit garantieren. Es wird vorausgesetzt, dass der Wert des Spiels Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle x_i = \frac {p_i} {a_*} (i = 1,\ldots, m)} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_1}} :

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac 1a_* = \sum_{i=1}^m x_i} zu minimieren unter den Nebenbedingungen Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_2}} :

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac 1a* = \sum_{j=1}^n y_j} zu maximieren unter den Nebenbedingungen Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_1}} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_2}} zueinander duale Programme darstellen, reicht es aus Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_1}} oder Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {L_2}} zu lösen, um die Strategien für beide Spieler zu ermitteln. Die Ergebnisse für Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {x_i}} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {y_j}} können aus dem entwickelten Simplex-Endtableau abgelesen werden und ermöglichen ohne viel Aufwand die Ermittlung des Spielwertes Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {W}} und der optimal gemischten Strategien Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {p^0}} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {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 Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle A = \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 &-1 \\ -1 & 1 & 0 \end{pmatrix}\Rrightarrow } Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle A^\prime = \begin{pmatrix} 2 & 1 & 3 \\ 3 & 2 & 1 \\ 1 & 3 & 2 \end{pmatrix} }

Daraus entwickeln sich die folgenden Optimierungsprobleme:

Zeilenspieler:

minimiere Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac 1a_* = \sum_{i=1}^3 x_i}

so dass

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \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}}


Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle x_i \geq 0} , Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle i = 1, \ldots, 3}


Spaltenspieler:

maximiere Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac {1}{a^*} = \sum_{j=1}^3 y_j}

so dass

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \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}}


Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle y_j \geq 0} , Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle x_1 = x_2 = x_3 = \frac {1}{6} \qquad y_1 = y_2 = y_3 = \frac {1}{6}}


Für Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac 1a_* = \sum_{i=1}^m x_i} lässt sich der Wert Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\frac {1}{2}} ermitteln.


Aufgrund der Beziehungen Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle x_i = \frac {p_i}{a_*}; \qquad y_j = \frac {q_j}{a^*}} ergeben sich die optimalen Strategien Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {p^0}} und Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {q^0}}

Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle p^*_i = \left( \frac{1}{3},\frac{1}{3}, \frac{1}{3} \right)}

Die optimale gemischte Strategie des Spaltenspielers lautet: Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle q^*_j = \left( \frac{1}{3},\frac{1}{3}, \frac{1}{3} \right)}

Der Wert des Spiels mit der Auszahlungsmatrix Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle A^\prime} beträgt Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {a_*}= {a^*}= {W^\prime}=2} . Für die Ausgangsmatrix Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {A}} ergibt sich der Spielwert durch Subtraktion der Konstanten und damit ist Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {W}= {W^\prime}- 2= 0} .

Gilt für ein Spiel Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {W}= 0} , so wird dieses Spiel als fair bezeichnet.


Die ermittelten optimalen Strategien für das Spiel Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {A^\prime}} stellen aufgrund der Äquivalenz gleichzeitig optimale Strategien für das Spiel Fehler beim Parsen (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \!\ {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.
Qsicon inArbeit.png
Qsicon inArbeit.png
Dieser Artikel befindet sich derzeit im Review-Prozess. Sag auch dort deine Meinung und hilf mit, den Artikel zu verbessern!