Summary 18. Imperfect information: information sets and sub-game perfection - YouTube (Youtube) www.youtube.com
11,330 words - YouTube video - View YouTube video
Speaker 0 So today, we have a lot of stuff to get through, but it's all gonna be fairly formal. We're not we're not we're not gonna have time to play a game today. So it's gonna be day we have to learn some new ideas. So the reason we need to go through some new formal ideas today is we've kind of exhausted what we can do with the ideas we've so far. So just to bring us up to date where we are, in the first half of the semester.
Speaker 0 So before the midterm, we looked at simultaneous move games added And 1 way thing about there's simultaneous move games were games where when I take my when when I make my choice, I don't know what you've done. And when you make your choice, you don't know what I've done. Right? And since the midterm, we've been looking at at simple examples of sequential move games, sequential move games under perfect information in which I typically do know what you did when when I get to make my choice. Alright?
Speaker 0 And you know I'm gonna know what you did when I get to make my choice. And what I wanna able to do moving forward is I wanna be to look at strategic situations that combine those 2 settings. I want about to analyze games, which involve both sequential moves and simultaneous move games. Alright? And and in particular, I wanna see how we can extend our the technique we've been focusing on for the last few weeks, which is back with induction.
Speaker 0 Want us to see how we can extend the notion of rapid induction to cope with games where some parts are sequential and some parts are simultaneous. Alright? We're gonna look at a lot of examples and we're going introduce some new ideas and I'm going to try and walk you through that today. So that's our goal. Let's start with an example.
Speaker 0 So So here's a very simple game in which player 1 moves first and has 3 choices, let's call them up middle and down. And then player 2 moves and player 2 has 2 choices from each of these nodes and we'll call the choices suggestive up and down up and down, and he will just call them left and right. And the payoff as follows, 400 04:04 04:01 200. So this is just a standard gave of perfect information. Much like all the games we've seen since the midterm a roll easy 1.
Speaker 0 So we know how to solve this game. We solve this game using what, using Backward induction. And that isn't so hard here, we know that player 2, if player 2 find herself up here, she will choose 4 rather than 0. If she finds herself here, she'll choose 4 rather than 0. And if you finds herself here, she'll choose 2 rather than 1, So player 1 won't want to go up here because he'll get 0 and he won't want to go into the middle because he'll get 0.
Speaker 0 And he won't wanna get... If... But if he goes down, player 1 will choose left and and play player 1 will get 1. So player 1 will choose down. So backward induction predicts that player 1 chooses down and player 2 responds by choosing left.
Speaker 0 And just staring at this a second, notice that the reason in this game is taking a step back from back conduction a second, the reason player 1, did not want to choose either up or middle was because that move was gonna to be observed by player 2. And in either case, Player 2 was gonna crush player 1. Right? So if player 1 went up, player 2 was playing this sort of strip competitive game with player player 1 and player player 2 could design it could bigger a choice that gave 2 4 and 1 0. And conversely, if player 1 chose middle, player 2 could crush play player 1 by choosing up which gave once again, player 2 4 and player 1 0.
Speaker 0 So there was a good reason here. To avoid going into the part of the game following upper middle, and the reason was 2 was to had a huge second mover advantage in those parts. Of the game. That cleared to everybody. So I now want to consider a similar but importantly different game.
Speaker 0 So I'm gonna draw the game again for But before I write it what Gonna do. So I I wanna introduce a new idea, and the new idea is gonna to be that play 2, the player 2 will not be able to distinguish between up or middle. Just to said again. So if if player 1 chooses down, player 2 will observe that, just as we've done before and put under in our standard perfect information games, But if Player 1 chooses either up or middle, I want to capture the idea that player 2 doesn't know which of those 2 choices was made. Right?
Speaker 0 Let's clearly gonna change the game a lot? And the first question is how do we represent that idea in a tree. So let me try and show a good way to represent that in a tree. Let's So the game has the same structure to it. Player 1 is again choosing between up Middle and o down.
Speaker 0 And player 2, once again is choosing here, up or down, up or down and here, left or right. And the payoffs haven't changed. They're still 4004400412 and 0 0. So that's exactly the same as you have in your notes already, But now I want to to adapt this tree to show how he indicates that player 2 cannot which cannot observe whether 1 shows up or middle, but can observe if player 1 has chosen down, the way we do that very simply, we draw a dotted line between the 2 nodes of player 2 between which 2 cannot distinguish. So this idea here, what this dotted line indicates is that these 2 nodes are set in the same information set.
Speaker 0 So our new idea here is the idea of an information set. 2 I did. I did. I did I did. Thank.
Speaker 0 0 4. For 0. Thank you, Ring. Alright. Prepared be the same on the left is on the right.
Speaker 0 Alright. So the idea here is that 2 player 2 cannot distinguish these 2 nodes. Player 2 knows, that she's in this information set, she knows that player 1 must have chosen either up or middle. She knows that player 1 did not choose down, but she doesn't know whether she's really here or here. Okay?
Speaker 0 Now what happens in this game? This game is a very different game. Why is it a different game? Well, let's trying to apply that form that loose intuition we applied what we talked about before? We said previously in the old game, that if player 1 shows up 2 new that player 1 had shows up and observe that by choosing down, Player 2 could crush 1.
Speaker 0 And if player 1 chose middle, player 2 could observe the player 1 and chosen middle. And this time Choosing up, could crush 1. The problem is that now in this new game, player 2 doesn't know whether he's here whether she's here in which case you would want to choose down or here in which case you'd wanna to choose up. Alright? So player two's choice is not so obvious anymore.
Speaker 0 That simple back conduction argument has disappeared. Moreover, player 1 knows that player 2 will not be able to reserve between upper middle So it isn't necessarily the case that player 1 will want to choose down anymore. It's still true that if player 1 did choose down, so player 2 would be able to observe that and we'll choose left. So that part of the argument is the same. What do we think is gonna to happen here that Well, we don't know, but let me give a suggestion what might happen here.
Speaker 0 Player 1 might say, hey, I could randomize between up and middle. I could choose half the time up and half the time middle. If I choose half the time up and half at time middle, player 2 isn't gonna to know general isn't isn't gonna know what I've done. Is isn't quite clear what player 2 is gonna do. And since I'm random randomized between upper middle, whatever player 2 is gonna do, I'm gonna get half the time 4 in and half the time is 0 for an expected value of 2.
Speaker 0 Alright? I said again, so player 1 might decide in this game and to randomize 50 50 between up and middle, knowing that half the time, therefore, he will get 2 4 and half the time he'll get 0, for an expected value of 2, which notice better is better than he got by choosing down. Alright? So this change in this game, changing the information in this game, not only to a different game, but it led to a very different outcome. Alright.
Speaker 0 So here here 1 might For example, then might randomize between, up and middle. And over here, we know exactly what 1 does. 1 chooses down. Run chooses down. If we get very different outcomes because of this change in information in the game.
Speaker 0 And the theme of today is that information is gonna matter. The way we're gonna model information is by thinking about these information sets, And as we go through today, I want to start giving you some formal definition. So this is the idea. Now let's look at the formal definition. Is he a lot of writing today.
Speaker 0 So I hope hope I hope you brought a notepad with some room on it. Alright. So the first formal definition of the day comes off that last example. The formal definition is the idea they want to capture, I wanna capture the idea that players down the tree may not know exactly what was done up the tree. And the formal definition is gonna is gonna go through the idea of an information set.
Speaker 0 So an information set of player I, in this case, the bold player 2, but more generally of player. I is a collection or a set if you like, it's a collection I of player i's nodes, between wit or I guess it can be more than 2. So let's say among which among which I cannot distinguish. There's a tone out that by clever use of information sets, we're gonna be able to use our technology, our technology of drawing trees to capture all sorts of interesting and increasingly complicated information settings. Alright?
Speaker 0 In this particular game, it's the case that player 1 knew that player 2 was not gonna be able to distinguish between upper middle in this tree. And player 1 knew that player 2 would be able to distinguish in the left entry. We can even use information sets in a more laboratory to capture the idea that player 1 may not know what player 2 is gonna know. But I won't do that now I'll leave that later, and you'll see some examples of that on the homework. Alright.
Speaker 0 So we have our formal definition. This is gonna be our the first of our big tools of the day, but let me just put down a few things that we have to careful about A couple of rules. So these information sets have to obey certain rules. And certain things are not allowed. Certain things are not allowed.
Speaker 0 So in particular, the following is not allowed. Here's a tree in which player 1 moves first, and player 2 does not observe player ones move. So these 2 nodes are player two's nodes between they're in the same information set. Which means player 2 is not meant to be able to distinguish between these 2 nodes. And suppose however, the tree look like this.
Speaker 0 Okay. So I claim that this is this is crazy. We couldn't allow this. It wouldn't make any sense to allow this. Can you anyone see why why wouldn't it...
Speaker 0 Why Why is this not really a sensible tree? You want see that? Why is that not a sensible tree Yeah, Don't want to grab somebody... Yeah. Just to guy behind you.
Speaker 0 That's good. That's great. Shout out.
Speaker 1 If Player 2 knows that he has 3 choices, and then he'll know he's at the top note.
Speaker 0 Exactly. Exactly. In this... Tree, you haven't put the payoffs in. But if player 2 if player 2 observe that she has 3 choices, She knows she must be in the top node.
Speaker 0 If she observe she has 2 choices, she must be at the bottom node. Right? So in this in this tree, it was supposed to be the case, that 2 didn't know whether she was here or here, but merely by observing how many choices she has she could infer whether she was at the top note or the bottom node. So that can't make any sense. So this is not allowed.
Speaker 0 So we'll put it away across you that 1. Now the second thing that's not allowed is a little bit more subtle and actually it's an interesting thing and this is just a bookkeeping. But the second thing is more interesting. So let's have a look at it. Here's a more interesting tree.
Speaker 0 Player 1 loose first, kind Player 2 observe that move. Alright and play a 2 move second. And then at the bottom of this, player 1 may have another chance to move again. So we're gonna have put payoffs in here. Player 1 move first, player 2 with second.
Speaker 0 And if player 2 chooses is down here or up. There, then player 1 gets to move again. Now I claim again that this is not a sensible tree. It's not a sensible arrangement of information sets. Can anyone see why this isn't sensible?
Speaker 0 Why is this not sound? Yeah. It's Steven. Shout it out?
Speaker 1 Player 1 knows what node he's at based on the... First toy city me.
Speaker 0 Exactly. Exactly. So to get to the upper node here for player 1, player 1 must have chosen up before. And to get to the lower node here, player 1 must have played down before. So provided that player 1 remembers his or her own move She knows where she is.
Speaker 0 Is that right? Alright? So provider player 1 can recall what she herself did earlier on the tree, she should be able to distinguish these things. We're gonna rule this out. But I just wanna make a remark here.
Speaker 0 There's an assumption in rolling it out, and the assumption is we're assuming... So perfect recall or perfect memory. We're assuming perfect recall. And people don't always in the real world, players don't always have perfect recall. There are 2 reasons.
Speaker 0 And we're we're always gonna assume this. Let me just make a remark. There are 2 reasons why people might not have perfect recall. 1 reason is, like me, they're getting old. Right?
Speaker 0 They simply can't remember what they did yesterday. Alright? So, I'm driving home, I know roughly how many traffic lights I have to go through before I turn right, but I sometimes forget which traffic light I'm at, and a turn right too early or too late. Alright? That doesn't happen to you guys, but happens to me as I'm getting a bit senior now.
Speaker 0 Alright? So old age would rule out perfect recall. A more important example perhaps, is if players of games are themselves institutions. It's sometimes useful, and we've often talked about it in this class to imagine a player of a game being a firm or a country or some kind of institution in which the actual decisions may be being taken by different different actual people within the firm institutional or country. Right?
Speaker 0 And this assumption of perfect recall is saying that the players within the institution, knew what the other players within that same institution we're doing. Right? So if if we're modeling general motors, there's 1 player, this assumption is assuming that the chief Financial Officer and the chief Executive Officer, of Gm are observing each other's actions are on the same page. The left hand knows what the right hand doing. Right?
Speaker 0 We are typically going to assume that, but just to make the point, it is an assumption. Alright? And it's quite interesting to see what happens if you're relaxed it. Alright, So with that in mind, we can move to our next definition. And this is something I've referred to early on in the class.
Speaker 0 I wanna to be formal now now we can be formal. We've talked earlier on this class about the idea of perfect information. So for example, when we talked about X theorem, we talked about games of perfect information. And we said informally what this was, the game of perfect information is a game where each player in the game can observe all previous moves. That was our informal definition but we can now give a formal definition, very simply.
Speaker 0 Perfect information is is a setting. Right where all information sets, all information sets, In the tree, games of perfect information are games where all information sets in the tree, contain just 1 node. Alright. It'll be clear here. So what we're saying here is here if we have a tree in which every information set is a single statement, We basically never bother with any dotted lines, that's a game of perfect information, and that shouldn't be surprise to anybody here because that's exactly how we drew trees since the midterm.
Speaker 0 Is that right? Course, the novelty is we're now going to be allowed to look at games of imperfect information. Right The reason we're doing this is because it will be interesting as in example we have seen to think about games where information is not perfect. So what is the definition of imperfect information, imperfect information, formal definition is not perfect information. Alright.
Speaker 0 We've define what perfect information is imperfect information is the rest. In the real world, there's a lot of games that turn out to have imperfect information. There's lots of strategic situations, the where I'm gonna to be able to observe some things that you've done, but other things I won't know quite what you've done. Okay. Let's go straight to an example Alright.
Speaker 0 So I I don't think we really need to keep that definition very vocal and let's getting rid that board. Alright. Let's do an example in many examples today. Alright. So this example is gonna to be a tree in which player 1 moves first, Player 2 cannot observe this move.
Speaker 0 And sometimes, rather than nailing both of these nodes with a 2, I'll just put a 2 on the information set. Right? Just to indicate that both of these nodes belong to player 2. So player 2 move seconds. And we'll call player 1 move up or down.
Speaker 0 And we'll call player two's move left or right. Kind of suggestive. Left or right. And Okay. So what's the information set here?
Speaker 0 The information set is indicating the fact that player 2 cannot observe. Whether player 1 moved up or down. Player 2 cannot observe whether player 1 shows up or down. Now where does that matter? Haven't put the payoffs in yet, but I want a second.
Speaker 0 It matters because had this game in the game with perfect information. This information set had there been 2 information sets here. This dotted line not been there, then player 2 could have chosen separately had whether to shoes left or right at this node or left or right and left or right at this mode. But since player 2 doesn't know whether she's at the upper node or the lower node. She doesn't know where the player 1, she's up or down.
Speaker 0 She really only has 1 choice to make here, She's either choosing left at both nodes or she's choosing right at both nodes. Just to pull it back to our first example in the class, We saw the same feature there. And when we move from a game of perfect information to a game of imperfect information, we reduced the choices available for player 2. Here player 2 could choose separately up or down at these 2 different modes. But here, player 2 only makes 1 choice that has to apply to both nodes because player 2 cannot distinguish those 2 nodes.
Speaker 0 Alright. So let's have a look and see once we put some payoffs silent to what it does in this particular game. Alright. So here's some payoffs, 2 2 minus 133 minus 1 and 0 0. Alright.
Speaker 0 Once again, player 2 cannot separately choose at the upper node or the lower node, she's either choosing left or she's choosing right. But it turns out that this game is a little easier than the game we started with? Why is it easier than the game we started with? It's easing in the game that we started with because from Player two's point of view, whether she thinks she's up here, or whether she thinks she's down here, she has the same best choice in either case. If she thinks she's at the upper node then by choosing left, she'll get 2 and right she'll get 3.
Speaker 0 So right seems better. If she thinks she's at the lower node, then choosing left gets minus 1 and right gets 0. So once again, right is better. So in fact, in this particular game, regardless of whether the player 2 thinks that player 1 shows up. And hence she's at the upper node, or whether the think player 2 thinks the player 1 shows down, and hence she's at the lower node, Player 2 is gonna make the same choice in this game namely right.
Speaker 0 So notice that this particular game actually solves out ra backward induction. Rather like back production. Actually know. Even though what even though Player two's choice is a little bit more complicated because she doesn't know where she is, it's actually clear what player 2 will do. At this information side.
Speaker 0 Now if we push this forward a little bit harder, we can see why. Player 1 in this game has 2 strategies up or down and player 2 has 2 strategies. She either chooses is left or right. Notice she only has 2 strategies because she has to choose the same thing at these 2 nodes. She doesn't know where she is.
Speaker 0 Alright. Okay. So let's try up the matrix for this game and see if it looks familiar. Alright. So player 1 is choosing between up or down and player 2 is choosing between left or right.
Speaker 0 And the payoffs as follows, up left is 2 2. Up right is minus 1 3. Down left is 3 minus 1 and down right is 0 0. Downright right is there a. What game is this?
Speaker 0 There wasn't meant to be a trick question. So somebody somebody wave better arm there. What game is this? To shout it out if you like? This is prisoners Dilemma.
Speaker 0 Right? This is a this is an old friend of ours. This is prisoners 11. Again, we saw the very first day. But notice, what are we seeing here?
Speaker 0 This is Prisoners dilemma that we have seen many, many times that's almost un unbearable familiar and most of you. Right? Now here's business Dilemma as represented the way in which we talked about games before the midterm. But here is the same game This is also prisoners Dilemma, but now I've drawn in a tree. Here I do it in the matrix and here I do in a tree.
Speaker 0 Now that we have information sets, we can represent all the games that we studied before the mid term all the games that were simultaneous move games, we can study using trees by building information says. And what's the key observation here it doesn't really matter whether player 1 moves first or player 2 moves first. It doesn't really matter what's happening temporarily in this game. What matters information, When player 1 makes her move, she doesn't know what player two's is gonna do. Right?
Speaker 0 And play oh, she doesn't do what 2 is doing. And when Player 2 makes her move, she doesn't know what 1 is doing. Alright. And that's a simultaneous move game, even if time is passing. The key is information, not not time.
Speaker 0 Alright? Now on the way here, I snuck something in. I should just tell you let Sm in. I snuck in what a strategy is. I went from an a tree or an extensive form game and to a normal form game.
Speaker 0 And we've already done that a couple of times before in the class. We did it with the entry game, for example, about a week ago. Alright? But there, all we did was we define what a strategy was in a game of perfect information. And just to remind you, a strategy in a game of perfect information is a complete plan of action.
Speaker 0 It tells the player in question, what they should do at each of their nodes. Right. But now we have to be bit more careful, we can't have a strategy. If once once we move to imperfect information, we can't have a strategy tell you what to do at each of your nodes. Because you yourself can't distinguish between those nodes.
Speaker 0 Alright? We need to adapt our notion or definition of a strategy to make it appropriate for these more complicated games. So let's just adapted it in the obvious way. Definition definition. I'll just define pure strategies for now.
Speaker 0 A pure strategy a pure strategy Of player I is a complete plan of action. This is the same as before. To complete plan of action. It's a complete plan of action, what does it mean to be a complete plan of action. It can't tell me what to do it every single node.
Speaker 0 Can't can't that can't be the right definition because I can't distinguish notes. So all it I can be doing is telling me what to do at each information set. So it specifies it specifies what player I should do should perhaps is the wrong word. I say will do at each of i's information says. Alright?
Speaker 0 So you go back about a week. You'll see almost exactly the same definition of a strategy, but the previous definition told I what to do in each node, and this 1 just tells I, what to do at each information. What I'm doing is tidying up the previous definition, so we can apply it to the more interesting games we're gonna look at from now on. Alright. So now we have the definition of a strategy, we can can we can carry on the idea we've just seen here?
Speaker 0 What's the idea here? Any game you give me in the form of a tree, I can rewrite the game in the form of a matrix. I let's see some other examples of that idea. A lot of new ideas today, but some of them are just tidying up. And kind of bookkeeping and some of them are more interesting.
Speaker 0 Alright. So let's start with a tree Let's make us a slightly more interesting tree than the 1 we've seen before, actually, that's too interesting. That's. Let's go a little bit slower. So let's have player 1, have 2 choices and player 2 have 3 choices.
Speaker 0 Alright? So here's a simple tree and let's put some payoffs in, but let me just put some letters in the payoffs rather than put in numbers. Alright? So we'll call these actions up and down and we'll call this action left, middle and right and left, middle and right, and we'll call the payoffs, A1A2B1B2C1C2D1D2E1E2 and F1F2. Alright.
Speaker 0 So just to keep track of it. And I wanna show you how we take this tree and turn it into a matrix. Alright? So how do we how do we turn into a matrix? We look and say, how many strategies is play 1 got and how many strategies play 2 got?
Speaker 0 So player 1 here just has 2 strategies up or down and player 2 has 3 strategies, either left, middle or right. Again, they can't choose separately at these 2 nodes so they really just have 3 choices left, middle or right. Look leave a space here in your notebook, leave a space to the right here, and let's draw the matrix for this tree down here, Alright. So here's my matrix. Player 2 is choosing left.
Speaker 0 Middle or right and player 1 is choosing up or down. Alright. And the payoffs go in the obvious way. So A1A2B1B2C1T2D1D2E1E2 and F1F2. Alright.
Speaker 0 So everyone understand was a simple exercise to show we can go from an extensive form a tree to the normal form the matrix. That Alright. However, that was easy. Right? However, there's an interesting thing in here.
Speaker 0 It isn't obvious that this is if if I just gave you the matrix, it isn't obvious that this is the tree from which it came. Let me draw another tree if that I claim corresponds to that same matrix. Right. Here's another tree. So this other tree, instead of having player 1 move first it's gonna have player 2 move first.
Speaker 0 Player 2 better have 3 choices, and we better call them left middle. And write. And it'd better be the case that player 1 is in 1 big information set and player 1 only has 2 choices, which will call up and down. Right. That's what this matrix is telling us.
Speaker 0 It's telling as player 2 had 3 choices and player what player 2 had 3 choices and player 1 had 2 choices. So that's... True in the in in the matrix I've drawn. And let's been a little bit careful where the payoffs are. So left up, that's easy.
Speaker 0 That's gonna be A1A2 left down is gonna be D1D2 Middle up is gonna be B1B2. Middle down is gonna be E1E2. Write up is gonna be C1C2 and write down is gonna be F1F2I had to be a little bit careful where I put the payoffs, but I think that's right I just did. And notice that what I did here, I started from this tree, It was an easy operation to construct the matrix, so easy it was kind of boring. And it's not that hard to see that I can do the other way and construct.
Speaker 0 This other tree from from the matrix. This is also a tree in which player 2 has 3 strategies and play out at 1. This is all player 1 as 2 strategies. Alright. So what?
Speaker 0 What do we learn from this? Right. What does I look at this more carefully? This tree is a tree in which player 1 moved first and player 2 didn't observe player one's choice. Is that right?
Speaker 0 This is a tree in which player 2 move first and player 1 didn't observe two's choice. Right. What are we noticing here? They're really the same game. There's no difference between these 2 games.
Speaker 0 Alright? They're really the same game. It doesn't matter whether it's player 1 moving first and player 2 who's unable to observe one's choice. Or whether it's player two's moving first and player 1 who is unable to observe two's choice. Right?
Speaker 0 All the matters is that neither player could observe the other person's choice they got to move, they both correspond to exactly the same the same game. Alright? Or So what's the message here? The message is something we've talked about before in the class I'm trying to be more formal about it. The message is that what matters.
Speaker 0 What matters is information What matters his information, not time. Not time. Clearly, time... Clear time isn't a relevant thing, I couldn't know something that hasn't happened yet. Alright?
Speaker 0 So time is gonna have an effects and information, but ultimately what matters information. What do I know and when did I know it?? So the key idea that we're trying to catch his share where these information sets repeat is what did the player know and when did they know it? Right? That's a famous expression from the water kit truck.
Speaker 0 Else. Alright. Okay. Let's look at a more interesting example and see if we can actually talk about what's going to happen in these games. So by the end of the day, I want to have enough machinery so we can actually start analyzing these games and predicting what's going to happen.
Speaker 0 Alright. So as we go on, we'll get more complicated. So let's get little more complicated now. Once again, here's a game in which player 1 is going to have 2 choices, and we'll call those choices up or down. It's getting familiar theme.
Speaker 0 And once again, player 2 is gonna to move next. And now this time just keep things simple, we'll have player 2 just have 2 choices, left or right. Oh, left or right. But now Gonna make things more interesting, let's have player 1 move again. So if up right happens, then player 1 gets to move again in which case player 1 is gonna choose up or down.
Speaker 0 I'll use a little view. And a little d to distinguish it from the worms furthest on the left in the tree. Alright? It's a very simple tree player a 1 moves first, play a 2 move second. If forgot to put a 2 in here.
Speaker 0 And then if up right as a occurred, then player 1 gets to move again. Let's put some payoffs in. So let's have this be 42001400 again, and 2 4. Alright? Let's just carry on analyzing this game using exactly the methods we've been talking about in the class today so far.
Speaker 0 So the first thing I'm gonna to do is I want to turn this into a matrix. Or turn this into a matrix. And the first thing to do on on that route is to try and figure out how many strategies does play 1 have and how many strategies that play at 2 half. Alright? And before we even do that, let's try and figure out how many information sets they have.
Speaker 0 Alright? So I claim that player 2 just has the 1 information set. Is that right? Player has the 1 information set, but player 1 has 2 information says. This information set at the beginning of the game and then potentially this second information set down further down the tree.
Speaker 0 Alright? A strategy must tell you every a strategy must tell the player, what to do at each of their information sets. So the strategies for play 1, strategies for player 1, a what? Well, 1 strategy is up and then up again. Another strategy is up and then write Another strategy is down and then up, and a fourth strategy is down and then right.
Speaker 0 And notice something which we've seen already in this class before, there's a little bit of a redundancy here. These 2 down strategies these 2 down strategies force the game into force the game into a part of the tree where this node will not arrive. Put it less ground. If player 1 chooses down, she knows that she won't have to she won't have to make a choice of up or down later on, Jay. Sorry.
Speaker 0 Thank you. Thanks Jake. Alright. Let me start again, do the wrong notation. Alright.
Speaker 0 So player ones, choices are up and then up, up and then down. Down and then up and down and then down? Thanks Jake. Sorry. Alright?
Speaker 0 Now why are the 4 strategies, it's a bit of a surprise perhaps because if player 1 chooses down, then she knows she will never have to make a choice at her second information set. Nevertheless, nevertheless, we write down every... When we write down a strategy, we have to write down an instruction for every single information set. So we include both of those strategies. Strategies for player 2 here are a little easier.
Speaker 0 Strategies for player 2 are just left or right. Alright. With that in mind, let's draw up the matrix. So player 1 here has... 4 strategies, and they are up up, up down down up and down down.
Speaker 0 And player 2 has 2 strategies and they are left or right. Alright? I've everyone a okay so far. We're just basically transferring things across. And now we have to compare for the payoffs across.
Speaker 0 So up up followed by left is going to be 4 2 up up followed by right is gonna to be 0 to up up right, but easy think goes up right up, up right up is 0 0. Up left up up down left is the same as up left down. So it's again 4 2. Up down right is gonna to be up right down. So it's gonna be 1 4.
Speaker 0 Down up left is the same as saying down left. So it's going gonna be 0 0. Alright. Down up right is gonna be 2 for. Down down left is once again, gonna be 0 0 and down down right is once again, gonna be 2 full.
Speaker 0 Alright. So everyone see how I got the payoffs. I just use those strategies to tell me which way I'm going through the tree. If I combine them, it gives me an entire path and gets me to an end mode. Alright.
Speaker 0 And you can see this redundancy we talked about. We pointed out that these things... A kind of the same thing, and you can see in the matrix that the bottom 4 squares of the matrix have repetition. Right? This row is the same as that row.
Speaker 0 Right. And we're happy with that. Okay. We have a matrix. Let's analyze it by finding the Nash Equilibrium in this game.
Speaker 0 Alright? So to find the Nash Equilibrium in this game, we're going find best responses Alright? So let's start by asking, what is the best response to left. So if player 2 chooses left, player one's best response. Is either up up or up down.
Speaker 0 If player 2 chooses right, then player one's best response is either down up, or down down. Alright. We're okay so far. Alright. If player 1 chooses up up, then player 2 is going to choose left.
Speaker 0 If player 1 chooses up down, then player two's best responses to choose right, if player 1 chooses down up, then player two's best responses is to choose right, and if player 1 chooses down down, then player two's best responses is to choose right. Alright? So this is kind of slow. And I just wanna be be careful, Then slow for a reason it's we're gonna gradually get harder. Wanna be able to careful I can to see people looking a little sleepy around the room.
Speaker 0 I know it's gonna a lunch lunchtime. If you see your neighbor getting sleepy, give them a good sharp elbow. I think this is this isn't a good time to fall asleep. In sometimes sense, I'm worried you're going miss something and they're gonna get harder, and you're gonna miss things. Because Alright.
Speaker 0 So what are the Nash equilibrium in this game? We know how to do that? The Nash equilibrium must be up up, followed by left. Should I get them all. Down up, followed by right and down down followed by right.
Speaker 0 Ion is 3 Nash equilibrium. Okay. So Wasn't so such a big deal. I got 3 in this game. And if I'd simply given you this game, in the first half of the semester.
Speaker 0 I hadn't shown you the tree. You never seen this tree. I just gave you this game and said find the Nash equilibrium in this game. And gonna be a question on the midterm, We'd have stopped here. Right?
Speaker 0 We'd have said, okay, I found these nash e, Maybe you'd gone on and found mixed ones. I don't know, but essentially we we'd be down at this point. Right? Let's say again. If we started as we would have done before the midterm, with me giving you a payoff matrix and ask you to find the Nash equilibrium, then at this point, we'd be done, We'd have found the 3 nash.
Speaker 0 It's the 3 pure strategy in nash equilibrium. The problem is If we go back to the tree to the dynamic game, the game that has some action going on it and actually look at this game, it's not clear that all of these nash equilibrium are really equally plausible. Alright. Can anyone see what might be a bit imp about some of these Nash equilibrium? What's imp about them?
Speaker 0 Can you take us on this? Well, let's look at this this this game again? This game's is a little bit complicated. It's not clear what 1 should do here perhaps. And perhaps it's not clear what player 2 should do here because after all, right player 2 doesn't know where he is, and he doesn't know where the player 1 if player 1 gets to move again, he's gonna choose up or down, but, watch the but.
Speaker 0 If we get a mic on on the on on Patrick.
Speaker 1 Yeah. So if you look at it backwards, you can cross out. Yeah player 1 second choice. He's always gonna choose down. So that's 1 4 at that node.
Speaker 1 K.
Speaker 0 So
Speaker 1 then you know, player 2 is always gonna choose right because his payoff is always 4. K. So player 159)We not going to have... I mean, player 1 knows which to choose then, he's going to choose... Hey.
Speaker 0 Down. Good. So this this just walk what Patrick Said, that's very good. So if we just... If we just analyze this game in the way we've been taught to analyze trees essentially using backward induction, we first all observe that play that if player 1 gets to move again here.
Speaker 0 She'll know where she is, and she'll know she's choosing between 1 and 0, she's gonna choose down. Is that right? She's gonna choose down. But knowing this, Player 2, even though player 2 doesn't know where he is, player 2 actually has a pretty easy choice to make. He knows that if he chooses left, he either gets 2 or 0.
Speaker 0 But if he chooses his right, he gets 4. Right? 4 is bigger than 2, 4 is bigger than 0. So player 2 is actually gonna choose. Right?
Speaker 0 And given that, given that player 2 is gonna choose rights, player 1 is essentially choosing between 1, if if she chooses up, which would be followed by writing and down and 2, which would what happened if she chooses down, followed by right. So this game, we can essentially analyze through backward induction. It's not quite backward to induction because we had to add in this little piece about to not knowing where she was. But it turned out no matter where she was, she had a dominant strategy. And she had a better strategy.
Speaker 0 Once she figures out that player 1 is going to shoes down. That right? If we go back and look at these nash equilibrium, the prediction that we just got, which is what down for player 159)We right for player 2 and then down again for player 1. Right? That strategy is this 1.
Speaker 0 So 1 of these nash equilibrium corresponds to our sensible analysis of this tree. But the other 2 do not. These 2 nash equilibrium are inconsistent. With backward induction. Right?
Speaker 0 They're inconsistent with backward induction. Right? They're perfectly good Nash whenever we've giving you this matrix at the midterm you'd thought they're just fine, but it turns out both of these Nash equilibrium involve player 1 choosing a strategy up. That we know that player 1 is not gonna to do if reached. And 1 of these Nash equilibrium, involves player 2 choosing a strategy left, that in fact she's only choosing because player because she thinks player 2...
Speaker 0 Player 1 is gonna choose, oh, which in fact we just argued, player 1 is not gonna do. Alright? The people at the back right there's a little bit too much volume bouncing off the wall there. So just keep it, keep it down in the balcony. Thank you.
Speaker 0 Alright? Alright? So these 2 these 2 At Nash, they're perfectly good Nash equilibrium of the game, but they don't make any sense. Right? They're completely inconsistent with the way we've learned to talk about games.
Speaker 0 Alright. Now we've seen this before. We've saw it on the entry game. This is a much more complicated, much more interesting example. But we saw in the entry game when there was 1 entrant entering into a market that in that game there were actually 2 Nash Equilibrium and 1 of them we argued was incredible.
Speaker 0 Here it's a bit more complicated, but nevertheless, these 2 equilibrium seem like bogus equilibrium or phony equilibrium or equilibrium we wouldn't really believe in. And the reason we don't believe in them is that they don't correspond to backward induction and our common and intuitions about backward induction. Alright. So we need some new notion. The aim of the class has been what.
Speaker 0 We wanna to be able to model games that have both sequential moves. And simultaneous moves, and we want to be able to look at the games and use our techniques from both after the class. We want to be able to use the idea of Nash equilibrium from the first half of the class, and we want to be able to use the idea of backward induction from the second half of the class. But what we're learning here, is that nash equilibrium. If we just take the notion of Nash equilibrium and p it down on these sequential move games, it will produce equilibrium that don't make any sense.
Speaker 0 So we need a more refined notion of equilibrium, a better notion of equilibrium than just nash equilibrium to deal with these settings where we have both simultaneous and sequential moves We have both some perfect information and some imperfect information. Alright. That was 1 example. Let me give you a second example if that example wasn't yet convincing. Let me leave that example up.
Speaker 0 So so far, we've seen that Nash equilibrium gets us into trouble in these games, and we've seen it got into trouble because it it basically conflicted with our backward induction intuitions. Now I'm gonna to show you a different game and we're going to see it again now nash equilibrium is going to get us into trouble. Alright? This is going to be a 3 player game. We'll get more complicated as we go along.
Speaker 0 So another example, this time with 3 players. So as an example of get harder, I need to be more alert. To see if you can follow them. Alright. So this a more complicated tree.
Speaker 0 Here's like a tree in which player 1 moves first and chooses between a or b. And if player 1 chooses a, the game is over, she gets 1 and the others who players get nothing. If she chooses b, then players 2 and 3 get to play a little game down here, in which 2 moves first in this little sub game and 3 moves second. And the payoffs in this sub game are as follows, Again, using player 159)We payoff first. So there's 01100200 minus 1 and 210.
Speaker 0 Alright. So this is quite a complicated game. It's got 3 players for a start. So it's going to be a little bit hard to to draw it up in a matrix. But nevertheless, let me try and do that.
Speaker 0 So I claim that we can model this game as follows. It's a game in which Player 1 is choosing which matrix. Let's call this matrix a. And matrix b. Player 1 is choosing the matrix, player 2, is choosing.
Speaker 0 It's call them up and down. Player 2 is choosing up or down, and player 3 is choosing left or right. Alright. And notice in this game player players 2 and 3 actually can observe the choice of Ao b to start with. Alright.
Speaker 0 So let's try and put in the payoffs in the correct places. It's not always easy to do, but try. So a is easy. If player 1 chooses a, then the payoffs in this matrix are somewhat trivial. Because if player 1, chooses says a, whatever anyone else does, the payoff is 100.
Speaker 0 Alright. So some some uni interesting matrix over the head But if player 1 chooses b, then life gets more interesting, then play If player 2 chooses up on player 3 chooses left, we end up here, so that's 011. If player 1... Player 2 chooses this is 2 and this is 3. There's 2 this is 3.
Speaker 0 If player 2 chooses up on player 3 chooses right, then we're 002. Alright? This is 002 going in here. If player 2 chooses is down, and player 3 chooses left, then we're at 0 0 minus 1, okay with that. And if player 2 chooses down and play...
Speaker 0 Sort 3 blues is down, then we're down here, which is 2 159)We 0. Alright. Okay. So here's a little game player. 1 is choosing the matrix.
Speaker 0 Player 2 is choosing the row in the matrix, albeit trivial on the left hand side, and player 3, is choosing the column in the matrix again, albeit trivial on the left hand side. We don't really care about this picture very much. Alright? Okay. So now what?
Speaker 0 Now what? Well, once again, we could look for Nash Equilibrium in this game. It turns out there are lots of Nash equilibrium in this game. Alright let me just show you 1 nash equilibrium and then we'll talk about it. Alright?
Speaker 0 So I I that there are lots of National. And of of is the Nash equilibrium a up left a up left. So let's see where that is in the tree first of all. So player 1 shows a. Player 2 upper and left, but it followed at a, so we end up here.
Speaker 0 We end up at 159)We it. Alright. Right. A up left is this box in the tree. Alright?
Speaker 0 Now let's just check that that actually is a Nash equilibrium. Right? So we all know how to do this from the first half of the class to check that that's a nash equilibrium, we better a check that no individual player can do better by devi. So let's start with player 1. If player 1 deviate, holding player 2 and prefix fixed, then player 1 will be switching.
Speaker 0 The matrix from matrix a to matrix b. Is that correct? Right? So we'll move from this box, in the left hand matrix to the equivalent box in the right hand matrix. Right?
Speaker 0 And player one's payoff will go from 1 to 0. From 1 to 0. So player 1 doesn't wanna deviate. Everyone happy with that. Player 1 doesn't want deviate here.
Speaker 0 How about player 2. If player 2 deviate, holding player 1 and 3 fixed, then player 1 is gonna switch rows in this matrix, so we'll move from this box from this box to this box. Player 2 is making 0 before. She's still making 0. So she's has no incentive to deviate.
Speaker 0 And the same argument applies for player 3 because she will be choosing the column holding the row and the matrix fixed. So once again, she gets 0 either the case. Alright. So everyone happy with that That actually is an nash equilibrium Again, if this has been the midterm, I could have set this up, I could have given you these mat c's. Or the story behind them and you'd have found this you could Could have asked you whether this was a nash equilibrium and the answer would have been yes.
Speaker 0 But I claim that once again this is just not a believable nash equilibrium. It isn't an nash actually equilibrium. Fall it's nash equilibrium the, but it's not a plausible prediction for how this game's is going to be played. Why is it not a plausible prediction for how this game's is going to be played? I on see?
Speaker 0 Stare at the tree of it. Right? So in in the information here, the pre midterm information, it's fine. But knowing about the actual structure of this game, I claim this makes no sense at all. Why does it make no sense?
Speaker 0 Well, notice that if player 1 were to switch her action. From the prescribed action a to action b, then we'd be here. Alright? And notice that the tree from a here on in looks like a little game. Is that right?
Speaker 0 The tree from here on, right looks like a little game. Alright. So this thing here is put it in green. This thing here is a little game within the game. It's a sub game.
Speaker 0 Alright? And this sub game really only involves 2 players. The 2 players that it involves are players 2 and player 3. Player one's done. Player one's put us into this game.
Speaker 0 But now in this little sub game, It's an little sub game involving just player 2 and player 3. So we can analyze this little sub game. If we analyze this little sub game, what will it give us? What will we find? Alright?
Speaker 0 So let's look at this sub game. So look at the green, the green sub game. Game that would have happened, had player 1, chosen b. This is a sub game involving just players 2 and 3. So 1 they just forget player 1.
Speaker 0 Right? We know what... I mean, Player 1 is part of the game game payoffs but player 1 has made their move. They're not really involved anymore. So let's just look at this game as a game involving players 2 and 3.
Speaker 0 And let's look at the matrix. For players 2 and 3. So this is this... Actually, it corresponds to the matrix above It's it's a matrix in which player 2 is choosing up and down. Here it is up and down.
Speaker 0 And simultaneously, player 3, is choosing left or right. Here it is, left or right at this information says. And the payoffs are 1 01:02 0 minus 1 and 1 0 Alright. Alright. So this is a claim, a representation.
Speaker 0 Of this little green game. That's should put this in green as well. Alright? This thing corresponds to that thing. Alright.
Speaker 0 Everyone okay with that. Alright? So if player 1 had chosen to... A chosen b rather than a, then... We'd be involved in little game, a game within a game or a sub game involving in just players 2 or 3, and we can analyze that game.
Speaker 0 It's a that's a straightforward game. Here it is. And what would we do with that game? We'd look for the nash equilibrium in that game? So let's look for the nash equilibrium in this game.
Speaker 0 So what do we notice about this game? So if player 3 chooses is left, then player out 2 would rather choose up. If player 3 chooses right, then player 2 should choose down. If player 2 chooses up, then player 3 would rather choose right because 2 is bigger than 1. And if player 2 would to choose down, then player 3 would choose right again because 0 is bigger than minus 1.
Speaker 0 Alright. So fact, in this little sub game, in this little sub game, actually, player 3 as a dominant strategy. Right? If it turned out that we got involved in this little sub game, player 3 has a dominant strategy, which is to play right. And moreover, this sub game has just 159)We Nash equilibrium.
Speaker 0 If I've given you this sub game on its own, it's clear that the Nash equilibrium of this sub game with this game within a game is down right. It's down right. So what's that telling us? It's telling us if player 2 and 3 ever get called upon to play in this game. That only happens when a player 1 chooses b.
Speaker 0 If player 2 and 3 ever get called upon to play in this game, we know from when we were young or at least from before the midterm, we know that they're going to play nash in that sub game, and the Nash equilibrium in the sub game is gonna have player 3 choosing rights and player 2 choosing down. Alright. But the equilibrium we talked about, this equilibrium we we argued before about AUL was... Doesn't... The equipment total 4, Au doesn't involve player 2 choosing down.
Speaker 0 In fact, she turns up. And it doesn't involve player 3 choosing right. In fact, she shows left. Alright. So let's sum up.
Speaker 0 This... We found an equilibrium of this game. This equilibrium of this game... Was AUL. But I claim this is not a plausible equilibrium.
Speaker 0 It's not a plausible equilibrium because it predicts that if we actually were play the game within the game, we wouldn't play equilibrium. Let me say it again. In the whole game in the whole game, a up left is an equilibrium. But I claim it's a silly equilibrium because it involves the prediction that if in fact we ever got into the game within the game we would no longer play equilibrium. And that doesn't seem right.
Speaker 0 If we're gonna believe an equilibrium we should be consistent and believe an equilibrium throughout. Alright. So this brings us to a new idea. Right. And the new idea is gonna have 2 parts to it.
Speaker 0 The first part is kind of on the board already. It's something we about informally, it's the notion of a sub game. It's the notion of a sub game. Right? What's a sub game?
Speaker 0 It's a game within a game. Right? I've been using that informally, but we need to start thinking about more formally what it means. So I talked about informally said that green objects is the game that would be played were player 1. To choose b.
Speaker 0 And we took about other sub games in this class. We talked about the sub game that would happen in the entry game if 1 of those 1 of those rival baking rival pizza companies moved in in... The Miami market or something. It was a game within a game. When we talked at the Tour France, we talked about the being game within a game that is about when you break away.
Speaker 0 And now will be formal about this notion of a game within a game and introduce some of the nomenclature. So the formal definition is this. Definition. A sub game with sub game is a part of a game Informally, that looks like a game within the tree and it has 3 properties. It satisfies.
Speaker 0 The following 3 properties. So 1, since it looks like a game itself, the sub game must start from a particular point. Right. So it starts, the sub game, must start, it starts from a single node. And let's just look at the example.
Speaker 0 In the example we just looked at the sub game started from this node here. Second, second, it comprises it comprises all successors to that node. So in our example, here's our sub game is our green sub game. Here's the node it starts from. Here are all the nodes that are successes of that node.
Speaker 0 These are the children, and these are the grandchildren. Right? You have this grandparent node, you have to have all of his children and all of his grandchildren. Alright. So it comprises all the successes of that node.
Speaker 0 And finally, this is important. It does not it does not break up. Does not break up any information sets. It does not break up any information sets. So a sub game informally, it's just a little game within the game.
Speaker 0 But slightly more formally, I can't put 1 node that's part of an information set into this sub game and I'm gonna put all the nodes that are part of that information set. Into the saga. Alright. Let's have a look at some examples. We've got 1 example up there.
Speaker 0 The entry game look something like this. Right? The entry game or something like this. So what are the sub games here? So no secrets here.
Speaker 0 This is a sub game. Right? There's actually another sub. I'm gonna see what the other sub game is. The whole game is a sub game.
Speaker 0 Alright? The whole game is itself a sub game. Somewhat trivial. So this is this this particular game, which is the end, which is the schematic of the entry game. It has actually 2 sub games, only 1 proper sub game.
Speaker 0 Alright Here's a more complicated example. Alright. This is actually gonna to be quite a complicated example. It's just make life interesting. So 1 is gonna move, then 2 is gonna move.
Speaker 0 And then 1 is gonna move again. This is all 1 big information set for player 1. And 1 is gonna move like this? So I get without payoffs, this is a little tree and the key point here is this is an information set. Right?
Speaker 0 Let's look let's stare at this tree a second and figure out what r on the not sub games. So first of all, what this was a sub game and this was a sub game. What about this thing here? Is that a sub game? It's not a...
Speaker 0 What what's what rule does it break? It's it's breaking up in information. Right? It's breaking up an information set. That's no good because of rule 3.
Speaker 0 What about this thing? That That doesn't break up an information. So. I've got the whole information said in there. Is that any good?
Speaker 0 No. That's no good because it doesn't start from a single to node that no good. It violates 1. And if we do this, we look at this piece, it's That piece there. That's also no good.
Speaker 0 Why is that no good? Again, it breaks up an information set. Alright? So this is no good again because of rule 3. Alright?
Speaker 0 So you can you can practice at home, drawing trees. And trying to identify what are anyone are not sub. Alright. So with with the definition of a sub game now formal, right? It's basically just formal something we've talked about before, is the idea of a game within the game.
Speaker 0 I want introduce our new... What's gonna be our new solution concepts and this is gonna be the solution concept we're going to use essentially almost until the final. Definition. So just remember our task is, our task is to come up with a solution concept, that picks up the idea from the first half of the semester, namely nash equilibrium, but does so in a way that respect what we've learned in the second half of the semester, namely that games have sequential elements and people move by backward induction. So in particular, what we want to rule out of those Nash Equilibrium that instruct players down the tree to play in sub games according to strategies that are not Nash c.
Speaker 0 Said again, we want to rule out those Nash That instruct people way down the tree to play according to something which is not a Nash equilibrium. We want our new notion to say, wherever you find yourself in a tree, play nash equilibrium. And that's exactly what the definition is gonna say. So a Nash equilibrium, NES1 star. S 2 star all the way up to s m star is a sub game perfect sub game perfect equilibrium a sub game perfect equilibrium, that's an s p.
Speaker 0 It's a sub game perfect equilibrium. If it induces a Nash equilibrium in every sub game of the game. Alright. So so in perfectly equilibrium equilibrium, it has to itself be an nash equilibrium, of course, But it also has to instruct players to play a Nash equilibrium in every sub game. Let's take that immediately back to our examples.
Speaker 0 In this example, in this example, we know let's bring it down. In this example, we know that this is a sub game, we know that in this sub game, there is only 1 Nash equilibrium and that Nash equilibrium involves player 2 choosing down and player 3 choosing right. Alright? So we know We know that player 2 is gonna choose down according to that equilibrium and player 3 is gonna choose right according to that equilibrium. If we now have a look for equilibrium of the whole game, let's go back to Player one's choice, player 1, if they choose a, will get 1.
Speaker 0 So If they chose b, then they know that this Nash equilibrium will be played, so they'll I'll get 2. They prefer 2 to 1, So the sub game perfect equilibrium here is player 1 chooses b. Player 2 chooses down and player 3 chooses right. This is an equilibrium of the game and it it it induces here it is. It induces an equilibrium in the sub game.
Speaker 0 Alright. So I mean, that example, the sub perfect equilibrium is found by first of all looking in the sub game, find the equilibrium in the sub game and then go back and look at the equilibrium around the whole game. The equipment we end up with, it is a nash equilibrium in the whole game, but more importantly, it induces a nash equilibrium in the sub. Let's just go back to our other example then I'll stop. So our other example was here.
Speaker 0 Here was our other example. And we claim hang on everybody. We claimed that the good equilibrium here, the 1 we believed in, was down down rights. Alright? Where are the sub games in this game?
Speaker 0 Where are the sub games in this tree? Anybody? So I claim there's only 1 real sub game here, and that's this piece? Right? This is a sub game.
Speaker 0 Alright? What's the Nash equilibrium of this somewhat trivial sub game? The mash equilibrium of this somewhat trivial sub game is that player 1 must choose down. So for a Nash equilibrium to be a sub game perfect equilibrium. Here are 3 Nash, 123.
Speaker 0 For this nash equilibrium to be a sub game perfect equilibrium, it's got to instruct player 1 to choose down. In the trivial sub game. And here it is. This is our sub game perfect equilibrium in this game. Now I know today with a lot of formal stuff, a lot of new ideas.
Speaker 0