# How do you use subgames of matrix games to find the game's value?

I have an assignment in my game theory book which goes like this:

Consider the following matrix game: $$A=\begin{pmatrix}3&1&4&0\\1&2&0&5\end{pmatrix}$$ a) Determine all the maximin rows and minimax columns. What can you conclude from this about the value of the game?

b) Consider the six $2\times2$ games that can be obtained by choosing 2 columns of the above game as follows: $$A_1=\begin{pmatrix}3&1\\1&2\end{pmatrix},\quad A_2=\begin{pmatrix}3&4\\1&0\end{pmatrix},\quad A_3=\begin{pmatrix}3&0\\1&5\end{pmatrix},$$ $$A_4=\begin{pmatrix}1&4\\2&0\end{pmatrix} ,\quad A_5=\begin{pmatrix}1&0\\2&5\end{pmatrix},\quad A_6=\begin{pmatrix}4&0\\0&5\end{pmatrix}.$$

Determine all the values of these games. Which one must be equal to the value of $A$?

Now, a) is pretty simple, row $1,2$ are both maximin rows and the only minimax column is $2$. This means for the value of the game $v(A)$, that $1\leq v(A)\leq 2$.

For b) I find the following values: $v(A_1)=1\frac23, v(A_2)=3, v(A_3)=2\frac17, v(A_4)=1\frac35, v(A_5)=2, v(A_6)=2\frac29$. So this means that the values of $A_1, A_4$ and $A_5$ lie in the allowed range.

This is where I got stuck, so I calculated the value of the game via a different method and found that $v(A_4)$ is the correct answer. This got me to think about whether it would just be the minimum of these subgames. Hence, I tried the same for the matrices $\begin{pmatrix}1&1\\2&0\\0&2\end{pmatrix}$ (in which all subgames result in $1$, which is the value of the game) and $\begin{pmatrix}1&4&7\\5&3&0\end{pmatrix}$, but for the latter this strategy failed because the value of the game was lower than the minimum values of each of the subgames. (Which is what I expected to be a possibility.)

So this leaves me with the question: How can I answer question b without using the phrase "$A_4$ leads to the minimum expected value", or how do I prove that $v(A)\geq v(A_4)$ without first calculating $v(A)$?

You made a mistake, in the last scenario, the value of the game is $3.18182$, and that is also the value of the submatrix $\left(\matrix{1& 7\\5&0}\right)$. You can use this page to check your computations (simply type the entries separated by spaces, one line per row).

In fact, your conjecture is true:

From Shapley, L. S.; Snow, R. N. Basic solutions of discrete games. Contributions to the Theory of Games, pp. 27–35. Annals of Mathematics Studies, no. 24. Princeton University Press, Princeton, N. J., 1950.

Theorem. If the value of a matrix game is not zero, then it is equal to the smallest value of a square submatrix.

See The Probability that a Random Game is Unfair by Thomas M. Cover and references therein. The theorem is also mentioned in Game Theory, part II by Thomas S. Ferguson.