In this article we will discuss about an algebraic method to solve by 2 or m by n game.
Algebraic method for 2 by 2 or m by n game
When pure strategies does not exists for a $2\times 2$ game or $m\times n$ game reducible to $2\times 2$, then algebraic method is used.
Thus algebraic method is used to solve the game under following situations:
- if the game is $2\times 2$ game and the game has no saddle point, or
- if the game is $m\times n$ game and the game has no saddle point and it can be reduced to $2\times 2$ game after applying dominance property.
Step by step procedure of algebraic method to solve game
For $m\times n$ or $2\times 2$ game, first apply 5 steps procedure of maximin-minimax principle.
Step 1
Select the minimum element of each row of the payoff matrix,
$$ \begin{equation*} \text{i.e., } \min_{j} \{ a_{ij} \}, i=1,2,\cdots, m. \end{equation*} $$
Step 2
Select the maximum element of each column of the payoff matrix,
$$ \begin{equation*} \text{i.e., } \max_{i} \{a_{ij}\}, j=1,2,\cdots, n. \end{equation*} $$
Step 3
Obtain the maximum value of each row minimum,
$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} \{a_{ij}\}=\underline{v}. \end{equation*} $$
Step 4
Obtain the minimum value of each column maximum,
$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} \{a_{ij}\}=\overline{v}. \end{equation*} $$
Step 5
-
Case I: If
$\min_{j}\max_{i} \{a_{ij}\}=\max_{i}\min_{j} \{a_{ij}\}=v$, i.e., $\max (\min) = \min (\max)$ then the position of that element is a saddle point of the payoff matrix. And the corresponding strategy is called optimal strategy. Stop the procedure. -
Case II: If
$\min_{j}\max_{i} \{a_{ij}\}\neq\max_{i}\min_{j} \{a_{ij}\}$, then the game has no saddle point. We can use mixed strategy to solve the game. If the game is $2\times 2$ then goto Step 7 Case I, otherwise Go to Step 6.
Step 6
Apply the dominance property to reduce the size of the game to $2\times 2$ or $2\times n$ or $m\times 2$.
If the game is reducible to $2\times 2$ then go to Step 7 Case II, otherwise use graphical method to solve $2\times n$ or $m\times 2$ game.
Step 7
Case I: The game is $2\times 2$ game.
player A's payoff matrix is
| Player A \ Player B | $B_1$ | $B_2$ |
|---|---|---|
| $A_1$ | $a$ | $b$ |
| $A_2$ | $c$ | $d$ |
the optimal strategies for player A can be determined by
$$ \begin{aligned} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ p_2 &= 1-p_1. \end{aligned} $$
and the optimal strategies for player B can be determined by
$$ \begin{aligned} q_1 &= \frac{d-b}{(a+d)-(b+c)}\\ q_2 &= 1-q_1. \end{aligned} $$
And the value of the game for player A is given by
$$ \begin{aligned} V &= \frac{ac-bd}{(a+d)-(b+c)} \end{aligned} $$
The optimal strategies for player A can be written as
$$ \begin{equation*} S_{A} = \begin{bmatrix} A_1 & A_2\\ p_1 & p_2 \end{bmatrix} \end{equation*} $$
and the optimal strategies for player B can be written as
$$ \begin{equation*} S_{B} = \begin{bmatrix} B_1 & B_2\\ q_1 & q_2 \end{bmatrix} \end{equation*} $$
Case II: After applying the dominance property, suppose the game is reduced to $2\times 2$. Suppose in the reduced game, player A's strategies are $A_i$ and $A_j$, and player B's strategies are $B_k$ and $B_l$, then
Reduced payoff matrix is
| Player A \ Player B | $B_k$ | $B_l$ |
|---|---|---|
| $A_i$ | $a$ | $b$ |
| $A_j$ | $c$ | $d$ |
the optimal strategies for player A can be determined by
$$ \begin{aligned} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ p_2 &= 1-p_1. \end{aligned} $$
and the optimal strategies for player B can be determined by
$$ \begin{aligned} q_1 &= \frac{d-b}{(a+d)-(b+c)}\\ q_2 &= 1-q_1. \end{aligned} $$
And the value of the game for player A is given by
$$ \begin{aligned} V &= \frac{ad-bc}{(a+d)-(b+c)} \end{aligned} $$
The optimal strategies for player A can be written as
$$ \begin{equation*} S_{A} = \begin{bmatrix} A_i & A_j\\ p_1 & p_2 \end{bmatrix} \end{equation*} $$
and the optimal strategies for player B can be written as
$$ \begin{equation*} S_{B} = \begin{bmatrix} B_k & B_l\\ q_1 & q_2 \end{bmatrix} \end{equation*} $$
Endnote
In this tutorial, you learned about the step by step procedure to use algebraic method to solve 2 by 2 or m by n game.
To learn more about different methods to solve a game please refer to the following tutorials:
Let me know in the comments if you have any questions on Algebraic method to solve game and your thought on this article.
