Mixed Strategy Algorithm Explained: Tips for Nash Equilibria

[00:00:01]hi I'm William spaniel let's learn some Game Theory today we're going to talk about the mixed strategy algorithm I go over this in lesson 1.5 of Game Theory 101 the complete textbook check the video description for more information about that now remember in the last video we covered matching pennies we saw that there weren't any pure strategy Nash equilibria and we guessed actually correctly that if both players flipped their coins then each player would be indifferent between choosing heads or tails and so neither player could change his or her strategy and expect to do better which met the definition of Nash equilibrium so flipping a coin served as a mixed strategy Nash equilibrium now that was relatively easy to guess because all of those payoffs are ones and negative ones however most games aren't going to have that simple of a payoff structure for example if we looked at this game where we have different weights associated with each outcome then it's not so obvious that coin flipping is going to work out so well and so what we're going to be doing in this video is developing an algorith a mixed strategy algorithm as the title implies that allows us to find what sort of mixed strategies uh for each of these players makes the other guy indifferent so for example what we need to do is we need to find a mixed strategy for player one so sometime he'll play up and the rest of the time he'll play down and we need to find a strategy that looks like that that leaves player two indifferent between selecting left and right if player two gets the same payoff for selecting left on average as she does for selecting right then it doesn't matter which strategy she chooses so she can choose a mixed strategy a randomization between left and right and if that randomization leaves player one indifferent between between choosing up and down then that means he's perfectly satisfied also maintaining his original mix strategy and so that means neither player is going to have incentive to change his or her strategy so we end up in a mixed strategy Nash equilibrium with those probabilities between the two strategies so that sounded a little bit confusing it'll become clearer as we actually go about solving for the Mixed strategies so let's start off with player one's mixed strategy now what we're trying to do here with this mixed strategy for player one is come up with a mixed strategy that makes player 2's expected utility for left her payoff for selecting left as a pure strategy equal to her payoff her expected utility for choosing right as a pure strategy and it's pretty obvious here that player 2's expected utility for left is a function this function f of a mixed strategy Sigma U this Sigma U represents the probability that player one plays up so if player two plays left then she's at the mercy of player one's decision between up and down to determine what her payoff is whether it's -3 or one and so that's what this is representing here and it's the same thing if player two is selecting right then she's at the mercy of player one's decision to choose up or down which this is what the sigma U is representing which is just a probability that player one plays up and a probability that player one plays down and that's going to determine whether she gets two or zero here now if you remember from basic algebra we have three equations here with three unknowns we have an expected utility for left an expected utility for right and a probability distribution which we're representing with Sigma up and so if you have three equations and three unknowns you can actually solve for all of them and that's what we'll be doing here so first let's start off by solving for player one's mixed strategy and looking at what the expected utility for left is as a function of this mixed strategy Sigma up all right well some percentage of the time player two is getting ne3 so in this case her expected utility for left that means player two is always selecting left here if we're trying to calculate her expected utility for left and so some percentage of the time player one is playing up and he's getting NE or she's getting neg3 and the rest of the time player one is playing down and player two is getting one and so her expected utility for left is Sigma up * -3 plus 1 - Sigma up * 1 let's go over this to be really explicit where all these numbers are coming from so Sigma up represents the probability that player one plays up and if player one plays up then that percentage of the time player two will getg -3 that's this payoff right here and then we need to add that payoff to what happens the rest of the time so one minus Sigma up is the probability that player two plays down or rather player one plays down and so that percentage of the time where player one is playing down player player two is earning one point of utility for that outcome and so you multiply the percentage of the time that player one plays down times that payoff of one and so adding those two things together you get player 2's expected utility for left now we need to do the same thing on the other side so what is player 2's expected utility for right as a function of a mixed strategy Sigma up well some percentage of the time player one is selecting up and player two is getting two and the rest of the time she's getting zero so we can write that like this her expected utility for right is some probability of the time some percentage of the time player one plays up and she gets two and then we to add that to the probability that player one plays down which is one minus Sigma up the rest of the time if player one isn't going up that means he must be going down and that percentage of the time player two is earning zero so we're multiplying it by zero and so that's what player 2's expected utility is for right now remember we want to set those two expect utilities equal to each other so we have expected utility for left and expected utility for right we've defined the expected utilities for each of those as a function of Sigma up and now we just set those two things equal to each other this equal to this and if you run through a little bit of algebra here and you solve for Sigma up running through those steps here you can pause if you're unclear about how I did each of those steps you can work through them for yourself you arrive at Sigma up equals 1 16 so what this is saying is if player one plays up 1 six of the time and down 56 of the time then player two is indifferent between left and right regardless of her choice she still winds up with the same expected utility that was from this equation right here so this mixture for player one leaves player two indifferent now we're going to do the opposite thing we're going to do the same thing basically except we're going to switch the players around so this time we're asking ourselves what is player one's expected utility for up and what player one's expected utility for down we're going to set those two things equal to each other well his expected utility for up is just a function of player two's mix strategy now so we're solving for player two's mix strategy and that's just going to be represented by this function of Sigma L and player one's expected utility for down is also a function of Sigma L we still have three unknown equations or three equations and three unknown variables that means we can solve for them so let's work through that let's first find player one's expected utility for up well again it's just a function of some mixed strategy Sigma left so if player one is playing up here cuz we're solving for his expected utility of up then some percentage of the time player one or player two is going to play left and player one is going to earn three and then the rest of the time player two is going to play right and player one is going to get Negative -2 so Sigma left is the probability that player two plays Left multiply that by this payoff of three here and then add that to one minus Sigma left the probability that player two plays right and multiply that by -2 here you sum those things two things together and you get player one's expected utility for for up now it's expected utility for down looks like this so some percentage of the time player one is getting ne1 and the rest of the time he's getting zero so his expected utility for down is Sigma left the probability that player two plays Left times Nega 1 plus the probability that uh player two plays right 1 minus Sigma left times this payoff of zero here and we're going to set those two equations equal to each other so the expected utility for up is equal to the expected utility for down those are the expected utility equations that we came up with in the last two slides and again if you want to pause you can see all of the step-by-step mathematics here but you eventually get to Sigma left is equal to 1/3 and so if player two is playing left with probability 1/3 and right with probability 2/3 then now player one is indifferent between choosing up and down again this equation right here assures that his expected utility is the same whether he plays up or down and so the mixed strategy Nash equilibrium of this game is for player one to play up with probability 1 Sixth and down with probability 56th and for player two to play left with probability 1/3 and right with probability 2/3 as long as the players are mixing in that manner then neither player can change his or her strategy and expect to do better because their expected utilities for up and down for player one are the same and player two's expected utilities for left and right are the same no one can profitably deviate and change their strategy and expect to do better based off of what every other one else is doing and so that leads to a mixed strategy Ash equilibrium and so that's how you use the uh the mix strategy algorithm to solve for mix strategy Nash equilibria we'll actually be exploring a couple more cases of this mix strategy algorithm so if you need more practice you will see more of that coming up in the next video or in the next couple of videos and actually next time we will talk about a common mistake that you see people make when they're writing mixed strategy Nash equilibrium and I'll tell you how to avoid that in the next video join me then