Graphical method to solve $2\times n$ game
A game where one player has only two course of action and the other player has more than two (say $n$) course of action is called $2\times n$ 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 $2\times n$ game or a game reducible to $2\times n$ after applying dominance property.
Step by Step Procedure to solve 2 by n game
Consider the $2\times n$ game. In this game player $A$ has $2$ strategies and player $B$ has $n$ strategies. Assume that the game does not have a saddle point.
| Player A \ Player B | $B_1$ | $B_2$ | $\cdots$ | $B_n$ |
|---|---|---|---|---|
| $A_1$ | $a_{11}$ | $a_{12}$ | $\cdots$ | $a_{1n}$ |
| $A_2$ | $a_{21}$ | $a_{22}$ | $\cdots$ | $a_{2n}$ |
Following are the steps to solve $2\times n$ game using graphical method.
Step 1
Apply maximin-minimax principle to check whether saddle point exists or not. If saddle point exists, then stop the method and calculate the value of the game, otherwise go to next step.
Step 2
Construct two vertical axis, axis 1 and axis 2, using appropriate scales.
Axis 1 represent the payoff values of $A_2$ strategy for player $A$ and axis 2 represent payoff values of $A_1$ strategy for player $A$.
(Graph is just a sample.)
Step 3
Joint the point representing $a_{1j}$ on axis 2 to the point representing $a_{2j}$ on axis 1 for all $j = 1, 2,\cdots,n$. (Graph is just a sample.)
Step 4
Mark the lowest boundary (called Lower envelope) of the lines by thick line segment. The highest point on the lower envelope gives the maximin point $P$ and it identifies the two critical moves (strategies) of player $B$.
Suppose the lower envelope is created by $B_1$ and $B_n$ strategy. The highest point on the lower envelope gives the maximin point. This shows that the two critical moves for player $B$ are $B_1$ and $B_n$.
Using the above selection the reduced game becomes
| Player A \ Player B | $B_1$ | $B_n$ |
|---|---|---|
| $A_1$ | $a_{11}$ | $a_{1n}$ |
| $A_2$ | $a_{21}$ | $a_{2n}$ |
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.)
2 by n game by graphical method Example 1
Solve the game with the following payoff for player A.
| Player A \ Player B | $B_1$ | $B_2$ | $B_3$ | $B_4$ |
|---|---|---|---|---|
| $A_1$ | 1 | 3 | -3 | 5 |
| $A_2$ | 2 | 5 | 4 | -4 |
Solution
Given game is $2\times 4$. That is for Player $A$ has two strategies and player $B$ has four strategies. Let us check using maximin-minimax principle whether the game has a saddle point or not.
| B1 | B2 | B3 | B4 | |
|---|---|---|---|---|
| A1 | 1 | 3 | -3 | 5 |
| A2 | 2 | 5 | 4 | -4 |
Step 1
Apply maximin-minimax principle to check whether saddle point exists or not.
| B1 | B2 | B3 | B4 | RowMin | |
|---|---|---|---|---|---|
| A1 | 1 | 3 | -3 | 5 | -3 |
| A2 | 2 | 5 | 4 | -4 | -4 |
| ColMax | 2 | 5 | 4 | 5 |
Thus $Max(min) = Max(-3, -4)=-3$ and $Min(max)=Min(2, 5, 4, 5)=2$. Since the $Max(min)\neq Min(max)$ for the game, the game has no saddle point.
Step 2
Construct two vertical axis, axis 1 and axis 2.
Axis 1 represent the payoff values of $A_2$ strategy for player $A$ and axis 2 represent payoff values of $A_1$ strategy for player $A$.
Let the player $A$ play the strategy $A_1$ with probability $p$ and strategy $A_2$ with probability $1-p$.
Expected payoff for player $A$ for any pure strategy of player $B$ would be given by
| $B$'s Strategy | Expected Payoff for $A$ |
|---|---|
| $B_1$ | $E_1= p+2(1-p) = -p+2$ |
| $B_2$ | $E_2= 3p+5(1-p)=-2p+5$ |
| $B_3$ | $E_3= -3p+4(1-p)=-7p+4$ |
| $B_4$ | $E_4= 5p-4(1-p)= 9p-4$ |
Step 3
Joint the point representing $a_{1j}$ on axis 2 to the point representing $a_{2j}$ on axis 1 for all $j = 1, 2,3$.
Step 4
Mark the lowest boundary (called Lower envelope) of the lines by thick line segment. The highest point on the lower envelope gives the maximin point $P$ and it identifies the two critical moves (strategies) of player $B$.
The two critical moves for player $B$ are $B_3$ and $B_4$.
The highest point $P$ on the lower envelope gives the maximin point.
Step 5
The reduced game (i.e. $2\times 2$) is
| Player A \ Player B | $B_3$ | $B_4$ |
|---|---|---|
| $A_1$ | -3 | 5 |
| $A_2$ | 4 | -4 |
Apply maximin criterion.
| B3 | B4 | |
|---|---|---|
| A1 | -3 | 5 |
| A2 | 4 | -4 |
- 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*} $$
| B3 | B4 | RowMin | |
|---|---|---|---|
| A1 | -3 | 5 | -3 |
| A2 | 4 | -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*} $$
| B3 | B4 | RowMin | |
|---|---|---|---|
| A1 | -3 | 5 | -3 |
| A2 | 4 | -4 | -4 |
| ColMax | 4 | 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(-3, -4)=-3$
- 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(4, 5)=4$.
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)-4}{(-3-4)-(5+4))}\\ &=\frac{-8}{-16}\\ &=\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{(-4)-5}{(-3-4)-(5+4)}\\ &=\frac{-9}{-16}\\ &=\frac{9}{16}\\ q_2 &= 1-q_1\\ &=\frac{7}{16}. \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 & B_3 & B_4\\ 0 & 0 & q_1 & q_2 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3 & B_4\\ 0 & 0 & \frac{9}{16} & \frac{7}{16} \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{(-3)(-4)-(5)(4)}{(-3-4)-(5+4)} \\ &=\frac{-8}{-16}\\ &=\frac{1}{2}. \end{aligned} $$
Thus, we conclude that player $A$ may choose strategy $A_1$ with probability $\dfrac{1}{2}$ and strategy $A_2$ with probability $\dfrac{1}{2}$. Player $B$ may choose strategy $B_3$ with probability $\dfrac{9}{16}$ and strategy $B_4$ with probability $\dfrac{7}{16}$. And value of the game for player A is $\dfrac{1}{2}$ and for player B is $-\dfrac{1}{2}$.
2 by n game by graphical method Example 2
Solve the game with the following payoff for player A.
| Player A \ Player B | $B_1$ | $B_2$ | $B_3$ |
|---|---|---|---|
| $A_1$ | 1 | 3 | 10 |
| $A_2$ | 8 | 6 | 2 |
Solution
Given game is $2\times 3$. That is for Player $A$ has two strategies and player $B$ has three strategies. Let us check using maximin-minimax principle whether the game has a saddle point or not.
| B1 | B2 | B3 | |
|---|---|---|---|
| A1 | 1 | 3 | 10 |
| A2 | 8 | 6 | 2 |
Step 1
Apply maximin-minimax principle to check whether saddle point exists or not.
| B1 | B2 | B3 | RowMin | |
|---|---|---|---|---|
| A1 | 1 | 3 | 10 | 1 |
| A2 | 8 | 6 | 2 | 2 |
| ColMax | 8 | 6 | 10 |
Thus $Max(min) = Max(1, 2, )=2$ and $Min(max)=Min(8, 6, 10)=6$. Since the $Max(min)\neq Min(max)$ for the game, the game has no saddle point.
Step 2
Construct two vertical axis, axis 1 and axis 2.
Axis 1 represent the payoff values of $A_2$ strategies for player $A$ and axis 2 represent payoff values of $A_1$ strategies for player $A$.
Step 3
Joint the point representing $a_{1j}$ on axis 2 to the point representing $a_{2j}$ on axis 1 for all $j = 1, 2,\cdots,n$.
Let the player $A$ play the strategy $A_1$ with probability $p$ and strategy $A_2$ with probability $1-p$.
Expected payoff for player $A$ for any pure strategy of player $B$ would be given by
| $B$'s Strategy | Expected Payoff for $A$ |
|---|---|
| $B_1$ | $E_1= p+8(1-p) = -7p+8$ |
| $B_2$ | $E_2= 3p+6(1-p)=-3p+6$ |
| $B_3$ | $E_3= 10p+2(1-p)=8p+2$ |
Step 4
Mark the lowest boundary (called Lower envelope) of the lines by thick line segment. The highest point on the lower envelope gives the maximin point $P$ and it identifies the two critical moves (strategies) of player $B$.
The two critical moves for player $B$ are $B_2$ and $B_3$.
The highest point $P$ on the lower envelope gives the maximin point.
Step 5
The reduced game (i.e. $2\times 2$) is
| Player A \ Player B | $B_2$ | $B_3$ |
|---|---|---|
| $A_1$ | 3 | 10 |
| $A_2$ | 6 | 2 |
Apply maximin criterion.
| B2 | B3 | |
|---|---|---|
| A1 | 3 | 10 |
| A2 | 6 | 2 |
- 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*} $$
| B2 | B3 | RowMin | |
|---|---|---|---|
| A1 | 3 | 10 | 3 |
| A2 | 6 | 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*} $$
| B2 | B3 | RowMin | |
|---|---|---|---|
| A1 | 3 | 10 | 3 |
| A2 | 6 | 2 | 2 |
| ColMax | 6 | 10 |
- 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(3, 2)=3$
- 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(6, 10)=6$.
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-6}{(3+2)-(10+6)}\\ &=\frac{-4}{-11}\\ &=\frac{4}{11}\\ p_2 &= 1-p_1\\ &=\frac{7}{11} \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-10}{(3+2)-(10+6)}\\ &=\frac{-8}{-11}\\ &=\frac{8}{11}\\ q_2 &= 1-q_1\\ &=\frac{3}{11}. \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{4}{11} &\frac{7}{11} \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 & B_3\\ 0 & q_1 & q_2 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3\\ 0 & \frac{8}{11} & \frac{3}{11} \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{(3)(2)-(10)(6)}{(3+2)-(10+6)} \\ &=\frac{-54}{-11}\\ &=4.9091. \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{8}{11}$ and strategy $B_2$ with probability $\dfrac{3}{11}$. And value of the game for player A is $4.9091$ and for player B is $-4.9091$.
Endnote
In this tutorial, you learned about graphical method to solve $2\times n$ game and how to use graphical method to solve $2\times n$ game with illustrated examples.
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 $2\times n$ game and your thought on this article.
