YT YouTube2Text

YouTube2Text → Transcripts → 15. Backward induction: chess, strategies, and credible threats

15. Backward induction: chess, strategies, and credible threats — Transcript

by YaleCourses · 10,006 words · 1,042 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01Professor Ben Polak: So last time we finished up by
0:04playing the game of Nim and you'll remember,
0:06I hope, that the game of Nim was a game where there was two
0:11piles of stones--we made do with lines on the board--and the
0:15winner was the person who picked up the last stone.
0:19Remember you had to pick piles. I want to use the game of Nim
0:23to make a transition here. So what we had pointed out
0:27about the game of Nim was it illustrated very nicely for us
0:31that games can have first mover advantages or they can have
0:34second mover advantages. A very small change in the
0:38game, essentially a very small change in where we started from,
0:42could switch a game from a game with a first mover advantage to
0:46a game with a second mover advantage.
0:49Now today, I want to just draw a slightly grander lesson out of
0:54that game. So not only was it the case
0:56that the game sometimes has first mover advantages and
0:59sometimes has second mover advantages,
1:01but moreover, we could tell when it had a
1:04first mover advantage and we could tell when it had a second
1:08mover advantage. Is that right?
1:10When we actually looked at the initial set up of those stones,
1:13we knew immediately that's a game in which Player 1 is going
1:16to win, or alternatively,
1:18we knew immediately that's a game which Player 2 is going to
1:22win. Now it turns out that that idea
1:24is very general and actually has a name attached to it,
1:28and that name is Zermelo.
1:35So today we'll start off by talking about a theorem due to a
1:38guy called Zermelo, and the idea of this theorem is
1:42this. We're going to look at games
1:44more general than just Nim, and we're going to ask the
1:46question, under what circumstances would
1:49you know about a game either that Player 1,
1:51the person who goes first, can force a win,
1:54or that Player 2 can force a win, or will allow a third
1:58possibility, which is it's going to be a tie.
2:03So here's the theorem, suppose there are two players
2:06in this game, like the games that we looked
2:09at last time, and suppose--I won't define
2:13this formally now--but suppose the game is a game of perfect
2:18information. So what do I mean by perfect
2:21information? I'll define this later on in
2:23the class, but for now all I mean is, that whenever a player
2:27has his turn to move, that player knows exactly what
2:31has happened prior in the game. So, for example,
2:34all these sequential move games we've been looking at are moves
2:36of perfect information. When I get to move I know
2:39exactly what you did yesterday, I know what I did the day
2:42before yesterday and so on. So it's a game of perfect
2:45information. I'm going to assume that the
2:48game has a finite number of nodes.
2:51So two things here, it can't go on forever,
2:54this game, and also there's no point in which it branches in an
2:58infinite way. So there's a finite number of
3:01nodes, and we'll assume that the game has three possible
3:04outcomes. Actually there's a more general
3:07version of this theorem but this will do for now.
3:09The three possible outcomes are either a win for Player 1,
3:14so I'll call it W_1, or a loss for Player 1,
3:19which is obviously a win for Player 2, or a tie.
3:25So the game--like Nim last time, that only had two
3:27outcomes. So here we're going to look up
3:30to three outcomes or three or fewer outcomes I should say.
3:35So these are the conditions and here's the result.
3:39So I said three, it could be three but it could
3:42also be two here, I'm just allowing for three.
3:45(One is trivial.) So under these conditions the following
3:51is true. Either Player 1 can force a
3:55win, so either it's the case that this game is a game that if
4:01Player 1 plays as well as they can,
4:04they're going to win the game no matter what Player 2 does.
4:09Or 1 can at least force a tie, which means Player 1 can play
4:17in such a way that they can assure themselves of a tie
4:23regardless of what Player 2 does.
4:28Or it could be a game in which 2 can force a loss on 1,
4:41so a win for 2. So this theorem,
4:45when you first look at it, it doesn't seem to say very
4:48much. You're staring at this
4:49thing--you might think, we already knew that we're
4:52looking at games that only have three possible outcomes win,
4:56loss, or tie so it doesn't seem so surprising if you look at
5:00this theorem, it says,
5:02well, you're going to end up with a win, or a loss,
5:04or a tie. However, that's not quite what
5:06the theorem says. The theorem says,
5:08not only are you going to end up there--we knew that
5:11already--but the games divide themselves.
5:13Games of these forms divide themselves into those games in
5:17which Player 1 has a way of winning regardless of what
5:20Player 2 does; or games in which Player 1 has
5:23a way of forcing a tie regardless of what Player 2
5:27does; or Player 2 has a way of
5:29winning regardless of what Player 1 does,
5:32so these games all have a solution.
5:34Let's just go back to Nim to illustrate the point.
5:37So in Nim actually there's no tie so we can forget the middle
5:41of these, and in Nim, under certain circumstances it
5:45is the case that Player 1 can force a win.
5:48Who remembers what the case was, for when Player 1 can force
5:52a win? Anybody?
5:54The people who played last time. No, yes, Ale,
6:00there's somebody here. Shout it out.
6:04Student: Insuring that the piles are equal for the
6:06other player. Professor Ben Polak: All
6:10right, so if the piles start unequal, then Player 1 can
6:14actually force a win. So in Nim if the piles are
6:21unequal at the start, then 1 can force a win.
6:29It really doesn't matter what 2 does, 2 is "toast."
6:33Or the alternative case is the piles are equal at the start,
6:37and if they're equal at the start then it's Player 1 who's
6:42"toast." Player 2 is going
6:44to--rather--force a loss on 1, so 2 can force a loss on 1,
6:51i.e. a win for Player 2.
6:55Does everyone remember that from last time?
6:58It's just before the weekend, it shouldn't be so long ago.
7:02So this theorem applies to all games of this form.
7:08So what games are of this form? Let's try and think of some
7:10other examples. So one example is tic-tac-toe.
7:15Everyone know the rules of tic-tac-toe?
7:16In England we call it Noughts and Crosses, but you guys call
7:18it tic-tac-toe, is that right?
7:20Everyone know what tic-tac-toe is?
7:22Yeah, which category is tic-tac-toe?
7:26Is it a game which Player 1 can force a win, or is it a category
7:29in which Player 1 can only force a tie,
7:32or is it a category which you'd rather go second and Player 2
7:35can force a win for Player 2 or a loss for Player 1?
7:37Which is tic-tac-toe? Let's have a show of hands here.
7:41Who thinks tic-tac-toe is a game in which Player 1 can force
7:45a win? Who thinks tic-tac-toe is a
7:47game in which Player 1 can only force a tie?
7:50Who thinks Player 2's going to win?
7:53Most of you are right. It's a game in which if people
7:56play correctly then it'll turn out to be a tie.
7:59So tic-tac-toe is a game that leads to a tie.
8:07Player 1 can still make a mistake, in which case they can
8:10lose. Player 2 can make a mistake in
8:13which case they would lose, but there is a way of playing
8:17that forces a tie. So these are fairly simple
8:19games, let's talk about more complicated games.
8:21So what about the game of checkers?
8:24So the game of checkers meets these conditions.
8:26It's a two player game. You always know all the moves
8:29prior to your move. It's finite:
8:31there's some rules in checkers that prevent it going on
8:34forever. And there are two or three
8:36outcomes: I guess there's a third outcome if you get into a
8:39cycle you could tie. So checkers fits all these
8:42descriptions and what this theorem tells us is that
8:45checkers has a solution. I'm not sure I know what that
8:48solution is, or I think actually somebody did compute it quite
8:50recently, even in the last few months,
8:52I just forgot to Google it this morning to remind myself.
8:54But what this theorem tells us even before those people that
8:57computed it: checkers has a solution.
9:00Let's be a bit more ambitious. What about chess?
9:04So chess meets this description. Chess is a two player game,
9:07everybody knows all the moves before them, it's sequential,
9:11it has finite number of moves, it's a very large number but it
9:15is finite, and it has three possible outcomes,
9:18a win, a loss, or a tie. So let's be careful,
9:21the reason it's finite is that if you cycle--I forget what it
9:25is--three times then the game is declared a draw,
9:28declared a tie. So what's this theorem telling
9:30us? It's telling us that there is a
9:35way to solve chess. Chess has a solution.
9:41We don't know what that solution is.
9:43It could be that solution is that Player 1,
9:45who's the player with the white pieces can force a win.
9:49It could be that Player 1 can only force a tie,
9:52and it could even be that Player 2 can force a win.
9:54We don't know which it is, but there is a solution.
9:59There's a catch to this theorem. What's the catch?
10:02The catch is it doesn't actually tell us--this theorem
10:05is not going to tell us what that solution is.
10:07It doesn't tell us how to play. This theorem,
10:10in and of itself, doesn't tell us how to play
10:12chess. It just says there is a
10:16way to play chess. So we're going to try and prove
10:19this. We don't often do proofs in
10:21class, but the reason I want to prove this particular one is
10:25because I think the proof is instructive as part of sort of
10:28QR at Yale. So here's another example here,
10:31and some other examples. You could think of chess as
10:34being the most dramatic example.
10:49So the reason I want to spend actually some time proving this
10:56today is because we're going to prove it by induction and I'm
11:03going to sketch the proof. I'm not going to go through
11:08every possible step but I want to give people here a feeling
11:10for what a proof by induction looks like.
11:12The reason for this is, my guess is,
11:14well let's find out, how many of you have seen a
11:17proof by induction before? How many have not?
11:20So for those of you who haven't I think it's a good thing in
11:22life, at one point in your life to see a proof by induction,
11:24and for those who have, my guess is you saw it in some
11:27awful math class in high school and it just went over--it didn't
11:30necessarily go over your head but,
11:32the excitement of it doesn't catch on.
11:36This is a context where it might appeal.
11:40So proof by induction. We're going to prove this by
11:46induction on the maximum length of the game and we'll call that
11:57N. We'll call N the maximum length
11:59of the game. What do I mean by this?
12:00If I write down a tree I can always look at all the paths
12:06from the beginning of the tree all the way through to the end
12:11of the tree. And I'm going to look at the
12:14path in that particular tree that has the largest length,
12:18and I'll call that the length of the game, the maximum length
12:21of the game. So we're going to do induction
12:24on the maximum length of the game.
12:26So how do we start a proof by induction?
12:28Let's just remind ourselves, those people who have seen them
12:30before. We're going to prove that this
12:33theorem this true, the claim in the theorem is
12:36true for the easy case when the game is only 1 move long.
12:41That's the first step, and then we're going to try and
12:45show that if it's true for all games of length <
12:49= N, whatever N is,
12:51then it must therefore be true for games of length N+1.
12:56That's the way you do a proof by induction.
12:58So let's just see how that works in practice.
13:01So let's start with the easy step and we'll do it in some
13:04detail, more detail than you really need to in a math class.
13:08So if N = 1, what do these games look like?
13:11Well let's look at some examples here.
13:13So I claim it's pretty trivial if N = 1 but let's do it anyway.
13:18So the game might look like this.
13:20Player 1 is going to move--here's Player 1
13:22moving--the game's only length one--so Player 1's the only
13:26player who ever gets to move. So the game might look like
13:30this. Let's put in a fifth branch,
13:32it might look like this. And at the end of this game,
13:34rather than putting payoffs let me just put the outcomes.
13:37So the outcome must either be a win, or a tie,
13:40or a loss, so suppose it looks like this.
13:43Suppose it's a win, or here we could have a tie,
13:47or here we could have a win again, or here we could have a
13:53loss, and here we could have a tie.
13:57So in this particular game I claim it's pretty clear this
14:02game has a solution. It's pretty clear what 1 should
14:06do. What should 1 do?
14:081 should pick one of her choices that leads to a win.
14:12To be careful I'll put 1 in here just to distinguish who it
14:15is who's actually winning and losing.
14:17So in this game I claim that this game has a pretty obvious
14:21solution, either Player 1 is going to choose this branch that
14:24leads to a win or this branch that leads to a win,
14:27and either way Player 1 is going to win.
14:31Is that obvious? It's so obvious,
14:33it's kind of painful. So I claim this game,
14:35we could actually replace this first node with what's going to
14:39happen which is Player 1's going to win.
14:43Is that right? That was easy.
14:45Let's look at a different example, we'll do three.
14:49So here's another possible example, and this again,
14:53Player 1 is going to move here and this time the possible
14:57outcomes are tie, or a loss, or a loss.
15:01Once again it's a one player game, this time he has three
15:05choices and the three choices lead to a tie or he loses,
15:09so I claim once again this is simple.
15:11What Player 1 should do is what? Choose the tie since there's no
15:13way of winning. But in that case he could
15:15actually force it. He could actually choose the
15:17tie in which case he's going to tie.
15:19So this game has a solution called choose the tie.
15:21And again, we could replace the first node of the game with
15:25what's actually going to happen which is a tie.
15:29Everyone happy? There's one other possibility I
15:32guess. The other possibility is that
15:35here Player 1 has a lot of choices, maybe four choices in
15:39this case, once again Player 1 is going to
15:43move but in each case--unfortunately for Player
15:481--in each case the outcome is that Player 1 loses.
15:54So this is a game in which Player 1 is going to lose no
15:56matter what they do. Once again it has a solution:
15:59the solution is Player 1 is toast and is going to lose.
16:08So I claim this has really captured all the possibilities
16:10of games of length 1. I mean you could imagine that
16:13there could be more branches on them, but basically there are
16:16these three possibilities. Either it's the case that one
16:19of those branches leads to a win, in which case the solution
16:22is Player 1 wins; or it's the case that none of
16:25the branches have wins in them, but one of them has a tie,
16:28in which Player 1 is going to tie;
16:30or it's the case that all the branches have loss in them,
16:33in which Player 1's going to lose.
16:35So I claim I'm for done for games of length one.
16:38Everyone okay? So that step is deceptively
16:42easy but there it is. All right, now we do the
16:45inductive step, the big step.
16:47What we're going to do is we're going to assume that the
16:50statement of the theorem, which I've now hidden
16:53unfortunately--let me unhide it if I can, it's not going to be
16:57easy.
17:05This now visible? So now let's assume that the
17:10statement of this theorem is true for all games length <
17:17= N, suppose that's the case. Suppose the claim is true for
17:29all games of this type, of length <= some N.
17:41What we need to show is--what we're going to try and show is
17:45therefore it will be true for all games of length N + 1.
17:50What we want to show is--we claim, therefore,
17:58it will be true for games of length N + 1,
18:07that's the key step in inductive proofs.
18:16All right, so how are we going to do that?
18:19Well let's have a look at a game of length N + 1,
18:22and obviously I can't use thousands here so let me choose
18:24from relatively small numbers, but the idea will go through.
18:28So let's have a look at a game. So here's a game in which
18:34Player 1 moves first, Player 2 moves second.
18:40Let's suppose that if Player 2 does this, then 1 only has
18:44little choice here, up here then one has a more
18:48complicated choice, and perhaps 2 could move again.
18:53So this is quite a complicated little game up here,
18:55and down here let's make it a little bit less complicated.
18:58Here the game looks like this and then comes to an end,
19:02so the tree looks like this. I haven't put the end,
19:06I haven't put the outcomes on it but the tree looks like this.
19:09So how long is this tree first of all?
19:12Well I claim that the longest path in this tree,
19:16from the beginning to the end has four steps.
19:20Let's just check. So one, two,
19:23three, four that's what I claim is the longest path.
19:27Any path going down this way only has three moves in it,
19:33so this is a game of length four.
19:36So we can apply it to our claim, let's assume that the
19:42theorem holds for all trees length three or fewer,
19:47so that N + 1 is 4 for the purpose of our example.
19:51So in this example--I don't want to put it here,
19:57let's put it here--in this example N = 3,
20:03so that N + 1 = 4. Everyone happy with this in the
20:09example? Now what I want to observe
20:12about this is the following: contained in this N + 1,
20:17or the game of length 4 are some smaller games.
20:21You could think of them as sub-games.
20:23They're games within the game, is that right?
20:26So let's have a look. I claim, in particular--draw
20:31around them in pink--there's a game here that follows Player 1
20:40choosing Up and there's a game here that follows Player 1
20:47choosing Down, is that right?
20:53Okay, so these are both games, and what do we have here?
20:58So this little game in here--the game in the top
21:02circle, the game that follows Player 1 moving up--that's a
21:06game and it has a length. So this little thing is a game
21:10and I'm going to call it a sub-game, some jargon that we'll
21:14be getting used to later on in the semester.
21:17It's a game within the game, but it's basically just a game:
21:25it's a sub-game and this is a sub-game following 1 choosing
21:32Up--let's put Up in here--following up.
21:38And I claim that this game has a length--this sub-game has a
21:41length. So we knew that we started from
21:44a game of length 4, we've taken one of the moves,
21:46and let's just make sure this is actually a game of length 3.
21:50So the game started here, this would be a game of length
21:533 because you could go one, two, three moves,
21:55is that right? So this is a game of length 3.
21:59So this is a sub-game following 1 choosing Up and it,
22:08the sub-game, has length 3.
22:13Down here, this is also a sub-game, it's a game that
22:21follows Player 1 choosing Down and this little sub-game has
22:29length--now here we have to be a little bit careful--you might
22:39think that since we started from a game of length 4,
22:48after the first move we must be in a game of length 3.
22:53But actually that's not true, and if we look carefully,
22:56we'll notice that this game down here, the game starting
22:58here actually isn't of length 3. It's of length 2.
23:02Is that right? So even though started from a
23:04game of length 4, by going this way we put
23:06ourselves into a game of length 2.
23:08Is that right? So 1,2 or 1,2--whatever--it has
23:16length 2. Okay, all right so in this
23:20example N is 3 and N + 1 is 4, and our assumption,
23:25our induction assumption is what?
23:29We've assumed that the claim of the theorem holds for all games
23:38<= N, which in this case means <= 3.
23:44So what does that tell us? That tells us,
23:47by our assumption, this game, which I've put a
23:51pink circle around on the top, this is a game of length 3,
23:56this game has a solution. It must have a solution because
24:02it's of length 3 or less. So by the induction hypothesis
24:07as it's called--by the induction hypothesis--this is a technical
24:14term, but what's the induction hypothesis?
24:19It's this thing. By the assumption that we made
24:29this game has a solution. So it's a game of length 3,3
24:38<= N in this case. So this game must have a
24:40solution. Now I don't immediately know by
24:44staring at it what it is, but let's suppose it was W,
24:50say it was W. And the game down below,
24:53this is also a game, and it's a game of length 2 but
24:572 is less than 3 as well, 2 <= 3.
25:00So this game also has a solution.
25:06This game also, by the same assumption,
25:13has a solution, so its solution is say--I don't
25:22know--maybe its L. So what does that mean to say
25:29that these games have solutions, in this case we're going to
25:33assume W is this one, and L is this one,
25:35what does it mean? It means that,
25:38just as we did with the games up there, we could put the
25:41solution at the beginning of the game.
25:44We know that if we get into this game, we're going to get
25:47the solution of this game; and we know if we get into this
25:51game, we're going to get the solution of this game.
25:54So we can replace this one with its solution which by assumption
25:58was W, and this one by its solution which by assumption was
26:03L. And here I want to be really
26:04careful, I need to keep track of which person it is it's a win or
26:08loss for. So this was a win for Player 1,
26:10hence it was a loss for Player 2, and this was a loss for
26:14Player 1, hence it was a win for Player 2.
26:18So these games, each of them have some
26:22solution, and this case I've written down the solutions as W
26:28or L. So now what could we do?
26:31Let me just bring down this board again.
26:33I can translate this game into a very simple game.
26:37I'm going to translate it up here, so this game can be
26:40translated as follows. Player 1 moves,
26:47if he goes Up then he hits a W and if he goes Down he hits a L.
27:06So in this particular example, Player 1 is effectively
27:09choosing between going Up and finding himself in a game which
27:13has a solution, and the solution is he wins it,
27:16or going Down and finding himself in a game which has a
27:20solution, and the solution is he's toast.
27:24But that's what? That's a one move game.
27:29So we know this has a solution, and in particular,
27:31he's going to choose Up. This one has a solution.
27:37This has a solution, it is a game of length 1.
27:55So what do we do? Somewhat schematically,
27:59we took a game of length N + 1, in this case that was 4;
28:04and we pointed out that once Player 1 has made her first move
28:09in this game, we are in a game,
28:12or in a sub-game if you like, that has length less than 4,
28:15it could be 3, it could be 2,
28:17whatever. Whatever sub-game we're in,
28:21by assumption, that game has a solution.
28:26So it's really effectively, Player 1 is choosing between
28:29going into a game with solution W or going into a game with
28:33solution L. And if there were 15 other
28:35sub-games here, each one would have a solution,
28:37and each one Player 1 would be able to associate that solution
28:41with what he's going to get--what she's going to get.
28:44So I claim that, if it in fact is true that each
28:49of these sub-games of length 3 or less had a solution,
28:55then the game of length 4 must have a solution,
28:59which is what? It's the solution which is:
29:03Player 1 should pick the best sub-game.
29:07Are people convinced by that step?
29:11People are looking slightly "deer in the headlamps" now,
29:15so let me just say it again. We started by assuming that all
29:20games of length 3 or less, or N or less,
29:23have a solution. We pointed out that any game
29:27that has length N + 1 can be thought of as an initial move by
29:32Player 1 followed by a game of length N or less,
29:37N or fewer I should say. Each of those games of N or
29:41fewer steps has a solution, so Player 1 is just going to
29:45choose the game that has the best solution for her and we're
29:49done. In this particular example,
29:54Player 1 is going to choose Up and therefore the solution to
30:02this parent game is Player 1 wins.
30:07Now the hard step I think in proofs by induction is realizing
30:11that you're done. So I claim we're now done,
30:15why are we done? Well we know that it was pretty
30:19easy that all games of length 1 have a solution.
30:23That was pretty trivial. And we've shown that if any
30:27game of length of N or fewer has a solution, then games of N + 1
30:32have a solution. So now let's see how we can
30:35proceed. We know that games of length 1
30:38have a solution, so let's consider games of
30:41length 2. Games of length 2,
30:43do games of length 2 have a solution?
30:45Well let's set N = 1. We know that if games of length
30:501 have a solution, then any game of length 2 could
30:52be thought of as an initial step followed by a game of length 1,
30:56but that has a solution, so therefore games of length 2
30:59have a solution. Now let's think of games with
31:01length 3, we've shown that games with length 1 have a solution
31:04and games with length 2 have a solution.
31:06Any game of length 3 can be thought of as a game in which
31:09there's an initial step followed by either a game of length 1 or
31:13a game of length 2, each of which have a solution,
31:16so once again a game of length 3 has a solution and so on.
31:20So games of induction, they work by building up on the
31:23length of the game, and we're ending up knowing
31:26that we're done. For those people who have never
31:29seen a proof by induction don't worry I'm not going to test you
31:34on a proof with induction on the exam,
31:37I just wanted you to see one once.
31:39Let's all take a deep breath and try and digest this a little
31:43bit by playing a game. I'll leave it up there so you
31:48can stare at it. We'll want it down again later.
31:57Let's try and actually play a game and see if we can actually
32:04throw any light on this. So I'm going to pick out
32:07volunteers like I did last time, but first of all,
32:10let me tell you what the game is.
32:11So once again I'm going to have rocks in this game,
32:14and once again I'm going to approximate those rocks with
32:17marks on the blackboard. So here's an example.
32:23The example is this. The game involves an array of
32:29rocks, so here the array has five rows and three columns.
32:37So the rocks are not arranged as they were before in piles,
32:41but rather in a sort of in a pretty array.
32:43I should have made it more even but this is: one,
32:45two, three, four, five rows;
32:47and one, two, three columns,
32:49at least in this example. But in general there's an array
32:59of rocks, N x M. We're going to play
33:04sequentially with the players. And the way the game is going
33:10to work is this--is when it's your turn to move,
33:17you have to point to one of these rocks and whichever rock
33:21you point to I will remove. I will delete that rock and all
33:26the rocks that lie above or to the right of it:
33:29all the rocks that lie to the northeast of it.
33:32So for example, if you pointed to this rock,
33:36then I will remove this rock and also this one,
33:41this one, and this one. If the next person comes along
33:46and chooses this one, then I will remove this one,
33:50and also that one. Okay, everyone understand?
33:53All right and the game is lost--this is important--the
34:00game is lost by the person who ends up taking the last rock.
34:08The loser is the person who ends up removing the last rock.
34:18Could I have some volunteers? Can I volunteer people then?
34:24How about the guy with the white t-shirt with the yellow on
34:28there? Okay, come on up front,
34:31and who else can I volunteer. Everyone's looking away from
34:36me, desperately looking away from me.
34:39How about the guy with the Yale sweatshirt on,
34:42the Yale football sweatshirt on, okay.
34:46So come on up. Your name is?
34:47I should get a mike, let me get a mike up here,
34:53thank you. Great, your name is?
34:55Student: Noah. Professor Ben Polak:
34:57Noah and your name is? Student: Koran.
34:58Professor Ben Polak:Say it into the mike.
34:59Student: Koran. Professor Ben Polak:
35:00Koran okay. So Noah and Koran are our
35:02players. Everyone understand the rules?
35:05Do you understand the rules? Yeah?
35:06So why don't we make Noah go first.
35:08So Noah which rock are you going to remove?
35:10Remember the last rock loses. Student: That one.
35:14Professor Ben Polak: That one.
35:15Okay, so Noah chose this one. So I'm going to remove this one
35:19and the one above it. Student: So all the
35:22rocks to the north and east are deleted, right?
35:23Professor Ben Polak: All the rocks to the north and east
35:27of it are deleted. That means you--last rock loses.
35:32Okay good. Student: That one.
35:47Professor Ben Polak: That one okay.
35:49So now we have an L shape. Student: That one.
36:00Professor Ben Polak: That one, all right.
36:05Student: That one. Professor Ben Polak:
36:06That one okay, okay.
36:07All right so we're done. Okay, everyone understand how
36:10that worked? Round of applause for our
36:14players please, thank you.
36:17Let me get two more volunteers now that everyone has seen it.
36:19These guys had the hard job, they had to figure it out cold.
36:23Two more volunteers? Oh I don't have to pick
36:26volunteers--this is Yale, somebody volunteer.
36:28Are you volunteering? Great.
36:29I have one volunteer. You can pick an opponent if you
36:35like. There you go thank you.
36:38Your name is, let's just wait until the mikes
36:43are here. So your name is?
36:45Student: Peter. Professor Ben Polak:
36:47Peter and your name is Justin. Student: Justin.
36:50Professor Ben Polak: Let me put a new array up here.
36:56So let's put a new array up here and this time let's make
36:59it--it doesn't have to be odd. So let's make it this time a
37:01little bit more complicated. So we'll have five--let's have
37:08four rows and five columns this time.
37:15Okay so last time I had five rows and three columns,
37:21and this time I have four rows and five columns.
37:27Away you go, let me move out of the way.
37:30Why don't you stand a bit nearer to the board--make it a
37:32little easier for people to see what's going on,
37:33there you go. So Peter you want to go first?
37:36Student: Sure, that one. Professor Ben Polak:
37:39That one okay. So this one goes,
37:41which means all of these go as well.
37:46Anyone got any advice from the floor?
37:48Shout things out, not too loud.
37:54Student: I'll try going here.
37:55Professor Ben Polak: There.
37:55Okay we're back to our L shape again here.
38:10Now people can see what's going on all right.
38:15Student: I'll go here and speed it up.
38:16Professor Ben Polak: All right thank you.
38:18So a round of applause again. Thank you guys.
38:26So here's what I claim about this game.
38:27First, and this isn't a formal claim, this is a lot harder than
38:30the game we played last time, right?
38:32Everyone is convinced by that all right.
38:34So here's going to be an exercise, or something that's a
38:37challenge. I may even put it formally on
38:40the problem set this week, but let me just say if I do put
38:43this on the problem set this week,
38:45I don't expect you all to solve it.
38:47So if I do put it on the problem set, it's an optional
38:49problem. But here's the challenge,
38:53the challenge is, I know from Zermelo's theorem
38:59that no matter what N is, and no matter what M is,
39:06this game has a solution. So Zermelo's theorem tells us
39:16this game has a solution. Now, notice it could have a
39:22different solution depending on the N and the M,
39:24depending on how many rows and how many columns,
39:27is that right?. So depending on N and M,
39:31each such game has a solution--is that right--which
39:38could depend on N and on M, on the number of rows and
39:45columns. So just as in Nim,
39:48it depended on how those piles started out.
39:52So what's going to be the homework assignment?
39:55Find the solution. Homework- what is the solution?
40:13So I claim, let me give you a hint, I claim it is useful to
40:19remember that there is a solution.
40:23It turns out to be useful to remember that.
40:24That wasn't much of a hint. You knew that already,
40:26but let me just emphasize that. Okay, so I want to do a bit of
40:30a transition now away from these games like chess and like
40:35checkers, and like this game with the
40:38rocks or Nim, and I want to be a little bit
40:40formal for a while. So one thing that we haven't
40:43done for a while, actually since the mid-term,
40:45is write down some formal definitions.
40:47So I'm going to do that now. I want at least one of these
40:52boards back.
41:16So as I warned very early in the class, there are some points
41:19of the day when we have to stop and do some work and the next
41:23twenty minutes or so is such a point.
41:41So what is this? This is formal stuff.
41:48The first thing I want to do is I want to give you a formal
41:51definition of something I've already mentioned today and
41:54that's the idea of perfect information.
41:57What we've been looking at, or at least since the mid-term,
42:00are games of perfect information.
42:02So a game of perfect information is one in which at
42:20every node, or at each node in the game the player whose turn
42:41it is to move at that node knows which node she is at.
43:02So it's a very simple idea. Every game we've seen since the
43:04mid-term has this property. When you're playing this game
43:08you know where you are. So you know which node you're
43:13at, you know what your choices are and what that means
43:21implicitly is she must know how she got there.
43:27So the whole history of the game is observed by everybody.
43:30When I get to move I know what you did yesterday,
43:32I know what I did the day before yesterday,
43:35and if I'm playing with a third person I know what they did the
43:38day before that. So a very simple idea but it
43:41turns out to be an idea that actually allows us to use things
43:46like backward induction very simply.
43:50Now so far all we've been doing is thinking about such games,
43:54games like perfect competition, sorry games like quantity
43:57competition between firms or games like the games where we
44:00were setting up incentives or games like Nim,
44:03and we've basically been solving these games by backward
44:05induction, rather informally. What I want to add in now is
44:09the notion of a strategy in these games.
44:11So when we had simultaneous move games, strategies were
44:14really unproblematic. It was obvious what strategies
44:17were. But when we have games which
44:19are sequential, that go on over a period of
44:22time, and information is emerging
44:24over a period of time, we need to be a little careful
44:27what we mean by a strategy. So what I want to do is I want
44:31to define a pure strategy at least as follows.
44:35So a pure strategy for Player i in a game of perfect
44:47information--so in the games we've been talking about,
45:00games which we can represent by trees is what?
45:03It's a complete plan of action. So in other words,
45:25what it does is it specifies which action I should
45:35take--let's not make it should take--let's say will
45:46take, at each of i's nodes,
45:52each of i's decision nodes. So when you first read this
46:00definition it seems completely uninteresting and unproblematic.
46:03A pure strategy for Player i just tells you in this game
46:07whenever you might be called upon to move,
46:09it tells you how you're going to move.
46:12So if you're going to move three times in the game,
46:14it tells you how you're going to move the first time;
46:16it tells you how you're going to move the second time;
46:18and it tells you how you're going to move the third time.
46:23So, so far none of this seems difficult but actually it's a
46:27bit more difficult than it looks.
46:29So let's have a look.
46:41What I want to do is I want to look at an example,
46:44and this example I'm hoping is going to illustrate some
46:46subtleties about this definition.
46:57So here's an example.
47:04In this example Player 1 moves first and they can choose in or
47:08out, or if you like let's call it up or down since that's the
47:12way we've drawn it. So they can choose down or
47:16up--and I'll use capital letters U and D.
47:20If Player chooses U then Player 2 gets to move and Player 2 can
47:29choose L or R. If Player 1 moves U followed by
47:34Player 2 choosing L, then Player 1 gets to move,
47:38in which case Player 1 could move up or down and I'll use
47:41little letters this time, u and d.
47:45Let's put some payoffs in this game.
47:48So the payoffs are 1,0 here, 0,2 here, 3,1 here and 2,4
48:00here. So on paper--it's on the
48:03board--when you first look at it, this is a perfectly simple
48:06game. It's just like many of the
48:07games we've been looking at since the mid-term.
48:09It has a tree. We could analyze it by backward
48:12induction, and in a moment we will analyze it by backward
48:15induction. But what I want to do first is
48:18I want to say what are the strategies in this game?
48:21So let's start with Player 2 since it's easier.
48:27Player 2's strategies here are what?
48:34Pretty simple: player 2 only has one decision
48:37node--here's Player 2's decision node--and the strategy has to
48:42tell Player 2 what he's going to do at that decision node.
48:47So there's only two choices, L or R.
48:49So Player 2's strategies are either L or R.
48:57Notice, however, already one slight subtlety
49:00here. Player 2 may never get to make
49:05this choice. So Player 2 is choosing L or R,
49:08but Player 2 may not ever get to make this choice.
49:11In particular, if 1 chose D it's really
49:14irrelevant whether Player 2 has chosen L or R.
49:17Nevertheless, the strategy has to specify
49:21what Player 2 would do were he called upon to make that move.
49:28Now let's look at Player 1's strategies.
49:37So what are Player 1's strategies in this game?
49:45Any takers? Anyone want to guess?
49:54So I claim it's tempting, but it turns out to be wrong,
49:59to say that Player 1 has three strategies here.
50:03It's tempting to say either Player 1 moves D,
50:08in which case we're done, or Player 1 moves U,
50:14in which case at some later date she may be called upon to
50:19choose u or d again. So it's very tempting to think
50:23that Player 1 has just three strategies here,
50:26D in which case we're done, or U followed by either u or d,
50:34if she's reached that point. But actually,
50:39if we follow this definition carefully, we notice that Player
50:431 actually has four strategies here.
50:46So let me say what they are and you'll see why it's a little
50:49odd. So here's one of the strategies
50:52we talked about, U followed by u,
50:54and here's another one we talked about,
50:56U followed by d, but I claim there are two
51:03others, D followed by u and D followed by d.
51:11So what's a little weird about this?
51:13What's weird is we know perfectly well that if Player 1
51:18chooses D she's not going to get to make the choice,
51:22the second choice u or d. But nevertheless the strategy
51:27has to tell us what she would do at every node,
51:31regardless of whether that node actually is reached by that
51:35strategy. Let me say it again,
51:38the strategy has to tell you what Player 1 would do at that
51:43node, regardless of whether that node
51:46is actually reached by playing that strategy.
51:50So a little weird. There's a bit of redundancy
51:54here. It's a bit redundant.
52:02Now why? Well we'll see why in a second.
52:05Let's first of all consider how this game will be played
52:09according to backward induction. So how do we play this game
52:13according to backward induction? Where do we start?
52:18Shouldn't be a trick question, where do we start the game
52:21according to backward induction? At the end okay.
52:25So the end here is Player 1 and Player 1 will choose here to go
52:32d, is that right? Because 3 is bigger than 2.
52:36So if we roll back to Player 2's move, Player 2 if she
52:40chooses L she knows that she'll be followed by Player 1 going d,
52:46in which case she'll get 1, but if she chooses R she'll get
52:512. So Player 2 will choose R.
52:56So Player 1 here, if she chooses U then Player 2
53:01will choose R and Player 1 will get 0, and if she chooses D
53:07she'll get 1, so Player 1 will choose D.
53:12So, backward induction suggests that Player 1 will choose D;
53:18and followed by Player 2--if Player 2 did get to move--she'd
53:22choose R; followed by Player 1--if she
53:25did get to move again--choosing d again.
53:28Notice that backward induction had to tell us what Player 2
53:35would have done had she got to move.
53:39Backward induction had to consider what Player 2 would
53:43think that Player 1 would have done were Player 1 to get to
53:47move again. So to do backward induction,
53:51Player 1 has to ask herself what Player 2 is going to do;
53:56and Player 2 has to therefore ask herself what Player 1 would
54:00have done; which means Player 1 has to ask
54:02herself what Player 2 thinks Player 1 would have done;
54:04which means we actually needed to say what Player 1 did over
54:09here. Let me say that again.
54:10So backward induction here tells us that Player 1 chooses D
54:13in which case the game is over. But to do backward induction,
54:17to think through backward induction, we really needed to
54:21consider not just what Player 2 was going to do were he to get
54:25to move, but also what Player 2 would
54:28think Player 1 would do were Player 2 to get to move and were
54:33to do choose L. So all of these redundant moves
54:37were actually part of our backward induction.
54:41We need them there so we can think about what people are
54:45thinking. So backward induction tells us
54:49that the outcome of the game is D, but it tells in terms of
54:54strategies, Player 1 chooses D and,
54:57were she to get to move again, would choose D again.
55:01And Player 2 chooses R. Now let's analyze this game a
55:12totally different way. We now know what the strategies
55:16are in the game: Player 2 has two strategies,
55:19L and R; and Player 1 has four
55:23strategies: U/u, U/d, D/u and D/d.
55:30So let's write up the matrix for this game,
55:35so here it is. It must be a 4 x 2 matrix,
55:40Player 2 is choosing between L and R and Player 1 is choosing
55:48between her four strategies Uu, Ud, Du and Dd and we can put
55:58all the payoffs in. So (Uu,L) gets us here which is
56:07(2,4). (Uu,R) gets us here which is
56:15(0,2). (Ud,L) gets us here which is
56:23(3,1). (Ud,R) gets us here again which
56:29is (0,2). And Du gets us,
56:32going right out of the game immediately, so we're going to
56:37go to (1,0). And in fact that's also true
56:42for (Du,R), and it's also true for (Dd,L) and it's also true
56:49for (D/d,R). So all of these four strategies
56:52at the bottom started off by Player 1 choosing D,
56:55in which case the game is over. So once again in this matrix
56:59you can kind of see the redundancy I was talking about.
57:02In this matrix, the third row,
57:06the Du row looks the same as the Dd row.
57:11Everyone happy with that? So when we've had matrices in
57:17the past how have we solved the game?
57:20Well we've been doing this backward induction stuff for a
57:23couple of weeks, but,
57:23prior to the mid-term--if I had given you this on the mid-term
57:27what would you have done? You'd look for a Nash
57:31Equilibrium right? So let's do that:
57:33let's look for Nash Equilibrium.
57:35So if Player 2 chooses L then Player 1's best response is Uu;
57:45and if Player 2 chooses R, then Player 1's best response
57:53is either Du or Dd. Conversely, if Player 1 chooses
57:58Uu then Player 2's best response is L.
58:02If Player 1 chooses Ud then Player 2's best response is R.
58:09If Player 1 chooses Du then Player 2 doesn't care because
58:13they're getting 0 anyway; and if Player 1 chooses Dd then
58:19again Player 2 doesn't care because they're getting 0
58:25anyway. So the Nash Equilibria in this
58:28game are what? So one of them is here,
58:33so that's one Nash Equilibrium. One of them is Dd followed by
58:44R, and that's a Nash Equilibrium we actually found by backward
58:54induction. The Nash Equilibrium (Dd,R)
58:59corresponds to the one we found by backward induction.
59:06But there's another Nash Equilibrium in this game.
59:08The other Nash Equilibrium in this game is this one.
59:14That's also a Nash Equilibrium. What does it involve?
59:17It involves Du and R--sorry Du and R.
59:35So what happened in that equilibrium?
59:38Player 1 went down which made everything else kind of
59:41irrelevant. Player 2 played R and Player 1
59:45in their plan of action was actually going to choose u.
59:52Say it again, Player 1 in fact went D,
59:55Player 2 had they got to move would have chosen R and Player 1
1:00:01had they got to move at this second time would have chosen u.
1:00:07So how can that be a Nash Equilibrium?
1:00:08It doesn't correspond to backward induction.
1:00:11In particular, Player 1 up here is choosing a
1:00:15strategy that seems silly. They're choosing u rather than
1:00:21d which gets them 2 rather than 3.
1:00:24So how could it possibly be that that's an equilibrium
1:00:28strategy? The reason is--the reason it
1:00:30can be an equilibrium strategy is it doesn't really matter what
1:00:33Player 1 chooses up here from Player 1's point of view because
1:00:37it's never going to be reached anyway.
1:00:39As long as Player 2 is going to choose R here,
1:00:43it really doesn't matter what Player 1 decides to do up there.
1:00:49From Player 1's point of view, it doesn't make a difference.
1:00:51It isn't reached anyway. So we're highlighting here a
1:00:56danger, and the danger is this. If you just mechanically find
1:01:01the Nash Equilibria in a game, you're going to find people
1:01:06choosing actions that, if they ever were called upon
1:01:12to make them, are silly.
1:01:14Say it again, if you just mechanically find
1:01:17the Nash Equilibria in the game, just as we did here,
1:01:19you're going to select some actions, in this case an action
1:01:23by Player 1, that were she called upon to
1:01:26take that action would be a silly action.
1:01:29The reason it's surviving our analysis is because in fact she
1:01:33isn't called upon to make it. Now to make that more concrete,
1:01:38let's take this to an economic example, this same idea.
1:01:57So what I want you to imagine is a market, and in this market
1:02:02there is a monopolist who controls the market,
1:02:06but there's an entrant who is thinking of entering into this
1:02:10market. So right now this market has a
1:02:14monopoly in it, and the monopolist is an
1:02:17incumbent--let's call him Inc--and an entrant who is
1:02:22trying to decide whether or not to enter the market or whether
1:02:27to stay out. If they stay out then the
1:02:31entrant gets nothing and the incumbent continues to get
1:02:35monopoly profits. So think of this as 3 million a
1:02:40year. If the entrant enters then the
1:02:43incumbent can do one of two things.
1:02:46The incumbent could choose to fight the entrant,
1:02:49by which I mean charge low prices, advertise a lot,
1:02:52try and drive him out of the market.
1:02:55He could play very competitively,
1:02:58in which case the entrant will actually make losses,
1:03:02and the incumbent will drive her profits down to zero.
1:03:08Conversely, the incumbent could choose not to fight.
1:03:13If they don't fight then they'll simply share the market
1:03:17and they'll both make, let's say Cournot profits or
1:03:20duopoly profits of a million each.
1:03:23So in this game, let's just say again,
1:03:25there's a market there. The monopolist is in the market
1:03:29and the monopolist is making 3 million a year which seems
1:03:32pretty nice for the monopolist. The entrant is trying to decide
1:03:36whether to invade this market. If she invades this market,
1:03:40if she's fought she's in trouble, but if the monopolist
1:03:44accommodates her, then they just go to duopoly
1:03:47profits and the entrant does very well, gets a million
1:03:51dollars in profit. Let's have a look at this game.
1:03:55Analyze--first of all this time, let's analyze it by Nash
1:03:58Equilibrium. So I claim in this game,
1:04:02this is pretty simple: the entrant has two strategies.
1:04:07I'll put it straight into the matrix.
1:04:08The entrant has two strategies, they're either to go in or to
1:04:19stay out; and the incumbent has two
1:04:24strategies, they are either to fight the entrant or not to
1:04:32fight. The payoffs of this game are as
1:04:34follows--let's put them in. In and fight was (-1,0),
1:04:38in and not fight was (1,1) and out led to the incumbents
1:04:44maintaining the monopoly profits.
1:04:48Let's have a look at the Nash Equilibria of this game.
1:04:52So the first thing to do is to look at the best responses for
1:04:56the entrant. So if the incumbent chooses
1:04:59fight, then the entrant's best response is to stay out.
1:05:04If the incumbent chooses not fight, then the entrant's best
1:05:11response is to enter. How about for the incumbent?
1:05:15If the entrant chooses to come in then the incumbent's best
1:05:20response is not to fight because 1 is bigger than 0.
1:05:24But if the entrant stays out it really doesn't matter what the
1:05:30incumbent does, they'll get 3 either way.
1:05:34So the Nash Equilibria here are either in followed by not
1:05:42fighting, you end up with a duopoly, or out followed by
1:05:50fighting. Of course the fight doesn't
1:05:54take place: out followed by "we would have fought had you
1:05:59entered." So these are the Nash
1:06:02Equilibria. Let's analyze this game by
1:06:04backward induction. From the incumbent's point of
1:06:08view, if the incumbent gets to move then is she going to choose
1:06:14fight or not fight? She's going to choose not
1:06:19fight, so the entrant should do what?
1:06:23Somebody? The entrant should enter,
1:06:25because if she enters she gets 1, if she stays out she gets 0.
1:06:28So backward induction just gives us this equilibrium.
1:06:41Now the question is what do we think is going on with this
1:06:44other equilibrium? Let's talk it through.
1:06:48So here you are, you're about to enter the
1:06:50market, you leave Yale, you set up your business,
1:06:52and your business is challenging some monopolist or
1:06:56quasi-monopolist like Microsoft say.,
1:06:58And you go out there and you're about to put out your new
1:07:01operating system. And you know that your new
1:07:04operating system will make plenty of money provided
1:07:07Microsoft doesn't retaliate and drop its prices by half and
1:07:12advertise you out of the market. So what does Bill Gates do?
1:07:16Bill Gates is the head of Microsoft.
1:07:17He says, wait a second before you graduate from Yale and go
1:07:21set up this company, let me just tell you I'm going
1:07:24to fight. If you enter I'm going to fight.
1:07:30And if you believe him, if you believe that he's going
1:07:34to fight, what should you do? You're not going to bother to
1:07:37enter his market. And if you believe that you're
1:07:39going to get fought by Bill Gates then you believe that if
1:07:42you enter you're going to make losses,
1:07:44so you choose to stay out. And this threat that Bill Gates
1:07:49makes here it doesn't cost him anything, provided you go out,
1:07:55he doesn't actually have to fight at all.
1:07:58That's why it is in fact an equilibrium to imagine you
1:08:02staying out believing that you're going to get fought if
1:08:06you enter, and it is a best response for
1:08:08the guy to fight knowing that you're going to stay out.
1:08:12But this doesn't sound right. Why doesn't this sound right?
1:08:17It doesn't sound right because you really shouldn't believe the
1:08:21guy who says he's going to fight you when you know that if you
1:08:25did enter fighting would cost the incumbent money.
1:08:29If you did enter, if he fights you he gets 0,
1:08:32if he doesn't fight he gets a million dollars.
1:08:36So this threat that the guy is going to fight you,
1:08:41this threat is not credible. This is an equilibrium but it
1:08:51relies on believing an incredible threat.
1:09:10It's true that if you think about entering the market that
1:09:13Microsoft is in, you're very likely to get a
1:09:15little email from Bill Gates. (But it won't be an email
1:09:19because that can be taken to Court, but some little
1:09:21threatening remark in your ear from Bill Gates.) It's true if
1:09:24you entered into the market that the people who build aircraft
1:09:28in, the head of Boeing might pay
1:09:30you a call one day or send someone round,
1:09:33but these threats are not credible threats.
1:09:36Is that right? They're not credible threats
1:09:38because we know that if you did enter, it isn't in their
1:09:42interest to fight. They're making a lot of noise
1:09:46about it but you know that if you did enter,
1:09:49backward induction tells us they're not going to fight.
1:09:53But now we're in slightly an odd situation,
1:09:57why are we in an odd situation? Two things.
1:10:01One, we seem to be finding that there are Nash Equilibria in
1:10:06games--we found one here and one up here--there are Nash
1:10:11Equilibria that are not supported by backward induction.
1:10:17That's the first reason we're a little worried here,
1:10:21and the second reason we're worried is even the economics of
1:10:25this doesn't quite smell right. For example,
1:10:29if you in fact did enter--sorry,
1:10:31if you did in fact announce you were going to operate,
1:10:35you were going to build a new operating system and got a
1:10:38threatening phone call from Bill Gates--there might be a reason
1:10:42why you might actually believe that call.
1:10:44Why might you believe that call? Can we get a mike out,
1:10:52I'll do it. So why might you believe a call
1:10:56from Bill Gates saying he's going to beat you up--not beat
1:10:59you up but he's going to charge low prices if you produce an
1:11:02operating system? Student: If you look at
1:11:05the future revenue streams, like for the next ten years and
1:11:07he consistently gets 1 million dollars for the next ten years,
1:11:10he would be better off if he just drove you out of the market
1:11:13for the first year and then get 3 million dollars for the next
1:11:16nine years. Professor Ben Polak:
1:11:17That wasn't quite what I wasn't thinking of.
1:11:18Okay, it's true if we cheat a bit and make one of the--Okay,
1:11:22so what you're saying is I could get 3 forever versus 1
1:11:25forever, assume these are both present
1:11:27discounted values of future cash earnings.
1:11:29So we've done the future cash flow analysis of this.
1:11:33So this isn't an accounting mistake, not for accounting
1:11:37reasons. There's some other reason when
1:11:40Gates threatens you, you might want to believe it.
1:11:43Let's try up here first. Student: He can afford
1:11:45to make an example of you so no other people will invade.
1:11:48Professor Ben Polak: Right, so one thing that's in
1:11:50Bill Gates' mind is right now, he's thinking about competing
1:11:54with you but down the road there's a lot more of you guys
1:11:59coming--whatever it is, 280 of you in this room and
1:12:02there's another 280 in next year's class and so on.
1:12:05And Bill Gates knows that each of you might come out and
1:12:08threaten his monopoly, his Microsoft monopoly.
1:12:11And he might think that by setting an example to one of you
1:12:15he might be able to keep the others out.
1:12:18And somewhere that kind of argument, the argument of making
1:12:22an example of somebody is missing here:
1:12:25missing completely. But it's got to be important,
1:12:29it's got to be an important idea.
1:12:31So we're going to come back and spend the first half of
1:12:35Wednesday's class picking up just precisely that idea.

About this transcript

This page contains the full transcript of 15. Backward induction: chess, strategies, and credible threats by YaleCourses, generated from the public captions YouTube serves with the video. The transcript has 10,006 words across 1,042 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.