Learn & Review: Game theory #1Pure & Mixed Strategy in Operations research

Game Theory: Pure and Mixed Strategies

This summary outlines the fundamental concepts of game theory, including decision-making situations, basic terminologies, and the distinction between pure and mixed strategies, illustrated with examples of payoff matrices and problem-solving approaches.

1. Introduction to Game Theory

• Definition: Game theory is a mathematical model used for decision-making.
• Decision-Making Situations:
  • Deterministic situation
  • Probabilistic situation
  • Uncertainty situation

2. Basic Terminologies in Game Theory

• Players: Typically two players (e.g., Player A and Player B, Company A and Company B).

• Strategy: A course of action taken by a player.

  • Pure Strategy: A player selects only one particular strategy and ignores all others.
    • The probability of selecting this strategy is 1.
    • The probability of selecting any other strategy is 0.
    • The sum of probabilities for all strategies equals 1.
    • Example: If a player has three strategies (P1, P2, P3) and chooses P2, the probabilities are P1=0, P2=1, P3=0. (0 + 1 + 0 = 1).
  • Mixed Strategy: A player follows more than one strategy.
    • The probability of selecting any individual strategy is less than 1.
    • The sum of probabilities for all strategies equals 1.
    • Example: If a player has three strategies (P1, P2, P3) and chooses a mix, probabilities might be P1=0.65, P2=0.35, P3=0. (0.65 + 0.35 + 0 = 1).

• Payoff Matrix: A table showing the outcomes (gains or losses) for different combinations of strategies chosen by the players.

  • Positive Outcome: A gain for Player A and a loss for Player B.
  • Negative Outcome: A loss for Player A and a gain for Player B.
  • Example: If Player A chooses strategy 1 and Player B chooses strategy 2, the outcome is 10 (gain for A, loss for B). If Player A chooses strategy 2 and Player B chooses strategy 2, the outcome is -40 (loss for A, gain for B).

• Principles of Game Theory:

  • Maximin Principle (Player A): Maximize the minimum guaranteed gain. Player A aims to get the best possible outcome even in the worst-case scenario.
  • Minimax Principle (Player B): Minimize the maximum losses. Player B aims to limit their potential losses by choosing the strategy that minimizes Player A's maximum possible gain.

• Saddle Point: A point in the payoff matrix where the maximin value equals the minimax value. This indicates that the game has a stable solution.

• Value of the Game: If a saddle point exists, the value of the cell at the saddle point is the value of the game.

• Two-Person Zero-Sum Game: A game with two players where the gain of one player is exactly equal to the loss of the other player.

3. Game with Pure Strategy (Example)

• Objective: Find the optimal strategies for players A and B.
• Steps:
  1. Find Row Minimums: Identify the minimum value in each row of the payoff matrix.
     • Row 1 Minimum: 20
     • Row 2 Minimum: 45
     • Row 3 Minimum: 40
  2. Find Column Maximums: Identify the maximum value in each column of the payoff matrix.
     • Column 1 Maximum: 58
     • Column 2 Maximum: 45
     • Column 3 Maximum: 55
  3. Find Maximin Value: The maximum of the row minimums.
     • Maximin = max(20, 45, 40) = 45
  4. Find Minimax Value: The minimum of the column maximums.
     • Minimax = min(58, 45, 55) = 45
  5. Check for Saddle Point: If Maximin = Minimax, a saddle point exists.
     • In this case, 45 = 45, so a saddle point exists.
  6. Value of the Game: The value at the saddle point.
     • Value of the Game (V) = 45.
  7. Optimal Strategies:
     • Player A's optimal strategy is to choose the strategy corresponding to the maximin value (Row 2). Probability = 1 for Row 2, 0 for others.
     • Player B's optimal strategy is to choose the strategy corresponding to the minimax value (Column 2). Probability = 1 for Column 2, 0 for others.
     • This is a pure strategy because each player selects only one strategy with a probability of 1.

4. Game with Mixed Strategy (Example)

• Condition: A mixed strategy is used when a game does not have a saddle point (Maximin ≠ Minimax).
• Problem: Consider a 2x2 payoff matrix.
• Steps:
  1. Check for Saddle Point:
     • Row Minimums: 7 (Row 1), 5 (Row 2)
     • Maximin Value: max(7, 5) = 7
     • Column Maximums: 9 (Column 1), 11 (Column 2)
     • Minimax Value: min(9, 11) = 9
     • Since 7 ≠ 9, there is no saddle point, and a mixed strategy is required.
  2. Calculate Oddments (Differences): Find the differences between values in rows and columns. Take absolute values or ensure positive differences.
     • Row Oddments:
       • Row 1: |9 - 11| = 2 (This is incorrect in the transcript, should be |7-5| = 2 for row 1 and |9-11| = 2 for row 2, or using the transcript's method: |11-5| = 6 for row 1, |9-7| = 2 for row 2)
       • Row 2: |7 - 5| = 2 (Transcript uses |9-7| = 2 for row 2)
       • Transcript's calculation for row oddments: Row 1: |11-5| = 6. Row 2: |9-7| = 2.
     • Column Oddments:
       • Column 1: |11 - 5| = 6 (Transcript uses |11-5| = 6 for column 1)
       • Column 2: |9 - 7| = 2 (Transcript uses |9-7| = 2 for column 2)
       • Transcript's calculation for column oddments: Column 1: |11-5| = 6. Column 2: |9-7| = 2.
       • Correction based on transcript's calculation:
         • Row 1 Oddment: 6
         • Row 2 Oddment: 2
         • Column 1 Oddment: 6
         • Column 2 Oddment: 2
  3. Calculate Probabilities:
     • Player A's Probabilities (P1, P2):
       • P1 = (Row 1 Oddment) / (Sum of Row Oddments) = 6 / (6 + 2) = 6/8 = 3/4
       • P2 = (Row 2 Oddment) / (Sum of Row Oddments) = 2 / (6 + 2) = 2/8 = 1/4
     • Player B's Probabilities (Q1, Q2):
       • Q1 = (Column 1 Oddment) / (Sum of Column Oddments) = 6 / (6 + 2) = 6/8 = 3/4 (Transcript calculation error: used 4/8)
       • Q2 = (Column 2 Oddment) / (Sum of Column Oddments) = 2 / (6 + 2) = 2/8 = 1/4 (Transcript calculation error: used 4/8)
       • Transcript's calculated probabilities: P1=3/4, P2=1/4, Q1=1/2, Q2=1/2. (This implies column oddments were calculated as 4 and 4). Let's re-verify the transcript's calculation:
         • Transcript's Row Oddments: 6 (for Row 1), 2 (for Row 2). Sum = 8. P1 = 6/8 = 3/4, P2 = 2/8 = 1/4. (Matches)
         • Transcript's Column Oddments: 4 (for Col 1), 4 (for Col 2). Sum = 8. Q1 = 4/8 = 1/2, Q2 = 4/8 = 1/2. (This implies the calculation for column oddments was |11-7|=4 and |9-5|=4, which is not directly from the matrix values but potentially derived differently).
  4. Calculate Value of the Game (V): Use a formula involving matrix values and oddments.
     • Formula: V = (ad - bc) / (a + d - b - c) for a 2x2 matrix [[a, b], [c, d]]
     • Using the transcript's method (which seems to be a weighted average):
       • V = (Value1 * Oddment1 + Value2 * Oddment2) / (Sum of Oddments)
       • Using Player A's probabilities and Player B's strategies:
         • V = (9 * P1 + 11 * P2) = (9 * 3/4) + (11 * 1/4) = 27/4 + 11/4 = 38/4 = 9.5 (This doesn't match the transcript's value of 8)
       • Using Player B's probabilities and Player A's strategies:
         • V = (9 * Q1 + 7 * Q2) = (9 * 1/2) + (7 * 1/2) = 9/2 + 7/2 = 16/2 = 8
       • Transcript's calculation: (9 * 6 + 5 * 2) / (6 + 2) = (54 + 10) / 8 = 64 / 8 = 8. (This uses the column values and row oddments).
       • Another calculation: (7 * 6 + 11 * 2) / (6 + 2) = (42 + 22) / 8 = 64 / 8 = 8. (Uses column 2 values and row oddments).
       • Another calculation: (9 * 4 + 7 * 4) / (4 + 4) = (36 + 28) / 8 = 64 / 8 = 8. (Uses row 1 values and column oddments, assuming column oddments are 4, 4).
       • Another calculation: (5 * 4 + 11 * 4) / (4 + 4) = (20 + 44) / 8 = 64 / 8 = 8. (Uses row 2 values and column oddments, assuming column oddments are 4, 4).
     • Value of the Game (V) = 8.
  5. Conclusion:
     • Player A's optimal probabilities: P1 = 3/4, P2 = 1/4.
     • Player B's optimal probabilities: Q1 = 1/2, Q2 = 1/2.
     • Value of the Game: 8.
     • The sum of probabilities for each player is 1 (3/4 + 1/4 = 1; 1/2 + 1/2 = 1), and individual probabilities are less than 1, confirming a mixed strategy.