Game Theory

Types of Games

Two-Person and N-Person Games: In two-person games, there are only two players, though each may have many possible choices. If more than two people are involved, it is called an n-person game.
Zero-Sum Game: A zero-sum game is one where the total gains and losses of all players equal zero, regardless of the outcome. The points gained by winners are offset by the points lost by losers.
Two-Person Zero-Sum Game: This type involves two players where the gain of one equals the loss of the other. It is often represented by a rectangular pay-off matrix.

Strategy

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

Pure Strategy: A strategy is called pure if one knows in advance of the play that it is certain to be adopted, irrespective of the strategy the other players might choose.
Mixed Strategy: The optimal strategy mixture for each player is determined by assigning probabilities to each strategy. This is called a mixed strategy because it is a probabilistic combination of available choices. Mixed strategies are denoted by a set:
S = {x1, x2, ..., xn}, where x is the probability of choosing a course of action.
So, x1 + x2 + ... + xn = 1.
Note: A pure strategy is a special case of a mixed strategy.

Pay-Off

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:

Row designations represent Player A's courses of action.
Column designations represent Player B's courses of action.
In a two-person zero-sum game, the entries in Player B's pay-off matrix will be the negatives of the corresponding entries in Player A's pay-off matrix. For example:
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} \]

The Maximin - Minimax Principle

This principle is used for the selection of optimal strategies by two players. Consider two players, A and B. Player A wishes to maximize their gains, while Player B wishes to minimize their losses. Since A would like to maximize their minimum gain, the value obtained for Player A is called the maximin value, and the corresponding strategy is called the maximin strategy.
On the other hand, since Player B wishes to minimize their maximum losses, a value called the minimax value, which is the minimum of the maximum losses, is calculated. The corresponding strategy is called the minimax strategy. When these two values are equal (maximin value = minimax value), the corresponding strategies are called optimal strategies, and the game is said to have a saddle point. The value of the game is given by the saddle point.
The selection of maximin and minimax strategies by A and B is based on the so-called maximin-minimax principle, which guarantees the best of the worst results.
Saddle Point: A saddle point is a position in the payoff matrix where the maximum of row minima coincides with the minimum of column maxima. The payoff at the saddle point is called the value of the game.
For example, in a 2x2 payoff matrix:
\[ \begin{pmatrix} 3 & 5 \\ 6 & 4 \\ \end{pmatrix} \]
- Find the minimum value in each row: Row 1 = 3, Row 2 = 4.
- Find the maximum value in each column: Column 1 = 6, Column 2 = 5.
- The saddle point exists where the maximum of the row minima (4) equals the minimum of the column maxima (4).
- Here, the saddle point is at position (2,2) with a value of 4.
The values used in the maximin and minimax principles are as follows:
- The maximin value is the value that Player A aims to maximize in the worst-case scenario of their strategies.
- The minimax value is the value that Player B aims to minimize in the worst-case scenario of the strategies chosen by Player A.
- The value of the game is the outcome at the saddle point, which represents the optimal result for both players.
Note:
1. The game is said to be fair if the maximin value equals the minimax value and both are 0, i.e., the expected payoff for both players is zero.
2. The game is said to be strictly determinable if the maximin value equals the minimax value and neither is 0, meaning there is a clear outcome for the game.
3. If the maximin value does not equal the minimax value, the game is indeterminate and players must use mixed strategies (involving probabilities) to optimize their results.

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.

Row Minima:
- Row A1: -2
- Row A2: 1
- Row A3: -4
- Row A4: -6
Max(Row Minima) = Max(-2, 1, -4, -6) = 1

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.

Column Maxima:
- Column B1: 5
- Column B2: 3
- Column B3: 1
- Column B4: 5
- Column B5: 6
Min(Column Maxima) = Min(5, 3, 1, 5, 6) = 1

                
                           
                          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:

Max(Row Minima) = 1
Min(Column Maxima) = 1

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:

Optimal Strategy: (A2, B3)

In simple terms:

Player A wants the highest guaranteed payoff (the best of the worst cases), so they focus on the row minima. Player B wants to limit Player A's gain as much as possible, so they focus on the column maxima. When these two match, a saddle point exists, and 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 |   
                 -       -

For (i):
```
            
(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:
- Row Minima:
  - Row A1: Min(-5, 2) = -5
  - Row A2: Min(-7, -4) = -7
- Max(Row Minima) = Max(-5, -7) = -5
- Column Maxima:
  - Column B1: Max(-5, -7) = -5
  - Column B2: Max(2, -4) = 2
- Min(Column Maxima) = Min(-5, 2) = -5
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:
- Value of the game = -5
- Optimal strategy: (A1, B1) — Player A chooses A1, and Player B chooses B1.
For (ii):
```
            
(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:
- Row Minima:
  - Row A1: Min(1, 1) = 1
  - Row A2: Min(4, -3) = -3
- Max(Row Minima) = Max(1, -3) = 1
- Column Maxima:
  - Column B1: Max(1, 4) = 4
  - Column B2: Max(1, -3) = 1
- Min(Column Maxima) = Min(4, 1) = 1
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:
- Value of the game = 1
- Optimal strategy: (A1, B1) — Player A chooses A1, and Player B chooses B1.

Summary:

Game (i) is strictly determinable with a value of -5 and an optimal strategy of (A1, B1).
Game (ii) is strictly determinable with a value of 1 and an optimal strategy of (A1, B1).

Games Without Saddle Points (Mixed Strategy)

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:

Solution Methods for Games Without Saddle Points:
1. 2x2 Games Without Saddle Point:
  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.
2. Graphical Method for 2xn or mx2 Games:
  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.
3. Dominance Property for mxn Games:
  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.
A mixed strategy is when a player doesn’t stick to just one choice (pure strategy) but instead assigns probabilities to multiple choices. It’s like saying, “I’ll pick option A 60% of the time and option B 40% of the time.” This way, the player keeps their opponent guessing and ensures a better outcome in games where no single choice (pure strategy) is the best.

2x2 Games Without Saddle Point

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
p2 = 1 - p1 = 4/5
q1 = (4 - 1) / ((5 + 4) - (1 + 3)) = 3 /5
q2 = 1 - 3/5 = 2/5

Value of the game = 17/5
∴ Optimum mixed strategy = SA = (1/5, 4/5) and SB = (3/5, 2/5)

Dominance Property

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:

A strategy dominates another strategy if it is better (or at least not worse) in every possible condition.
- For example, if you’re comparing two rows (strategies for Player A) and one row always has better payoffs than the other, you can ignore the weaker row.
- Similarly, for columns (strategies for Player B), if one column always gives worse payoffs than another, you can ignore it.
How does this help?
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:

Row Dominance:
If all the values in one row (say Row k) are less than or equal to the values in another row (say Row r), then Row k is dominated by Row r and can be ignored.
Column Dominance:
If all the values in one column (say Column k) are greater than or equal to the values in another column (say Column r), then Column k is dominated by Column r and can be ignored.
Reducing the Payoff Matrix:
We can delete dominated rows and columns to make the matrix smaller. This makes calculations easier without affecting the optimal strategies.
Combination Dominance:
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:
- Row Minima:
  - Row 1: Min(1, 7, 2) = 1
  - Row 2: Min(6, 2, 7) = 2
  - Row 3: Min(5, 1, 6) = 1
  Max(Row Minima) = 2
- Column Maxima:
  - Column 1: Max(1, 6, 5) = 6
  - Column 2: Max(7, 2, 1) = 7
  - Column 3: Max(2, 7, 6) = 7
  Min(Column Maxima) = 6
Since Max(Row Minima) ≠ Min(Column Maxima), there is no saddle point. We proceed using the dominance property.
Step 2: Apply Dominance Property:

We simplify the matrix by identifying dominated rows or columns and removing them:
1. Compare Columns:
  Let’s compare the columns pairwise:
  - Column 1 vs Column 3:
    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 1 is dominated by Column 3. We remove Column 1.
  Updated matrix after removing Column 1:
```
                    
             Player B 
            -       -
           |  7    2 |   
Player A   |  2    7 | 
           |  1    6 |    
            -       -
                    
                
```
Step 3: Eliminate Dominated Rows:

We compare the rows in the updated matrix:
```
    
            Player B 
           -       -
          |  7    2 |   
Player A  |  2    7 | 
          |  1    6 |    
           -       -
    
```
- Compare Row 1 and Row 3:
  Row 1: (7, 2) | Row 3: (1, 6)
  
  All values in Row 1 are greater 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 
            -       -
           |  7    2 |   
Player A   |  2    7 | 
            -       -
    
```
Now we have this 2x2 so we can further solve it.