I need some help solving the value of this payoff matrix and finding the optimal strategy:
$$
\begin{matrix}
1 & 2 & 4 \\
-1 & 5 & 3 \\
3 & 3 & 2 \\
\end{matrix}
$$
So far I have written that the expected payoff of players are as follows:
$$ E(P_1)=p_1+2p_2+4p_3\\
E(P_2)=-p_1+5p_2+3p_3\\
E(P_3)=3p_1+3p_2+2p_3
$$
Our job is to maximize the minimum of ${ E(P_1), E(P_2), E(P_3)}$ and the sum of all $p_i$ should equal to 1 and lie in [0,1]. I tried putting using the sum of all $p_i$ to solve for the system of equations above but I am getting numbers like 3 for $p_1$ which is clearly not in [0,1]. How would you solve this by hand without using a computer?
Best Answer
The solution is the row-selector, trying to maximize the value V, chooses row 1 25% of the time and row 3 75% of the time. The column-selector, trying to minimize V, chooses column 1 half the time and column 3 half the time.
The value of the game (assuming the row selector is trying to maximize) is 5/2.
Your equations miss the point: the right equations to use are of the form (for example) of $$ V \leq P_1 - P_2 + 3P_3 $$ $$ V \leq -P_1 +5 P_2 + 3P_3 $$ $$ V \leq 4P_1 +3 P_2 + 2P_3 $$ $$ P_1 + P_2 + P_3 = 1 $$ and maximize V subject to all variables $P_i \geq 0$.
For this specific game, you can immediately tell that the second column is dominated by the first, and after eliminating the second column, that the second row is dominated by the first, leaving a 2x2 game with the solution as given.
Although the general way to solve such games is the simplex method, and that actually is not too ugly to do for a 3x3 game matrix, my mantra when given a 3x3 game is:
Form, for the rows, two extra twos consisting of the top row minus the second, then top minus the third. Among those two rows, write the determinant of the (1,2) columns square matrix under the third column, the determinant of the (2,3) square under the first column, and the determinant of the (3,1) column square under the second column.
Then do the same for the columns, subtracting columns 2 and 3 from the first. $$ \begin{array}{c c c | c c | c} 1 & 2 & 4 & -1 & -3 & -6 \\ -1 & 5 & 3 & -6 & -4 & +1 \\ 3 & 3 & 2 & 0 & 1 & -14 \\ \hline 2 & -3 & 1 & & & \\ -2 & -1 & 2 & & & \\ \hline -5 & -6 & -8 & & & \end{array} $$
If the answers for the rows are all the same sign, and the answers for the columns are all the same sign, then the game solution requires use of all three rows and all three columns, and you read off the strategies as the ratios of the numbers you just found. But in this case, that does not work because the column numbers are -6, +1, and -14. That means that the correct solution will use fewer than three rows.
Try eliminating one row and solving the resulting 2x3 game: First you might try eliminating row 1. But the solution to that game (of value 11/5) has the column chooser selecting column 3 80% of the time and column 1 20%; clearly the row chooser can do better than 11/5 by picking row 1.
When we eliminate row 2, we get the right solution, which is the solution presented above. It is easy to check that neither player can improve his result by choosing one of the eliminated choices.
In some rare cases, you have a situation where there are a family of correct solutions, but each member of the family requires a mix of all 3 rows (or columns) while the strategy for the other player is always the same ratio of only two of the columns (or rows). This makes the solution less obvious, although the simplex method always works. I may present such a game as a problem on this site at a later date.