VIDEO
HIGHLIGHT
Log InSign up
Game Theory 101 (#8): The Mixed Strategy Algorithm
SummaryTranscriptChat

Game Theory 101 (#8): The Mixed Strategy Algorithm

Introduction to Mixed Strategy Algorithm

In this section, William Spaniel introduces the concept of the mixed strategy algorithm and its application in game theory.

Understanding Mixed Strategy Nash Equilibrium

  • In the previous video on matching pennies, it was observed that there were no pure strategy Nash equilibria.
  • Flipping a coin served as a mixed strategy Nash equilibrium because both players were indifferent between choosing heads or tails.
  • However, most games have more complex payoff structures, making it less obvious to determine the optimal mixed strategy.

Developing a Mixed Strategy Algorithm

  • The goal is to find a mixed strategy for each player that makes the other player indifferent between their available strategies.
  • Player one needs to find a mixed strategy that leaves player two indifferent between selecting left and right.
  • Similarly, player two needs to find a mixed strategy that leaves player one indifferent between choosing up and down.

Solving for Mixed Strategies

This section focuses on solving for the mixed strategies of both players using algebraic equations.

Player One's Mixed Strategy

  • Player one's expected utility for selecting left is represented by a function of their mixed strategy (Sigma U).
  • By setting the expected utility for left equal to the expected utility for right, we can solve for Sigma U using algebraic equations.

Player Two's Expected Utilities

  • Similar to player one, player two's expected utility for selecting right is also represented by a function of Sigma U.
  • We can set up equations with three unknowns (expected utility for left, expected utility for right, and Sigma U) and solve them simultaneously.

Calculating Expected Utilities

This section explains how to calculate the expected utilities based on the mixed strategies.

Player One's Expected Utility for Left

  • Player two's expected utility for left is a combination of the outcomes when player one plays up and down.
  • The expected utility for left is calculated as Sigma U times negative 3 plus 1 minus Sigma U times 1.

Player Two's Expected Utility for Right

  • Similarly, player two's expected utility for right is calculated based on the outcomes when player one plays up and down.
  • The expected utility for right is calculated as Sigma U times 2 plus 1 minus Sigma U times 0.

Conclusion

In this section, William Spaniel concludes the discussion on solving for mixed strategies in game theory.

Solving Equations to Find Mixed Strategies

  • By setting the expected utilities equal to each other, we can solve the equations to find the optimal mixed strategies for both players.
  • This process allows us to determine a mixed strategy Nash equilibrium with probabilities between the available strategies.

The transcript does not provide further information beyond this point.

Player 2's Expected Utility

This section discusses the expected utility for Player 2 and how it is calculated.

Calculation of Player 2's Expected Utility

  • Player 2's expected utility is determined by multiplying the percentage of time they earn 0 by 0.
  • The expected utility for left and right choices are set equal to each other.
  • By solving the equation, it is found that if Player 1 plays up 1/6 of the time and down 5/6 of the time, Player 2 is indifferent between left and right.

Setting Expected Utilities Equal

This section explains how to set the expected utilities equal to each other.

Setting Expected Utilities Equal

  • The expected utilities for up and down choices for Player 1 are defined as functions of Sigma L (Player 2's mixed strategy).
  • By setting these two equations equal to each other, Sigma L can be solved for.
  • After solving through algebraic steps, it is found that Sigma L equals 1/6.

Indifference Point for Player 1

This section discusses the indifference point for Player 1 when considering their expected utilities.

Indifference Point Calculation

  • When considering player one's expected utility for up and down choices, player two's mixed strategy (Sigma L) comes into play.
  • The expected utility for player one choosing up depends on player two playing left or right with certain probabilities.
  • Similarly, the expected utility for player one choosing down also depends on player two's probabilities.
  • By setting these two equations equal to each other, Sigma L is found to be equal to 1/3.
  • Therefore, if player two plays left with probability 1/3 and right with probability 2/3, player one is indifferent between choosing up and down.

Mixed Strategy Nash Equilibrium

This section explains the concept of mixed strategy Nash equilibrium and how it applies to the game.

Mixed Strategy Nash Equilibrium

  • The mixed strategy Nash equilibrium for this game is for player one to play up with probability 1/6 and down with probability 5/6.
  • Player two should play left with probability 1/3 and right with probability 2/3.
  • As long as both players follow these strategies, neither can profitably deviate and expect better outcomes.
  • This leads to a stable equilibrium where no player can improve their situation by changing their strategy.

Conclusion

This section concludes the discussion on using the mixed strategy algorithm to find mixed strategy Nash equilibria.

Summary

  • The mixed strategy algorithm was used to find the mixed strategy Nash equilibrium in this game.
  • More cases of this algorithm will be explored in future videos for further practice.
Video description

Game Theory 101: The Complete Textbook on Amazon: https://www.amazon.com/Game-Theory-101-Complete-Textbook/dp/1492728152/ http://gametheory101.com/courses/game-theory-101/ To check for mixed strategy Nash equilibria, we must run the mixed strategy algorithm. This algorithm shows whether there exists a mixed strategy for a player that leaves the other player indifferent between his or her two pure strategies. If such a mixed strategy exists for both players, then those strategies collectively form a mixed strategy Nash equilibrium. The mixed strategy algorithm is the first computationally intensive part of game theory we have encountered. However, we will be using the algorithm quite a bit later on, so do not be worried if the logic of the math is difficult to grasp at first.