Algebraic Method to solve a game-examples

## Algebraic Method to solve a game

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.

## Algebraic method to solve game Example 1

Solve the following $2\times 2$ game. The payoff matrix is given for player A as follows:

PlayerA \ Player B | $B_1$ | $B_2$ |
---|---|---|

$A_1$ | 4 | 1 |

$A_2$ | 2 | 3 |

#### Solution

We have two players A and B. Player A has two strategies and player B also has two strategies.

B1 | B2 | |
---|---|---|

A1 | 4 | 1 |

A2 | 2 | 3 |

Since the game is $2 \times 2$, let us apply **Maximin-Minimax** principle to check if there exists a saddle point.

#### 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*} $$ `

B1 | B2 | RowMin | |
---|---|---|---|

A1 | 4 | 1 | 1 |

A2 | 2 | 3 | 2 |

#### 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*} $$ `

B1 | B2 | RowMin | |
---|---|---|---|

A1 | 4 | 1 | 1 |

A2 | 2 | 3 | 2 |

ColMax | 4 | 3 |

#### 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*} $$ `

Thus $Max(min) = Max(1, 2)=2$

#### 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*} $$ `

Thus $Min(max)=Min(4, 3)=3$.

#### Step 5

$Max(min) =2$ and $Min(max)=3$. Since the $Max(min)\neq Min(max)$ for the game, the game has no saddle point.

Hence the optimal strategies for the given game can be obtained by the algebraic method.

` $$ \begin{aligned} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ &=\frac{3-2}{(4+3)-(1+2)}\\ &=\frac{1}{4}\\ p_2 &= 1-p_1\\ &=\frac{3}{4} \end{aligned} $$ `

and the optimal strategies for player B can be determined by

` $$ \begin{aligned} q_1 &= \frac{d-b}{(a+d)-(b+c)}\\ &=\frac{3-1}{(4+3)-(1+2)}\\ &=\frac{2}{4}=\frac{1}{2}\\ q_2 &= 1-q_1\\ &=\frac{1}{2}. \end{aligned} $$ `

The optimal strategies for player A can be written as

` $$ \begin{aligned} S_{A} &= \begin{bmatrix} A_1 & A_2\\ p_1 & p_2 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2\\ \frac{1}{4} & \frac{3}{4} \end{bmatrix} \end{aligned} $$ `

and the optimal strategies for player B can be written as

` $$ \begin{aligned} S_{B} &= \begin{bmatrix} B_1 & B_2\\ q_1 & q_2 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2\\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \end{aligned} $$ `

And the value of the game for player A is given by

` $$ \begin{aligned} V &= \frac{ad-bc}{(a+d)-(b+c)}\\ &=\frac{(4)(3)-(1)(2)}{(4+3)-(2+1)}\\ &=\frac{10}{4}=\frac{5}{2}. \end{aligned} $$ `

Thus, we conclude that player $A$ may choose strategy $A_1$ with probability $\dfrac{1}{4}$ and strategy $A_2$ with probability $\dfrac{3}{4}$. Player $B$ may choose strategy $B_1$ with probability $\dfrac{1}{2}$ and strategy $B_2$ with probability $\dfrac{1}{2}$. And value of the game for player A is $\dfrac{5}{2}$ and for player B is $-\dfrac{5}{2}$.

## Algebraic method to solve game Example 2

Solve the following $3\times 3$ game. The payoff matrix for player A is as follows:

PlayerA \ Player B | $B_1$ | $B_2$ | $B_3$ |
---|---|---|---|

$A_1$ | -5 | 10 | 20 |

$A_2$ | 5 | -10 | -10 |

$A_3$ | 5 | -20 | -20 |

#### Solution

We have two players A and B. Player A has three strategies and player B also has three strategies.

B1 | B2 | B3 | |
---|---|---|---|

A1 | -5 | 10 | 20 |

A2 | 5 | -10 | -10 |

A3 | 5 | -20 | -20 |

Since the game is $3 \times 3$, let us apply **Maximin-Minimax** principle to check if there exists a saddle point.

#### 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*} $$ `

B1 | B2 | B3 | RowMin | |
---|---|---|---|---|

A1 | -5 | 10 | 20 | -5 |

A2 | 5 | -10 | -10 | -10 |

A3 | 5 | -20 | -20 | -20 |

#### 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*} $$ `

B1 | B2 | B3 | RowMin | |
---|---|---|---|---|

A1 | -5 | 10 | 20 | -5 |

A2 | 5 | -10 | -10 | -10 |

A3 | 5 | -20 | -20 | -20 |

ColMax | 5 | 10 | 20 |

#### 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*} $$ `

Thus $Max(min) = Max(-5, -10, -20)=-5$

#### 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*} $$ `

Thus $Min(max)=Min(5, 10, 20)=5$.

#### Step 5

$Max(min) =-5$ and $Min(max)=5$. Since the $Max(min)\neq Min(max)$ for the game, the game has no saddle point.

Thus we reduce the size of pay-off matrix using **dominance property**.

As every element of $3^{rd}$ column ($B_3$) $\geq$ every element of $2^{nd}$ column ($B_2$), the $3^{rd}$ strategy of player B is dominated. (i.e. strategy $B_3$ is inferior to strategy $B_2$). Hence deleting $B_3$, the reduced game is

Player A \ Player B | $B_1$ | $B_2$ | Min |
---|---|---|---|

$A_1$ | -5 | 10 | -5 |

$A_2$ | 5 | -10 | -10 |

$A_3$ | 5 | -20 | -20 |

Max | 5 | 10 |

Apply the Maximin-minimax principle on the reduced game. We have $Max(min) = max(-5,-10,-20)=-5$ and $Min(max)=min(5,10)=5$. Since the $Max(min)\neq min(max)$ for the reduced game, the game has no saddle point.

As every element of $3^{rd}$ row ($A_3$) $\leq$ every element of $2^{nd}$ row ($A_2$), the $3^{rd}$ strategy of player A is dominated. (i.e strategy $A_3$ is inferior to $A_2$). Hence deleting $A_3$, the reduced game is

Player A \ Player B | $B_1$ | $B_2$ | Min |
---|---|---|---|

$A_1$ | -5 | 10 | -5 |

$A_2$ | 5 | -10 | -10 |

Max | 5 | 10 |

Apply the Maximin-minimax principle on the reduced game. We have $Max(min) = max(-5,-10)=-5$ and $Min(max)=min(5,10)=5$. Since the $Max(min)\neq min(max)$ for the reduced game, the game has no saddle point.

Hence the optimal strategies can be obtained by the algebraic method.

Comparing the reduced game with

Player A \ Player B | $B_1$ | $B_2$ |
---|---|---|

$A_1$ | $a$ | $b$ |

$A_2$ | $c$ | $d$ |

The optimal strategy for player $A$ can be determined as

` $$ \begin{aligned} p_1 &=\frac{d-c}{(a+d)-(b+c)}\\ &=\frac{(-10)-5}{(-5)+(-10)-(10+5)}\\ &=\frac{1}{2}\\ p_2 &= 1-p_1\\ &=\frac{1}{2} \end{aligned} $$ `

and the optimal strategies for player B can be determined by

` $$ \begin{aligned} q_1 &= \frac{d-b}{(a+d)-(b+c)}\\ &=\frac{(-10)-10}{(-5)+(-10)-(10+5)}\\ &=\frac{2}{3}\\ q_2 &= 1-q_1\\ &=\frac{1}{3}. \end{aligned} $$ `

The optimal strategies for player A can be written as

` $$ \begin{aligned} S_{A} &= \begin{bmatrix} A_1 & A_2\\ p_1 & p_2 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2\\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \end{aligned} $$ `

and the optimal strategies for player B can be written as

` $$ \begin{aligned} S_{B} &= \begin{bmatrix} B_1 & B_2\\ q_1 & q_2 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2\\ \frac{2}{3} & \frac{1}{3} \end{bmatrix} \end{aligned} $$ `

And the value of the game for player A is given by

` $$ \begin{aligned} V &= \frac{ad-bc}{(a+d)-(b+c)}\\ &=\frac{(-5)(-10)-(10)(5)}{((-5)+(-10))-(10+5)}\\ &=0. \end{aligned} $$ `

Thus, we conclude that player $A$ may choose strategy $A_1$ and $A_2$ with probability $\dfrac{1}{2}$ each and will never choose $A_3$. Player $B$ may choose strategy $B_1$ with probability $\dfrac{2}{3}$ and strategy $B_2$ with probability $\dfrac{1}{3}$, while he never choose strategy $B_3$. And since value of the game is zero, the game will end in a draw.

## Endnote

In this tutorial, you learned about how to solve 2 by 2 or m by n game by algebraic method.

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 **Examples on Algebraic method to solve game** and your thought on this article.