11.3: Reduction by Dominance
- Page ID
- 37941
Sometimes an \(m \times n\) game matrix can be reduced to a \(2 \times 2\) matrix by deleting certain rows and columns. A row can be deleted if there exists another row that will produce a payoff of an equal or better value. Similarly, a column can be deleted if there is another column that will produce a payoff of an equal or better value for the column player. The row or column that produces a better payoff for its corresponding player is said to dominate the row or column with the lesser payoff.
For the following game, determine the optimal strategy for both the row player and the column player, and find the value of the game.
\[G=\left[\begin{array}{ccc}
-2 & 6 & 4 \\
-1 & -2 & -3 \\
1 & 2 & -2
\end{array}\right] \nonumber \]
Solution
We first look for a saddle point and determine that none exist. Next, we try to reduce the matrix to a \(2 \times 2\) matrix by eliminating the dominated row.
Since every entry in row 3 is larger than the corresponding entry in row 2, row 3 dominates row 2. Therefore, a rational row player will never play row 2, and we eliminate row 2. We get
\[\left[\begin{array}{ccc}
-2 & 6 & 4 \\
1 & 2 & -2
\end{array}\right] \nonumber \]
Now we try to eliminate a column. Remember that the game matrix represents the payoffs for the row player and not the column player; therefore, the larger the number in the column, the smaller the payoff for the column player.
The column player will never play column 2, because it is dominated by both column 1 and column 3. Therefore, we eliminate column 2 and get the modified matrix, M, below.
\[\mathrm{M}=\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{array}\right] \nonumber \]
To find the optimal strategy for both the row player and the column player, we use the method learned in Section 11.2.
Let the row player's strategy be \(\mathrm{R}=\left[\begin{array}{ll}
\mathrm{r} & 1-\mathrm{r}
\end{array}\right]\), and the column player's be strategy be \(C=\left[\begin{array}{c}
c \\
1-c
\end{array}\right]\)
To find the optimal strategy for the row player, we, first, find the product RM as below.
\[\left[\begin{array}{lll}
\mathrm{r} & 1-\mathrm{r}
\end{array}\right]\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{array}\right]=\left[\begin{array}{ll}
-3 r+1 & 6 r-2
\end{array}\right] \nonumber \]
By setting the entries equal, we get
\[-3r + 1 = 6r - 2 \nonumber \]
or
\[r = 1/3 \nonumber. \nonumber \]
Therefore, the optimal strategy for the row player is \(\left[\begin{array}{ll}
1/ 3 & 2 / 3
\end{array}\right]\), but relative to the original game matrix it is \(\left[\begin{array}{lll}
1 / 3 & 0 & 2/3
\end{array}\right]\).
To find the optimal strategy for the column player we, first, find the following product.
\[\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{array}\right]\left[\begin{array}{c}
c \\
1-c
\end{array}\right]=\left[\begin{array}{c}
-6 c+4 \\
3 c-2
\end{array}\right] \nonumber \]
We set the entries in the product matrix equal to each other, and we get,
\[-6c + 4 = 3c - 2 \nonumber \]
or
\[c = 2/3 \nonumber. \nonumber \]
Therefore, the optimal strategy for the column player is \(\left[\begin{array}{l}
2 / 3 \\
1 / 3
\end{array}\right]\), but relative to the original game matrix, the strategy for the column player is \(\left[\begin{array}{c}
2 / 3 \\
0 \\
1 / 3
\end{array}\right]\).
To find the expected value, V, of the game, we have two choices: either to find the product of matrices R, M and C, or multiply the optimal strategies relative to the original matrix to the original matrix. We choose the first, and get
\[\begin{array}{l}
\mathrm{V}=\left[\begin{array}{lll}
1 / 3 & 2 / 3
\end{array}\right]\left[\begin{array}{cc}
-2 & 4 \\
1 & -2
\end{array}\right]\left[\begin{array}{l}
2 / 3 \\
1 / 3
\end{array}\right] \\
\mathrm{V}=\left[\begin{array}{l}
0
\end{array}\right]
\end{array} \nonumber \]
Therefore, if both players play their optimal strategy, the value of the game is zero.
We summarize as follows:
- Sometimes an \(m \times n\) game matrix can be reduced to a \(2 \times 2\) matrix by deleting dominated rows and columns.
- A row is called a dominated row if there exists another row that will produce a payoff of an equal or better value. That happens when there exists a row whose every entry is larger than the corresponding entry of the dominated row.
- A column is called a dominated column if there exists another column that will produce a payoff of an equal or better value. This happens when there exists a column whose every entry is smaller than the corresponding entry of the dominated row.