Game Theory 101 (#3): Iterated Elimination of Strictly Dominated Strategies

Game Theory 101: The Complete Textbook on Amazon: www.amazon.com/Game-Theory-10...
gametheory101.com/courses/game...
The prisoner's dilemma had an obvious solution because each player had one strategy that was always the best regardless of what the other players do. Most games don't have solutions that are that simple, however. What if one player's best strategy depends entirely on which strategy the other player chose?
This video covers iterated elimination of strictly dominated strategies. If one strategy is always worse than another for a player, that means the other player should infer that the first player would never choose that poor strategy. But this has interesting implications. It is possible to keep removing strategies from a game based on this information, until you eventually arrive at a single solution. We go over an example in this video.
As a general rule, if you ever see a strictly dominated strategy, you should always eliminate it immediately. Although there may be more strictly dominated strategies that you could eliminate first, those other strictly dominated strategies will still be strictly dominated in the reduced game. Therefore, you lose nothing by immediately eliminating a strategy.

[@PunmasterSTP]

Iterated elimination? More like "Whoa, this is great information!" I really can't believe how amazing this videos series is, while at the same time being freely available. You sir are an achievement of the human race!

[@Gatewaycreed]

Brilliant. This is helping me get the basics so well it makes me feel way smarter than I am. Thanks so much for this.

[@Gametheory101]

The players move simultaneously. Player 2 has no choice in the matter because she has no ability to control player 1's move, and player 1 has no reason to play up when he could play middle instead.

[@NoraGreen1992]

Omg thank you so much. So helpful. It was driving me nuts.

[@isabellatoral3616]

the second example is so useful, thanks a lot!

[@kautukraj]

Beautiful explanation, loved it.

[@salomondeleeuw]

This was a great explination, so much more clear then "choice theory a shrt introduktion" by Allingham, thasnks.

[@Sheaffer72]

Thank you for these videos. You are really helping me with my decision theory class as we are spending a lot of time on game theory.

[@PunmasterSTP]

Hey I know it's been awhile, but how did your decision theory class go?

[@Sheaffer72]

@@PunmasterSTP It went really well. It was one of my favorite classes.

[@PunmasterSTP]

@@Sheaffer72 Sweet; I’m glad to hear it! Are you still studying or did you get your degree?

[@Sheaffer72]

@@PunmasterSTP I graduated last summer.

[@PunmasterSTP]

@@Sheaffer72 I'm glad to hear it!

[@Kateaclysmic]

Thank you for teaching this online for free, greatly appreciated.

[@leonekdal7070]

Well and simply explained, thank you so much!

[@grapheggspecies8907]

Would be hillarious to play as chaotically as possible to just mess with this. Great video tho

[@pingukutepro]

In real life situation or life and death you won't do that. Image if you had to play this in Squid Game

[@grapheggspecies8907]

@@pingukutepro that's fair, maybe not as chaotically as possible. Perhaps just use that as another tactic carefully.

[@lalalallaallala]

This is the reason some great players (in few cases) get beat by beginners who don't understand the strategy and get lucky picking a risky option that the good player could not predict. @@pingukutepro

[@MOLRobocop]

This is more helpful than other vids I've watched. Inference over inference over inference though, wrinkles my brain.

[@CalumnMcAulay]

your logic is flawless! I am not convinced I have the aptitude for this.

[@Gametheory101]

Most of it is time and effort. A lot of mathematical thinking is trained, not innate. I barely passed my math classes in high school before taking this up as a career.

[@EvilSapphireR]

Everyone has the aptitude for this.

[@user-nx8bj4vu2d]

The thing which u are seeing is just basic, go to advance game theory it will beat the shit out of you

[@mustafam2078]

I am loving this thanks alot.

[@Gametheory101]

Check out the next video on pure strategy Nash equilibrium!

[@mikeysbestfriend6496]

Nice job explaining this but it would be helpful if you had labeled the players on the 3 by 3.

[@andresdiaz7112]

He did that on purpose, you didn't pay attention. By destroying the rules, he made you want to get the book out of self interest now that you are interested in the subject. Sneaky bastard. Disgusting individual is the creator of this series.

[@TheCanadian0495]

This explanation was so helpful! Thank you so much. Also, did he sound like Ben Wyatt from Parks and Rec to anyone else?

[@Gametheory101]

I don't hear it. But this literally the third KZbin comment that has said this, so what do I know?

[@FuckThisShit422]

great vid, thanks

[@Gametheory101]

Entirely different, yes.

[@matthewtully4103]

Is there a physical copy of the textbook available, or is it just Kindle?

[@Robleh100]

Some of your simplified descriptions of probability theory have actually sparked me to review a topic outside my field of mathematical logic. When you mentioned negative probability it got me thinking about a paper Richard Feynman wrote long time ago, when I was math student minoring in physics. Something about that made me remember that somebody had proposed the idea of negative probability and lo and behold I searched for it and find it's there.There is negative probability in QM BTW William. It can apply to quantum states of small sub-atomic particles... the theory is so unrelated I won't delve into it here. Then you mentioned one that's bugged me for a long time x/0, the undefined operation in abstract algebra. I am starting to theorize how if this is allowed the profound implications of creating a new dimension to AA. BTW, though your descriptions are sometimes painfully simple and directed at novices, I still enjoy them.

[@beataszendrey786]

Do I have to eliminate them in case of cooperative games too? Or only in non-cooperatives

[@anggaraadhari1933]

better than any confusing textbooks

[@simonsrensen8008]

@William Spaniel when is the textbook from? I need it for a school assignment...

[@jamiemcdougall492]

what happens if there is a 3 strategy game and one strategy is dominated by both of the other 2 strategies but not by any 1 single strategy ? thanks a lot

[@user-nn4nl9lv1x]

Up down middle should be replaced with action to make this explanation more clearer..

[@thekingprajna]

Thanks a lot

[@seanoleary2348]

What if the game is fixed though?.. ok, probably a dumb question. I sort of got where all the numbers come from in the prisoner's dilemma, maybe this would make more sense to me if these numbers fit into a particular situation. Does that make sense? Sorry if I'm just being thick though. Thanks for your time and for making all these videos!

[@ajoeannabrown9563]

Why wouldn't (13,3) be the answer? The way I rationalize it, is that; P1 will never choose middle because that's the action or move that will make him absolute worst off and P2 with also knowing the information P1 knows will never choose C because he know even though he has an highest return of 4 that P2 will always be unsatisfied because 13 is a larger lost to 3 for P1 than 4 is to 3 for P2. Thus, I will rather loose 4 to 3 as player two than to let player one loose 13 to 3 ... which uses the exact same logic why neither P1 nor P2 will choose (4,1) nor (1,4) respectively. I personally and strongly believe choosing (3,3) goes against the logical or rational pattern initiated from the beginning of the game.

[@samahshohdy1396]

firstly thank you Sir for the explanation , but please why do we prefer -8 more than -1 for example if both of them keep quiet will secure at least only one month in jail for both of them instead of 8 months

[@prathiksharamaswamy5776]

very clear :)

[@jojomama020]

If we would say that the choice was between both of the players keeping quiet and both of them confessing then keeping quiet would be the dominant outcome. So could we not also, just as you did at the beginning of the video by comparing when one talked and the other stayed quiet the better outcome, compare the outcomes of both staying quiet or both confessing? If they were rational actors would they also not see that that was the best outcome?

[@sakshikumari5621]

but as per IESDS, one talking and one not is a sds so we eleminate it at once

[@edrynazarif1996]

thank you thank you thank you

[@makerc4]

what if for player 2 Center isn't a strictly dominating strategy? for example, in UP;CENTER if you have (1,2) instead of (1,4), then center isn't better than right

[@adamasadis6193]

Can we calculate here the expected value of all three choices for 2nd player and then assume that he is going to choose the option with the greatest expected value?

[@tradetor]

I outsmarted you outsmarted me outsmarted you....

[@louisyork8120]

Wonderful video. Is (3,3) the Nash Equilibrium?

[@Gametheory101]

Equilibria are strategies sets, not payoffs. So [middle, center] is the equilibrium; 3,3 is the payoff pair associated with that equilibrium.

[@louisyork8120]

@@Gametheory101 Yep, got it. Thanks! Moving on to the next video... I recently discontinued a game theory course on Coursera in favor of your game theory videos. You make it so easy and interesting.

[@krishnasaivootla8761]

Heey Thank u for the videos. A quick question. How is the win defined? is it : 1.) To get a maximum for myself or 2.) To be greater than the other.

[@Gametheory101]

Players maximize their own payoffs. If the goal of the game were to outscore the opponent, this would already be reflected in the payoffs.

[@rossentein]

Hi William... thanks for the video. i was trying out a different example. (5,9) (6,3) (-1,8) (8,-1) (3,6) (9,5) (4,4) (2,7) (7,2) i first compared C and R, and eliminated R since C dominated R by 2:1. then I removed D as it has lesser payoff in comparison to U and M. Now, I was left with - (5,9) (6,3) (8,-1) (3,6) How to proceed from here?

[@Xandr017]

you'll have to watch more videos if there isn't a strictly dominated strategy :P

[@user-nk7uc2yt2s]

I think (3,6).

[@Gametheory101]

Then you'd have to change the payoffs entirely.

[@Robleh100]

But what if they have no knowledge of their prison times? The payoff matrices should change drastically. If the only knowledge prisoner A and B are given is they can confess or not and that's all their accomplice can do is implicit. Here the minimization strategy should be to keep quiet with the rational assumption the other will too, because he doesn't know what will happen too. They do know that if they don't rat, the police can't do much to them. This is a permutation of PR. There are permutations to PT.

[@Elite7555]

Dealing with uncertainty is an entire chapter for itself. But you are completely right: not knowing the exact payoffs or miscalculating them will lead to irrational decisions.

[@simka321]

What's the application of this kind of knowledge? Can you give any historical or real world scenarios where knowing how this works has given someone an advantage or benefit?

[@friedrichnietzsche9760]

He mentions that in the first video

[@omnomnom504]

what is player one's strategic goal is to deny points to player two rather than earn maximum points?

[@teambubka]

Is the objective of the game is to have good outcomes for both the players?

[@muhammadzeshan2727]

for player 2 why do you eliminate the option of right? because i am o with its elimination when u compare it with center but if u compare it with left no strategy between left and right seems strictly dominated....

[@karmax8042]

+1

[@emmanuel5566]

*What if* the inference made by each player about other player's smartness turns out to be wrong?

[@Kateaclysmic]

I guess you'd have to figure out the other player's k-level (chat to them first if possible to figure out their intelligence) then once you think you know that, you know where they'd stop reasoning, then play your best move based on where they got to in the above logic. If you're player 1 and figure player 2 figured out to get rid of right then though, "sweet, I'll play left because it has a 9" then you'd choose up. But if they figured out to get rid of right, maybe they're smart enough to figure out that 15 is better than 13 (summed) so they're better to play centre, in which case you'd still be best to choose middle. Both of these are based on assuming player 2 doesn't think past their best move and look into your best moves. If you think your opponent is at that level, then you'll choose up or middle but still never down. If you're unsure of which outcome they came to ("9 is good, let's hope for 9" or "15 is better than 13, so my odds are better at centre") then it will depend on your goal. If your goal is to beat the other player, both up and middle are the same likelihood (50:50). If your goal is to beat or at least draw with the other player, choose middle (100%). If you're playing multiple rounds, and points accumulate, choose up because 14 is higher than 7. But if you're playing multiple rounds against the same person, expect them to get better and progress to higher k-levels.

[@omnomnom504]

oh okay, so that would mean the numerical values in the grid would be different then?

[@programmer1840]

Are the numbers arbitrary? I.e. you wouldn't take the average of the numbers on each row and use the row with the highest average? Even if it actually loses 2 out of 3 matchups? Let's say these are the two columns: 1 2 3 4 10 5 Column 2 wins two out of three, but the average result is way higher for column 1.

[@chatman-xh8le]

Are theses numbers all randomized?

[@bilalinjukuni2979]

What a teaching

[@Matthew8473]

I'm blown away by this content. I recently discovered similar material, and it was absolutely mesmerizing. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

[@ashutoshthakare3015]

Heyyy Can you help me i am having difficulty in understanding this session

[@bobvance9519]

What can we say about a scenario where both players are irrational?

[@mishthiagarwal1680]

Both players are rational players means they try maximize there reward so they are playing strict dominance but you said in #2 that rational players can never play strict dominance. Pls clear

[@wolfgangi]

Does the elimination always follow a strict order? As in player 1 eliminates a strategy, then it's player 2's turn to eliminate a strategy, then it's back to player 1 to eliminate another ????

[@thuytran-vg5vz]

It's not actual elimination. It's only logical elimination by knowing enemy's moves. He is just explaining both player's thought process. Logical elimination usually is turn based like this bc if player 1 can remove 2 strategies regardless of player 2's available strategy then it wouldn't make a game theory

[@chatman-xh8le]

Should I always choose the middle???

[@lwandilezuma2292]

So does this mean (3,3) becomes the Nash Equilibrium?

[@vamsikrishna4107]

If the two teams were aware of each other's strategies the match would end as a draw. Can I say like this?

[@peterfessel9910]

Is there a jump in the video? How did we get from confess vs. keep quiet to up, middle, down vs. left, center, right? I don't understand what game this matrix is dealing with.

[@EvilSapphireR]

This is a different game where player 1 gets to choose between 3 choices: Up, Middle and Bottom. And Player 2 gets to choose between 3 choices as well: Left, Center, and right.

[@MysteryyXasn]

You talk really fast haha, even faster than I do. Do you also sell your book in a paper version rather than the ebook format? I prefer paper books and would like to buy it!

[@Gametheory101]

I sent page proofs to a printer today. So...if everything goes well...maybe there will be a paper book in a week? The printing cost is going to make the physical book considerably more expensive, though.

[@Heymanesaymane]

Man I'm so lost. I guess it's the graph that's throwing me off.

[@user-se4jc1kn6i]

This assumes that the players are aware of each other's payouts, correct? That seems odd to me.

[@Gametheory101]

+Adam Smith The assumption is a bit less restrictive than that. For example, you would still be able to generate the same expectation if you could accurately estimate the other's payoff within a certain window. (I think plus/minus .5 works in this case.) Really, you just need to be able to accurately know how the other player ranks each of his outcomes, and you can even fudge this a little bit too. If you can't do those things in the situation you are looking at, then you are entering the world of incomplete information game theory. And you can't begin to study that until you fully comprehend how complete information game theory works. So think of this as a building block to get to empirically richer topics.

[@agb0810]

"right" is not actually STRICTLY dominated because it's better than "left" when player one does middle. I believe the correct terminology is "never a best response" so right is dominated by middle but not by left therefore it is not strictly dominated however it is never a best response because middle is always better than left.

[@Gametheory101]

"Center strictly dominates right" (or "right is strictly dominated by center") is the correct statement. "A strictly dominates B" is a pairwise comparison, and however the payoffs work for tertiary strategies is irrelevant. This can be confusing because "A is a strictly dominant strategy" is a global statement, meaning that A is better than every other strategy the player has. It took me an embarrassingly long time to get my head around this.

[@ferrafy]

But why you let player ref plays first because blue would’ve chose left

[@bryceblazegamingyt9741]

what about a 3 player game

[@erandeser5830]

Where is the fire ?

[@audreybarnes6527]

The prisoners dilemma reads well, unless you have a legal right to silence.

[@harrylinley4042]

Why does (3,3) dominate (1,4)? doesn't Player 2 dominate by deviating?

[@wwefan791]

Player 2 already has left and right elimanted. They have no option but to rationally pick the center option. The only decision left is whether P1 picks up or middle. Only P1 can choose the outcome.

[@addieh3112]

Da BaCiCs CuZ I WaNnA bE a GaMe dEvElOpEr

[@huidezhu7566]

HAHAHA, we all know that the assumption of intelligence doesn't always hold. :/

[@qwerty9170x]

"This is so stupid it just might work" -Turn based game champion, 2015

[@qwerty9170x]

"This is so stupid it just might work" -Turn based game champion, 2015

[@aychtooo3981]

Pak Huide yes but the definition of game theory is: "The study of mathematical models of conflict and cooperation between intelligent and rational decision-makers", according to Wikipedia

[@jonavuka]

it will eventually converge, meaning people will catch on eventually to the optimal strategy... you probably lost your first tic tac toe games, then eventually you figured out that you can never actually win or lose when playing optimally

[@XxxXxx-yh5gz]

Tbh, IESDS is a fracking long ass word

[@SeekingUnity]

Basically this theory assumes that both players have some intelligence to figure out their best move right?

[@Gametheory101]

Yes.

[@jck7986]

So far I just see a sudoku game wrapped in story telling….

[@quicksilver2923]

that's literally what a basic introduction to game theory is. it is in the name

[@maleagosuemohlala3274]

u r too fast sir yoh decrease your speed as you are teaching students, u sound as if u r in a hurry

[@andresdiaz7112]

Very clever how you destroyed the rules here, did not explain them, and makes people think about purchasing the book. Demonstration of very poor integrity on your part as an educator not understanding that honesty and trust is the key to long term business success. Failed.

[@Gametheory101]

Entirely different, yes.