The term Strategy refers to a complete plan of action, specifying what a player will do
in any
future contingency during the game. Strategies can be classified as:
(i) Pure strategy (ii) Mixed strategy
Pay-off is the outcome of playing the game. A pay-off matrix is a table showing the amount received by
the player after all possible plays of the game. The payment is made by the player listed at the top of
the table.
If Player A has m courses of action and Player B has n courses, the pay-off matrix
is constructed as follows:
Player A's Pay-Off Matrix: \[ \begin{pmatrix} & 1 & 2 & 3 & \cdots & n \\ 1 & a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ 2 & a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ 3 & a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ m & a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \\ \end{pmatrix} \]
Player B's Pay-Off Matrix (Negative of A's): \[ \begin{pmatrix} & 1 & 2 & 3 & \cdots & n \\ 1 & -a_{11} & -a_{12} & -a_{13} & \cdots & -a_{1n} \\ 2 & -a_{21} & -a_{22} & -a_{23} & \cdots & -a_{2n} \\ 3 & -a_{31} & -a_{32} & -a_{33} & \cdots & -a_{3n} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ m & -a_{m1} & -a_{m2} & -a_{m3} & \cdots & -a_{mn} \\ \end{pmatrix} \]
\[ \begin{pmatrix} 3 & 5 \\ 6 & 4 \\ \end{pmatrix} \]
- Find the minimum value in each row: Row 1 = 3, Row 2 = 4.Q1: Solve the game whose pay-off matrix is given below:
Player B
B1 B2 B3 B4 B5
-----------------------------------------
A1 | -2 0 0 5 3 |
Player A A2 | 3 2 1 2 2 |
A3 | -4 -3 0 -2 6 |
A4 | 5 3 -4 2 -6 |
-----------------------------------------
Let’s solve this step by step:
Step 1: First, we look at the row minima. These values tell us the worst outcome for Player A if they pick each row. Player A wants to make sure they get the best possible payoff, even in the worst case. So, they will choose the row with the highest row minimum.
Step 2: Next, we look at the column maxima. These values tell us the best outcome for Player B if they pick each column. Player B wants to limit Player A's gain as much as possible, so they will choose the column with the lowest column maximum.
Player B
B1 B2 B3 B4 B5 | Row Minima
-----------------------------------------------
A1 | -2 0 0 5 3 | -2
Player A A2 | 3 2 1 2 2 | 1
A3 | -4 -3 0 -2 6 | -4
A4 | 5 3 -4 2 -6 | -6
-----------------------------------------------
Column Maxima 5 3 1 5 6
Step 3: Compare the results:
Since these two values are equal, there is a saddle point in this game.
Value of the game = 1
The position of the saddle point tells us the optimal strategy for both players. It is:
In simple terms:
Player A wants to play it safe and go for the highest guaranteed payoff. To do this, they look at the
smallest numbers in each row (called the row minima) and pick the best of those. On the other hand,
Player B wants to keep Player A’s payoff as low as possible. So, they focus on the largest numbers
in each column (called the column maxima) to try to limit Player A’s gain.
If the number Player A picks (from the row minima) matches the number Player B picks (from the
column maxima), it’s called a saddle point. At this point, the game is solved!
Q2: Determine which of the following two-person zero-sum games are strictly determinable and fair. Provide the optimum strategy for each player in the case of strictly determinable games.
(i)
Player B
B1 B2
- -
A1 | -5 2 |
Player A A2 | -7 -4 |
- -
(ii)
Player B
B1 B2
- -
A1 | 1 1 |
Player A A2 | 4 -3 |
- -
(i)
Player B
B1 B2
- - Row Minima
A1 | -5 2 | -5
Player A A2 | -7 -4 | -7
- -
Column Maxima -5 2
Step 1: Find the Row Minima and Column Maxima:
Step 2: Compare Max(Row Minima) and Min(Column Maxima):
Since Max(Row Minima) = Min(Column Maxima) = -5, the game is strictly determinable.
Step 3: Value of the game and optimal strategy:
(ii)
Player B
B1 B2
- - Row Minima
A1 | 1 1 | 1
Player A A2 | 4 -3 | -3
- -
Column Maxima 4 1
Step 1: Find the Row Minima and Column Maxima:
Step 2: Compare Max(Row Minima) and Min(Column Maxima):
Since Max(Row Minima) = 1 and Min(Column Maxima) = 1, the game is strictly determinable.
Step 3: Value of the game and optimal strategy:
Summary:
In some two-person zero-sum games, a saddle point does not exist. This happens when the max of the row minima is not equal to the min of the column maxima. Such games are solved using mixed strategies, where players assign probabilities to their strategies instead of selecting a single pure strategy.
Various methods are available to solve games without a saddle point, depending on the size and structure of the payoff matrix:
For 2x2 games, the mixed strategy solution involves solving simultaneous linear equations to find the optimal probabilities for each player. The expected value of the game is then calculated using these probabilities.
This method applies to games where one player has two strategies, and the other has more than two. The strategy probabilities are determined by plotting payoff lines on a graph and identifying the feasible region for the optimal solution.
For larger games (e.g., 5x6), the dominance property helps simplify the matrix by eliminating dominated rows or columns. A row or column is dominated if there exists another row or column that gives equal or better payoffs in all scenarios. After reduction, simpler solution methods like the graphical or algebraic method can be applied.
Consider a 2x2 two-person zero-sum game without any saddle point, having the pay-ff matrix for player A as:
Player B
B1 B2
- -
A1 | a11 a12 |
Player A A2 | a21 a22 |
- -
The optimum mixed strategies,
- -
A1 | A1 A2 |
S A = A2 | p1 p2 |
- -
- -
A1 | B1 B2 |
S B = A2 | q1 q2 |
- -
where, \( p_1 = \frac{a_{22} - a_{21}}{(a_{11} + a_{22}) - (a_{12} + a_{21})} \)
p1 + p2 = 1 → p2 = 1 - p1
\( q_1 = \frac{a_{22} - a_{12}}{(a_{11} + a_{22}) - (a_{12} + a_{21})} \)
q1 + q2 = 1 → q2 = 1 - q1
The value of the game :
\( r = \frac{a_{11}a_{22} - a_{12}a_{21}}{(a_{11} + a_{22}) - (a_{12} + a_{21})} \)
Q: Solve the following pay-off matrix. Also determine the optimal strategies and value of the game.
Player B
- -
| 5 1 |
Player A | 3 4 |
- -
Solution:
- -
A1 | A1 A2 |
S A = A2 | p1 p2 |
- -
- -
A1 | B1 B2 |
S B = A2 | q1 q2 |
- -
p1 = (4 - 3) / ((5 + 4) - (1 + 3)) = 1/5
The principle of dominance is a simple way to simplify a game matrix. It says that if one strategy is clearly better than another in all situations, we can ignore the weaker strategy. This helps reduce the size of the payoff matrix without affecting the optimal solution.
Let’s break it down:
By applying the dominance property, we can shrink the payoff matrix. This makes solving the game easier without changing the final result.
The Rules of Dominance:
Compare two rows. If one row (e.g., Row k) has values that are greater than or equal to the corresponding values in another row (e.g., Row r), then Row k is dominated by Row r. The dominated row (k) can be removed since it will never lead to a better outcome.
Key takeaway: Remove the row with the minimum values because it offers less favorable outcomes.
Compare two columns. If one column (e.g., Column k) has values that are less than or equal to the corresponding values in another column (e.g., Column r), then Column k is dominated by Column r. The dominated column (k) can be removed as it always gives worse payoffs.
Key takeaway: Remove the column with the maximum values because it represents less favorable strategies.
We can delete dominated rows and columns to make the matrix smaller. This makes calculations easier without affecting the optimal strategies.
Sometimes, a linear combination of rows or columns can dominate another row or column. In that case, the dominated row or column can still be removed. This is less common but follows the same idea.
In simple terms:
The dominance property helps us focus only on the important strategies by removing weaker ones. It’s like cleaning up unnecessary options in a game to make solving it faster and simpler!
Q: Solve the following game:
Player B
- -
| 1 7 2 |
Player A | 6 2 7 |
| 5 1 6 |
- -
Solution:
Step 1: Check for a Saddle Point:
A saddle point exists if the max of the row minima equals the min of the column maxima. Let’s calculate these:
Since Max(Row Minima) ≠ Min(Column Maxima), there is no saddle point. We proceed using the dominance property to simplify the matrix.
Step 2: Apply Dominance Property:
We simplify the matrix by identifying dominated rows or columns and removing them:
Let’s compare the columns pairwise:
Column 1: (1, 6, 5) | Column 3: (2, 7, 6)
All values in Column 3 are greater than or equal to the corresponding values in Column 1. This means Column 3 is dominating Column 1. We remove Column 3.
Updated matrix after removing Column 3:
Player B
- -
| 1 7 |
Player A | 6 2 |
| 5 1 |
- -
Step 3: Eliminate Dominated Rows:
Now, we compare the rows in the updated matrix:
Player B
- -
| 1 7 |
Player A | 6 2 |
| 5 1 |
- -
Row 1: (1, 7) | Row 3: (5, 1)
All values in Row 1 are less than or equal to the corresponding values in Row 3. This means Row 3 is dominated by Row 1, and we can remove Row 3.
Updated matrix after removing Row 3:
Player B
- -
| 1 7 |
Player A | 6 2 |
- -
Step 4: Solving the 2x2 Game Matrix:
Now that we have a 2x2 matrix, we can apply the dominance property again or use a different method to find the optimal strategies. In this case, we will:
Thus, the optimal solution occurs at the cell (Row 1, Column 2), which has a payoff of 7 for Player A and 7 for Player B.