Dominance property with examples

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:

  1. 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

  1. 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.

  2. 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:

  1. 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.

  2. 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.

  3. 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.

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.

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