Linear Optimization (Game Theory)

The linear programming is in the context of game theory to determine optimal mixed strategies used. The method is particularly applicable to very complicated zero-sum games and also guarantees the determination of equilibria in games with more than two people and a large number of possible strategies.

Action

Two-person games that have a finite playing time can, according to John von Neumann and Oskar Morgenstern , be brought to the following normal form:

	S 1	S 2	${\displaystyle \ldots }$	S n-1	S n
Z 1	a 1.1	a 1.2	${\displaystyle \ldots }$	a 1, n-1	a 1, n
Z 2	a 2.1	a 2.2	${\displaystyle \ldots }$	a 2, n-1	a 2, n
${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$	${\displaystyle \ddots }$	${\displaystyle \vdots }$	${\displaystyle \vdots }$
Z m-1	a m-1.1	a m-1.2	${\displaystyle \ldots }$	a m-1, n-1	a m-1, n
Z m	a m, 1	a m, 2	${\displaystyle \ldots }$	a m, n-1	a m, n

The set are the strategies of the line player Z. The set are the strategies of the column player S. ${\displaystyle Z_{1},\ldots ,Z_{m}}$ ${\displaystyle S_{1},\ldots ,S_{n}}$

The payout matrix with the values describes all payouts made by the line player. If in zero-sum games the line player chooses the pure strategy 1 and the column player chooses the pure strategy 1, Z gets the payout and S the payout . ${\displaystyle a_{i,j}(i=1,\ldots ,m;j=1,\ldots ,n)}$ ${\displaystyle a_{1,1}}$ ${\displaystyle -a_{1,1}}$

According to the min-max theorem , both players should choose their strategy in such a way that their own maximum losses are minimized. If no saddle point can be determined with the help of the min-max criterion and therefore no pure strategy that is optimal for each player, it is advisable to mix the respective strategies. In order to maximize your own payouts, the selection of strategies must be done randomly with certain probabilities. If a player randomly “rolls” his strategy according to this probability distribution, he is certain of the best possible profit expectation that he can have if he chooses his strategy independently of that of his opponent.

The probabilities with which Z selects the strategies are denoted in the following with and the probabilities with which S plays the strategies with . With the distribution of the probabilities over , Z receives his mixed strategy and with the distribution of the probabilities over , S receives his mixed strategy. The line player's expected profit is as follows: ${\displaystyle Z_{i}(i=1,\ldots ,m)}$ ${\displaystyle p_{i}(p_{i}\geq 0,\sum _{i=1}^{m}p_{i}=1)}$ ${\displaystyle S_{j}(j=1,\ldots ,n)}$ ${\displaystyle q_{j}(q_{j}\geq 0,\sum _{j=1}^{n}q_{j}=1)}$ ${\displaystyle \!\ {p}}$ ${\displaystyle {Z_{1},\ldots ,Z_{m}}}$ ${\displaystyle \!\ {q}}$ ${\displaystyle {S_{1},\ldots ,S_{n}}}$ ${\displaystyle \!\ {E}}$

${\displaystyle \operatorname {E} (p,q)=\sum _{i=1}^{m}\sum _{j=1}^{n}p_{i}q_{j}a_{ij}}$. Conversely, the column player loses exactly this expected value.

For the further procedure it is necessary to extend the Min-Max theorem and its idea to mixed strategies. It is important to play the mixed strategy that maximizes the minimum of the expected profit or minimizes the maximum of the expected loss. In other words, represent the upper payout limit of the line player and the lower payout limit of the column player. ${\displaystyle \!\ {a_{*}}}$ ${\displaystyle \!\ {a^{*}}}$

${\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})}$

The maximizing player Z finds his optimal strategy by solving the following problem: ${\displaystyle \!\ {p^{0}}}$

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

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

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

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

The minimization player S has to solve the following problem in search of the optimal strategy : ${\displaystyle \!\ {q^{0}}}$

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

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

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

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

If so, the result is a mixed value . This value both players can only because of the knowledge of the payoff matrix by selecting the mixed minimax strategy and any time guarantee. It is assumed that the value of the game is greater than 0. This is always ensured when the payout matrix only contains positive elements. If this is not the case, it can be achieved by adding a sufficiently large uniform constant. This constant is deducted again after the calculation has been completed. ${\displaystyle \!\ {a_{*}}={a^{*}}}$ ${\displaystyle \!\ {W}}$ ${\displaystyle \!\ {p^{0}}}$ ${\displaystyle \!\ {q^{0}}}$ ${\displaystyle \!\ {W}}$

The introduction of the new variables and leads to the final linear optimization problems by inserting them into the equations determined above. ${\displaystyle x_{i}={\frac {p_{i}}{a_{*}}}(i=1,\ldots ,m)}$ ${\displaystyle y_{j}={\frac {q_{j}}{a^{*}}}(j=1,\ldots ,n)}$

The following optimization problem arises for the line player : ${\displaystyle \!\ {L_{1}}}$

${\displaystyle \!{\frac {1}{a}}_{*}=\sum _{i=1}^{m}x_{i}}$ to minimize under the constraints ${\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)}$

The following optimization problem arises for the column player : ${\displaystyle \!\ {L_{2}}}$

${\displaystyle \!{\frac {1}{a}}*=\sum _{j=1}^{n}y_{j}}$ to maximize under the constraints ${\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)}$

The task is solved using the simplex method . Since and represent dual programs to one another, it is sufficient to solve or to determine the strategies for both players. The results for and can be read from the developed Simplex end table and enable the determination of the game value and the optimally mixed strategies and without much effort . ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle W}$ ${\displaystyle p^{0}}$ ${\displaystyle q^{0}}$

example

The procedure for determining the optimally mixed strategies should be illustrated using the puzzle game scissors, stone, paper . The two-person zero-sum game has the following payout matrix:

	scissors	stone	paper
scissors	0	−1	1
stone	1	0	−1
paper	−1	1	0

For the given game there is no saddle point in pure strategies. The problem is solved with the help of linear optimization and the determination of the probability distributions.

Since positive values ​​of the payout matrix are assumed for the further procedure, a constant is added. This does not lead to a change in the optimal strategies, but only to a change in the expected values. After solving the optimization problem, this constant must be subtracted again. In the example chosen, adding 2 leads to the desired result.

This is how the output matrix arises ${\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}}}$

This leads to the following optimization problems:

Line player:

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

${\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}$

Column player:

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

${\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}$

The two linear programs can be solved with the help of the simplex method . The following values ​​result for the selected example:

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

The value for can be determined. ${\displaystyle {\frac {1}{a_{*}}}=\sum _{i=1}^{m}x_{i}}$ ${\displaystyle {\frac {1}{2}}}$

The optimal strategies and result from the relationships . ${\displaystyle x_{i}={\frac {p_{i}}{a_{*}}};\quad y_{j}={\frac {q_{j}}{a^{*}}}}$ ${\displaystyle \ p^{*}}$ ${\displaystyle q^{*}}$

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

The line player's optimal mixed strategy is: ${\displaystyle \ p_{i}^{*}=\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}$

The column player's optimal mixed strategy is: ${\displaystyle \ q_{j}^{*}=\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}$

The value of the game with the payout matrix is . For the output matrix, the play value is obtained by subtracting the constants and thus is . ${\displaystyle A^{\prime }}$ ${\displaystyle a_{*}=a^{*}=W^{\prime }=2}$ ${\displaystyle A}$ ${\displaystyle W=W^{\prime }-2=0}$

If it applies to a game , that game is said to be fair. ${\displaystyle W=0}$

The determined optimal strategies for the game represent at the same time optimal strategies for the game due to the equivalence . ${\displaystyle A^{\prime }}$ ${\displaystyle A}$

In order to achieve the optimal profit, both players have to play each of the possible strategies with a probability of 33.33% and thus randomly apply them equally often.

supporting documents

1. ↑ Avinash K. Dixit / Barry J. Nalebuff: Game Theory for Beginners. Strategic know-how for winners . Schaeffer-Poeschel Verlag, Stuttgart, 1997, p. 175.
2. ^ John von Neumann / Oskar Morgenstern: Game theory and economic behavior , Physica-Verlag, Würzburg, 1967, p. 93.
3. ^ Hans-Jürgen Zimmermann: Operations Research , Vieweg + Teubner Verlag, Braunschweig / Wiesbaden, 2005, p. 38.
4. ↑ Frederick S. Hillier / Gerald J. Liebermann: Operations Research , Oldenbourg, 1996, p. 360.
5. ↑ Hans-Jürgen Zimmermann: Operations Research , Vieweg + Teubner Verlag, Braunschweig / Wiesbaden, 2005, p. 37.
6. ^ Karl Manteuffel / Dieter Stumpe: Game theory , Vieweg + Teubner Verlag, Leipzig, 1997, p. 32.

literature

• John von Neumann, Oskar Morgenstern: Game theory and economic behavior . 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: Game Theory for Beginners. Strategic know-how for winners . 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: Game theory , Vieweg + Teubner Verlag, Leipzig 1997, ISBN 978-3322007247 .