Home » Operations Research » Game Theory » Algebraic Method To Solve 2 by 2 or m by n Game

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.

Leave a Comment