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.

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