WEBVTT 00:01.740 --> 00:04.610 Professor Ben Polak: So last time we finished up by 00:04.612 --> 00:06.932 playing the game of Nim and you'll remember, 00:06.930 --> 00:11.140 I hope, that the game of Nim was a game where there was two 00:11.135 --> 00:15.405 piles of stones--we made do with lines on the board--and the 00:15.412 --> 00:19.402 winner was the person who picked up the last stone. 00:19.400 --> 00:21.240 Remember you had to pick piles. 00:21.240 --> 00:25.660 I want to use the game of Nim to make a transition here. 00:25.660 --> 00:29.170 So what we had pointed out about the game of Nim was it 00:29.165 --> 00:33.115 illustrated very nicely for us that games can have first mover 00:33.124 --> 00:36.764 advantages or they can have second mover advantages. 00:36.760 --> 00:40.110 A very small change in the game, essentially a very small 00:40.107 --> 00:44.347 change in where we started from, could switch a game from a game 00:44.352 --> 00:48.422 with a first mover advantage to a game with a second mover 00:48.421 --> 00:51.761 advantage. Now today, I want to just draw 00:51.758 --> 00:55.288 a slightly grander lesson out of that game. 00:55.290 --> 00:58.240 So not only was it the case that the game sometimes has 00:58.235 --> 01:01.065 first mover advantages and sometimes has second mover 01:01.071 --> 01:02.761 advantages, but moreover, 01:02.758 --> 01:06.428 we could tell when it had a first mover advantage and we 01:06.432 --> 01:09.842 could tell when it had a second mover advantage. 01:09.840 --> 01:11.870 Is that right? When we actually looked at the 01:11.872 --> 01:14.872 initial set up of those stones, we knew immediately that's a 01:14.867 --> 01:16.997 game in which Player 1 is going to win, 01:17.000 --> 01:20.100 or alternatively, we knew immediately that's a 01:20.101 --> 01:22.721 game which Player 2 is going to win. 01:22.720 --> 01:26.810 Now it turns out that that idea is very general and actually has 01:26.812 --> 01:30.062 a name attached to it, and that name is Zermelo. 01:30.060 --> 01:35.360 01:35.360 --> 01:38.990 So today we'll start off by talking about a theorem due to a 01:38.985 --> 01:42.055 guy called Zermelo, and the idea of this theorem is 01:42.057 --> 01:43.997 this. We're going to look at games 01:44.003 --> 01:46.643 more general than just Nim, and we're going to ask the 01:46.642 --> 01:49.082 question, under what circumstances would 01:49.078 --> 01:51.648 you know about a game either that Player 1, 01:51.652 --> 01:54.662 the person who goes first, can force a win, 01:54.661 --> 01:58.821 or that Player 2 can force a win, or will allow a third 01:58.815 --> 02:03.525 possibility, which is it's going to be a tie. 02:03.530 --> 02:06.770 So here's the theorem, suppose there are two players 02:06.766 --> 02:09.426 in this game, like the games that we looked 02:09.431 --> 02:13.061 at last time, and suppose--I won't define 02:13.060 --> 02:18.630 this formally now--but suppose the game is a game of perfect 02:18.633 --> 02:21.253 information. So what do I mean by perfect 02:21.245 --> 02:23.675 information? I'll define this later on in 02:23.676 --> 02:27.626 the class, but for now all I mean is, that whenever a player 02:27.631 --> 02:31.191 has his turn to move, that player knows exactly what 02:31.185 --> 02:33.255 has happened prior in the game. 02:33.259 --> 02:35.469 So, for example, all these sequential move games 02:35.469 --> 02:38.149 we've been looking at are moves of perfect information. 02:38.150 --> 02:41.180 When I get to move I know exactly what you did yesterday, 02:41.177 --> 02:44.147 I know what I did the day before yesterday and so on. 02:44.150 --> 02:46.140 So it's a game of perfect information. 02:46.139 --> 02:50.889 I'm going to assume that the game has a finite number of 02:50.889 --> 02:52.849 nodes. So two things here, 02:52.853 --> 02:56.413 it can't go on forever, this game, and also there's no 02:56.405 --> 02:59.685 point in which it branches in an infinite way. 02:59.690 --> 03:03.480 So there's a finite number of nodes, and we'll assume that the 03:03.477 --> 03:05.647 game has three possible outcomes. 03:05.650 --> 03:08.540 Actually there's a more general version of this theorem but this 03:08.543 --> 03:12.013 will do for now. The three possible outcomes are 03:12.010 --> 03:16.950 either a win for Player 1, so I'll call it W_1, 03:16.949 --> 03:22.679 or a loss for Player 1, which is obviously a win for 03:22.680 --> 03:25.040 Player 2, or a tie. 03:25.039 --> 03:27.579 So the game--like Nim last time, that only had two 03:27.579 --> 03:30.539 outcomes. So here we're going to look up 03:30.543 --> 03:35.253 to three outcomes or three or fewer outcomes I should say. 03:35.250 --> 03:39.930 So these are the conditions and here's the result. 03:39.930 --> 03:42.820 So I said three, it could be three but it could 03:42.822 --> 03:45.842 also be two here, I'm just allowing for three. 03:45.840 --> 03:51.650 (One is trivial.) So under these conditions the following 03:51.652 --> 03:55.302 is true. Either Player 1 can force a 03:55.303 --> 04:01.113 win, so either it's the case that this game is a game that if 04:01.111 --> 04:04.791 Player 1 plays as well as they can, 04:04.789 --> 04:09.759 they're going to win the game no matter what Player 2 does. 04:09.759 --> 04:17.089 Or 1 can at least force a tie, which means Player 1 can play 04:17.089 --> 04:23.669 in such a way that they can assure themselves of a tie 04:23.673 --> 04:28.273 regardless of what Player 2 does. 04:28.269 --> 04:41.219 Or it could be a game in which 2 can force a loss on 1, 04:41.222 --> 04:45.982 so a win for 2. So this theorem, 04:45.977 --> 04:48.217 when you first look at it, it doesn't seem to say very 04:48.221 --> 04:49.851 much. You're staring at this 04:49.848 --> 04:52.718 thing--you might think, we already knew that we're 04:52.719 --> 04:56.409 looking at games that only have three possible outcomes win, 04:56.410 --> 05:00.440 loss, or tie so it doesn't seem so surprising if you look at 05:00.440 --> 05:02.080 this theorem, it says, 05:02.079 --> 05:04.559 well, you're going to end up with a win, or a loss, 05:04.563 --> 05:06.523 or a tie. However, that's not quite what 05:06.522 --> 05:07.372 the theorem says. 05:07.370 --> 05:10.040 The theorem says, not only are you going to end 05:10.039 --> 05:12.999 up there--we knew that already--but the games divide 05:12.999 --> 05:15.449 themselves. Games of these forms divide 05:15.447 --> 05:18.777 themselves into those games in which Player 1 has a way of 05:18.778 --> 05:21.348 winning regardless of what Player 2 does; 05:21.350 --> 05:25.270 or games in which Player 1 has a way of forcing a tie 05:25.270 --> 05:27.910 regardless of what Player 2 does; 05:27.910 --> 05:31.280 or Player 2 has a way of winning regardless of what 05:31.282 --> 05:33.912 Player 1 does, so these games all have a 05:33.913 --> 05:36.583 solution. Let's just go back to Nim to 05:36.581 --> 05:37.991 illustrate the point. 05:37.990 --> 05:41.750 So in Nim actually there's no tie so we can forget the middle 05:41.749 --> 05:45.429 of these, and in Nim, under certain circumstances it 05:45.433 --> 05:48.653 is the case that Player 1 can force a win. 05:48.649 --> 05:52.139 Who remembers what the case was, for when Player 1 can force 05:52.137 --> 05:54.447 a win? Anybody? 05:54.450 --> 05:58.560 The people who played last time. 05:58.560 --> 06:03.270 No, yes, Ale, there's somebody here. 06:03.270 --> 06:05.700 Shout it out. Student: Insuring that 06:05.696 --> 06:07.426 the piles are equal for the other player. 06:07.430 --> 06:12.400 Professor Ben Polak: All right, so if the piles start 06:12.398 --> 06:16.608 unequal, then Player 1 can actually force a win. 06:16.610 --> 06:24.970 So in Nim if the piles are unequal at the start, 06:24.965 --> 06:29.405 then 1 can force a win. 06:29.410 --> 06:33.820 It really doesn't matter what 2 does, 2 is "toast." 06:33.819 --> 06:37.979 Or the alternative case is the piles are equal at the start, 06:37.982 --> 06:42.002 and if they're equal at the start then it's Player 1 who's 06:42.003 --> 06:44.763 "toast." Player 2 is going 06:44.764 --> 06:51.184 to--rather--force a loss on 1, so 2 can force a loss on 1, 06:51.181 --> 06:55.051 i.e. a win for Player 2. 06:55.050 --> 06:58.940 Does everyone remember that from last time? 06:58.940 --> 07:02.650 It's just before the weekend, it shouldn't be so long ago. 07:02.649 --> 07:08.449 So this theorem applies to all games of this form. 07:08.450 --> 07:09.820 So what games are of this form? 07:09.819 --> 07:11.479 Let's try and think of some other examples. 07:11.480 --> 07:15.200 So one example is tic-tac-toe. 07:15.199 --> 07:16.279 Everyone know the rules of tic-tac-toe? 07:16.279 --> 07:18.839 In England we call it Noughts and Crosses, but you guys call 07:18.840 --> 07:20.230 it tic-tac-toe, is that right? 07:20.230 --> 07:22.150 Everyone know what tic-tac-toe is? 07:22.149 --> 07:26.389 Yeah, which category is tic-tac-toe? 07:26.389 --> 07:29.899 Is it a game which Player 1 can force a win, or is it a category 07:29.897 --> 07:32.177 in which Player 1 can only force a tie, 07:32.180 --> 07:35.170 or is it a category which you'd rather go second and Player 2 07:35.169 --> 07:37.859 can force a win for Player 2 or a loss for Player 1? 07:37.860 --> 07:40.680 Which is tic-tac-toe? 07:40.680 --> 07:41.760 Let's have a show of hands here. 07:41.759 --> 07:45.579 Who thinks tic-tac-toe is a game in which Player 1 can force 07:45.581 --> 07:47.641 a win? Who thinks tic-tac-toe is a 07:47.644 --> 07:50.224 game in which Player 1 can only force a tie? 07:50.220 --> 07:53.690 Who thinks Player 2's going to win? 07:53.690 --> 07:54.650 Most of you are right. 07:54.649 --> 07:58.099 It's a game in which if people play correctly then it'll turn 07:58.103 --> 08:04.813 out to be a tie. So tic-tac-toe is a game that 08:04.811 --> 08:09.271 leads to a tie. Player 1 can still make a 08:09.269 --> 08:11.289 mistake, in which case they can lose. 08:11.290 --> 08:15.100 Player 2 can make a mistake in which case they would lose, 08:15.098 --> 08:18.438 but there is a way of playing that forces a tie. 08:18.439 --> 08:20.979 So these are fairly simple games, let's talk about more 08:20.979 --> 08:21.919 complicated games. 08:21.920 --> 08:24.840 So what about the game of checkers? 08:24.839 --> 08:26.469 So the game of checkers meets these conditions. 08:26.470 --> 08:27.970 It's a two player game. 08:27.970 --> 08:30.870 You always know all the moves prior to your move. 08:30.870 --> 08:33.270 It's finite: there's some rules in checkers 08:33.269 --> 08:35.269 that prevent it going on forever. 08:35.269 --> 08:37.779 And there are two or three outcomes: I guess there's a 08:37.776 --> 08:40.326 third outcome if you get into a cycle you could tie. 08:40.330 --> 08:43.760 So checkers fits all these descriptions and what this 08:43.757 --> 08:47.117 theorem tells us is that checkers has a solution. 08:47.120 --> 08:49.460 I'm not sure I know what that solution is, or I think actually 08:49.464 --> 08:51.044 somebody did compute it quite recently, 08:51.039 --> 08:53.199 even in the last few months, I just forgot to Google it this 08:53.201 --> 08:54.191 morning to remind myself. 08:54.190 --> 08:57.810 But what this theorem tells us even before those people that 08:57.808 --> 09:00.198 computed it: checkers has a solution. 09:00.200 --> 09:01.940 Let's be a bit more ambitious. 09:01.940 --> 09:04.270 What about chess? 09:04.270 --> 09:06.290 So chess meets this description. 09:06.289 --> 09:09.409 Chess is a two player game, everybody knows all the moves 09:09.405 --> 09:13.075 before them, it's sequential, it has finite number of moves, 09:13.084 --> 09:16.864 it's a very large number but it is finite, and it has three 09:16.862 --> 09:20.672 possible outcomes, a win, a loss, or a tie. 09:20.669 --> 09:23.549 So let's be careful, the reason it's finite is that 09:23.548 --> 09:27.118 if you cycle--I forget what it is--three times then the game is 09:27.117 --> 09:29.187 declared a draw, declared a tie. 09:29.190 --> 09:30.650 So what's this theorem telling us? 09:30.649 --> 09:38.669 It's telling us that there is a way to solve chess. 09:38.670 --> 09:41.700 Chess has a solution. 09:41.700 --> 09:43.100 We don't know what that solution is. 09:43.100 --> 09:45.850 It could be that solution is that Player 1, 09:45.853 --> 09:49.593 who's the player with the white pieces can force a win. 09:49.590 --> 09:52.080 It could be that Player 1 can only force a tie, 09:52.080 --> 09:54.950 and it could even be that Player 2 can force a win. 09:54.950 --> 09:59.000 We don't know which it is, but there is a solution. 09:59.000 --> 10:00.180 There's a catch to this theorem. 10:00.180 --> 10:02.410 What's the catch? 10:02.409 --> 10:05.259 The catch is it doesn't actually tell us--this theorem 10:05.259 --> 10:07.839 is not going to tell us what that solution is. 10:07.840 --> 10:09.410 It doesn't tell us how to play. 10:09.409 --> 10:11.029 This theorem, in and of itself, 10:11.028 --> 10:12.968 doesn't tell us how to play chess. 10:12.970 --> 10:18.020 It just says there is a way to play chess. 10:18.019 --> 10:19.519 So we're going to try and prove this. 10:19.519 --> 10:23.319 We don't often do proofs in class, but the reason I want to 10:23.318 --> 10:26.988 prove this particular one is because I think the proof is 10:26.986 --> 10:29.996 instructive as part of sort of QR at Yale. 10:30.000 --> 10:33.070 So here's another example here, and some other examples. 10:33.070 --> 10:36.850 You could think of chess as being the most dramatic example. 10:36.850 --> 10:49.020 10:49.019 --> 10:56.199 So the reason I want to spend actually some time proving this 10:56.203 --> 11:03.393 today is because we're going to prove it by induction and I'm 11:03.388 --> 11:06.978 going to sketch the proof. 11:06.980 --> 11:09.580 I'm not going to go through every possible step but I want 11:09.584 --> 11:12.234 to give people here a feeling for what a proof by induction 11:12.234 --> 11:14.104 looks like. The reason for this is, 11:14.096 --> 11:15.726 my guess is, well let's find out, 11:15.733 --> 11:18.653 how many of you have seen a proof by induction before? 11:18.650 --> 11:20.610 How many have not? 11:20.610 --> 11:22.630 So for those of you who haven't I think it's a good thing in 11:22.633 --> 11:24.763 life, at one point in your life to see a proof by induction, 11:24.759 --> 11:27.559 and for those who have, my guess is you saw it in some 11:27.557 --> 11:30.877 awful math class in high school and it just went over--it didn't 11:30.883 --> 11:32.893 necessarily go over your head but, 11:32.889 --> 11:36.069 the excitement of it doesn't catch on. 11:36.070 --> 11:40.140 This is a context where it might appeal. 11:40.140 --> 11:41.440 So proof by induction. 11:41.440 --> 11:51.890 We're going to prove this by induction on the maximum length 11:51.892 --> 11:58.272 of the game and we'll call that N. 11:58.269 --> 11:59.719 We'll call N the maximum length of the game. 11:59.720 --> 12:00.830 What do I mean by this? 12:00.830 --> 12:06.000 If I write down a tree I can always look at all the paths 12:06.001 --> 12:11.541 from the beginning of the tree all the way through to the end 12:11.542 --> 12:14.722 of the tree. And I'm going to look at the 12:14.719 --> 12:18.239 path in that particular tree that has the largest length, 12:18.240 --> 12:21.740 and I'll call that the length of the game, the maximum length 12:21.742 --> 12:24.592 of the game. So we're going to do induction 12:24.586 --> 12:26.946 on the maximum length of the game. 12:26.950 --> 12:28.710 So how do we start a proof by induction? 12:28.710 --> 12:30.970 Let's just remind ourselves, those people who have seen them 12:30.965 --> 12:33.565 before. We're going to prove that this 12:33.572 --> 12:36.972 theorem this true, the claim in the theorem is 12:36.965 --> 12:41.485 true for the easy case when the game is only 1 move long. 12:41.490 --> 12:45.520 That's the first step, and then we're going to try and 12:45.524 --> 12:49.334 show that if it's true for all games of length < 12:49.330 --> 12:51.260 = N, whatever N is, 12:51.264 --> 12:56.564 then it must therefore be true for games of length N+1. 12:56.559 --> 12:58.849 That's the way you do a proof by induction. 12:58.850 --> 13:01.750 So let's just see how that works in practice. 13:01.750 --> 13:04.810 So let's start with the easy step and we'll do it in some 13:04.811 --> 13:08.201 detail, more detail than you really need to in a math class. 13:08.200 --> 13:11.250 So if N = 1, what do these games look like? 13:11.250 --> 13:13.210 Well let's look at some examples here. 13:13.210 --> 13:18.260 So I claim it's pretty trivial if N = 1 but let's do it anyway. 13:18.259 --> 13:20.599 So the game might look like this. 13:20.600 --> 13:22.910 Player 1 is going to move--here's Player 1 13:22.912 --> 13:26.132 moving--the game's only length one--so Player 1's the only 13:26.128 --> 13:27.988 player who ever gets to move. 13:27.990 --> 13:30.520 So the game might look like this. 13:30.519 --> 13:33.319 Let's put in a fifth branch, it might look like this. 13:33.320 --> 13:36.030 And at the end of this game, rather than putting payoffs let 13:36.029 --> 13:37.269 me just put the outcomes. 13:37.269 --> 13:40.219 So the outcome must either be a win, or a tie, 13:40.215 --> 13:43.025 or a loss, so suppose it looks like this. 13:43.029 --> 13:47.699 Suppose it's a win, or here we could have a tie, 13:47.697 --> 13:53.357 or here we could have a win again, or here we could have a 13:53.357 --> 13:57.227 loss, and here we could have a tie. 13:57.230 --> 14:02.090 So in this particular game I claim it's pretty clear this 14:02.090 --> 14:04.000 game has a solution. 14:04.000 --> 14:07.240 It's pretty clear what 1 should do. 14:07.240 --> 14:08.130 What should 1 do? 14:08.129 --> 14:12.359 1 should pick one of her choices that leads to a win. 14:12.360 --> 14:15.580 To be careful I'll put 1 in here just to distinguish who it 14:15.582 --> 14:17.752 is who's actually winning and losing. 14:17.750 --> 14:21.150 So in this game I claim that this game has a pretty obvious 14:21.149 --> 14:24.669 solution, either Player 1 is going to choose this branch that 14:24.665 --> 14:27.825 leads to a win or this branch that leads to a win, 14:27.830 --> 14:31.680 and either way Player 1 is going to win. 14:31.680 --> 14:33.090 Is that obvious? It's so obvious, 14:33.086 --> 14:34.026 it's kind of painful. 14:34.029 --> 14:37.719 So I claim this game, we could actually replace this 14:37.718 --> 14:42.268 first node with what's going to happen which is Player 1's going 14:42.274 --> 14:44.474 to win. Is that right? 14:44.470 --> 14:47.650 That was easy. Let's look at a different 14:47.649 --> 14:49.739 example, we'll do three. 14:49.740 --> 14:53.590 So here's another possible example, and this again, 14:53.588 --> 14:57.898 Player 1 is going to move here and this time the possible 14:57.899 --> 15:01.209 outcomes are tie, or a loss, or a loss. 15:01.210 --> 15:05.270 Once again it's a one player game, this time he has three 15:05.272 --> 15:09.482 choices and the three choices lead to a tie or he loses, 15:09.480 --> 15:11.110 so I claim once again this is simple. 15:11.110 --> 15:12.120 What Player 1 should do is what? 15:12.120 --> 15:14.840 Choose the tie since there's no way of winning. 15:14.840 --> 15:16.200 But in that case he could actually force it. 15:16.200 --> 15:19.040 He could actually choose the tie in which case he's going to 15:19.041 --> 15:20.671 tie. So this game has a solution 15:20.674 --> 15:21.824 called choose the tie. 15:21.820 --> 15:25.720 And again, we could replace the first node of the game with 15:25.717 --> 15:29.007 what's actually going to happen which is a tie. 15:29.010 --> 15:32.520 Everyone happy? There's one other possibility I 15:32.523 --> 15:35.093 guess. The other possibility is that 15:35.086 --> 15:39.156 here Player 1 has a lot of choices, maybe four choices in 15:39.155 --> 15:43.475 this case, once again Player 1 is going to 15:43.481 --> 15:48.501 move but in each case--unfortunately for Player 15:48.499 --> 15:54.389 1--in each case the outcome is that Player 1 loses. 15:54.389 --> 15:56.799 So this is a game in which Player 1 is going to lose no 15:56.798 --> 15:57.778 matter what they do. 15:57.779 --> 16:00.159 Once again it has a solution: the solution is Player 1 is 16:00.164 --> 16:01.404 toast and is going to lose. 16:01.400 --> 16:08.130 16:08.129 --> 16:10.919 So I claim this has really captured all the possibilities 16:10.915 --> 16:12.055 of games of length 1. 16:12.059 --> 16:14.899 I mean you could imagine that there could be more branches on 16:14.897 --> 16:17.637 them, but basically there are these three possibilities. 16:17.639 --> 16:20.929 Either it's the case that one of those branches leads to a 16:20.928 --> 16:23.868 win, in which case the solution is Player 1 wins; 16:23.870 --> 16:27.210 or it's the case that none of the branches have wins in them, 16:27.211 --> 16:30.271 but one of them has a tie, in which Player 1 is going to 16:30.274 --> 16:32.234 tie; or it's the case that all the 16:32.226 --> 16:35.076 branches have loss in them, in which Player 1's going to 16:35.084 --> 16:37.104 lose. So I claim I'm for done for 16:37.103 --> 16:38.353 games of length one. 16:38.350 --> 16:42.050 Everyone okay? So that step is deceptively 16:42.053 --> 16:44.463 easy but there it is. 16:44.460 --> 16:46.680 All right, now we do the inductive step, 16:46.677 --> 16:49.197 the big step. What we're going to do is we're 16:49.200 --> 16:51.950 going to assume that the statement of the theorem, 16:51.950 --> 16:55.670 which I've now hidden unfortunately--let me unhide it 16:55.670 --> 16:58.390 if I can, it's not going to be easy. 16:58.390 --> 17:05.120 17:05.120 --> 17:07.340 This now visible? 17:07.339 --> 17:14.049 So now let's assume that the statement of this theorem is 17:14.045 --> 17:21.465 true for all games length < = N, suppose that's the case. 17:21.470 --> 17:35.080 Suppose the claim is true for all games of this type, 17:35.077 --> 17:41.617 of length <= some N. 17:41.619 --> 17:45.919 What we need to show is--what we're going to try and show is 17:45.916 --> 17:50.136 therefore it will be true for all games of length N + 1. 17:50.140 --> 17:58.980 What we want to show is--we claim, therefore, 17:58.984 --> 18:07.234 it will be true for games of length N + 1, 18:07.225 --> 18:16.065 that's the key step in inductive proofs. 18:16.069 --> 18:19.589 All right, so how are we going to do that? 18:19.589 --> 18:22.039 Well let's have a look at a game of length N + 1, 18:22.038 --> 18:24.898 and obviously I can't use thousands here so let me choose 18:24.895 --> 18:28.825 from relatively small numbers, but the idea will go through. 18:28.830 --> 18:31.850 So let's have a look at a game. 18:31.849 --> 18:37.239 So here's a game in which Player 1 moves first, 18:37.238 --> 18:40.048 Player 2 moves second. 18:40.049 --> 18:44.519 Let's suppose that if Player 2 does this, then 1 only has 18:44.522 --> 18:48.812 little choice here, up here then one has a more 18:48.814 --> 18:53.854 complicated choice, and perhaps 2 could move again. 18:53.849 --> 18:55.869 So this is quite a complicated little game up here, 18:55.872 --> 18:58.302 and down here let's make it a little bit less complicated. 18:58.299 --> 19:02.499 Here the game looks like this and then comes to an end, 19:02.504 --> 19:04.844 so the tree looks like this. 19:04.839 --> 19:07.669 I haven't put the end, I haven't put the outcomes on 19:07.672 --> 19:09.562 it but the tree looks like this. 19:09.559 --> 19:12.279 So how long is this tree first of all? 19:12.279 --> 19:16.379 Well I claim that the longest path in this tree, 19:16.380 --> 19:20.480 from the beginning to the end has four steps. 19:20.480 --> 19:22.450 Let's just check. 19:22.450 --> 19:25.890 So one, two, three, four that's what I claim 19:25.890 --> 19:27.650 is the longest path. 19:27.650 --> 19:33.110 Any path going down this way only has three moves in it, 19:33.107 --> 19:36.577 so this is a game of length four. 19:36.579 --> 19:42.059 So we can apply it to our claim, let's assume that the 19:42.061 --> 19:47.441 theorem holds for all trees length three or fewer, 19:47.440 --> 19:51.590 so that N + 1 is 4 for the purpose of our example. 19:51.589 --> 19:57.939 So in this example--I don't want to put it here, 19:57.937 --> 20:03.337 let's put it here--in this example N = 3, 20:03.338 --> 20:06.308 so that N + 1 = 4. 20:06.309 --> 20:10.689 Everyone happy with this in the example? 20:10.690 --> 20:15.380 Now what I want to observe about this is the following: 20:15.381 --> 20:19.811 contained in this N + 1, or the game of length 4 are 20:19.811 --> 20:21.811 some smaller games. 20:21.809 --> 20:23.599 You could think of them as sub-games. 20:23.599 --> 20:26.829 They're games within the game, is that right? 20:26.830 --> 20:28.040 So let's have a look. 20:28.039 --> 20:35.849 I claim, in particular--draw around them in pink--there's a 20:35.848 --> 20:44.058 game here that follows Player 1 choosing Up and there's a game 20:44.061 --> 20:50.121 here that follows Player 1 choosing Down, 20:50.120 --> 20:56.210 is that right? Okay, so these are both games, 20:56.211 --> 20:58.641 and what do we have here? 20:58.640 --> 21:02.130 So this little game in here--the game in the top 21:02.134 --> 21:06.374 circle, the game that follows Player 1 moving up--that's a 21:06.373 --> 21:08.533 game and it has a length. 21:08.529 --> 21:12.349 So this little thing is a game and I'm going to call it a 21:12.346 --> 21:16.566 sub-game, some jargon that we'll be getting used to later on in 21:16.571 --> 21:21.341 the semester. It's a game within the game, 21:21.342 --> 21:29.082 but it's basically just a game: it's a sub-game and this is a 21:29.082 --> 21:35.272 sub-game following 1 choosing Up--let's put Up in 21:35.273 --> 21:38.373 here--following up. 21:38.369 --> 21:41.809 And I claim that this game has a length--this sub-game has a 21:41.814 --> 21:44.024 length. So we knew that we started from 21:44.015 --> 21:46.605 a game of length 4, we've taken one of the moves, 21:46.610 --> 21:50.070 and let's just make sure this is actually a game of length 3. 21:50.069 --> 21:53.299 So the game started here, this would be a game of length 21:53.304 --> 21:55.894 3 because you could go one, two, three moves, 21:55.891 --> 21:59.011 is that right? So this is a game of length 3. 21:59.009 --> 22:08.079 So this is a sub-game following 1 choosing Up and it, 22:08.081 --> 22:13.141 the sub-game, has length 3. 22:13.140 --> 22:21.000 Down here, this is also a sub-game, it's a game that 22:21.004 --> 22:29.954 follows Player 1 choosing Down and this little sub-game has 22:29.948 --> 22:39.358 length--now here we have to be a little bit careful--you might 22:39.355 --> 22:48.295 think that since we started from a game of length 4, 22:48.299 --> 22:53.209 after the first move we must be in a game of length 3. 22:53.210 --> 22:56.020 But actually that's not true, and if we look carefully, 22:56.021 --> 22:58.891 we'll notice that this game down here, the game starting 22:58.885 --> 23:00.755 here actually isn't of length 3. 23:00.760 --> 23:02.410 It's of length 2. 23:02.410 --> 23:04.450 Is that right? So even though started from a 23:04.451 --> 23:06.721 game of length 4, by going this way we put 23:06.716 --> 23:08.756 ourselves into a game of length 2. 23:08.760 --> 23:16.020 Is that right? So 1,2 or 1,2--whatever--it has 23:16.023 --> 23:20.713 length 2. Okay, all right so in this 23:20.708 --> 23:25.868 example N is 3 and N + 1 is 4, and our assumption, 23:25.868 --> 23:29.658 our induction assumption is what? 23:29.660 --> 23:38.360 We've assumed that the claim of the theorem holds for all games 23:38.357 --> 23:44.527 <= N, which in this case means <= 3. 23:44.530 --> 23:46.090 So what does that tell us? 23:46.089 --> 23:49.079 That tells us, by our assumption, 23:49.075 --> 23:54.385 this game, which I've put a pink circle around on the top, 23:54.392 --> 23:59.712 this is a game of length 3, this game has a solution. 23:59.710 --> 24:04.500 It must have a solution because it's of length 3 or less. 24:04.500 --> 24:11.270 So by the induction hypothesis as it's called--by the induction 24:11.266 --> 24:17.916 hypothesis--this is a technical term, but what's the induction 24:17.923 --> 24:22.003 hypothesis? It's this thing. 24:22.000 --> 24:36.350 By the assumption that we made this game has a solution. 24:36.349 --> 24:39.739 So it's a game of length 3,3 <= N in this case. 24:39.740 --> 24:41.270 So this game must have a solution. 24:41.269 --> 24:47.179 Now I don't immediately know by staring at it what it is, 24:47.181 --> 24:51.721 but let's suppose it was W, say it was W. 24:51.720 --> 24:55.150 And the game down below, this is also a game, 24:55.147 --> 24:59.507 and it's a game of length 2 but 2 is less than 3 as well, 24:59.509 --> 25:04.569 2 <= 3. So this game also has a 25:04.565 --> 25:09.215 solution. This game also, 25:09.222 --> 25:16.652 by the same assumption, has a solution, 25:16.650 --> 25:27.010 so its solution is say--I don't know--maybe its L. 25:27.009 --> 25:31.209 So what does that mean to say that these games have solutions, 25:31.214 --> 25:34.524 in this case we're going to assume W is this one, 25:34.523 --> 25:37.353 and L is this one, what does it mean? 25:37.349 --> 25:40.059 It means that, just as we did with the games 25:40.055 --> 25:43.695 up there, we could put the solution at the beginning of the 25:43.703 --> 25:45.963 game. We know that if we get into 25:45.960 --> 25:49.530 this game, we're going to get the solution of this game; 25:49.529 --> 25:52.779 and we know if we get into this game, we're going to get the 25:52.778 --> 25:54.098 solution of this game. 25:54.099 --> 25:58.839 So we can replace this one with its solution which by assumption 25:58.837 --> 26:03.197 was W, and this one by its solution which by assumption was 26:03.198 --> 26:04.978 L. And here I want to be really 26:04.977 --> 26:08.007 careful, I need to keep track of which person it is it's a win or 26:08.011 --> 26:10.821 loss for. So this was a win for Player 1, 26:10.820 --> 26:14.870 hence it was a loss for Player 2, and this was a loss for 26:14.867 --> 26:18.117 Player 1, hence it was a win for Player 2. 26:18.119 --> 26:22.059 So these games, each of them have some 26:22.063 --> 26:28.353 solution, and this case I've written down the solutions as W 26:28.350 --> 26:31.150 or L. So now what could we do? 26:31.150 --> 26:33.350 Let me just bring down this board again. 26:33.349 --> 26:37.329 I can translate this game into a very simple game. 26:37.329 --> 26:40.929 I'm going to translate it up here, so this game can be 26:40.929 --> 26:42.559 translated as follows. 26:42.559 --> 26:56.259 Player 1 moves, if he goes Up then he hits a W 26:56.259 --> 27:06.609 and if he goes Down he hits a L. 27:06.609 --> 27:09.959 So in this particular example, Player 1 is effectively 27:09.958 --> 27:13.748 choosing between going Up and finding himself in a game which 27:13.749 --> 27:16.799 has a solution, and the solution is he wins it, 27:16.797 --> 27:20.007 or going Down and finding himself in a game which has a 27:20.014 --> 27:24.644 solution, and the solution is he's toast. 27:24.640 --> 27:29.330 But that's what? That's a one move game. 27:29.329 --> 27:31.939 So we know this has a solution, and in particular, 27:31.936 --> 27:33.316 he's going to choose Up. 27:33.320 --> 27:37.260 This one has a solution. 27:37.259 --> 27:55.819 This has a solution, it is a game of length 1. 27:55.820 --> 27:57.960 So what do we do? 27:57.960 --> 28:02.230 Somewhat schematically, we took a game of length N + 1, 28:02.232 --> 28:06.682 in this case that was 4; and we pointed out that once 28:06.677 --> 28:10.507 Player 1 has made her first move in this game, 28:10.514 --> 28:13.874 we are in a game, or in a sub-game if you like, 28:13.867 --> 28:16.247 that has length less than 4, it could be 3, 28:16.254 --> 28:19.024 it could be 2, whatever. 28:19.019 --> 28:23.389 Whatever sub-game we're in, by assumption, 28:23.385 --> 28:26.255 that game has a solution. 28:26.259 --> 28:29.539 So it's really effectively, Player 1 is choosing between 28:29.542 --> 28:33.002 going into a game with solution W or going into a game with 28:33.004 --> 28:35.354 solution L. And if there were 15 other 28:35.351 --> 28:37.921 sub-games here, each one would have a solution, 28:37.918 --> 28:41.318 and each one Player 1 would be able to associate that solution 28:41.322 --> 28:44.562 with what he's going to get--what she's going to get. 28:44.559 --> 28:49.649 So I claim that, if it in fact is true that each 28:49.647 --> 28:55.707 of these sub-games of length 3 or less had a solution, 28:55.710 --> 28:59.290 then the game of length 4 must have a solution, 28:59.293 --> 29:03.523 which is what? It's the solution which is: 29:03.518 --> 29:07.928 Player 1 should pick the best sub-game. 29:07.930 --> 29:11.300 Are people convinced by that step? 29:11.299 --> 29:15.449 People are looking slightly "deer in the headlamps" now, 29:15.447 --> 29:17.707 so let me just say it again. 29:17.710 --> 29:22.480 We started by assuming that all games of length 3 or less, 29:22.481 --> 29:25.161 or N or less, have a solution. 29:25.160 --> 29:30.070 We pointed out that any game that has length N + 1 can be 29:30.071 --> 29:35.511 thought of as an initial move by Player 1 followed by a game of 29:35.508 --> 29:39.258 length N or less, N or fewer I should say. 29:39.259 --> 29:43.319 Each of those games of N or fewer steps has a solution, 29:43.315 --> 29:47.515 so Player 1 is just going to choose the game that has the 29:47.520 --> 29:50.600 best solution for her and we're done. 29:50.599 --> 29:58.409 In this particular example, Player 1 is going to choose Up 29:58.413 --> 30:06.233 and therefore the solution to this parent game is Player 1 30:06.226 --> 30:09.376 wins. Now the hard step I think in 30:09.381 --> 30:12.881 proofs by induction is realizing that you're done. 30:12.880 --> 30:17.170 So I claim we're now done, why are we done? 30:17.170 --> 30:21.800 Well we know that it was pretty easy that all games of length 1 30:21.796 --> 30:24.736 have a solution. That was pretty trivial. 30:24.740 --> 30:29.900 And we've shown that if any game of length of N or fewer has 30:29.903 --> 30:34.283 a solution, then games of N + 1 have a solution. 30:34.279 --> 30:35.799 So now let's see how we can proceed. 30:35.799 --> 30:39.249 We know that games of length 1 have a solution, 30:39.250 --> 30:42.100 so let's consider games of length 2. 30:42.099 --> 30:44.889 Games of length 2, do games of length 2 have a 30:44.888 --> 30:48.348 solution? Well let's set N = 1. 30:48.349 --> 30:51.119 We know that if games of length 1 have a solution, 30:51.119 --> 30:54.679 then any game of length 2 could be thought of as an initial step 30:54.681 --> 30:57.861 followed by a game of length 1, but that has a solution, 30:57.863 --> 31:00.273 so therefore games of length 2 have a solution. 31:00.269 --> 31:03.049 Now let's think of games with length 3, we've shown that games 31:03.053 --> 31:05.753 with length 1 have a solution and games with length 2 have a 31:05.746 --> 31:07.846 solution. Any game of length 3 can be 31:07.851 --> 31:11.271 thought of as a game in which there's an initial step followed 31:11.266 --> 31:14.286 by either a game of length 1 or a game of length 2, 31:14.289 --> 31:18.429 each of which have a solution, so once again a game of length 31:18.429 --> 31:20.429 3 has a solution and so on. 31:20.430 --> 31:23.700 So games of induction, they work by building up on the 31:23.699 --> 31:26.539 length of the game, and we're ending up knowing 31:26.536 --> 31:29.916 that we're done. For those people who have never 31:29.919 --> 31:34.219 seen a proof by induction don't worry I'm not going to test you 31:34.217 --> 31:37.057 on a proof with induction on the exam, 31:37.059 --> 31:39.069 I just wanted you to see one once. 31:39.069 --> 31:43.169 Let's all take a deep breath and try and digest this a little 31:43.170 --> 31:44.810 bit by playing a game. 31:44.809 --> 31:50.919 I'll leave it up there so you can stare at it. 31:50.920 --> 31:51.440 We'll want it down again later. 31:51.440 --> 31:57.550 31:57.549 --> 32:04.049 Let's try and actually play a game and see if we can actually 32:04.045 --> 32:06.855 throw any light on this. 32:06.859 --> 32:09.489 So I'm going to pick out volunteers like I did last time, 32:09.490 --> 32:11.650 but first of all, let me tell you what the game 32:11.651 --> 32:13.691 is. So once again I'm going to have 32:13.686 --> 32:16.216 rocks in this game, and once again I'm going to 32:16.217 --> 32:19.297 approximate those rocks with marks on the blackboard. 32:19.300 --> 32:23.360 So here's an example. 32:23.360 --> 32:24.990 The example is this. 32:24.990 --> 32:33.190 The game involves an array of rocks, so here the array has 32:33.186 --> 32:37.496 five rows and three columns. 32:37.500 --> 32:41.160 So the rocks are not arranged as they were before in piles, 32:41.161 --> 32:43.941 but rather in a sort of in a pretty array. 32:43.940 --> 32:45.970 I should have made it more even but this is: one, 32:45.970 --> 32:47.240 two, three, four, five rows; 32:47.240 --> 32:49.020 and one, two, three columns, 32:49.015 --> 32:50.785 at least in this example. 32:50.789 --> 33:03.799 But in general there's an array of rocks, N x M. 33:03.799 --> 33:06.199 We're going to play sequentially with the players. 33:06.200 --> 33:14.350 And the way the game is going to work is this--is when it's 33:14.349 --> 33:19.339 your turn to move, you have to point to one of 33:19.338 --> 33:24.098 these rocks and whichever rock you point to I will remove. 33:24.099 --> 33:28.169 I will delete that rock and all the rocks that lie above or to 33:28.171 --> 33:31.181 the right of it: all the rocks that lie to the 33:31.175 --> 33:34.005 northeast of it. So for example, 33:34.007 --> 33:39.597 if you pointed to this rock, then I will remove this rock 33:39.597 --> 33:44.087 and also this one, this one, and this one. 33:44.089 --> 33:47.909 If the next person comes along and chooses this one, 33:47.909 --> 33:51.579 then I will remove this one, and also that one. 33:51.580 --> 33:53.190 Okay, everyone understand? 33:53.190 --> 34:00.300 All right and the game is lost--this is important--the 34:00.301 --> 34:08.621 game is lost by the person who ends up taking the last rock. 34:08.619 --> 34:18.789 The loser is the person who ends up removing the last rock. 34:18.790 --> 34:22.740 Could I have some volunteers? 34:22.740 --> 34:24.790 Can I volunteer people then? 34:24.789 --> 34:27.999 How about the guy with the white t-shirt with the yellow on 34:27.997 --> 34:31.457 there? Okay, come on up front, 34:31.460 --> 34:35.400 and who else can I volunteer. 34:35.400 --> 34:38.540 Everyone's looking away from me, desperately looking away 34:38.539 --> 34:41.689 from me. How about the guy with the Yale 34:41.689 --> 34:45.199 sweatshirt on, the Yale football sweatshirt 34:45.197 --> 34:47.317 on, okay. So come on up. 34:47.320 --> 34:50.240 Your name is? I should get a mike, 34:50.241 --> 34:54.691 let me get a mike up here, thank you. 34:54.690 --> 34:55.850 Great, your name is? 34:55.850 --> 34:56.460 Student: Noah. 34:56.460 --> 34:57.910 Professor Ben Polak: Noah and your name is? 34:57.910 --> 34:58.810 Student: Koran. 34:58.809 --> 34:59.569 Professor Ben Polak:Say it into the mike. 34:59.570 --> 35:00.140 Student: Koran. 35:00.139 --> 35:01.339 Professor Ben Polak: Koran okay. 35:01.340 --> 35:03.320 So Noah and Koran are our players. 35:03.320 --> 35:05.110 Everyone understand the rules? 35:05.110 --> 35:06.070 Do you understand the rules? 35:06.070 --> 35:08.220 Yeah? So why don't we make Noah go 35:08.215 --> 35:09.845 first. So Noah which rock are you 35:09.847 --> 35:14.277 going to remove? Remember the last rock loses. 35:14.280 --> 35:14.610 Student: That one. 35:14.610 --> 35:15.130 Professor Ben Polak: That one. 35:15.130 --> 35:16.740 Okay, so Noah chose this one. 35:16.739 --> 35:21.709 So I'm going to remove this one and the one above it. 35:21.710 --> 35:22.970 Student: So all the rocks to the north and east are 35:22.973 --> 35:25.233 deleted, right? Professor Ben Polak: All 35:25.228 --> 35:28.318 the rocks to the north and east of it are deleted. 35:28.320 --> 35:32.580 That means you--last rock loses. 35:32.580 --> 35:47.550 Okay good. Student: That one. 35:47.550 --> 35:49.170 Professor Ben Polak: That one okay. 35:49.170 --> 35:59.980 So now we have an L shape. 35:59.980 --> 36:00.520 Student: That one. 36:00.519 --> 36:05.219 Professor Ben Polak: That one, all right. 36:05.220 --> 36:05.770 Student: That one. 36:05.769 --> 36:07.209 Professor Ben Polak: That one okay, 36:07.213 --> 36:09.333 okay. All right so we're done. 36:09.329 --> 36:11.279 Okay, everyone understand how that worked? 36:11.280 --> 36:16.230 Round of applause for our players please, 36:16.226 --> 36:18.616 thank you. Let me get two more volunteers 36:18.619 --> 36:19.559 now that everyone has seen it. 36:19.559 --> 36:23.199 These guys had the hard job, they had to figure it out cold. 36:23.200 --> 36:25.580 Two more volunteers? 36:25.579 --> 36:27.529 Oh I don't have to pick volunteers--this is Yale, 36:27.534 --> 36:28.394 somebody volunteer. 36:28.390 --> 36:28.840 Are you volunteering? 36:28.840 --> 36:30.930 Great. I have one volunteer. 36:30.929 --> 36:36.939 You can pick an opponent if you like. 36:36.940 --> 36:38.770 There you go thank you. 36:38.769 --> 36:43.459 Your name is, let's just wait until the mikes 36:43.458 --> 36:45.568 are here. So your name is? 36:45.570 --> 36:46.090 Student: Peter. 36:46.090 --> 36:48.210 Professor Ben Polak: Peter and your name is Justin. 36:48.210 --> 36:50.840 Student: Justin. 36:50.840 --> 36:56.900 Professor Ben Polak: Let me put a new array up here. 36:56.900 --> 36:59.390 So let's put a new array up here and this time let's make 36:59.388 --> 37:00.808 it--it doesn't have to be odd. 37:00.809 --> 37:02.459 So let's make it this time a little bit more complicated. 37:02.460 --> 37:13.880 So we'll have five--let's have four rows and five columns this 37:13.879 --> 37:18.599 time. Okay so last time I had five 37:18.602 --> 37:25.062 rows and three columns, and this time I have four rows 37:25.062 --> 37:27.502 and five columns. 37:27.500 --> 37:30.340 Away you go, let me move out of the way. 37:30.340 --> 37:32.060 Why don't you stand a bit nearer to the board--make it a 37:32.059 --> 37:33.529 little easier for people to see what's going on, 37:33.528 --> 37:36.298 there you go. So Peter you want to go first? 37:36.300 --> 37:38.690 Student: Sure, that one. 37:38.690 --> 37:39.450 Professor Ben Polak: That one okay. 37:39.449 --> 37:45.969 So this one goes, which means all of these go as 37:45.969 --> 37:48.059 well. Anyone got any advice from the 37:48.058 --> 37:50.518 floor? Shout things out, not too loud. 37:50.520 --> 37:54.010 37:54.010 --> 37:55.110 Student: I'll try going here. 37:55.110 --> 37:55.550 Professor Ben Polak: There. 37:55.550 --> 38:10.440 Okay we're back to our L shape again here. 38:10.440 --> 38:15.260 Now people can see what's going on all right. 38:15.260 --> 38:16.580 Student: I'll go here and speed it up. 38:16.579 --> 38:18.589 Professor Ben Polak: All right thank you. 38:18.590 --> 38:20.320 So a round of applause again. 38:20.320 --> 38:27.180 Thank you guys. So here's what I claim about 38:27.177 --> 38:29.077 this game. First, and this isn't a formal 38:29.079 --> 38:32.009 claim, this is a lot harder than the game we played last time, 38:32.007 --> 38:33.897 right? Everyone is convinced by that 38:33.897 --> 38:35.897 all right. So here's going to be an 38:35.904 --> 38:38.514 exercise, or something that's a challenge. 38:38.510 --> 38:41.660 I may even put it formally on the problem set this week, 38:41.662 --> 38:45.042 but let me just say if I do put this on the problem set this 38:45.044 --> 38:47.344 week, I don't expect you all to solve 38:47.340 --> 38:48.560 it. So if I do put it on the 38:48.556 --> 38:50.156 problem set, it's an optional problem. 38:50.159 --> 38:55.789 But here's the challenge, the challenge is, 38:55.793 --> 39:03.043 I know from Zermelo's theorem that no matter what N is, 39:03.036 --> 39:10.276 and no matter what M is, this game has a solution. 39:10.280 --> 39:21.560 So Zermelo's theorem tells us this game has a solution. 39:21.559 --> 39:24.239 Now, notice it could have a different solution depending on 39:24.237 --> 39:26.357 the N and the M, depending on how many rows and 39:26.361 --> 39:28.071 how many columns, is that right?. 39:28.070 --> 39:34.210 So depending on N and M, each such game has a 39:34.207 --> 39:42.157 solution--is that right--which could depend on N and on M, 39:42.159 --> 39:47.459 on the number of rows and columns. 39:47.460 --> 39:51.340 So just as in Nim, it depended on how those piles 39:51.338 --> 39:54.078 started out. So what's going to be the 39:54.084 --> 39:55.444 homework assignment? 39:55.440 --> 40:02.910 Find the solution. 40:02.910 --> 40:13.750 Homework- what is the solution? 40:13.750 --> 40:19.610 So I claim, let me give you a hint, I claim it is useful to 40:19.611 --> 40:23.251 remember that there is a solution. 40:23.250 --> 40:24.560 It turns out to be useful to remember that. 40:24.560 --> 40:25.200 That wasn't much of a hint. 40:25.199 --> 40:28.259 You knew that already, but let me just emphasize that. 40:28.260 --> 40:33.700 Okay, so I want to do a bit of a transition now away from these 40:33.695 --> 40:36.935 games like chess and like checkers, 40:36.940 --> 40:39.170 and like this game with the rocks or Nim, 40:39.172 --> 40:42.022 and I want to be a little bit formal for a while. 40:42.019 --> 40:44.129 So one thing that we haven't done for a while, 40:44.131 --> 40:46.621 actually since the mid-term, is write down some formal 40:46.619 --> 40:51.929 definitions. So I'm going to do that now. 40:51.929 --> 40:52.979 I want at least one of these boards back. 40:52.980 --> 41:16.370 41:16.369 --> 41:19.709 So as I warned very early in the class, there are some points 41:19.712 --> 41:23.062 of the day when we have to stop and do some work and the next 41:23.055 --> 41:25.335 twenty minutes or so is such a point. 41:25.340 --> 41:41.660 41:41.660 --> 41:48.510 So what is this? This is formal stuff. 41:48.510 --> 41:51.670 The first thing I want to do is I want to give you a formal 41:51.670 --> 41:54.670 definition of something I've already mentioned today and 41:54.667 --> 41:57.007 that's the idea of perfect information. 41:57.010 --> 42:00.320 What we've been looking at, or at least since the mid-term, 42:00.321 --> 42:02.321 are games of perfect information. 42:02.320 --> 42:20.100 So a game of perfect information is one in which at 42:20.102 --> 42:41.442 every node, or at each node in the game the player whose turn 42:41.442 --> 43:02.072 it is to move at that node knows which node she is at. 43:02.070 --> 43:03.570 So it's a very simple idea. 43:03.570 --> 43:05.730 Every game we've seen since the mid-term has this property. 43:05.730 --> 43:09.970 When you're playing this game you know where you are. 43:09.969 --> 43:17.389 So you know which node you're at, you know what your choices 43:17.387 --> 43:25.057 are and what that means implicitly is she must know how 43:25.056 --> 43:28.666 she got there. So the whole history of the 43:28.670 --> 43:30.220 game is observed by everybody. 43:30.219 --> 43:32.829 When I get to move I know what you did yesterday, 43:32.831 --> 43:35.281 I know what I did the day before yesterday, 43:35.280 --> 43:38.470 and if I'm playing with a third person I know what they did the 43:38.472 --> 43:41.822 day before that. So a very simple idea but it 43:41.816 --> 43:46.986 turns out to be an idea that actually allows us to use things 43:46.994 --> 43:50.364 like backward induction very simply. 43:50.360 --> 43:54.020 Now so far all we've been doing is thinking about such games, 43:54.024 --> 43:57.404 games like perfect competition, sorry games like quantity 43:57.397 --> 44:00.487 competition between firms or games like the games where we 44:00.493 --> 44:03.103 were setting up incentives or games like Nim, 44:03.099 --> 44:05.829 and we've basically been solving these games by backward 44:05.830 --> 44:07.370 induction, rather informally. 44:07.369 --> 44:10.809 What I want to add in now is the notion of a strategy in 44:10.805 --> 44:13.115 these games. So when we had simultaneous 44:13.124 --> 44:15.804 move games, strategies were really unproblematic. 44:15.800 --> 44:17.640 It was obvious what strategies were. 44:17.639 --> 44:20.409 But when we have games which are sequential, 44:20.407 --> 44:22.657 that go on over a period of time, 44:22.659 --> 44:25.879 and information is emerging over a period of time, 44:25.883 --> 44:29.833 we need to be a little careful what we mean by a strategy. 44:29.829 --> 44:33.779 So what I want to do is I want to define a pure strategy at 44:33.784 --> 44:35.084 least as follows. 44:35.079 --> 44:47.219 So a pure strategy for Player i in a game of perfect 44:47.224 --> 45:00.564 information--so in the games we've been talking about, 45:00.559 --> 45:03.809 games which we can represent by trees is what? 45:03.810 --> 45:22.060 It's a complete plan of action. 45:22.059 --> 45:30.959 So in other words, what it does is it specifies 45:30.957 --> 45:40.817 which action I should take--let's not make it should 45:40.822 --> 45:47.982 take--let's say will take, 45:47.980 --> 45:58.790 at each of i's nodes, each of i's decision nodes. 45:58.789 --> 46:01.579 So when you first read this definition it seems completely 46:01.583 --> 46:03.253 uninteresting and unproblematic. 46:03.250 --> 46:07.050 A pure strategy for Player i just tells you in this game 46:07.052 --> 46:09.892 whenever you might be called upon to move, 46:09.886 --> 46:12.786 it tells you how you're going to move. 46:12.789 --> 46:14.629 So if you're going to move three times in the game, 46:14.632 --> 46:16.662 it tells you how you're going to move the first time; 46:16.659 --> 46:18.449 it tells you how you're going to move the second time; 46:18.449 --> 46:23.819 and it tells you how you're going to move the third time. 46:23.820 --> 46:27.210 So, so far none of this seems difficult but actually it's a 46:27.212 --> 46:29.262 bit more difficult than it looks. 46:29.260 --> 46:29.660 So let's have a look. 46:29.660 --> 46:41.510 46:41.510 --> 46:44.100 What I want to do is I want to look at an example, 46:44.103 --> 46:46.963 and this example I'm hoping is going to illustrate some 46:46.961 --> 46:48.921 subtleties about this definition. 46:48.920 --> 46:57.330 46:57.330 --> 46:57.900 So here's an example. 46:57.900 --> 47:04.050 47:04.050 --> 47:08.320 In this example Player 1 moves first and they can choose in or 47:08.324 --> 47:12.534 out, or if you like let's call it up or down since that's the 47:12.528 --> 47:14.138 way we've drawn it. 47:14.139 --> 47:19.699 So they can choose down or up--and I'll use capital letters 47:19.701 --> 47:24.971 U and D. If Player chooses U then Player 47:24.972 --> 47:31.512 2 gets to move and Player 2 can choose L or R. 47:31.510 --> 47:35.900 If Player 1 moves U followed by Player 2 choosing L, 47:35.902 --> 47:39.802 then Player 1 gets to move, in which case Player 1 could 47:39.796 --> 47:42.536 move up or down and I'll use little letters this time, 47:42.540 --> 47:47.790 u and d. Let's put some payoffs in this 47:47.788 --> 47:54.728 game. So the payoffs are 1,0 here, 47:54.726 --> 48:02.356 0,2 here, 3,1 here and 2,4 here. 48:02.360 --> 48:05.160 So on paper--it's on the board--when you first look at 48:05.161 --> 48:07.171 it, this is a perfectly simple game. 48:07.170 --> 48:08.820 It's just like many of the games we've been looking at 48:08.817 --> 48:09.467 since the mid-term. 48:09.470 --> 48:12.290 It has a tree. We could analyze it by backward 48:12.289 --> 48:15.179 induction, and in a moment we will analyze it by backward 48:15.179 --> 48:17.999 induction. But what I want to do first is 48:18.004 --> 48:21.744 I want to say what are the strategies in this game? 48:21.739 --> 48:27.449 So let's start with Player 2 since it's easier. 48:27.449 --> 48:34.629 Player 2's strategies here are what? 48:34.630 --> 48:37.910 Pretty simple: player 2 only has one decision 48:37.912 --> 48:42.462 node--here's Player 2's decision node--and the strategy has to 48:42.464 --> 48:47.094 tell Player 2 what he's going to do at that decision node. 48:47.090 --> 48:49.470 So there's only two choices, L or R. 48:49.469 --> 48:57.339 So Player 2's strategies are either L or R. 48:57.340 --> 49:00.470 Notice, however, already one slight subtlety 49:00.470 --> 49:05.070 here. Player 2 may never get to make 49:05.068 --> 49:08.558 this choice. So Player 2 is choosing L or R, 49:08.560 --> 49:11.390 but Player 2 may not ever get to make this choice. 49:11.389 --> 49:14.299 In particular, if 1 chose D it's really 49:14.297 --> 49:17.967 irrelevant whether Player 2 has chosen L or R. 49:17.969 --> 49:21.949 Nevertheless, the strategy has to specify 49:21.954 --> 49:28.234 what Player 2 would do were he called upon to make that move. 49:28.230 --> 49:29.270 Now let's look at Player 1's strategies. 49:29.270 --> 49:37.580 49:37.579 --> 49:45.329 So what are Player 1's strategies in this game? 49:45.330 --> 49:54.300 Any takers? Anyone want to guess? 49:54.300 --> 49:59.210 So I claim it's tempting, but it turns out to be wrong, 49:59.212 --> 50:03.672 to say that Player 1 has three strategies here. 50:03.670 --> 50:08.820 It's tempting to say either Player 1 moves D, 50:08.820 --> 50:14.440 in which case we're done, or Player 1 moves U, 50:14.440 --> 50:19.630 in which case at some later date she may be called upon to 50:19.634 --> 50:21.644 choose u or d again. 50:21.639 --> 50:25.179 So it's very tempting to think that Player 1 has just three 50:25.181 --> 50:30.021 strategies here, D in which case we're done, 50:30.020 --> 50:38.470 or U followed by either u or d, if she's reached that point. 50:38.469 --> 50:41.519 But actually, if we follow this definition 50:41.519 --> 50:46.129 carefully, we notice that Player 1 actually has four strategies 50:46.130 --> 50:48.430 here. So let me say what they are and 50:48.431 --> 50:50.221 you'll see why it's a little odd. 50:50.219 --> 50:53.169 So here's one of the strategies we talked about, 50:53.169 --> 50:55.739 U followed by u, and here's another one we 50:55.743 --> 50:59.603 talked about, U followed by d, 50:59.601 --> 51:09.021 but I claim there are two others, D followed by u and D 51:09.023 --> 51:13.473 followed by d. So what's a little weird about 51:13.473 --> 51:15.683 this? What's weird is we know 51:15.676 --> 51:20.896 perfectly well that if Player 1 chooses D she's not going to get 51:20.900 --> 51:24.880 to make the choice, the second choice u or d. 51:24.880 --> 51:29.930 But nevertheless the strategy has to tell us what she would do 51:29.925 --> 51:33.645 at every node, regardless of whether that node 51:33.648 --> 51:37.038 actually is reached by that strategy. 51:37.039 --> 51:40.869 Let me say it again, the strategy has to tell you 51:40.874 --> 51:43.914 what Player 1 would do at that node, 51:43.909 --> 51:49.089 regardless of whether that node is actually reached by playing 51:49.091 --> 51:51.591 that strategy. So a little weird. 51:51.590 --> 51:55.260 There's a bit of redundancy here. 51:55.260 --> 52:02.030 It's a bit redundant. 52:02.030 --> 52:05.440 Now why? Well we'll see why in a second. 52:05.440 --> 52:09.950 Let's first of all consider how this game will be played 52:09.951 --> 52:12.741 according to backward induction. 52:12.739 --> 52:15.319 So how do we play this game according to backward induction? 52:15.320 --> 52:18.650 Where do we start? 52:18.650 --> 52:21.990 Shouldn't be a trick question, where do we start the game 52:21.991 --> 52:24.021 according to backward induction? 52:24.020 --> 52:28.530 At the end okay. So the end here is Player 1 and 52:28.528 --> 52:34.138 Player 1 will choose here to go d, is that right? 52:34.140 --> 52:36.640 Because 3 is bigger than 2. 52:36.639 --> 52:40.899 So if we roll back to Player 2's move, Player 2 if she 52:40.902 --> 52:46.212 chooses L she knows that she'll be followed by Player 1 going d, 52:46.210 --> 52:51.790 in which case she'll get 1, but if she chooses R she'll get 52:51.785 --> 52:56.095 2. So Player 2 will choose R. 52:56.099 --> 53:01.399 So Player 1 here, if she chooses U then Player 2 53:01.396 --> 53:07.926 will choose R and Player 1 will get 0, and if she chooses D 53:07.931 --> 53:12.891 she'll get 1, so Player 1 will choose D. 53:12.889 --> 53:18.789 So, backward induction suggests that Player 1 will choose D; 53:18.789 --> 53:22.359 and followed by Player 2--if Player 2 did get to move--she'd 53:22.363 --> 53:25.363 choose R; followed by Player 1--if she 53:25.363 --> 53:28.783 did get to move again--choosing d again. 53:28.780 --> 53:35.090 Notice that backward induction had to tell us what Player 2 53:35.087 --> 53:39.217 would have done had she got to move. 53:39.219 --> 53:43.339 Backward induction had to consider what Player 2 would 53:43.338 --> 53:47.838 think that Player 1 would have done were Player 1 to get to 53:47.844 --> 53:51.374 move again. So to do backward induction, 53:51.373 --> 53:56.273 Player 1 has to ask herself what Player 2 is going to do; 53:56.269 --> 54:00.099 and Player 2 has to therefore ask herself what Player 1 would 54:00.103 --> 54:02.143 have done; which means Player 1 has to ask 54:02.142 --> 54:04.402 herself what Player 2 thinks Player 1 would have done; 54:04.400 --> 54:09.260 which means we actually needed to say what Player 1 did over 54:09.263 --> 54:10.883 here. Let me say that again. 54:10.880 --> 54:13.880 So backward induction here tells us that Player 1 chooses D 54:13.881 --> 54:15.591 in which case the game is over. 54:15.590 --> 54:19.380 But to do backward induction, to think through backward 54:19.376 --> 54:23.646 induction, we really needed to consider not just what Player 2 54:23.654 --> 54:26.674 was going to do were he to get to move, 54:26.670 --> 54:30.840 but also what Player 2 would think Player 1 would do were 54:30.843 --> 54:34.573 Player 2 to get to move and were to do choose L. 54:34.570 --> 54:39.380 So all of these redundant moves were actually part of our 54:39.377 --> 54:41.177 backward induction. 54:41.179 --> 54:45.669 We need them there so we can think about what people are 54:45.671 --> 54:49.241 thinking. So backward induction tells us 54:49.240 --> 54:54.400 that the outcome of the game is D, but it tells in terms of 54:54.403 --> 54:57.373 strategies, Player 1 chooses D and, 54:57.371 --> 55:01.341 were she to get to move again, would choose D again. 55:01.340 --> 55:09.990 And Player 2 chooses R. 55:09.989 --> 55:14.199 Now let's analyze this game a totally different way. 55:14.199 --> 55:17.339 We now know what the strategies are in the game: 55:17.336 --> 55:19.936 Player 2 has two strategies, L and R; 55:19.940 --> 55:26.680 and Player 1 has four strategies: U/u, 55:26.679 --> 55:30.139 U/d, D/u and D/d. 55:30.139 --> 55:35.599 So let's write up the matrix for this game, 55:35.599 --> 55:40.939 so here it is. It must be a 4 x 2 matrix, 55:40.940 --> 55:48.470 Player 2 is choosing between L and R and Player 1 is choosing 55:48.465 --> 55:58.085 between her four strategies Uu, Ud, Du and Dd and we can put 55:58.085 --> 56:01.905 all the payoffs in. 56:01.909 --> 56:08.189 So (Uu,L) gets us here which is (2,4). 56:08.190 --> 56:17.410 (Uu,R) gets us here which is (0,2). 56:17.409 --> 56:25.239 (Ud,L) gets us here which is (3,1). 56:25.239 --> 56:31.209 (Ud,R) gets us here again which is (0,2). 56:31.210 --> 56:35.000 And Du gets us, going right out of the game 56:35.004 --> 56:39.074 immediately, so we're going to go to (1,0). 56:39.070 --> 56:45.800 And in fact that's also true for (Du,R), and it's also true 56:45.802 --> 56:50.912 for (Dd,L) and it's also true for (D/d,R). 56:50.909 --> 56:54.329 So all of these four strategies at the bottom started off by 56:54.329 --> 56:57.459 Player 1 choosing D, in which case the game is over. 56:57.460 --> 57:00.580 So once again in this matrix you can kind of see the 57:00.580 --> 57:02.600 redundancy I was talking about. 57:02.599 --> 57:06.279 In this matrix, the third row, 57:06.284 --> 57:11.624 the Du row looks the same as the Dd row. 57:11.620 --> 57:15.720 Everyone happy with that? 57:15.719 --> 57:20.269 So when we've had matrices in the past how have we solved the 57:20.269 --> 57:21.819 game? Well we've been doing this 57:21.820 --> 57:23.630 backward induction stuff for a couple of weeks, 57:23.625 --> 57:25.945 but, prior to the mid-term--if I had 57:25.953 --> 57:29.733 given you this on the mid-term what would you have done? 57:29.730 --> 57:33.010 You'd look for a Nash Equilibrium right? 57:33.010 --> 57:35.040 So let's do that: let's look for Nash 57:35.040 --> 57:40.540 Equilibrium. So if Player 2 chooses L then 57:40.536 --> 57:49.246 Player 1's best response is Uu; and if Player 2 chooses R, 57:49.246 --> 57:56.006 then Player 1's best response is either Du or Dd. 57:56.010 --> 58:01.820 Conversely, if Player 1 chooses Uu then Player 2's best response 58:01.824 --> 58:05.734 is L. If Player 1 chooses Ud then 58:05.728 --> 58:09.468 Player 2's best response is R. 58:09.469 --> 58:13.939 If Player 1 chooses Du then Player 2 doesn't care because 58:13.936 --> 58:19.426 they're getting 0 anyway; and if Player 1 chooses Dd then 58:19.426 --> 58:25.016 again Player 2 doesn't care because they're getting 0 58:25.023 --> 58:28.433 anyway. So the Nash Equilibria in this 58:28.433 --> 58:33.593 game are what? So one of them is here, 58:33.593 --> 58:39.153 so that's one Nash Equilibrium. 58:39.150 --> 58:49.500 One of them is Dd followed by R, and that's a Nash Equilibrium 58:49.502 --> 58:56.632 we actually found by backward induction. 58:56.630 --> 59:03.440 The Nash Equilibrium (Dd,R) corresponds to the one we found 59:03.441 --> 59:06.261 by backward induction. 59:06.260 --> 59:08.970 But there's another Nash Equilibrium in this game. 59:08.969 --> 59:14.679 The other Nash Equilibrium in this game is this one. 59:14.680 --> 59:16.640 That's also a Nash Equilibrium. 59:16.640 --> 59:17.540 What does it involve? 59:17.539 --> 59:35.979 It involves Du and R--sorry Du and R. 59:35.980 --> 59:38.230 So what happened in that equilibrium? 59:38.230 --> 59:41.450 Player 1 went down which made everything else kind of 59:41.454 --> 59:45.724 irrelevant. Player 2 played R and Player 1 59:45.723 --> 59:52.193 in their plan of action was actually going to choose u. 59:52.190 --> 59:55.600 Say it again, Player 1 in fact went D, 59:55.601 --> 1:00:01.231 Player 2 had they got to move would have chosen R and Player 1 1:00:01.226 --> 1:00:07.216 had they got to move at this second time would have chosen u. 1:00:07.219 --> 1:00:08.659 So how can that be a Nash Equilibrium? 1:00:08.659 --> 1:00:11.139 It doesn't correspond to backward induction. 1:00:11.139 --> 1:00:15.629 In particular, Player 1 up here is choosing a 1:00:15.631 --> 1:00:18.491 strategy that seems silly. 1:00:18.489 --> 1:00:23.889 They're choosing u rather than d which gets them 2 rather than 1:00:23.886 --> 1:00:26.156 3. So how could it possibly be 1:00:26.163 --> 1:00:28.803 that that's an equilibrium strategy? 1:00:28.800 --> 1:00:31.950 The reason is--the reason it can be an equilibrium strategy 1:00:31.954 --> 1:00:35.274 is it doesn't really matter what Player 1 chooses up here from 1:00:35.271 --> 1:00:38.641 Player 1's point of view because it's never going to be reached 1:00:38.643 --> 1:00:42.173 anyway. As long as Player 2 is going to 1:00:42.171 --> 1:00:46.081 choose R here, it really doesn't matter what 1:00:46.084 --> 1:00:49.274 Player 1 decides to do up there. 1:00:49.269 --> 1:00:51.229 From Player 1's point of view, it doesn't make a difference. 1:00:51.230 --> 1:00:54.800 It isn't reached anyway. 1:00:54.800 --> 1:00:59.380 So we're highlighting here a danger, and the danger is this. 1:00:59.380 --> 1:01:04.340 If you just mechanically find the Nash Equilibria in a game, 1:01:04.344 --> 1:01:08.724 you're going to find people choosing actions that, 1:01:08.719 --> 1:01:13.529 if they ever were called upon to make them, 1:01:13.534 --> 1:01:15.584 are silly. Say it again, 1:01:15.575 --> 1:01:18.795 if you just mechanically find the Nash Equilibria in the game, 1:01:18.800 --> 1:01:21.540 just as we did here, you're going to select some 1:01:21.544 --> 1:01:24.234 actions, in this case an action by Player 1, 1:01:24.230 --> 1:01:28.000 that were she called upon to take that action would be a 1:01:28.001 --> 1:01:31.431 silly action. The reason it's surviving our 1:01:31.426 --> 1:01:36.546 analysis is because in fact she isn't called upon to make it. 1:01:36.550 --> 1:01:40.400 Now to make that more concrete, let's take this to an economic 1:01:40.399 --> 1:01:42.039 example, this same idea. 1:01:42.040 --> 1:01:57.150 1:01:57.150 --> 1:02:02.220 So what I want you to imagine is a market, and in this market 1:02:02.222 --> 1:02:06.282 there is a monopolist who controls the market, 1:02:06.280 --> 1:02:10.880 but there's an entrant who is thinking of entering into this 1:02:10.878 --> 1:02:14.208 market. So right now this market has a 1:02:14.206 --> 1:02:17.616 monopoly in it, and the monopolist is an 1:02:17.620 --> 1:02:22.090 incumbent--let's call him Inc--and an entrant who is 1:02:22.085 --> 1:02:27.425 trying to decide whether or not to enter the market or whether 1:02:27.426 --> 1:02:31.106 to stay out. If they stay out then the 1:02:31.110 --> 1:02:35.470 entrant gets nothing and the incumbent continues to get 1:02:35.473 --> 1:02:37.093 monopoly profits. 1:02:37.090 --> 1:02:41.320 So think of this as 3 million a year. 1:02:41.320 --> 1:02:45.640 If the entrant enters then the incumbent can do one of two 1:02:45.638 --> 1:02:48.228 things. The incumbent could choose to 1:02:48.231 --> 1:02:51.131 fight the entrant, by which I mean charge low 1:02:51.131 --> 1:02:54.561 prices, advertise a lot, try and drive him out of the 1:02:54.559 --> 1:02:56.979 market. He could play very 1:02:56.982 --> 1:03:00.972 competitively, in which case the entrant will 1:03:00.973 --> 1:03:05.423 actually make losses, and the incumbent will drive 1:03:05.418 --> 1:03:08.138 her profits down to zero. 1:03:08.139 --> 1:03:13.159 Conversely, the incumbent could choose not to fight. 1:03:13.159 --> 1:03:17.159 If they don't fight then they'll simply share the market 1:03:17.156 --> 1:03:20.786 and they'll both make, let's say Cournot profits or 1:03:20.789 --> 1:03:23.549 duopoly profits of a million each. 1:03:23.550 --> 1:03:25.640 So in this game, let's just say again, 1:03:25.638 --> 1:03:27.048 there's a market there. 1:03:27.050 --> 1:03:30.920 The monopolist is in the market and the monopolist is making 3 1:03:30.916 --> 1:03:34.716 million a year which seems pretty nice for the monopolist. 1:03:34.719 --> 1:03:38.419 The entrant is trying to decide whether to invade this market. 1:03:38.420 --> 1:03:42.230 If she invades this market, if she's fought she's in 1:03:42.227 --> 1:03:45.957 trouble, but if the monopolist accommodates her, 1:03:45.960 --> 1:03:49.950 then they just go to duopoly profits and the entrant does 1:03:49.951 --> 1:03:53.231 very well, gets a million dollars in profit. 1:03:53.230 --> 1:03:55.130 Let's have a look at this game. 1:03:55.130 --> 1:03:58.980 Analyze--first of all this time, let's analyze it by Nash 1:03:58.978 --> 1:04:02.108 Equilibrium. So I claim in this game, 1:04:02.112 --> 1:04:07.092 this is pretty simple: the entrant has two strategies. 1:04:07.090 --> 1:04:08.890 I'll put it straight into the matrix. 1:04:08.889 --> 1:04:19.169 The entrant has two strategies, they're either to go in or to 1:04:19.166 --> 1:04:24.386 stay out; and the incumbent has two 1:04:24.390 --> 1:04:32.010 strategies, they are either to fight the entrant or not to 1:04:32.007 --> 1:04:34.587 fight. The payoffs of this game are as 1:04:34.586 --> 1:04:35.826 follows--let's put them in. 1:04:35.829 --> 1:04:41.919 In and fight was (-1,0), in and not fight was (1,1) and 1:04:41.920 --> 1:04:47.450 out led to the incumbents maintaining the monopoly 1:04:47.446 --> 1:04:50.806 profits. Let's have a look at the Nash 1:04:50.813 --> 1:04:52.553 Equilibria of this game. 1:04:52.550 --> 1:04:56.230 So the first thing to do is to look at the best responses for 1:04:56.231 --> 1:04:59.641 the entrant. So if the incumbent chooses 1:04:59.637 --> 1:05:04.917 fight, then the entrant's best response is to stay out. 1:05:04.920 --> 1:05:11.230 If the incumbent chooses not fight, then the entrant's best 1:05:11.228 --> 1:05:13.728 response is to enter. 1:05:13.730 --> 1:05:15.520 How about for the incumbent? 1:05:15.519 --> 1:05:20.179 If the entrant chooses to come in then the incumbent's best 1:05:20.180 --> 1:05:24.520 response is not to fight because 1 is bigger than 0. 1:05:24.519 --> 1:05:30.079 But if the entrant stays out it really doesn't matter what the 1:05:30.080 --> 1:05:34.000 incumbent does, they'll get 3 either way. 1:05:34.000 --> 1:05:42.190 So the Nash Equilibria here are either in followed by not 1:05:42.190 --> 1:05:50.090 fighting, you end up with a duopoly, or out followed by 1:05:50.088 --> 1:05:54.568 fighting. Of course the fight doesn't 1:05:54.573 --> 1:05:59.933 take place: out followed by "we would have fought had you 1:05:59.931 --> 1:06:02.091 entered." So these are the Nash 1:06:02.085 --> 1:06:04.775 Equilibria. Let's analyze this game by 1:06:04.779 --> 1:06:06.409 backward induction. 1:06:06.409 --> 1:06:11.589 From the incumbent's point of view, if the incumbent gets to 1:06:11.594 --> 1:06:16.344 move then is she going to choose fight or not fight? 1:06:16.340 --> 1:06:23.060 She's going to choose not fight, so the entrant should do 1:06:23.059 --> 1:06:24.809 what? Somebody? 1:06:24.809 --> 1:06:27.309 The entrant should enter, because if she enters she gets 1:06:27.309 --> 1:06:28.809 1, if she stays out she gets 0. 1:06:28.809 --> 1:06:41.659 So backward induction just gives us this equilibrium. 1:06:41.659 --> 1:06:44.849 Now the question is what do we think is going on with this 1:06:44.850 --> 1:06:45.970 other equilibrium? 1:06:45.970 --> 1:06:48.420 Let's talk it through. 1:06:48.420 --> 1:06:50.410 So here you are, you're about to enter the 1:06:50.407 --> 1:06:52.877 market, you leave Yale, you set up your business, 1:06:52.880 --> 1:06:56.220 and your business is challenging some monopolist or 1:06:56.217 --> 1:06:58.817 quasi-monopolist like Microsoft say., 1:06:58.820 --> 1:07:01.580 And you go out there and you're about to put out your new 1:07:01.575 --> 1:07:02.505 operating system. 1:07:02.510 --> 1:07:06.250 And you know that your new operating system will make 1:07:06.250 --> 1:07:10.210 plenty of money provided Microsoft doesn't retaliate and 1:07:10.206 --> 1:07:14.806 drop its prices by half and advertise you out of the market. 1:07:14.810 --> 1:07:16.190 So what does Bill Gates do? 1:07:16.190 --> 1:07:17.680 Bill Gates is the head of Microsoft. 1:07:17.679 --> 1:07:21.569 He says, wait a second before you graduate from Yale and go 1:07:21.572 --> 1:07:24.932 set up this company, let me just tell you I'm going 1:07:24.927 --> 1:07:30.147 to fight. If you enter I'm going to fight. 1:07:30.150 --> 1:07:34.230 And if you believe him, if you believe that he's going 1:07:34.225 --> 1:07:36.605 to fight, what should you do? 1:07:36.610 --> 1:07:37.910 You're not going to bother to enter his market. 1:07:37.909 --> 1:07:40.759 And if you believe that you're going to get fought by Bill 1:07:40.755 --> 1:07:43.745 Gates then you believe that if you enter you're going to make 1:07:43.750 --> 1:07:47.060 losses, so you choose to stay out. 1:07:47.059 --> 1:07:52.399 And this threat that Bill Gates makes here it doesn't cost him 1:07:52.396 --> 1:07:57.376 anything, provided you go out, he doesn't actually have to 1:07:57.382 --> 1:08:00.652 fight at all. That's why it is in fact an 1:08:00.653 --> 1:08:04.093 equilibrium to imagine you staying out believing that 1:08:04.089 --> 1:08:06.929 you're going to get fought if you enter, 1:08:06.929 --> 1:08:11.029 and it is a best response for the guy to fight knowing that 1:08:11.030 --> 1:08:12.940 you're going to stay out. 1:08:12.940 --> 1:08:15.240 But this doesn't sound right. 1:08:15.240 --> 1:08:17.120 Why doesn't this sound right? 1:08:17.119 --> 1:08:21.399 It doesn't sound right because you really shouldn't believe the 1:08:21.403 --> 1:08:25.623 guy who says he's going to fight you when you know that if you 1:08:25.618 --> 1:08:29.348 did enter fighting would cost the incumbent money. 1:08:29.350 --> 1:08:32.980 If you did enter, if he fights you he gets 0, 1:08:32.979 --> 1:08:36.939 if he doesn't fight he gets a million dollars. 1:08:36.939 --> 1:08:41.799 So this threat that the guy is going to fight you, 1:08:41.802 --> 1:08:44.782 this threat is not credible. 1:08:44.779 --> 1:08:55.859 This is an equilibrium but it relies on believing an 1:08:55.856 --> 1:09:00.196 incredible threat. 1:09:00.200 --> 1:09:10.530 1:09:10.529 --> 1:09:13.579 It's true that if you think about entering the market that 1:09:13.581 --> 1:09:15.881 Microsoft is in, you're very likely to get a 1:09:15.883 --> 1:09:17.653 little email from Bill Gates. 1:09:17.649 --> 1:09:20.509 (But it won't be an email because that can be taken to 1:09:20.508 --> 1:09:23.308 Court, but some little threatening remark in your ear 1:09:23.312 --> 1:09:26.662 from Bill Gates.) It's true if you entered into the market that 1:09:26.656 --> 1:09:28.756 the people who build aircraft in, 1:09:28.760 --> 1:09:32.270 the head of Boeing might pay you a call one day or send 1:09:32.274 --> 1:09:34.814 someone round, but these threats are not 1:09:34.813 --> 1:09:36.183 credible threats. 1:09:36.180 --> 1:09:38.600 Is that right? They're not credible threats 1:09:38.597 --> 1:09:42.577 because we know that if you did enter, it isn't in their 1:09:42.579 --> 1:09:44.099 interest to fight. 1:09:44.100 --> 1:09:48.280 They're making a lot of noise about it but you know that if 1:09:48.275 --> 1:09:51.225 you did enter, backward induction tells us 1:09:51.228 --> 1:09:53.458 they're not going to fight. 1:09:53.460 --> 1:09:57.110 But now we're in slightly an odd situation, 1:09:57.111 --> 1:09:59.981 why are we in an odd situation? 1:09:59.980 --> 1:10:03.970 Two things. One, we seem to be finding that 1:10:03.965 --> 1:10:09.685 there are Nash Equilibria in games--we found one here and one 1:10:09.686 --> 1:10:14.066 up here--there are Nash Equilibria that are not 1:10:14.072 --> 1:10:17.602 supported by backward induction. 1:10:17.600 --> 1:10:21.470 That's the first reason we're a little worried here, 1:10:21.465 --> 1:10:25.935 and the second reason we're worried is even the economics of 1:10:25.937 --> 1:10:28.587 this doesn't quite smell right. 1:10:28.590 --> 1:10:30.780 For example, if you in fact did 1:10:30.779 --> 1:10:33.989 enter--sorry, if you did in fact announce you 1:10:33.992 --> 1:10:37.492 were going to operate, you were going to build a new 1:10:37.488 --> 1:10:40.688 operating system and got a threatening phone call from Bill 1:10:40.685 --> 1:10:43.985 Gates--there might be a reason why you might actually believe 1:10:43.993 --> 1:10:50.303 that call. Why might you believe that call? 1:10:50.300 --> 1:10:54.210 Can we get a mike out, I'll do it. 1:10:54.210 --> 1:10:57.560 So why might you believe a call from Bill Gates saying he's 1:10:57.563 --> 1:11:01.093 going to beat you up--not beat you up but he's going to charge 1:11:01.089 --> 1:11:03.979 low prices if you produce an operating system? 1:11:03.979 --> 1:11:06.559 Student: If you look at the future revenue streams, 1:11:06.558 --> 1:11:09.318 like for the next ten years and he consistently gets 1 million 1:11:09.316 --> 1:11:12.216 dollars for the next ten years, he would be better off if he 1:11:12.215 --> 1:11:15.175 just drove you out of the market for the first year and then get 1:11:15.175 --> 1:11:17.285 3 million dollars for the next nine years. 1:11:17.289 --> 1:11:18.419 Professor Ben Polak: That wasn't quite what I wasn't 1:11:18.417 --> 1:11:20.437 thinking of. Okay, it's true if we cheat a 1:11:20.439 --> 1:11:23.819 bit and make one of the--Okay, so what you're saying is I 1:11:23.817 --> 1:11:26.227 could get 3 forever versus 1 forever, 1:11:26.229 --> 1:11:29.199 assume these are both present discounted values of future cash 1:11:29.195 --> 1:11:31.865 earnings. So we've done the future cash 1:11:31.871 --> 1:11:33.571 flow analysis of this. 1:11:33.569 --> 1:11:37.399 So this isn't an accounting mistake, not for accounting 1:11:37.400 --> 1:11:40.000 reasons. There's some other reason when 1:11:40.002 --> 1:11:43.222 Gates threatens you, you might want to believe it. 1:11:43.220 --> 1:11:44.640 Let's try up here first. 1:11:44.640 --> 1:11:47.120 Student: He can afford to make an example of you so no 1:11:47.122 --> 1:11:48.242 other people will invade. 1:11:48.239 --> 1:11:50.789 Professor Ben Polak: Right, so one thing that's in 1:11:50.785 --> 1:11:54.545 Bill Gates' mind is right now, he's thinking about competing 1:11:54.546 --> 1:11:58.996 with you but down the road there's a lot more of you guys 1:11:59.001 --> 1:12:02.511 coming--whatever it is, 280 of you in this room and 1:12:02.508 --> 1:12:05.278 there's another 280 in next year's class and so on. 1:12:05.279 --> 1:12:08.679 And Bill Gates knows that each of you might come out and 1:12:08.681 --> 1:12:11.651 threaten his monopoly, his Microsoft monopoly. 1:12:11.649 --> 1:12:15.539 And he might think that by setting an example to one of you 1:12:15.541 --> 1:12:18.361 he might be able to keep the others out. 1:12:18.359 --> 1:12:22.809 And somewhere that kind of argument, the argument of making 1:12:22.814 --> 1:12:25.734 an example of somebody is missing here: 1:12:25.733 --> 1:12:27.503 missing completely. 1:12:27.500 --> 1:12:31.360 But it's got to be important, it's got to be an important 1:12:31.357 --> 1:12:33.857 idea. So we're going to come back and 1:12:33.857 --> 1:12:37.177 spend the first half of Wednesday's class picking up 1:12:37.177 --> 1:12:38.997 just precisely that idea.