In this tutorial we will discuss the dominance property and some examples based on the use of dominance property to solve the game.
Dominance Property
In some of the games, one pure strategy of a player is better or superior than another strategy (irrespective of the strategy used by the opponent player). In such a case one strategy is dominated by the other strategy. Such a property is called dominance property.
In such a case the redundant strategy (row or column) can be eliminated and the game size can be reduced. Thus from a game the inferior strategy may be simply ignored by assigning a zero probability while searching for optimal strategy.
Dominance property for rows
The dominance property for rows can be summarized as:
- If all entries in one row, say
$r^{th}$row of the payoff matrix is less than the corresponding entries in the other row, say$s^{th}$, then the player $A$ will never choose the$r^{th}$strategy. That is, if$a_{rj}< a_{sj}$for all $j = 1, 2,\cdots, n$, then the$r^{th}$strategy is said to be srictly dominated by the$s^{th}$strategy. In such situation the $r^{th}$ row of the payoff matrix can be deleted.
For example, suppose we have a 3 by 3 games
-
If all entries in one row, say
$r^{th}$row of the payoff matrix is less than or equal to the corresponding entries in the other row, say$s^{th}$, then the player $A$ will never choose the$r^{th}$strategy. That is, if$a_{rj}\leq a_{sj}$for all $j = 1, 2,\cdots, n$, then the$r^{th}$strategy is said to be weakly dominated by the$s^{th}$strategy. In such situation the $r^{th}$ row of the payoff matrix can be deleted. -
A given strategy can be dominated if it is inferior to an average of two or more other pure strategies, i.e. if some convex combination of some rows dominates the $i^{th}$ row, then the $i^{th}$ row will be deleted. If $i^{th}$ row dominates the convex combination of some other rows, then one of the rows involving the convex combination may be deleted.
Dominance property for columns
The dominance property for columns can be summarized as:
-
If all entries in one column, say
$r^{th}$column of the payoff matrix is greater than the corresponding entries in the other column, say$s^{th}$, then the player $B$ will never choose the$r^{th}$strategy. i.e., if$a_{ir}> a_{is}$for all $i = 1, 2,\cdots, m$, then the $r^{th}$ strategy is said to be strictly dominated by the $s^{th}$ strategy. In such situation the $r^{th}$ column of the payoff matrix can be deleted. -
If all entries in one column, say
$r^{th}$column of the payoff matrix is greater than or equal to the corresponding entries in the other column, say$s^{th}$, then the player $B$ will never choose the$r^{th}$strategy. i.e., if$a_{ir}\geq a_{is}$for all $i = 1, 2,\cdots, m$, then the $r^{th}$ strategy is said to be weakly dominated by the $s^{th}$ strategy. In such situation the $r^{th}$ column of the payoff matrix can be deleted. -
A given strategy can be dominated if it is inferior to an average of two or more other pure strategies, i.e. if some convex combination of some columns dominates the $i^{th}$ column, then the $i^{th}$ column will be deleted. If $i^{th}$ column dominates the convex combination of some other column, then one of the column involving the convex combination may be deleted.
For any game first apply the maximin-minimax principle to test whether the saddle point for the game exists or not. If there is no saddle point for the game, then apply the dominance property and try to reduce the game size to either $2\times 2$ or $2\times n$ or $m\times 2$. Again test whether the saddle point exists or not.
- If the game is reduced to $2\times 2$ and there is no saddle point for the reduced game then use algebraic method to solve the game.
- If the game is reduced $2\times n$ or $m\times 2$ and there is no saddle point for the reduced game then use graphical method to solve the game.
Examples of Dominance property
In this tutorial we will discuss some examples based on the use of dominance property to solve the game.
Dominance property Example 1
Solve the following $3\times 3$ game. The payoff matrix for player A is as follows:
| Player A \ 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 |
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.
Step 6 (Use 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
| B1 | B2 | |
|---|---|---|
| A1 | -5 | 10 |
| A2 | 5 | -10 |
| A3 | 5 | -20 |
Use maximin-minimax principle.
| B1 | B2 | RowMin | |
|---|---|---|---|
| A1 | -5 | 10 | -5 |
| A2 | 5 | -10 | -10 |
| A3 | 5 | -20 | -20 |
| ColMax | 5 | 10 |
Thus $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
| B1 | B2 | |
|---|---|---|
| A1 | -5 | 10 |
| A2 | 5 | -10 |
Thus $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.
Step 7 (Algebraic Method)
As the game has no saddle point, the optimal strategies can be obtained by the algebraic method.
Compairing the reduced game with
| Player A \ Player B | $B_k$ | $B_l$ |
|---|---|---|
| $A_i$ | $a$ | $b$ |
| $A_j$ | $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 & A_3\\ p_1 & p_2 & 0 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2 & A_3\\ \frac{1}{2} & \frac{1}{2} & 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 & B_3\\ q_1 & q_2 & 0 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3\\ \frac{2}{3} & \frac{1}{3} & 0 \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.
Dominance property Example 2
Solve the following $3\times 3$ game. The payoff matrix for player A is as follows:
| Player A \ Player B | $B_1$ | $B_2$ | $B_3$ |
|---|---|---|---|
| $A_1$ | 2 | 0 | 4 |
| $A_2$ | 1 | 2 | 3 |
| $A_3$ | 4 | 1 | 2 |
Solution
We have two players A and B. Player A has three strategies and player B also has three strategies.
| B1 | B2 | B3 | |
|---|---|---|---|
| A1 | 2 | 0 | 4 |
| A2 | 1 | 2 | 3 |
| A3 | 4 | 1 | 2 |
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 | 2 | 0 | 4 | 0 |
| A2 | 1 | 2 | 3 | 1 |
| A3 | 4 | 1 | 2 | 1 |
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 | 2 | 0 | 4 | 0 |
| A2 | 1 | 2 | 3 | 1 |
| A3 | 4 | 1 | 2 | 1 |
| ColMax | 4 | 2 | 4 |
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(0, 1, 1)=1$
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, 2, 4)=2$.
Step 5
$Max(min) =1$ and $Min(max)=2$. 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.
Step 6 (Use dominance property)
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
| B1 | B2 | |
|---|---|---|
| A1 | 2 | 0 |
| A2 | 1 | 2 |
| A3 | 4 | 1 |
As every element of $1^{st}$ row ($A_1$) $\leq$ every element of $3^{rd}$ row ($A_3$), the $1^{st}$ strategy of player A is dominated. (i.e strategy $A_1$ is inferior to $A_3$). Hence deleting $A_1$, the reduced game is
| B1 | B2 | |
|---|---|---|
| A2 | 1 | 2 |
| A3 | 4 | 1 |
Use maximin-minimax principle.
| B1 | B2 | RowMin | |
|---|---|---|---|
| A2 | 1 | 2 | 1 |
| A3 | 4 | 1 | 1 |
| ColMax | 4 | 2 |
Thus $Max(min) = Max(1, 1)=1$ and $Min(max)=Min(4, 2)=2$. Since the $Max(min)\neq min(max)$ for the reduced game, the game has no saddle point.
Step 7 (Algebraic Method)
As the game has no saddle point, the optimal strategies can be obtained by the algebraic method.
Compairing the reduced game with
| Player A \ Player B | $B_k$ | $B_l$ |
|---|---|---|
| $A_i$ | $a$ | $b$ |
| $A_j$ | $c$ | $d$ |
The optimal strategy for player A can be determined as
$$ \begin{aligned} p_1 &= \frac{d-c}{(a+d)-(b+c)}\\ &=\frac{1-4}{1+1-(2+4)}\\ &=\frac{-3}{-4}=\frac{3}{4}\\ p_2 &= 1-p_1\\ &=\frac{1}{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{1-2}{1+1-(2+4)}\\ &=\frac{-1}{-4}=\frac{1}{4}\\ q_2 &= 1-q_1\\ &=\frac{3}{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\\ 0 & p_1 & p_2 \end{bmatrix}\\ &=\begin{bmatrix} A_1 & A_2 & A_3\\ 0 & \frac{3}{4} & \frac{1}{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 & B_3\\ q_1 & q_2 & 0 \end{bmatrix}\\ &= \begin{bmatrix} B_1 & B_2 & B_3\\ \frac{1}{4} & \frac{3}{4} & 0 \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{(1)(1)-(4)(2)}{(1+1)-(2+4)}\\ &=\frac{-7}{-4}\\ &=\frac{7}{4}. \end{aligned} $$
Thus, we conclude that player $A$ may choose strategy $A_2$ and $A_3$ with respective probability $\dfrac{1}{4}$ and $\dfrac{3}{4}$ and will never choose $A_1$. Player $B$ may choose strategy $B_1$ with probability $\dfrac{3}{4}$ and strategy $B_2$ with probability $\dfrac{1}{4}$, while he never choose strategy $B_3$. And the value of the game for player A is $\frac{7}{4}$.
Endnote
In this tutorial, you learned about how to use dominance property to solve 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 dominance property to solve game and your thought on this article.