I'm stuck with understanding the way of finding mixed strategy Nash equilibrium for non-square matrices and want to explain my difficulties with the help of the following example.
Let the following table describe a strictly competitive game:
\begin{matrix}
& B_1 & B_2 \\
A_1 & 7 & -1 \\
A_2 & 5 & 4 \\
A_3 & 1 & 5 \\
A_4 & 3 & -2 \\
A_5 & 2 & 1
\end{matrix}
Matrix cells contain player $A$ payoffs $u_1(A_i, B_j)$ which are opposite to player $B$ payoffs $u_2(A_i, B_j)$ for each eligible pair $(i, j)$.
I have to find a Nash equilibrium for this game, so firstly I tried to find it in pure strategies. The following figure shows the best responses for player $A$:
\begin{matrix}
& B_1 & B_2 \\
A_1 & \underline{7} & -1 \\
A_2 & 5 & 4 \\
A_3 & 1 & \underline{5} \\
A_4 & 3 & -2 \\
A_5 & 2 & 1
\end{matrix}
and player $B$:
\begin{matrix}
& B_1 & B_2 \\
A_1 & 7 & -\underline{1} \\
A_2 & 5 & \underline{4} \\
A_3 & \underline{1} & 5 \\
A_4 & 3 & -\underline{2} \\
A_5 & 2 & \underline{1}
\end{matrix}
(remember that player $A$ tends to choose a maximum value from each column, while player $B$ – the minimum from each row).
As we have no profile (pair of some $A_i$ and $B_j$) which is the best response for both players, this problem has no solution in pure strategies (correct me if I'm wrong).
Thus, we have to look for some mixed strategy. First of all, I remove rows $4$ and $5$, as options $A_4$ and $A_5$ always give less payoff for player $A$ than the option $A_2$.
After that we have the following matrix which can't be simplified by the same way (removing majorated rows or minorated columns):
\begin{matrix}
& B_1 & B_2 \\
A_1 & 7 & -1 \\
A_2 & 5 & 4 \\
A_3 & 1 & 5 \\
\end{matrix}
Let $\alpha_i$ and $\beta_j$ be the probabilities of choosing option $A_i$ by player $A$ and option $B_j$ by player $B$ correspondently. There is a theorem that states:
Every action in the support of any player's equilibrium mixed strategy yields that player the same payoff.
For player $A$ it means:
$A_1$ payoff: $7\beta_1 – \beta_2$
$A_2$ payoff: $5\beta_1 + 4\beta_2$
$A_3$ payoff: $\beta_1 + 5\beta_2$
and all these expressions should be equal to each other.
Substituting $\beta_2 = 1 – \beta_1$, we got:
$$8\beta_1 – 1 = \beta_1 + 4 = 5 – 4\beta_1$$
This system obviously has no solutions, as equating the first expression to the second we get $\beta_1 = \frac{5}{7}$, the second to the third – $\beta_1 = \frac{1}{5}$, the first to the third – $\beta_1 = \frac{1}{2}$.
I wouldn't like to go on with my reasoning, as I wasn't able to find $\beta_1$ from these equations and so far I can't find a mixed equilibrium.
What am I doing wrong? Thanks in advance for help.
Best Answer
Firstly, as you noted that game has no equilibrium in pure strategies.
It is then true that because player II has only two pure strategies that there must be an equilibrium where both players have support size 2 (if the game was degenerate there could be other types of equilibria too, but it turns out not to be degenerate, i.e. for every mixed strategy with support size $k$ there are at most $k$ best responses; thus, because the game is non-degenerate and zero-sum, there is a unique equilibrium where both players play exactly two strategies).
Which supports of player I are candidate supports? Well we only need to consider $2 \times 2$ sub-games with "cyclic preferences", since only these can allow to make the other player indifferent.
The only two possibilities for player I's supports are $A_1,A_3$ and $A_2,A_3$ (for $A_1,A_2$ we see that player II prefers $B_2$ against both rows and so cannot be made indifferent).
Now we try both. Since the game is zero-sum and non-degenerate we know that in one case, even though we can find probabilities for player II to make player I indifferent between the two strategies, the third will give a better payoff (which happens for $A_1,A_3$).
So, it turns out that the unique equilibrium is for player I to play $A_1,A_2,A_3$ with probabilities $0,0.8,0.2$ and player II to play $0.2,0.8$. Against player II's strategy, player I gets the same, best payoff for $A_2$ and $A_3$ as required.
For $2 \times n$ or $n \times 2$ games (even non-zero sum games) it is easy to analyse them with a diagram of best responses plotted against the mixed strategies of the player with two strategies. See my answer here
Mixed strategy nash equilibria in from $2\times N$ bimatrix form
Also check out our online game solvers:
http://banach.lse.ac.uk/
and
http://gte.csc.liv.ac.uk/gte/builder/