Algebraic Method To Solve 2 by 2 or m by n Game

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.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.

Leave a Comment