Module 7: Nash equilibrium | Highlights and Annotations by Gistr.

This video explains game theory concepts, focusing on eliminating dominated strategies to find predictable outcomes. It highlights that eliminating strictly dominated strategies yields consistent results regardless of order, unlike weakly dominated strategies. The video then introduces Nash Equilibrium, a more robust solution concept where no player benefits from unilaterally changing their strategy, illustrating it with examples where dominant strategies don't exist. Finally, it establishes a hierarchical relationship between strictly dominant strategy equilibrium, weakly dominant strategy equilibrium, and pure strategy Nash equilibrium. example. So suppose there are two players, and both of them have three strategies, player one has T, m, and B, top model, middle and bottom, And the player 2 has three strategies, L, C, and R, left, center and right, and the utilities are as shown in this in this matrix. Now, first, let us try to identify which are the dominated strategies. So in player 1, let us see first that the strategy t is a dominated strategy. Why? because there is a, there is another strategy, but of the same player m, which quickly dominates it. So it is a weekly dominated strategy. So if you look at these components, you see that this is actually weekly dominating the ah, the strategy T. So, in this elimination, we are first removing this particular strategy. So we are going by this order 1. And then after that, we will go to 2. And in this particular order of this process is known as the elimination of dominated strategies. So in order to do this elimination, we also see another problem in which order over these players and the strategies we go to, to eliminate these dominated strategies, So there are multiple players in which order should we go over these All right, so with dominated strategies, one, one of the fundamental question that we can ask is whether that exists. So far, the examples we have seen, they are very special examples. And we have always seen either weak or strictly dominated strategies exist. And also, sometimes the dominant strategy equilibrium So we are going to ask that question. So I am going to give you two examples, where it is not guaranteed, in fact, dominant strategy, or dominant strategy equilibrium might not exist in a normal form game. So here are two examples. The first game is called the Coordination game. So why coordination? It says that if both of the players are choosing the same strategy, then both of them get some positive payoff. Otherwise, they get zero payoff. Think of this as a, as driving on on a road. So if both the both the cars are driving on the left, left side, so they are coming towards each other, then they get some kind of a positive payoff, because they can then pass through. If one drives on the left and the other drives on the right, then none of these cars can move. So they get zero payoff. So that is a coordination game. Now, the question is, do there exist any dominant strategy here? And the answer is no, Because if you pick, the other player is picking the strategy L, then for you, for player 1, it is better to choose the strategy L. But if the other player is playing R, it is better to produce the strategy R. So there does not exist any specific strategy, which is strictly better or weakly better, irrespective of what the other player is choosing. So this is, this is one example, where dominant strategies does not exist. none of these players have any dominant strategy. And therefore, it does not also have a dominant strategy equilibrium quite Let us look at a different order of elimination. So now we see that in the first case, we started with T as the elimination order. Now, we can see that even B is a weekly dominated strategy by the same as the same strategy M, it weekly dominates it. So therefore, we can remove B first. Now, once we remove B in the reduced game, now, it turns out that the L, ah, the strategy L is actually a, ah, dummy netted strategy weekly dominated strategy, um, by ah, interestingly, by the strategy r in the previous elimination order, R was being dominated by L, but now L is being weakly dominated by R. So L is dominated because this numbers are larger, and this is equal. So this is the, this is the fallacy that happens when you are uh, dealing with weakly dominated strategies, uh, based on the order, the strategies that you are eliminating might get, uh, interchanged And therefore, you are going to remove L from the system. Now, in the, in the reduced game, again, yeah, you have this smaller, smaller set of strategies for each of these players. Now, you can see that C is a dominated strategy, C is dominated by r again. So you can remove C as well. Once you do that, there are, there are only two strategies, you, the two strategies for player one, and T is a dominated strategy. So you end up having m comma r. So here, the outcome is completely different, and the utilities are three comma What we do is, uh, what is called the refinement, refine the equilibrium concept. Ah, we are going to define a new equilibrium concept. So, this is one of the most celebrated equilibrium, and it is named after the inventor John Nash, who discovered it as part of his Phd thesis. So this is called Nash equilibrium. So the intuition, or the, ah, the principle here is that no player gains by a unilateral deviation. So in the previous game itself, you can think of that, why is L and L, not a good outcome, not a predictable outcome, if you ever end up having in that kind of a situation where both the players are choosing L, there is no reason for any of these players to go and pick any other action. Because if they do, then they are only going to lose, it is something like a local maxima point where any unilateral deviation will be bad. And that is actually captured by this Nash equilibrium concept. So, how does it, how is it defined formally? So a strategy profile, s I star, and s minus i star. Now, we are using the shorthand notation, you, you can expand this to denote s i star and all the other strategies of all the other players. This is called a pure strategy Nash equilibrium. And note this pure strategy, at this point, we are just talking about s i stars, which are just elements of this set capital S, I. So that is why it is a pure strategy. The, the players can only pick them in whole or none at all. But they cannot mix the strategies, which we will be discussing later. So this strategy profile s i star is minus i star is a pure strategy Nash equilibrium. If for every player i in n, and for all s i in in capital s i, the following thing happens that if all the players are committing their strategies to be, to be this equilibrium strategy, that is s, I start s minus i star, then if only player i moves from s i, to s, i, start to s, i, then they will never be better off. So their utility can go down or stay the same, but it will never increase. So this is the the definition of Nash equilibrium. If we can find such kind of a strategy profile, then we will call that a pure strategy Nash equilibrium. Now, we can look at the football or cricket game. And you can clearly see, according to this definition, which of, ah, is there any, ah, Nash equilibrium, pure strategy Nash equilibrium in this game, maybe pause for a while and think about it. So let me give you the answer, Ah, the, you can see that this strategy f comma f, if you, ah, consider that you can apply this definition and see that it, this is indeed, ah, pure strategy Nash equilibrium. Why? because if, if you ever end up in in this in this strategy profile, player 1, uh, gets no benefit by deviating from that to to c. So in other words, if you look at u1, and you write down f comma f, this is certainly going to be, in this case, it is strictly greater and greater than u1. When he, player 1 is changing his strategy to c, and the other player is still holding on to the same strategy. Similarly, for player 2 as well, if you look at f comma f, it is getting a payoff of 1, which is strictly greater than if we deviates when player 1 is still playing the same strategy. And it is deviating to cricket. So certainly, this is a pure strategy Nash equilibrium. Now, and we call this a best response view. So a best response, let us first define what is the best response of a player, the best response of player i, against the strategy profile s minus i of the other players is, is a strategy that gives the maximum utility. it could be a set. So it could be a not only one strategy, but a bunch of strategies, but that together will consist the best response set for player line. So we denote that as, as this notation B, i of s minus i, which means that it is the best response set of player i, when the other players are choosing the strategy s minus sign, and how is it defined? These are those strategies in its own strategy set, where if you play those strategies, they are going to be at least as good as any other strategy in this, in the strategy set for that player. So in, if you look at this specific example, so here you have only two players, so let us say I have, so player 2. so I am looking at player i, which is equal to 1. And suppose the other player s minus i, which is equal to s 2, in this case, is choosing the strategy of C, right? If there are more players, then it would have been a strategy profile. But here, there is only C, then what is the best response set for player 1? Clearly, that best response set will have only one element, which is C, because this is the strategy, which is actually better than any other strategy In, in its own strategy set, when the other player is playing s minus i, which is equal to C. So if the other player is holding on to the strategy c, then the best response set is only lying here. And therefore, C is the best response set for player 1.. now, in that case, PSNE is is a strategy profile, s i star is minus i star, such that this si star belongs to that best response set When the other players are playing this s minus i star, right? So, according to this definition, this is just reformulating the same definition. And in in in giving this definition, I have already given a hint in the previous example, which other strategy is a best response strategy. But notice that this condition has to hold for both the players. I mean, for all the players in this set n, it is not sufficient that you check this property for only one player. And you cannot conclude that this is a PSNE, your strategy Nash equilibrium, you will have to check it for every player. If that holds, then you can call call this a Nash equilibrium. So, ah, PSne, we will argue that it gives some kind of a stability. So no player has any reason to unilaterally deviate from this Nash equilibrium profile. Now, we have actually defined three different kinds of equilibrium concept, as we have defined the strictly dominant strategy equilibrium, the weekly dominant strategy equilibrium, And also now, the pure strategy Nash equilibrium. ah, can you say something like a relationship? does any of this equilibrium concept imply the other equilibrium concept. So if you start with an SDAC, you can clearly see by the definition that SDAC is also a weekly dominant strategy equilibrium, just that some of the conditions of the weekly dominant strategy is not at all necessary. I mean, the inequalities, where it is also meeting with equalities is just absent. But that also, I mean, that is well within the definition of weekly dominant strategy equilibrium. And also, if you look at the definition of weekly dominant strategy equilibrium, you can see that that definition also follows. ah, the definition of pure strategy Nash Nash equilibrium. So in other words, we are actually weakening our equilibrium concept. The objective of game theory is to identify a reasonable outcome for a given game. This involves analyzing strategies and eliminating dominated strategies, which rational players would avoid because better alternatives exist. The goal is to simplify the game to find the most predictable outcome. However, not all games have dominant strategies, so more refined equilibrium concepts, like Nash equilibrium, are needed to predict outcomes in such cases. , Nash equilibrium focuses on situations where no player benefits from unilaterally changing their strategy. A pure strategy Nash equilibrium is defined as a strategy profile where no player can improve their outcome by unilaterally changing their strategy, given that all other players maintain their strategies. In simpler terms, it's a stable state where each player's choice is the best response to the choices of others. Its significance lies in its ability to predict the outcome of a game, even when dominant strategies are absent. , It represents a point of stability where no player has an incentive to deviate from their chosen strategy. Nash Equlibrium The Problem Statement A rational player avoids a dominated strategy because there's always a better alternative available. A dominated strategy yields a worse outcome than another strategy, regardless of what the other players do. Therefore, a rational player, aiming to maximize their utility, would always choose the superior strategy.