# Problem 6. Game Theory

Problem text. A subsidiary of an oil and gas holding company is in charge of building gas transportation infrastructure oriented towards new markets. The first of its divisions has expertise only in pipeline, while the second has expertise only in maritime transportation and have difficulties in establishing communication due to internal economic reasons. You are tasked with determining the optimal strategies ${ }^{1}$ for the two divisions and the value of the game ${ }^{2}$ for improving coordination. The analytical department has already prepared a payoff matrix for calculating profits in billions of rubles from the use of promising routes by the divisions in accordance with "pure" strategies.

|  | Marine route schemes |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: |
| Pipeline route schemes |  | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{4}$ |
|  | $\mathbf{1}$ | 3 | 0 | 4 | $(-2)$ |
|  | $\mathbf{2}$ | 2 | 4 | 5 | 5 |

Note. Present your answer using formulas and graphically. The answer in the part of determining strategies are the payoff matrices of the two players, the profit values in which are adjusted for optimal coefficients.
Solution to the problem. First, we determine the upper and lower game values and conclude whether a solution in pure strategies is possible. For Pipeline Route Schemes (PRS), the maximin, i.e., the lower game value, can be calculated by selecting the maximum number from the two minimum numbers in each row: \(\max \min (-2,2)=2\).

Similarly, for Maritime Route Schemes (MRS), the minimax, i.e., the upper game value, is determined by finding the minimum value from the maximum values in each column: \(\operatorname{minmax}(3,4,5,5)=3\).

Since \(\max \min \neq \min \max\), we can conclude that a solution in pure strategies is not possible. The game value lies in the interval \(2 < v < 3\).

To reduce the computational volume, let's try to reduce the matrix size by eliminating non-beneficial strategies. Notice that all values in the MRS3 column are greater than all values in the MRS1 column, so the MRS3 column can be removed.

\[
\left(\begin{array}{ccc}
3 & 0 & -2 \\
2 & 4 & 5
\end{array}\right)
\]

Let's find the solution in mixed strategies. MRS can have three pure strategies, which can be represented as lines for a geometric solution. We will calculate the average payoff for PRS under the condition that they use a mixed strategy, while MRS uses pure strategies.

The equation will look like this:

\[
M_{j}\left(x_{1}\right)=\left(a_{1 j}-a_{2 j}\right) * x_{1}+a_{2 j}
\]

Thus, we get three line equations:

\[
\begin{gathered}
M_{1}\left(x_{1}\right)=\left(a_{11}-a_{21}\right) * x_{1}+a_{21}=x_{1}+2 \\
M_{2}\left(x_{1}\right)=\left(a_{12}-a_{22}\right) * x_{1}+a_{22}=-4 x_{1}+4 \\
M_{3}\left(x_{1}\right)=\left(a_{13}-a_{23}\right) * x_{1}+a_{23}=-7 x_{1}+5
\end{gathered}
\]

Let's construct the corresponding graph.

![](https://cdn.mathpix.com/cropped/2024_05_06_609d616e5e19547b23a1g-12.jpg?height=574&width=479&top_left_y=844&top_left_x=914)

For MRS, the goal is to minimize the payoff of PRS by choosing their strategy. Therefore, the corresponding solution area is marked in purple. The goal of PRS is to maximize profit, so we should take the highest point \(\boldsymbol{M}\). Thus, the game can be described by a \(2 \times 2\) matrix:

\[
\left(\begin{array}{ll}
3 & 0 \\
2 & 4
\end{array}\right)
\]

Let's find the optimal strategies:

\[
\left\{\begin{array}{c}
x_{1}+2=-7 x_{1}+5=v \\
x_{1}+x_{2}=1
\end{array}\right.
\]

From this, we get the strategy for PRS:

\[
x_{1}=3 / 8 \quad x_{2}=5 / 8 \quad v=19 / 8
\]

Strategies for MRS:

\(3 y_{1}+0 y_{1}=v=19 / 8\), so \(y_{1}=19 / 24 \quad y_{2}=5 / 24\)

Thus, we get the final answer:

\[
\mathrm{PRS}^{*}=\left(\frac{3}{8}, \frac{5}{8}\right) \mathrm{MRS}^{*}=\left(\frac{19}{24}, \frac{5}{24}, 0,0\right) v=\frac{19}{8}
\]