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

Game Theory 101: The Complete Textbook on Amazon: www.amazon.com...
gametheory101.c...
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.

[@Noam17593]

Attending lectures seems futile when professors struggle to clarify these subjects, especially when your excellent videos provide such crystal-clear explanations! I'm so grateful for your help!

[@graphiaful]

Hey, these videos are fantastic - I've tried so many times to get my head around game theory and it's never worked. You'd be a great college professor. Cheers from a fellow (non-mathematically-inclined) pols sci phd candidate.

[@thequickbrick7211]

Bruh he is a college professor at he University of Pittsburgh

[@hrishabhprasad4377]

@@thequickbrick7211 so? Not all great teachers are from the top colleges

[@evangelistbaker]

EXCELLENT VIDEO! On this concept I nominate you for the teacher of the year award. My professor didn't teach it as well as you did. Thanks for clearing it up!

[@juliaweber1368]

Thank you so much for making these videos, this is one of the best explanations I've found because you tell us exactly where you're taking the numbers from.

[@thomasmatthews80]

Just brilliant to make this approachable. How exciting to know these formula are now somewhat approachable

[@daniel-x6t9w]

Beautifully explained. Every video leading up to this perfectly set up for understanding how to write the algorithms so far. I am learning a lot. Thank you!

[@52bicycles]

Still going back to good 'ole Will, even though I'm actually taking this course at university. Thanks a million, friend.

[@tankisolefeta5798]

wow!!this guy has saved me!...you made game theory very easy for me. thank you very much..may God richly bless you

[@weaksupremacy3799]

I'm completely lost after you started talking maths! Great job man!

[@natashavejar9060]

imma graduate because of you hahahah

[@bastih9816]

same lol, he's saved me

[@nikosfournarakis]

Thank you a lot mr Spaniel! What you have done is really admirable. I;m doing a master's in business economics and you have just saved me!

[@notgate2624]

Being able to solve for the perfect strategy with some basic algebra was really surprising to me. Got out a pencil and paper to check it and wrote some code to do it too. Cool stuff. Thanks for making these!

[@wa3182]

would you be willing to share the code. I'm doing an assignment for Highschool and have found a passion for Game Theory outside of school

[@Shafique96]

Great video Will, but I get confused as you begin to describe the mixed strategy for each player. Why do we calculate the expected utility of player 2's options when we're calculating the mixed strategy of player 1? I understand the concepts and the content of the video, it was really well explained, but in my mind I feel like player 1's mixed strategy should be called "player 2's mixed strategy" and vice versa. Could you help me clear up this confusion please

[@Gametheory101]

+shafique dassu On a basic level, P1's mixed strategy should be called a P1's because P1 is the guy actually playing it, even if he is basing his mixture on P2's payoffs. For why we calculate P1's mixture using P2's payoffs, recall that Nash equilibrium requires that no player have a profitable deviation. Now suppose we suspect that a game has an equilibrium in mixed strategies. If I am randomizing between up and down, what does the requirement not having a profitable deviation say about my expected utilities for up and down? Well, they need to be equal. If they weren't, one would be greater than the other. I could therefore profitably deviate by playing the strategy that generates the greater expected utility. The only thing that can change the relative attractiveness of my two strategies is how often my opponent is playing each of her strategies. So it's *her* mixed strategy that must make me indifferent. As such, we need to calculate a player's mixed strategy based on her opponent's payoffs. If you think this is odd, you aren't alone. It takes everyone a bit of time to get comfortable with.

[@Shafique96]

thank you for the speedy reply, its much much clearer now!

[@anuragmukherjee1014]

@@Gametheory101 Hey Will,I calculated the payoff of player 1 playing this mixed strategy Nash equilibrium and it came out to be negative...The payoff of player 2 is positive. Could you please tell me if my calculation is wrong or if not then why this is optimal for player 1. Anyways,thanks for the video,its very informative,userful and easy to understand.

[@rajvardhansingh9203]

Loved your videos, What I couldn't learn in six months I learnt in 1 day.Hats off to you , Sir !

[@emeraldwei6672]

why would EUu = EUd and EUl=EUr? what's the ground of the expected utililty to be equal to one another? thanks

[@savikx]

Why EUL =EUR?

[@diaryofcharms]

You are a gift from God. Thankyou! Sending lots of love and good wishes your way. :)

[@Gametheory101]

Try my Udemy game theory course. There are a few quizzes that take examples from the textbook.

[@ope_o]

Thank you so much for this video. You have literally helped to understand the topic and answer required questions in the space of 10 minutes.

[@ElDiablo123]

the best tutorial I've found! thank you!

[@jyh8238]

god bless you. You are genius. The world need you, guy!!!!!

[@batmandevil9489]

Hey would you know how he simplifies the equations. I'm bad at algebra so im a little lost

[@shreyabathla5030]

You are great at explaining!! Thank you so much♥️

[@harrysingh5838]

Wow, I finally understand. Thanks

[@BLVGamingY]

Question, in the previous lesson you gave the example of battling a mind reader to make sense of why people would want a cooperative strategy. My guess is that mixed strategy nash equilibriums are used when both players are mind readers, and so they both want to cooperate. How would you calculate your pay-offs if you weren't a mind reader but your opponent is? Does it make sense to assume the worst outcome (the case in which the opponent is malicious)?

[@manaphylv100]

The whole point of equilibrium is the best choice goes in a circle. Say you are Player 1, and you'd want to choose down to avoid losing points. But, P2 also recognizes that, and so has an incentive to choose left to try to win points. Then you may want to take the chance once in a while (i.e. 1/6) and choose up for 3 points, and that makes a circle. If both players just want to play it safe, they will get 0 every turn by choosing down and right, then there will be no point in playing the game.

[@Jr-xs9hy]

Explained so well. You're amazing!

[@Tom-si1tv]

Im curious why the expected utility is not calculated by multiplying the probability of the column and row?? For instance, if we apply the solution to the game, the expectation value for player 1 to go up(1/6*1/3*3+1/6*2/3*-2) isnt equal to going down(5/6*1/3*-1+5/6*2/3*0).

[@Loteksolutions]

Quick question... what are the implications of the EU for each player if they are choosing best responses? For example, with the payout matrix in this video, assuming both players play their mixed strategy Nash eq, Player 1's expected utility is -1/3, and Player 2's is 1/3. Does this mean player two wins most of the time?

[@2012toby1]

Second, you have to be clear what Nash Equilibrium means, as William said before, it's when no player in the game have incentive to change their strategy, however, under your suggestion, where player two choose right and player choose down, then player 2 will have the incentive to move left because it's better off for her, and under that condition, player 1 now want to move up.....we implement mixed strategy because there's not strictly dominate strategy.

[@antman7673]

Listened to all videos from the start in one go. As someone with a math background I can follow the train of thought easily. But I keep thinking it is only important to recognize how to model each situation accordingly. And it greatly depends to have the complete picture. If someone had the intentions to win in some games, immensely complicated structures and patterns can arise on how to deviate strategies. To me game Theory seems to be about the simpleton games, with easy clear pictures.

[@Vipin_129]

Nice presentation , well explained. Thanks

[@crakzgaming2438]

Thanks for a great video, this will help me with my exam :)

[@Gametheory101]

But if player 1 is always choosing down, then player 2 should switch to left. The MSNE is the only set of strategies that breaks this cycle.

[@arman_gokalp]

This is super helpful. thank you

[@AdamRab-pu4ul]

I've seen this done with Matrices, and I think it just looks a lot simpler on screen and easier to understand. Although, I'm pretty sure the exact method I saw only works for total conflict.

[@waynerooney4674]

fantastic lessons mahn..tysm

[@kieranive8763]

jeez. my brain hurts but I'm a hell of a lot closer to getting this than I was after my lecturer tried to explain it. thank you.

[@nativechatter999]

Imagine that you're player 1. Then the goal is just to randomize which moves you make so that player 2 gets the same payoff regardless of which move they make.

[@diegoaguinaga4182]

BEST TEACHER EVER!

[@sakshamagarwal5994]

One question in this mixed probability why would the red player ever choose anything apart from right , he has a positive expected utility (either 0 or 2 for the 2 choices of blue player), is it something like it isn't the maximum expected utility ?

[@lordbob5000]

Hey, I know it's been awhile, but I was pondering this as well. I think i figured it out. If player 2 only played right (because they either win 2 or 0), then player 1 could just play down (both players win 0). This is an improvement for player 1 (under MSNE player 1 was winning -1/3, now winning 0) and it's worse for player 2 (was winning 1/3, now winning 0). Thanks for the comments everyone! It helped put my thoughts in order and come to this conclusion.

[@ginchung4092]

thank you for your video i learn a lot in this

[@manaphylv100]

Well, that is because P1 has a negative "net return" (or whatever you call it) of -1/3 in this game, i.e., he is expected to lose -1/3 every turn. But he still has a different best response to every choice P2 makes, since 0 is better than -2, and 3 is better than -1. Sorry I can't explain it very well, but the word "equilibrium" in this subject does not indicate a "fair game," and I think this is what you are getting confused with.

[@JoeyBurbs]

William 4 president

[@Gametheory101]

Joey Burbs I'd rather be the shadowy backroom figure. :)

[@spectacledpikachu6391]

You deserve so many more subs man!

[@Gametheory101]

One at a time!

[@A.S-k7d]

So at 4.07 for example: When he says sigmau (-3). Is it a fonction`? or is sigma just like any other variable x?

[@Gametheory101]

Nice. Good luck. Tell your friend!

[@nwang9573]

if the (5/6,2/3) is also a Nash Equilibrium

[@fabiocoelho1381]

does this mean the best outcome you can aim for is to make your opponent indiferente between his strategies? is it impossible to devise a strategy that will make you win more than 50% of the time? that's a bit frustrating =p

[@ZemanTheMighty]

Well zero sum games never get played on a 2×2 grid (;

[@putskan]

Hi ! after geting to vid num 20, i got back in order to fully understand. i don't fully get the mixed strategy thing. if P1 would go up 1/6 and down 5/6 of the times, then EU(L)=EU(R). however, why would P2 go 1/3 Left? he doesnt really care for the other player right? it wont get him any extra profit... in lesson 19 (Multiple Subgame Perfect Equilibria), it doesnt matter which path to take because the EU of the mixed strategy of the subgame is the same as the EU of getting out. what assures us to gain the same EU in the mixed strategy? y would the other one go for the mixed strategy if it doesnt matter what he chooses? thnx so much for the videos! subscribed already

[@Gametheory101]

putskan At the risk of answering your question with another question, why *wouldn't* the player select the equilibrium mixture? She's indifferent between his pure strategies. So choosing 1/3 left is just as good as every other choice. However, unlike every other strategy, picking 1/3 left ensures that player 1 cannot exploit her strategy. That makes the MSNE strategies much more salient than any other strategy combination. For example, if this represented payoffs for soccer penalty kicks (which is an example in a later lecture), not picking the MSNE as a striker would allow the goalie to counter your aiming choice, resulting in fewer goals being scored. Picking your MSNE strategy avoids that.

[@putskan]

think i understand. thnx alot!

[@noneofyoureffingbizness5806]

ok player 2(left-right) i claim is better here.and the reason why is his strategy can be to 100% choose right. in this way he either draws or wins,which means he has nothing to lose. and even if you use your MSA, all you do is "minimize" your loss. am i correct?

[@remavas5470]

Alex Kalder if p2 is always right, p1's best response is down, so she would end up getting 0, and would want to play another strategy

[@plushloler]

I am slowly starting to understand

[@Luden0906]

you explain better than my prof. :D

[@bobvance9519]

This may be an odd question, but how do mixed strategy equilibria behave when the players are irrational?

[@sarpcakc56]

amazing vid.

[@mankey2919]

Is the sigma is needed? Or no, it could be represented by any variable?

[@Dururugi]

Thanks Bud!

[@borntorun9492]

This algorithm to calculate the probabilities only works for 2x2 games. In NxN (N>=3), it only works if the probabilities for all strategies are non-zero. It is possible however to have a strategy in the NE with zero probability that is not dominated (strictly or weakly). Please someone correct me if this is incorrect.

[@ingelodder27]

+Balazs Rau I solved a 3x3 matrix with this strategy but I don't get when it works and when it doesn't...

[@mannusharma9227]

I think this will be other way around, when player 1 plays with probability 1/3 and player 2 plays with probability 1/6

[@Elfmonkeyjacks]

Cool video! Weird question here! How does one find a mixed Pareto strategy. Apparently, it exists. I can’t find anywhere online on how to algebraically solve for it. Apparently involves using probabilities to compute average outcomes for each player, and then using these as points in the normal Pareto definition. Does anyone know how this is accomplished?

[@abhishekkapoor2062]

if player 1 sticks to above nash equilibrium (i.e. Up= 1/6 and Down = 5/6) but player 2 changes her strategy to Left = 1 and Right = 0, then player 2 earns [ -3*1 + 1*5 = 2 points] every 6 rounds(on an average ) which is more than what she would get from the above nash equilibrium point. Does this not defy the basic definition of Nash equilibrium point ?

[@Gametheory101]

Where did the 5 come from?

[@abhishekkapoor2062]

​@@Gametheory101 Assuming they play 6 rounds of the game, player 2 would earn [-3 points * 1 round + 1 point * 5 rounds = 2 points]. Please remember that Player 2 has modified her strategy to Left = 1 and Right = 0

[@abhishekkapoor2062]

The number '5' comes from the fact that Player 1 would pick 'Up' 1 time and Down '5' times, if they play 6 rounds of the game.

[@vrbic207]

Can anyone explain to me how is possible to be better for player 1 to play up in 1/6 cases and down in 5/6 cases, when profit is negative? Does it mean that the player 2 has better position? And globally will be winner with positive profit? What about situation, when both players play randomly ie with probability 1/2 for any choice? It leads to draw.

[@alessiodenny6123]

outstanding !!

[@gauravbhootna4475]

hey, can u explain me wlehat is the use of learning this game theory???

[@juliasturz2986]

Thank you so much / saved me

[@mikyjo2012]

That was amazing

[@aa1944-k2r]

thx it helped a lot!

[@XtremeKillah101]

Hey william, can i run the mixed strategy algorithm on a game that has strictly dominated strategies? Or should i eliminate the strictly dominant strategies through IEOSDS first then run the algorithm?

[@Gametheory101]

You should just eliminate a strictly dominated strategy whenever you find one.

[@XtremeKillah101]

@@Gametheory101 ok thanks, I think i aced the mixed strategy question on my midterm because of this video

[@2012toby1]

you are trying to switch this question to a purely probability one, however you should note that if both players implement their mixed strategy given the condition they are playing infinite times of game, the probability won't matter, no matter if it's 2/3 or 99/100, the concept of infinite automatically ignores your finite number of probability.

[@2012toby1]

I see what you mean. But there are two fundamental flaws. First, in game theory games, players always try to maximize there own interest, and in economics (which game theory is a sub-subject of), there's something called opportunity cost---when you can earn 2 and you just choose to get 0 to be safe, is the same as choosing -2 when you don't have to pay anything.

[@gk4539]

can you do a plot of best responses?

[@lololo87113]

Thank you

[@mankey2919]

Also, would the equation still be valid if the pay offs was different?

[@anuragmukherjee1014]

Yeah but the function of probability up and probability left will be different. EUl will still be equal to EUr and EUu will still be equal to EUd when calculating the mixed strategies for both players. I hope this helps.

[@MrTravis0901]

Why can't player 1 always choose "Right" in the mixed algorithm? If player 1 chooses right, he will never suffer any loss. If P1 chooses right and P2 chooses left, P1 gains 2. If P1 chooses right and P2 chooses down, then P1 gains none making P1 have no risk at all.

[@MrTravis0901]

My apologies, Switch P1 and P2. What I refer to as Player 1 is red player and Player 2 as blue player, however they are labelled differently in your video.

[@janestewart5537]

I know this response is late, but P2 wouldn't exclusively choose "right" as they can still have a gain when P1 plays "down" (1 vs. 0), meaning that they're not at equilibrium. Also, if P2 only played "right", then P1 would change their strategy to only play "down", which would yield a game with no gain or loss to either side (kind of boring).

[@52bicycles]

For that course we're graded by ranking. To maximize my scores, I keep a low friend count as this minimizes any help I have to give due to the laws of the unwritten "friend code". Thus, your original reply was more valid. :)

[@xpduelist1312]

This is going to sound bad. but how did you get 6sig(u) = 1? i'm completely lost...

[@Gametheory101]

It's algebraic manipulation of the previous line. Nothing fancy.

[@KozzmoKnight]

I'll be honest, it took me awhile to figure it out, I'll substitute q for sig 3Ql - 2 + 2Ql = -Ql 3Ql + 2Ql + Ql = 2 When you reverse sides a neg becomes pos, vice versa 6Ql = 2 (Its been over 25 years since I took algebra, so I'm proud to have figured this out)

[@elmo1846]

No, that's not how he did it. Substituting Q for sig: -3Q + 1 - Q = 2Q -3Q + 1 = 3Q Here all you do is add the Q to the other side 1 = 6Q Now add -3Q to the other side to get 6Q Q = 1/6 Divide Q by 6 to get Q = 1/6

[@sherryflavour3791]

Omar Soliman thanks

[@quijadajr]

what if the game is 3X3 matrix, how you assign probability ?

[@Gametheory101]

Game Theory 101 MOOC (#37): Mixing among Three Strategies The math gets complicated very quickly outside of 2x2 games. I have a couple more examples and tricks in the textbook, but it's not easy.

[@motazart5961]

Is it just me or does he sound like a non-nasal version of Jesse Eisenberg? Anyway..thanks for the uploads Mr Spaniel. :)

[@adtseven]

I wish you were my college prof

[@winnieng6225]

you using sigma is a bad choice. you could use (x) & (x-1) which is not so confusing.

[@Gametheory101]

And by friend, I mean friends. =/

[@bumpinugly4985]

Playing around with this by use of a random number generator, keep getting utility values that equal out to zero. Ugh

[@orbayasdmasldmk]

Dude great video but you talk too fast.

[@naeday6614]

I'm stuck! 😃

[@NoName-kr3se]

I got it (after watching about three times XD)

[@thomasmatthews80]

Ah indifference. Central to GTO poker

[@daddydsg4827]

First time I clicked on this kind of video. Let's just say I need a dictionary. And a lot of help.

[@Gametheory101]

Definitely want to start at the top of the playlist!

[@zes7215]

no such thing as hapx or not about those, hapx no matter what

[@ivang5388]

I think u over complicated things. Write out equations with x equations with y, set x to x, y to y and solve

[@danielx40]

Isn’t this amazing…😮

[@FG-fc1yz]

1:30!!!

[@alem4you]

What if the game is not zero-sum?

[@Gametheory101]

Works the same way (if an MSNE exists).

[@chickybeefmoore8638]

Great work but I still suck at math haha

[@Gametheory101]

That may be the case, but congratulations on moving into first place.

[@Blossoming_Fate]

I don't get this. the equations broke me. fffffaaaaaaaaaaaaaaaaaq meeeeeeeeee

[@liworren9749]

omg this has helped me so much for my ee btw check out my MC lets play videos!

[@delelegndesalegn7036]

Great video Will, but I get confused as you begin to describe the mixed strategy for each player. Why do we calculate the expected utility of player 2's options when we're calculating the mixed strategy of player 1? I understand the concepts and the content of the video, it was really well explained, but in my mind I feel like player 1's mixed strategy should be called "player 2's mixed strategy" and vice versa. Could you help me clear up this