Graphical Method to solve m by 2 game

Graphical method to solve $m\times 2$ game

A game where one player has more than $m$ course of action and the other player has only two course of action is called $m\times 2$ game.

Graphical method can be used to solve a $2\times n$ or $m\times 2$ game or a game reducible to either $2\times n$ or $m\times 2$ after applying a dominance property.

In this tutorial we will discuss about the graphical method to solve a $m\times 2$ game or a game reducible to $m\times 2$ after applying dominance property.

Step by Step Procedure to solve m by 2 game

Consider the $m\times 2$ game. In this game player $A$ has $m$ strategies and player $B$ has $2$ strategies. Assume that the game does not have a saddle point.

Player A \ Player B $B_1$ $B_2$
$A_1$ $a_{11}$ $a_{12}$
$A_2$ $a_{21}$ $a_{22}$
$\vdots$ $\vdots$ $\vdots$
$A_m$ $a_{m1}$ $a_{m2}$

Following are the steps to solve $m\times 2$ game using graphical method.

Step 1

Construct two vertical axis, axis 1 and axis 2, by taking suitable scale. (Graph is just a sample)

m by 2 game
m by 2 game

Step 2

Axis 1 represent the payoff values of $B_2$ strategy for player $B$ and axis 2 represent payoff values of $B_1$ strategy for player $B$.

Step 3

Joint the point representing $a_{i1}$ on axis 2 to the point representing $a_{i2}$ on axis 1 for all $i = 1, 2,\cdots,m$. (Graph is just a sample)

m by 2 game
m by 2 game

Step 4

Mark the upper boundary (called upper envelope) of the lines by thick line segment. The lowest point on the upper envelope gives the minimax point $P$ and it identifies the two critical moves (strategies) of player $A$.

Suppose the upper envelope is created by $A_1$ and $A_m$ strategy. The lowest point on the upper envelope gives the minimax point. This shows that the two critical moves for player $A$ are $A_1$ and $A_m$.

Using the above selection the reduced game becomes

Player A \ Player B $B_1$ $B_2$
$A_1$ $a_{11}$ $a_{12}$
$A_m$ $a_{m1}$ $a_{m2}$
m by 2 game
m by 2 game

Step 5

Solve the reduced game (i.e. $2\times 2$) using maximin criterion. (if saddle point exists then find the value of the game otherwise use mixed strategy technique to find the value of the game.)

m by 2 game by graphical method Example 1

Solve the game with the following payoff for player A.

Player A / Player B $B_1$ $B_2$
$A_1$ -2 5
$A_2$ -5 3
$A_3$ 0 -2
$A_4$ -3 0
$A_5$ 1 -4

Solution

Given game is $5\times 2$. That is for Player $A$ has five strategies and player $B$ has two strategies. Let us check using maximin-minimax principle whether the game has a saddle point or not.

B1 B2
A1 -2 5
A2 -5 3
A3 0 -2
A4 -3 0
A5 -1 -4

Step 1

Apply maximin-minimax principle to check whether saddle point exists or not.

B1 B2 RowMin
A1 -2 5 -2
A2 -5 3 -5
A3 0 -2 -2
A4 -3 0 -3
A5 -1 -4 -4
ColMax 0 5

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

Step 2

Draw two vertical axis, axis 1 and axis 2. Mark appropriate scale on each axis. The two axis represents strategies for player B. Axis 1 represent the payoff values of $B_2$ strategy for player $B$ and axis 2 represent payoff values of $B_1$ strategy for player $B$.

m by 2 game
m by 2 game

Let the player B play the strategy $B_1$ with probability $q$ and strategy $B_2$ with probability $1-q$.

Expected payoff for player B for any pure strategy of player A would be given by

A's Strategy Expected Payoff for B
$A_1$ $E_1=-2q+5(1-q) = 7q+5$
$A_2$ $E_2=-5q+3(1-q)=-8q+3$
$A_3$ $E_3 = 0q+(-2)(1-q)=2q-2$
$A_4$ $E_4=-3q+0(1-q)= -3q$
$A_5$ $E_5 = -1q+(-4)(1-q)=3q-4$

Step 3

Draw the graph of expected payoff $E_1,E_2,E_3, E_4, E_5$ against $q$

Joint the point representing $a_{i1}$ on axis 2 to the point representing $a_{i2}$ on axis 1 for all $i = 1, 2,\cdots,m$.

m by 2 game
m by 2 game

Step 4

Mark the upper boundary (called upper envelope) of the lines by thick line segment. The lowest point on the upper envelope gives the minimax point $P$.

m by 2 game
m by 2 game

The upper envelope is created by $A_1$ and $A_5$ strategy.

The two critical moves (strategies) of player $A$ are $A_1$ and $A_5$.

The lowest point $P$ on the upper envelope gives the minimax point.

Step 5

The reduced game (i.e. $2\times 2$) is

Player A / Player B $B_1$ $B_2$
$A_1$ -2 5
$A_5$ 1 -4

Apply maximin-minimax principle on the reduced $2\times 2$ game.

B1 B2
A1 -2 5
A5 1 -4

For each row of the payoff matrix, select the minimum element and call it RowMin.

$$ \begin{equation*} \text{i.e., } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{equation*} $$

B1 B2 RowMin
A1 -2 5 -2
A5 1 -4 -4

For each column of the payoff matrix, select the maximum element and call it ColMax.

$$ \begin{equation*} \text{i.e., } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$

B1 B2 RowMin
A1 -2 5 -2
A5 1 -4 -4
ColMax 1 5

From each RowMin, obtain the maximum value, i.e., $Max(RowMin)$.

$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$

Thus $Max(min) = Max(-2, -4)=-2$

For each ColMax, obtain the minimum value, i.e. $Min(ColMax)$.

$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$

Thus $Min(max)=Min(1, 5)= 1$.

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

Hence the optimal strategy for the reduced game can be obtained by algebraic method.

$$ \begin{aligned} p_1 &=\frac{d-c}{(a+d)-(b+c)}\\ &=\frac{(-4)-1}{(-2)+(-4)-(5+1)}\\ &=\frac{5}{12}\\ p_2 &= 1-p_1\\ &=\frac{7}{12} \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{(-4)-5}{(-2) +(-4) -(5+1)}\\ &=\frac{9}{12}=\frac{3}{4}\\ q_2 &= 1-q_1\\ &=\frac{1}{4}. \end{aligned} $$

The optimal strategies for player A can be written as

$$ \begin{aligned} S_{A} &= \begin{bmatrix} A_1 & A_2 & A_3 & A_4 & A_5\\ p_1 & 0 & 0 & 0 & p_2 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2 & A_3 & A_4 & A_5\\ \frac{5}{12} & 0 & 0 & 0 & \frac{7}{12} \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{3}{4} & \frac{1}{4} \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{(-2)(-4)-(5)(1)}{(-2)+(-4)-(5+1)}\\ &=\frac{3}{12}=\frac{1}{4}. \end{aligned} $$

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

m by 2 game by graphical method Example 2

Solve the game with the following payoff for player A.

Player A / Player B $B_1$ $B_2$
$A_1$ 2 4
$A_2$ 2 3
$A_3$ 3 2
$A_4$ -2 6

Solution

Given game is $4\times 2$. That is for Player $A$ has four strategies and player $B$ has two strategies. Let us check using maximin-minimax principle whether the game has a saddle point or not.

B1 B2
A1 2 4
A2 2 3
A3 3 2
A4 -2 6

Step 1

Apply maximin-minimax principle to check whether saddle point exists or not.

B1 B2 RowMin
A1 2 4 2
A2 2 3 2
A3 3 2 2
A4 -2 6 -2
ColMax 3 6

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

Step 2

Draw two vertical axis, axis 1 and axis 2. Mark appropriate scale on each axis. The two axis represents strategies for player B. Axis 1 represent the payoff values of $B_2$ strategy for player $B$ and axis 2 represent payoff values of $B_1$ strategy for player $B$.

m by 2 game
m by 2 game

Let the player B play the strategy $B_1$ with probability $q$ and strategy $B_2$ with probability $1-q$.

Expected payoff for player B for any pure strategy of player A would be given by

A's Strategy Expected Payoff for B
$A_1$ $E_1= 2q+4(1-q) = -2q+4$
$A_2$ $E_2= 2q+3(1-q)=-q+3$
$A_3$ $E_3= 3q+2(1-q)=q+2$
$A_4$ $E_4=-2q+6(1-q)= -8q+6$

Step 3

Draw the graph of expected payoff $E_1,E_2,E_3, E_4$ against $q$

Joint the point representing $a_{i1}$ on axis 2 to the point representing $a_{i2}$ on axis 1 for all $i = 1, 2,\cdots,m$.

m by 2 game
m by 2 game

Step 4

Mark the upper boundary (called upper envelope) of the lines by thick line segment. The lowest point on the upper envelope gives the minimax point $P$.

m by 2 game
m by 2 game

The upper envelope is created by $A_1$ and $A_3$ strategy.

The two critical moves (strategies) of player $A$ are $A_1$ and $A_3$.

The lowest point $P$ on the upper envelope gives the minimax point.

Step 5

The reduced game (i.e. $2\times 2$) is

Player A / Player B $B_1$ $B_2$
$A_1$ 2 4
$A_3$ 3 2

Apply maximin-minimax principle on the reduced $2\times 2$ game.

B1 B2
A1 2 4
A3 3 2

For each row of the payoff matrix, select the minimum element and call it RowMin.

$$ \begin{equation*} \text{i.e., } \min_{j} a_{ij}, i=1,2,\cdots, m. \end{equation*} $$

B1 B2 RowMin
A1 2 4 2
A3 3 2 2

For each column of the payoff matrix, select the maximum element and call it ColMax.

$$ \begin{equation*} \text{i.e., } \max_{i} a_{ij}, j=1,2,\cdots, n. \end{equation*} $$

B1 B2 RowMin
A1 2 4 2
A3 3 2 2
ColMax 3 4

From each RowMin, obtain the maximum value, i.e., $Max(RowMin)$.

$$ \begin{equation*} \text{i.e., } \max_{i}\min_{j} a_{ij}=\underline{v}. \end{equation*} $$

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

For each ColMax, obtain the minimum value, i.e. $Min(ColMax)$.

$$ \begin{equation*} \text{i.e., } \min_{j}\max_{i} a_{ij}=\overline{v}. \end{equation*} $$

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

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

Hence the optimal strategy for the reduced game can be obtained by algebraic method.

$$ \begin{aligned} p_1 &=\frac{d-c}{(a+d)-(b+c)}\\ &=\frac{2-3}{(2+2)-(4+3)}\\ &=\frac{-1}{-3}\\ &=\frac{1}{3}\\ p_2 &= 1-p_1\\ &=\frac{2}{3} \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{2-4}{(2+2)-(4+3)}\\ &=\frac{-2}{-3}\\ &=\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 & A_3 & A_4 \\ p_1 & 0 & p_2 & 0 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2 & A_3 & A_4 \\ \frac{1}{3} & 0 & \frac{2}{3} & 0 \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{2*2-4*3}{(2+2)-(4+3)}\\ &=\frac{-8}{-3}\\ &=\frac{8}{3}. \end{aligned} $$

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

Endnote

In this tutorial, you learned about graphical method to solve $m\times 2$ game and how to use graphical method to solve $m\times 2$ game with illustrated example.

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 Graphical method to solve $m\times 2$ 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