[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:01.74,0:00:04.61,Default,,0000,0000,0000,,Professor Ben Polak: So\Nlast time we finished up by
Dialogue: 0,0:00:04.61,0:00:06.93,Default,,0000,0000,0000,,playing the game of Nim and\Nyou'll remember,
Dialogue: 0,0:00:06.93,0:00:11.14,Default,,0000,0000,0000,,I hope, that the game of Nim\Nwas a game where there was two
Dialogue: 0,0:00:11.14,0:00:15.41,Default,,0000,0000,0000,,piles of stones--we made do with\Nlines on the board--and the
Dialogue: 0,0:00:15.41,0:00:19.40,Default,,0000,0000,0000,,winner was the person who picked\Nup the last stone.
Dialogue: 0,0:00:19.40,0:00:23.53,Default,,0000,0000,0000,,Remember you had to pick piles.\NI want to use the game of Nim
Dialogue: 0,0:00:23.53,0:00:27.35,Default,,0000,0000,0000,,to make a transition here.\NSo what we had pointed out
Dialogue: 0,0:00:27.35,0:00:31.11,Default,,0000,0000,0000,,about the game of Nim was it\Nillustrated very nicely for us
Dialogue: 0,0:00:31.11,0:00:34.88,Default,,0000,0000,0000,,that games can have first mover\Nadvantages or they can have
Dialogue: 0,0:00:34.88,0:00:38.31,Default,,0000,0000,0000,,second mover advantages.\NA very small change in the
Dialogue: 0,0:00:38.31,0:00:42.14,Default,,0000,0000,0000,,game, essentially a very small\Nchange in where we started from,
Dialogue: 0,0:00:42.14,0:00:46.56,Default,,0000,0000,0000,,could switch a game from a game\Nwith a first mover advantage to
Dialogue: 0,0:00:46.56,0:00:49.35,Default,,0000,0000,0000,,a game with a second mover\Nadvantage.
Dialogue: 0,0:00:49.35,0:00:54.33,Default,,0000,0000,0000,,Now today, I want to just draw\Na slightly grander lesson out of
Dialogue: 0,0:00:54.33,0:00:56.76,Default,,0000,0000,0000,,that game.\NSo not only was it the case
Dialogue: 0,0:00:56.76,0:00:59.65,Default,,0000,0000,0000,,that the game sometimes has\Nfirst mover advantages and
Dialogue: 0,0:00:59.65,0:01:01.89,Default,,0000,0000,0000,,sometimes has second mover\Nadvantages,
Dialogue: 0,0:01:01.89,0:01:04.56,Default,,0000,0000,0000,,but moreover,\Nwe could tell when it had a
Dialogue: 0,0:01:04.56,0:01:08.50,Default,,0000,0000,0000,,first mover advantage and we\Ncould tell when it had a second
Dialogue: 0,0:01:08.50,0:01:10.35,Default,,0000,0000,0000,,mover advantage.\NIs that right?
Dialogue: 0,0:01:10.35,0:01:13.45,Default,,0000,0000,0000,,When we actually looked at the\Ninitial set up of those stones,
Dialogue: 0,0:01:13.45,0:01:16.44,Default,,0000,0000,0000,,we knew immediately that's a\Ngame in which Player 1 is going
Dialogue: 0,0:01:16.44,0:01:18.17,Default,,0000,0000,0000,,to win,\Nor alternatively,
Dialogue: 0,0:01:18.17,0:01:22.24,Default,,0000,0000,0000,,we knew immediately that's a\Ngame which Player 2 is going to
Dialogue: 0,0:01:22.24,0:01:24.73,Default,,0000,0000,0000,,win.\NNow it turns out that that idea
Dialogue: 0,0:01:24.73,0:01:28.24,Default,,0000,0000,0000,,is very general and actually has\Na name attached to it,
Dialogue: 0,0:01:28.24,0:01:30.06,Default,,0000,0000,0000,,and that name is Zermelo.
Dialogue: 0,0:01:30.06,0:01:35.36,Default,,0000,0000,0000,,
Dialogue: 0,0:01:35.36,0:01:38.98,Default,,0000,0000,0000,,So today we'll start off by\Ntalking about a theorem due to a
Dialogue: 0,0:01:38.98,0:01:42.06,Default,,0000,0000,0000,,guy called Zermelo,\Nand the idea of this theorem is
Dialogue: 0,0:01:42.06,0:01:44.00,Default,,0000,0000,0000,,this.\NWe're going to look at games
Dialogue: 0,0:01:44.00,0:01:46.64,Default,,0000,0000,0000,,more general than just Nim,\Nand we're going to ask the
Dialogue: 0,0:01:46.64,0:01:49.08,Default,,0000,0000,0000,,question,\Nunder what circumstances would
Dialogue: 0,0:01:49.08,0:01:51.65,Default,,0000,0000,0000,,you know about a game either\Nthat Player 1,
Dialogue: 0,0:01:51.65,0:01:54.66,Default,,0000,0000,0000,,the person who goes first,\Ncan force a win,
Dialogue: 0,0:01:54.66,0:01:58.82,Default,,0000,0000,0000,,or that Player 2 can force a\Nwin, or will allow a third
Dialogue: 0,0:01:58.82,0:02:03.53,Default,,0000,0000,0000,,possibility,\Nwhich is it's going to be a tie.
Dialogue: 0,0:02:03.53,0:02:06.77,Default,,0000,0000,0000,,So here's the theorem,\Nsuppose there are two players
Dialogue: 0,0:02:06.77,0:02:09.43,Default,,0000,0000,0000,,in this game,\Nlike the games that we looked
Dialogue: 0,0:02:09.43,0:02:13.06,Default,,0000,0000,0000,,at last time,\Nand suppose--I won't define
Dialogue: 0,0:02:13.06,0:02:18.63,Default,,0000,0000,0000,,this formally now--but suppose\Nthe game is a game of perfect
Dialogue: 0,0:02:18.63,0:02:21.24,Default,,0000,0000,0000,,information.\NSo what do I mean by perfect
Dialogue: 0,0:02:21.24,0:02:23.68,Default,,0000,0000,0000,,information?\NI'll define this later on in
Dialogue: 0,0:02:23.68,0:02:27.63,Default,,0000,0000,0000,,the class, but for now all I\Nmean is, that whenever a player
Dialogue: 0,0:02:27.63,0:02:31.18,Default,,0000,0000,0000,,has his turn to move,\Nthat player knows exactly what
Dialogue: 0,0:02:31.18,0:02:34.01,Default,,0000,0000,0000,,has happened prior in the game.\NSo, for example,
Dialogue: 0,0:02:34.01,0:02:36.93,Default,,0000,0000,0000,,all these sequential move games\Nwe've been looking at are moves
Dialogue: 0,0:02:36.93,0:02:39.50,Default,,0000,0000,0000,,of perfect information.\NWhen I get to move I know
Dialogue: 0,0:02:39.50,0:02:42.53,Default,,0000,0000,0000,,exactly what you did yesterday,\NI know what I did the day
Dialogue: 0,0:02:42.53,0:02:45.46,Default,,0000,0000,0000,,before yesterday and so on.\NSo it's a game of perfect
Dialogue: 0,0:02:45.46,0:02:48.56,Default,,0000,0000,0000,,information.\NI'm going to assume that the
Dialogue: 0,0:02:48.56,0:02:51.58,Default,,0000,0000,0000,,game has a finite number of\Nnodes.
Dialogue: 0,0:02:51.58,0:02:54.40,Default,,0000,0000,0000,,So two things here,\Nit can't go on forever,
Dialogue: 0,0:02:54.40,0:02:58.55,Default,,0000,0000,0000,,this game, and also there's no\Npoint in which it branches in an
Dialogue: 0,0:02:58.55,0:03:01.49,Default,,0000,0000,0000,,infinite way.\NSo there's a finite number of
Dialogue: 0,0:03:01.49,0:03:04.90,Default,,0000,0000,0000,,nodes, and we'll assume that the\Ngame has three possible
Dialogue: 0,0:03:04.90,0:03:07.07,Default,,0000,0000,0000,,outcomes.\NActually there's a more general
Dialogue: 0,0:03:07.07,0:03:09.37,Default,,0000,0000,0000,,version of this theorem but this\Nwill do for now.
Dialogue: 0,0:03:09.37,0:03:14.22,Default,,0000,0000,0000,,The three possible outcomes are\Neither a win for Player 1,
Dialogue: 0,0:03:14.22,0:03:19.53,Default,,0000,0000,0000,,so I'll call it W_1,\Nor a loss for Player 1,
Dialogue: 0,0:03:19.53,0:03:25.04,Default,,0000,0000,0000,,which is obviously a win for\NPlayer 2, or a tie.
Dialogue: 0,0:03:25.04,0:03:27.58,Default,,0000,0000,0000,,So the game--like Nim last\Ntime, that only had two
Dialogue: 0,0:03:27.58,0:03:30.54,Default,,0000,0000,0000,,outcomes.\NSo here we're going to look up
Dialogue: 0,0:03:30.54,0:03:35.25,Default,,0000,0000,0000,,to three outcomes or three or\Nfewer outcomes I should say.
Dialogue: 0,0:03:35.25,0:03:39.93,Default,,0000,0000,0000,,So these are the conditions and\Nhere's the result.
Dialogue: 0,0:03:39.93,0:03:42.82,Default,,0000,0000,0000,,So I said three,\Nit could be three but it could
Dialogue: 0,0:03:42.82,0:03:45.84,Default,,0000,0000,0000,,also be two here,\NI'm just allowing for three.
Dialogue: 0,0:03:45.84,0:03:51.65,Default,,0000,0000,0000,,(One is trivial.) So under\Nthese conditions the following
Dialogue: 0,0:03:51.65,0:03:55.30,Default,,0000,0000,0000,,is true.\NEither Player 1 can force a
Dialogue: 0,0:03:55.30,0:04:01.11,Default,,0000,0000,0000,,win, so either it's the case\Nthat this game is a game that if
Dialogue: 0,0:04:01.11,0:04:04.79,Default,,0000,0000,0000,,Player 1 plays as well as they\Ncan,
Dialogue: 0,0:04:04.79,0:04:09.76,Default,,0000,0000,0000,,they're going to win the game\Nno matter what Player 2 does.
Dialogue: 0,0:04:09.76,0:04:17.09,Default,,0000,0000,0000,,Or 1 can at least force a tie,\Nwhich means Player 1 can play
Dialogue: 0,0:04:17.09,0:04:23.67,Default,,0000,0000,0000,,in such a way that they can\Nassure themselves of a tie
Dialogue: 0,0:04:23.67,0:04:28.27,Default,,0000,0000,0000,,regardless of what Player 2\Ndoes.
Dialogue: 0,0:04:28.27,0:04:41.22,Default,,0000,0000,0000,,Or it could be a game in which\N2 can force a loss on 1,
Dialogue: 0,0:04:41.22,0:04:45.98,Default,,0000,0000,0000,,so a win for 2.\NSo this theorem,
Dialogue: 0,0:04:45.98,0:04:48.22,Default,,0000,0000,0000,,when you first look at it,\Nit doesn't seem to say very
Dialogue: 0,0:04:48.22,0:04:49.85,Default,,0000,0000,0000,,much.\NYou're staring at this
Dialogue: 0,0:04:49.85,0:04:52.72,Default,,0000,0000,0000,,thing--you might think,\Nwe already knew that we're
Dialogue: 0,0:04:52.72,0:04:56.41,Default,,0000,0000,0000,,looking at games that only have\Nthree possible outcomes win,
Dialogue: 0,0:04:56.41,0:05:00.44,Default,,0000,0000,0000,,loss, or tie so it doesn't seem\Nso surprising if you look at
Dialogue: 0,0:05:00.44,0:05:02.08,Default,,0000,0000,0000,,this theorem,\Nit says,
Dialogue: 0,0:05:02.08,0:05:04.56,Default,,0000,0000,0000,,well, you're going to end up\Nwith a win, or a loss,
Dialogue: 0,0:05:04.56,0:05:06.52,Default,,0000,0000,0000,,or a tie.\NHowever, that's not quite what
Dialogue: 0,0:05:06.52,0:05:08.36,Default,,0000,0000,0000,,the theorem says.\NThe theorem says,
Dialogue: 0,0:05:08.36,0:05:11.32,Default,,0000,0000,0000,,not only are you going to end\Nup there--we knew that
Dialogue: 0,0:05:11.32,0:05:13.87,Default,,0000,0000,0000,,already--but the games divide\Nthemselves.
Dialogue: 0,0:05:13.87,0:05:17.20,Default,,0000,0000,0000,,Games of these forms divide\Nthemselves into those games in
Dialogue: 0,0:05:17.20,0:05:20.30,Default,,0000,0000,0000,,which Player 1 has a way of\Nwinning regardless of what
Dialogue: 0,0:05:20.30,0:05:23.61,Default,,0000,0000,0000,,Player 2 does;\Nor games in which Player 1 has
Dialogue: 0,0:05:23.61,0:05:27.31,Default,,0000,0000,0000,,a way of forcing a tie\Nregardless of what Player 2
Dialogue: 0,0:05:27.31,0:05:29.53,Default,,0000,0000,0000,,does;\Nor Player 2 has a way of
Dialogue: 0,0:05:29.53,0:05:32.23,Default,,0000,0000,0000,,winning regardless of what\NPlayer 1 does,
Dialogue: 0,0:05:32.23,0:05:34.79,Default,,0000,0000,0000,,so these games all have a\Nsolution.
Dialogue: 0,0:05:34.79,0:05:37.99,Default,,0000,0000,0000,,Let's just go back to Nim to\Nillustrate the point.
Dialogue: 0,0:05:37.99,0:05:41.75,Default,,0000,0000,0000,,So in Nim actually there's no\Ntie so we can forget the middle
Dialogue: 0,0:05:41.75,0:05:45.43,Default,,0000,0000,0000,,of these, and in Nim,\Nunder certain circumstances it
Dialogue: 0,0:05:45.43,0:05:48.65,Default,,0000,0000,0000,,is the case that Player 1 can\Nforce a win.
Dialogue: 0,0:05:48.65,0:05:52.14,Default,,0000,0000,0000,,Who remembers what the case\Nwas, for when Player 1 can force
Dialogue: 0,0:05:52.14,0:05:54.45,Default,,0000,0000,0000,,a win?\NAnybody?
Dialogue: 0,0:05:54.45,0:06:00.26,Default,,0000,0000,0000,,The people who played last time.\NNo, yes, Ale,
Dialogue: 0,0:06:00.26,0:06:04.50,Default,,0000,0000,0000,,there's somebody here.\NShout it out.
Dialogue: 0,0:06:04.50,0:06:06.81,Default,,0000,0000,0000,,Student: Insuring that\Nthe piles are equal for the
Dialogue: 0,0:06:06.81,0:06:10.04,Default,,0000,0000,0000,,other player.\NProfessor Ben Polak: All
Dialogue: 0,0:06:10.04,0:06:14.59,Default,,0000,0000,0000,,right, so if the piles start\Nunequal, then Player 1 can
Dialogue: 0,0:06:14.59,0:06:21.23,Default,,0000,0000,0000,,actually force a win.\NSo in Nim if the piles are
Dialogue: 0,0:06:21.23,0:06:29.41,Default,,0000,0000,0000,,unequal at the start,\Nthen 1 can force a win.
Dialogue: 0,0:06:29.41,0:06:33.82,Default,,0000,0000,0000,,It really doesn't matter what 2\Ndoes, 2 is "toast."
Dialogue: 0,0:06:33.82,0:06:37.98,Default,,0000,0000,0000,,Or the alternative case is the\Npiles are equal at the start,
Dialogue: 0,0:06:37.98,0:06:42.00,Default,,0000,0000,0000,,and if they're equal at the\Nstart then it's Player 1 who's
Dialogue: 0,0:06:42.00,0:06:44.76,Default,,0000,0000,0000,,"toast."\NPlayer 2 is going
Dialogue: 0,0:06:44.76,0:06:51.18,Default,,0000,0000,0000,,to--rather--force a loss on 1,\Nso 2 can force a loss on 1,
Dialogue: 0,0:06:51.18,0:06:55.05,Default,,0000,0000,0000,,i.e.\Na win for Player 2.
Dialogue: 0,0:06:55.05,0:06:58.94,Default,,0000,0000,0000,,Does everyone remember that\Nfrom last time?
Dialogue: 0,0:06:58.94,0:07:02.65,Default,,0000,0000,0000,,It's just before the weekend,\Nit shouldn't be so long ago.
Dialogue: 0,0:07:02.65,0:07:08.45,Default,,0000,0000,0000,,So this theorem applies to all\Ngames of this form.
Dialogue: 0,0:07:08.45,0:07:10.86,Default,,0000,0000,0000,,So what games are of this form?\NLet's try and think of some
Dialogue: 0,0:07:10.86,0:07:15.20,Default,,0000,0000,0000,,other examples.\NSo one example is tic-tac-toe.
Dialogue: 0,0:07:15.20,0:07:16.28,Default,,0000,0000,0000,,Everyone know the rules of\Ntic-tac-toe?
Dialogue: 0,0:07:16.28,0:07:18.84,Default,,0000,0000,0000,,In England we call it Noughts\Nand Crosses, but you guys call
Dialogue: 0,0:07:18.84,0:07:20.23,Default,,0000,0000,0000,,it tic-tac-toe,\Nis that right?
Dialogue: 0,0:07:20.23,0:07:22.15,Default,,0000,0000,0000,,Everyone know what tic-tac-toe\Nis?
Dialogue: 0,0:07:22.15,0:07:26.39,Default,,0000,0000,0000,,Yeah, which category is\Ntic-tac-toe?
Dialogue: 0,0:07:26.39,0:07:29.90,Default,,0000,0000,0000,,Is it a game which Player 1 can\Nforce a win, or is it a category
Dialogue: 0,0:07:29.90,0:07:32.18,Default,,0000,0000,0000,,in which Player 1 can only force\Na tie,
Dialogue: 0,0:07:32.18,0:07:35.17,Default,,0000,0000,0000,,or is it a category which you'd\Nrather go second and Player 2
Dialogue: 0,0:07:35.17,0:07:37.86,Default,,0000,0000,0000,,can force a win for Player 2 or\Na loss for Player 1?
Dialogue: 0,0:07:37.86,0:07:41.76,Default,,0000,0000,0000,,Which is tic-tac-toe?\NLet's have a show of hands here.
Dialogue: 0,0:07:41.76,0:07:45.58,Default,,0000,0000,0000,,Who thinks tic-tac-toe is a\Ngame in which Player 1 can force
Dialogue: 0,0:07:45.58,0:07:47.64,Default,,0000,0000,0000,,a win?\NWho thinks tic-tac-toe is a
Dialogue: 0,0:07:47.64,0:07:50.22,Default,,0000,0000,0000,,game in which Player 1 can only\Nforce a tie?
Dialogue: 0,0:07:50.22,0:07:53.69,Default,,0000,0000,0000,,Who thinks Player 2's going to\Nwin?
Dialogue: 0,0:07:53.69,0:07:56.38,Default,,0000,0000,0000,,Most of you are right.\NIt's a game in which if people
Dialogue: 0,0:07:56.38,0:07:59.14,Default,,0000,0000,0000,,play correctly then it'll turn\Nout to be a tie.
Dialogue: 0,0:07:59.14,0:08:07.94,Default,,0000,0000,0000,,So tic-tac-toe is a game that\Nleads to a tie.
Dialogue: 0,0:08:07.94,0:08:10.92,Default,,0000,0000,0000,,Player 1 can still make a\Nmistake, in which case they can
Dialogue: 0,0:08:10.92,0:08:13.29,Default,,0000,0000,0000,,lose.\NPlayer 2 can make a mistake in
Dialogue: 0,0:08:13.29,0:08:17.04,Default,,0000,0000,0000,,which case they would lose,\Nbut there is a way of playing
Dialogue: 0,0:08:17.04,0:08:19.66,Default,,0000,0000,0000,,that forces a tie.\NSo these are fairly simple
Dialogue: 0,0:08:19.66,0:08:21.92,Default,,0000,0000,0000,,games, let's talk about more\Ncomplicated games.
Dialogue: 0,0:08:21.92,0:08:24.84,Default,,0000,0000,0000,,So what about the game of\Ncheckers?
Dialogue: 0,0:08:24.84,0:08:26.47,Default,,0000,0000,0000,,So the game of checkers meets\Nthese conditions.
Dialogue: 0,0:08:26.47,0:08:29.69,Default,,0000,0000,0000,,It's a two player game.\NYou always know all the moves
Dialogue: 0,0:08:29.69,0:08:31.56,Default,,0000,0000,0000,,prior to your move.\NIt's finite:
Dialogue: 0,0:08:31.56,0:08:34.64,Default,,0000,0000,0000,,there's some rules in checkers\Nthat prevent it going on
Dialogue: 0,0:08:34.64,0:08:36.50,Default,,0000,0000,0000,,forever.\NAnd there are two or three
Dialogue: 0,0:08:36.50,0:08:39.24,Default,,0000,0000,0000,,outcomes: I guess there's a\Nthird outcome if you get into a
Dialogue: 0,0:08:39.24,0:08:42.04,Default,,0000,0000,0000,,cycle you could tie.\NSo checkers fits all these
Dialogue: 0,0:08:42.04,0:08:45.34,Default,,0000,0000,0000,,descriptions and what this\Ntheorem tells us is that
Dialogue: 0,0:08:45.34,0:08:48.23,Default,,0000,0000,0000,,checkers has a solution.\NI'm not sure I know what that
Dialogue: 0,0:08:48.23,0:08:50.58,Default,,0000,0000,0000,,solution is, or I think actually\Nsomebody did compute it quite
Dialogue: 0,0:08:50.58,0:08:52.06,Default,,0000,0000,0000,,recently,\Neven in the last few months,
Dialogue: 0,0:08:52.06,0:08:54.19,Default,,0000,0000,0000,,I just forgot to Google it this\Nmorning to remind myself.
Dialogue: 0,0:08:54.19,0:08:57.81,Default,,0000,0000,0000,,But what this theorem tells us\Neven before those people that
Dialogue: 0,0:08:57.81,0:09:00.20,Default,,0000,0000,0000,,computed it: checkers has a\Nsolution.
Dialogue: 0,0:09:00.20,0:09:04.27,Default,,0000,0000,0000,,Let's be a bit more ambitious.\NWhat about chess?
Dialogue: 0,0:09:04.27,0:09:07.79,Default,,0000,0000,0000,,So chess meets this description.\NChess is a two player game,
Dialogue: 0,0:09:07.79,0:09:11.13,Default,,0000,0000,0000,,everybody knows all the moves\Nbefore them, it's sequential,
Dialogue: 0,0:09:11.13,0:09:15.10,Default,,0000,0000,0000,,it has finite number of moves,\Nit's a very large number but it
Dialogue: 0,0:09:15.10,0:09:18.23,Default,,0000,0000,0000,,is finite, and it has three\Npossible outcomes,
Dialogue: 0,0:09:18.23,0:09:21.82,Default,,0000,0000,0000,,a win, a loss, or a tie.\NSo let's be careful,
Dialogue: 0,0:09:21.82,0:09:25.28,Default,,0000,0000,0000,,the reason it's finite is that\Nif you cycle--I forget what it
Dialogue: 0,0:09:25.28,0:09:28.04,Default,,0000,0000,0000,,is--three times then the game is\Ndeclared a draw,
Dialogue: 0,0:09:28.04,0:09:30.48,Default,,0000,0000,0000,,declared a tie.\NSo what's this theorem telling
Dialogue: 0,0:09:30.48,0:09:35.52,Default,,0000,0000,0000,,us?\NIt's telling us that there is a
Dialogue: 0,0:09:35.52,0:09:41.70,Default,,0000,0000,0000,,way to solve chess.\NChess has a solution.
Dialogue: 0,0:09:41.70,0:09:43.10,Default,,0000,0000,0000,,We don't know what that\Nsolution is.
Dialogue: 0,0:09:43.10,0:09:45.85,Default,,0000,0000,0000,,It could be that solution is\Nthat Player 1,
Dialogue: 0,0:09:45.85,0:09:49.59,Default,,0000,0000,0000,,who's the player with the white\Npieces can force a win.
Dialogue: 0,0:09:49.59,0:09:52.08,Default,,0000,0000,0000,,It could be that Player 1 can\Nonly force a tie,
Dialogue: 0,0:09:52.08,0:09:54.95,Default,,0000,0000,0000,,and it could even be that\NPlayer 2 can force a win.
Dialogue: 0,0:09:54.95,0:09:59.00,Default,,0000,0000,0000,,We don't know which it is,\Nbut there is a solution.
Dialogue: 0,0:09:59.00,0:10:02.41,Default,,0000,0000,0000,,There's a catch to this theorem.\NWhat's the catch?
Dialogue: 0,0:10:02.41,0:10:05.26,Default,,0000,0000,0000,,The catch is it doesn't\Nactually tell us--this theorem
Dialogue: 0,0:10:05.26,0:10:07.84,Default,,0000,0000,0000,,is not going to tell us what\Nthat solution is.
Dialogue: 0,0:10:07.84,0:10:10.11,Default,,0000,0000,0000,,It doesn't tell us how to play.\NThis theorem,
Dialogue: 0,0:10:10.11,0:10:12.48,Default,,0000,0000,0000,,in and of itself,\Ndoesn't tell us how to play
Dialogue: 0,0:10:12.48,0:10:16.06,Default,,0000,0000,0000,,chess.\NIt just says there is a
Dialogue: 0,0:10:16.06,0:10:19.28,Default,,0000,0000,0000,,way to play chess.\NSo we're going to try and prove
Dialogue: 0,0:10:19.28,0:10:21.29,Default,,0000,0000,0000,,this.\NWe don't often do proofs in
Dialogue: 0,0:10:21.29,0:10:25.15,Default,,0000,0000,0000,,class, but the reason I want to\Nprove this particular one is
Dialogue: 0,0:10:25.15,0:10:28.95,Default,,0000,0000,0000,,because I think the proof is\Ninstructive as part of sort of
Dialogue: 0,0:10:28.95,0:10:31.70,Default,,0000,0000,0000,,QR at Yale.\NSo here's another example here,
Dialogue: 0,0:10:31.70,0:10:34.77,Default,,0000,0000,0000,,and some other examples.\NYou could think of chess as
Dialogue: 0,0:10:34.77,0:10:36.85,Default,,0000,0000,0000,,being the most dramatic example.
Dialogue: 0,0:10:36.85,0:10:49.02,Default,,0000,0000,0000,,
Dialogue: 0,0:10:49.02,0:10:56.20,Default,,0000,0000,0000,,So the reason I want to spend\Nactually some time proving this
Dialogue: 0,0:10:56.20,0:11:03.39,Default,,0000,0000,0000,,today is because we're going to\Nprove it by induction and I'm
Dialogue: 0,0:11:03.39,0:11:08.21,Default,,0000,0000,0000,,going to sketch the proof.\NI'm not going to go through
Dialogue: 0,0:11:08.21,0:11:10.91,Default,,0000,0000,0000,,every possible step but I want\Nto give people here a feeling
Dialogue: 0,0:11:10.91,0:11:12.92,Default,,0000,0000,0000,,for what a proof by induction\Nlooks like.
Dialogue: 0,0:11:12.92,0:11:14.71,Default,,0000,0000,0000,,The reason for this is,\Nmy guess is,
Dialogue: 0,0:11:14.71,0:11:17.12,Default,,0000,0000,0000,,well let's find out,\Nhow many of you have seen a
Dialogue: 0,0:11:17.12,0:11:20.61,Default,,0000,0000,0000,,proof by induction before?\NHow many have not?
Dialogue: 0,0:11:20.61,0:11:22.63,Default,,0000,0000,0000,,So for those of you who haven't\NI think it's a good thing in
Dialogue: 0,0:11:22.63,0:11:24.76,Default,,0000,0000,0000,,life, at one point in your life\Nto see a proof by induction,
Dialogue: 0,0:11:24.76,0:11:27.56,Default,,0000,0000,0000,,and for those who have,\Nmy guess is you saw it in some
Dialogue: 0,0:11:27.56,0:11:30.88,Default,,0000,0000,0000,,awful math class in high school\Nand it just went over--it didn't
Dialogue: 0,0:11:30.88,0:11:32.89,Default,,0000,0000,0000,,necessarily go over your head\Nbut,
Dialogue: 0,0:11:32.89,0:11:36.07,Default,,0000,0000,0000,,the excitement of it doesn't\Ncatch on.
Dialogue: 0,0:11:36.07,0:11:40.14,Default,,0000,0000,0000,,This is a context where it\Nmight appeal.
Dialogue: 0,0:11:40.14,0:11:46.40,Default,,0000,0000,0000,,So proof by induction.\NWe're going to prove this by
Dialogue: 0,0:11:46.40,0:11:57.38,Default,,0000,0000,0000,,induction on the maximum length\Nof the game and we'll call that
Dialogue: 0,0:11:57.38,0:11:59.29,Default,,0000,0000,0000,,N.\NWe'll call N the maximum length
Dialogue: 0,0:11:59.29,0:12:00.83,Default,,0000,0000,0000,,of the game.\NWhat do I mean by this?
Dialogue: 0,0:12:00.83,0:12:06.00,Default,,0000,0000,0000,,If I write down a tree I can\Nalways look at all the paths
Dialogue: 0,0:12:06.00,0:12:11.54,Default,,0000,0000,0000,,from the beginning of the tree\Nall the way through to the end
Dialogue: 0,0:12:11.54,0:12:14.72,Default,,0000,0000,0000,,of the tree.\NAnd I'm going to look at the
Dialogue: 0,0:12:14.72,0:12:18.24,Default,,0000,0000,0000,,path in that particular tree\Nthat has the largest length,
Dialogue: 0,0:12:18.24,0:12:21.74,Default,,0000,0000,0000,,and I'll call that the length\Nof the game, the maximum length
Dialogue: 0,0:12:21.74,0:12:24.59,Default,,0000,0000,0000,,of the game.\NSo we're going to do induction
Dialogue: 0,0:12:24.59,0:12:26.95,Default,,0000,0000,0000,,on the maximum length of the\Ngame.
Dialogue: 0,0:12:26.95,0:12:28.71,Default,,0000,0000,0000,,So how do we start a proof by\Ninduction?
Dialogue: 0,0:12:28.71,0:12:30.96,Default,,0000,0000,0000,,Let's just remind ourselves,\Nthose people who have seen them
Dialogue: 0,0:12:30.96,0:12:33.57,Default,,0000,0000,0000,,before.\NWe're going to prove that this
Dialogue: 0,0:12:33.57,0:12:36.96,Default,,0000,0000,0000,,theorem this true,\Nthe claim in the theorem is
Dialogue: 0,0:12:36.96,0:12:41.49,Default,,0000,0000,0000,,true for the easy case when the\Ngame is only 1 move long.
Dialogue: 0,0:12:41.49,0:12:45.52,Default,,0000,0000,0000,,That's the first step,\Nand then we're going to try and
Dialogue: 0,0:12:45.52,0:12:49.33,Default,,0000,0000,0000,,show that if it's true for all\Ngames of length <
Dialogue: 0,0:12:49.33,0:12:51.26,Default,,0000,0000,0000,,= N,\Nwhatever N is,
Dialogue: 0,0:12:51.26,0:12:56.56,Default,,0000,0000,0000,,then it must therefore be true\Nfor games of length N+1.
Dialogue: 0,0:12:56.56,0:12:58.85,Default,,0000,0000,0000,,That's the way you do a proof\Nby induction.
Dialogue: 0,0:12:58.85,0:13:01.75,Default,,0000,0000,0000,,So let's just see how that\Nworks in practice.
Dialogue: 0,0:13:01.75,0:13:04.81,Default,,0000,0000,0000,,So let's start with the easy\Nstep and we'll do it in some
Dialogue: 0,0:13:04.81,0:13:08.20,Default,,0000,0000,0000,,detail, more detail than you\Nreally need to in a math class.
Dialogue: 0,0:13:08.20,0:13:11.25,Default,,0000,0000,0000,,So if N = 1,\Nwhat do these games look like?
Dialogue: 0,0:13:11.25,0:13:13.21,Default,,0000,0000,0000,,Well let's look at some\Nexamples here.
Dialogue: 0,0:13:13.21,0:13:18.26,Default,,0000,0000,0000,,So I claim it's pretty trivial\Nif N = 1 but let's do it anyway.
Dialogue: 0,0:13:18.26,0:13:20.60,Default,,0000,0000,0000,,So the game might look like\Nthis.
Dialogue: 0,0:13:20.60,0:13:22.91,Default,,0000,0000,0000,,Player 1 is going to\Nmove--here's Player 1
Dialogue: 0,0:13:22.91,0:13:26.13,Default,,0000,0000,0000,,moving--the game's only length\None--so Player 1's the only
Dialogue: 0,0:13:26.13,0:13:30.06,Default,,0000,0000,0000,,player who ever gets to move.\NSo the game might look like
Dialogue: 0,0:13:30.06,0:13:31.100,Default,,0000,0000,0000,,this.\NLet's put in a fifth branch,
Dialogue: 0,0:13:31.100,0:13:34.61,Default,,0000,0000,0000,,it might look like this.\NAnd at the end of this game,
Dialogue: 0,0:13:34.61,0:13:37.27,Default,,0000,0000,0000,,rather than putting payoffs let\Nme just put the outcomes.
Dialogue: 0,0:13:37.27,0:13:40.22,Default,,0000,0000,0000,,So the outcome must either be a\Nwin, or a tie,
Dialogue: 0,0:13:40.22,0:13:43.03,Default,,0000,0000,0000,,or a loss, so suppose it looks\Nlike this.
Dialogue: 0,0:13:43.03,0:13:47.70,Default,,0000,0000,0000,,Suppose it's a win,\Nor here we could have a tie,
Dialogue: 0,0:13:47.70,0:13:53.36,Default,,0000,0000,0000,,or here we could have a win\Nagain, or here we could have a
Dialogue: 0,0:13:53.36,0:13:57.23,Default,,0000,0000,0000,,loss, and here we could have a\Ntie.
Dialogue: 0,0:13:57.23,0:14:02.09,Default,,0000,0000,0000,,So in this particular game I\Nclaim it's pretty clear this
Dialogue: 0,0:14:02.09,0:14:06.87,Default,,0000,0000,0000,,game has a solution.\NIt's pretty clear what 1 should
Dialogue: 0,0:14:06.87,0:14:08.13,Default,,0000,0000,0000,,do.\NWhat should 1 do?
Dialogue: 0,0:14:08.13,0:14:12.36,Default,,0000,0000,0000,,1 should pick one of her\Nchoices that leads to a win.
Dialogue: 0,0:14:12.36,0:14:15.58,Default,,0000,0000,0000,,To be careful I'll put 1 in\Nhere just to distinguish who it
Dialogue: 0,0:14:15.58,0:14:17.75,Default,,0000,0000,0000,,is who's actually winning and\Nlosing.
Dialogue: 0,0:14:17.75,0:14:21.15,Default,,0000,0000,0000,,So in this game I claim that\Nthis game has a pretty obvious
Dialogue: 0,0:14:21.15,0:14:24.66,Default,,0000,0000,0000,,solution, either Player 1 is\Ngoing to choose this branch that
Dialogue: 0,0:14:24.66,0:14:27.83,Default,,0000,0000,0000,,leads to a win or this branch\Nthat leads to a win,
Dialogue: 0,0:14:27.83,0:14:31.68,Default,,0000,0000,0000,,and either way Player 1 is\Ngoing to win.
Dialogue: 0,0:14:31.68,0:14:33.09,Default,,0000,0000,0000,,Is that obvious?\NIt's so obvious,
Dialogue: 0,0:14:33.09,0:14:35.55,Default,,0000,0000,0000,,it's kind of painful.\NSo I claim this game,
Dialogue: 0,0:14:35.55,0:14:39.96,Default,,0000,0000,0000,,we could actually replace this\Nfirst node with what's going to
Dialogue: 0,0:14:39.96,0:14:43.07,Default,,0000,0000,0000,,happen which is Player 1's going\Nto win.
Dialogue: 0,0:14:43.07,0:14:45.56,Default,,0000,0000,0000,,Is that right?\NThat was easy.
Dialogue: 0,0:14:45.56,0:14:49.74,Default,,0000,0000,0000,,Let's look at a different\Nexample, we'll do three.
Dialogue: 0,0:14:49.74,0:14:53.59,Default,,0000,0000,0000,,So here's another possible\Nexample, and this again,
Dialogue: 0,0:14:53.59,0:14:57.90,Default,,0000,0000,0000,,Player 1 is going to move here\Nand this time the possible
Dialogue: 0,0:14:57.90,0:15:01.21,Default,,0000,0000,0000,,outcomes are tie,\Nor a loss, or a loss.
Dialogue: 0,0:15:01.21,0:15:05.27,Default,,0000,0000,0000,,Once again it's a one player\Ngame, this time he has three
Dialogue: 0,0:15:05.27,0:15:09.48,Default,,0000,0000,0000,,choices and the three choices\Nlead to a tie or he loses,
Dialogue: 0,0:15:09.48,0:15:11.11,Default,,0000,0000,0000,,so I claim once again this is\Nsimple.
Dialogue: 0,0:15:11.11,0:15:13.91,Default,,0000,0000,0000,,What Player 1 should do is what?\NChoose the tie since there's no
Dialogue: 0,0:15:13.91,0:15:15.61,Default,,0000,0000,0000,,way of winning.\NBut in that case he could
Dialogue: 0,0:15:15.61,0:15:17.55,Default,,0000,0000,0000,,actually force it.\NHe could actually choose the
Dialogue: 0,0:15:17.55,0:15:19.33,Default,,0000,0000,0000,,tie in which case he's going to\Ntie.
Dialogue: 0,0:15:19.33,0:15:21.82,Default,,0000,0000,0000,,So this game has a solution\Ncalled choose the tie.
Dialogue: 0,0:15:21.82,0:15:25.72,Default,,0000,0000,0000,,And again, we could replace the\Nfirst node of the game with
Dialogue: 0,0:15:25.72,0:15:29.01,Default,,0000,0000,0000,,what's actually going to happen\Nwhich is a tie.
Dialogue: 0,0:15:29.01,0:15:32.52,Default,,0000,0000,0000,,Everyone happy?\NThere's one other possibility I
Dialogue: 0,0:15:32.52,0:15:35.09,Default,,0000,0000,0000,,guess.\NThe other possibility is that
Dialogue: 0,0:15:35.09,0:15:39.16,Default,,0000,0000,0000,,here Player 1 has a lot of\Nchoices, maybe four choices in
Dialogue: 0,0:15:39.16,0:15:43.48,Default,,0000,0000,0000,,this case,\Nonce again Player 1 is going to
Dialogue: 0,0:15:43.48,0:15:48.50,Default,,0000,0000,0000,,move but in each\Ncase--unfortunately for Player
Dialogue: 0,0:15:48.50,0:15:54.39,Default,,0000,0000,0000,,1--in each case the outcome is\Nthat Player 1 loses.
Dialogue: 0,0:15:54.39,0:15:56.80,Default,,0000,0000,0000,,So this is a game in which\NPlayer 1 is going to lose no
Dialogue: 0,0:15:56.80,0:15:59.02,Default,,0000,0000,0000,,matter what they do.\NOnce again it has a solution:
Dialogue: 0,0:15:59.02,0:16:01.40,Default,,0000,0000,0000,,the solution is Player 1 is\Ntoast and is going to lose.
Dialogue: 0,0:16:01.40,0:16:08.13,Default,,0000,0000,0000,,
Dialogue: 0,0:16:08.13,0:16:10.92,Default,,0000,0000,0000,,So I claim this has really\Ncaptured all the possibilities
Dialogue: 0,0:16:10.92,0:16:13.43,Default,,0000,0000,0000,,of games of length 1.\NI mean you could imagine that
Dialogue: 0,0:16:13.43,0:16:16.27,Default,,0000,0000,0000,,there could be more branches on\Nthem, but basically there are
Dialogue: 0,0:16:16.27,0:16:19.31,Default,,0000,0000,0000,,these three possibilities.\NEither it's the case that one
Dialogue: 0,0:16:19.31,0:16:22.72,Default,,0000,0000,0000,,of those branches leads to a\Nwin, in which case the solution
Dialogue: 0,0:16:22.72,0:16:25.48,Default,,0000,0000,0000,,is Player 1 wins;\Nor it's the case that none of
Dialogue: 0,0:16:25.48,0:16:28.66,Default,,0000,0000,0000,,the branches have wins in them,\Nbut one of them has a tie,
Dialogue: 0,0:16:28.66,0:16:30.72,Default,,0000,0000,0000,,in which Player 1 is going to\Ntie;
Dialogue: 0,0:16:30.72,0:16:33.63,Default,,0000,0000,0000,,or it's the case that all the\Nbranches have loss in them,
Dialogue: 0,0:16:33.63,0:16:35.50,Default,,0000,0000,0000,,in which Player 1's going to\Nlose.
Dialogue: 0,0:16:35.50,0:16:38.35,Default,,0000,0000,0000,,So I claim I'm for done for\Ngames of length one.
Dialogue: 0,0:16:38.35,0:16:42.05,Default,,0000,0000,0000,,Everyone okay?\NSo that step is deceptively
Dialogue: 0,0:16:42.05,0:16:45.82,Default,,0000,0000,0000,,easy but there it is.\NAll right, now we do the
Dialogue: 0,0:16:45.82,0:16:47.53,Default,,0000,0000,0000,,inductive step,\Nthe big step.
Dialogue: 0,0:16:47.53,0:16:50.49,Default,,0000,0000,0000,,What we're going to do is we're\Ngoing to assume that the
Dialogue: 0,0:16:50.49,0:16:53.45,Default,,0000,0000,0000,,statement of the theorem,\Nwhich I've now hidden
Dialogue: 0,0:16:53.45,0:16:57.82,Default,,0000,0000,0000,,unfortunately--let me unhide it\Nif I can, it's not going to be
Dialogue: 0,0:16:57.82,0:16:58.39,Default,,0000,0000,0000,,easy.
Dialogue: 0,0:16:58.39,0:17:05.12,Default,,0000,0000,0000,,
Dialogue: 0,0:17:05.12,0:17:10.69,Default,,0000,0000,0000,,This now visible?\NSo now let's assume that the
Dialogue: 0,0:17:10.69,0:17:17.64,Default,,0000,0000,0000,,statement of this theorem is\Ntrue for all games length <
Dialogue: 0,0:17:17.64,0:17:29.06,Default,,0000,0000,0000,,= N, suppose that's the case.\NSuppose the claim is true for
Dialogue: 0,0:17:29.06,0:17:41.62,Default,,0000,0000,0000,,all games of this type,\Nof length <= some N.
Dialogue: 0,0:17:41.62,0:17:45.92,Default,,0000,0000,0000,,What we need to show is--what\Nwe're going to try and show is
Dialogue: 0,0:17:45.92,0:17:50.14,Default,,0000,0000,0000,,therefore it will be true for\Nall games of length N + 1.
Dialogue: 0,0:17:50.14,0:17:58.98,Default,,0000,0000,0000,,What we want to show is--we\Nclaim, therefore,
Dialogue: 0,0:17:58.98,0:18:07.22,Default,,0000,0000,0000,,it will be true for games of\Nlength N + 1,
Dialogue: 0,0:18:07.22,0:18:16.07,Default,,0000,0000,0000,,that's the key step in\Ninductive proofs.
Dialogue: 0,0:18:16.07,0:18:19.59,Default,,0000,0000,0000,,All right, so how are we going\Nto do that?
Dialogue: 0,0:18:19.59,0:18:22.04,Default,,0000,0000,0000,,Well let's have a look at a\Ngame of length N + 1,
Dialogue: 0,0:18:22.04,0:18:24.90,Default,,0000,0000,0000,,and obviously I can't use\Nthousands here so let me choose
Dialogue: 0,0:18:24.90,0:18:28.83,Default,,0000,0000,0000,,from relatively small numbers,\Nbut the idea will go through.
Dialogue: 0,0:18:28.83,0:18:34.78,Default,,0000,0000,0000,,So let's have a look at a game.\NSo here's a game in which
Dialogue: 0,0:18:34.78,0:18:40.05,Default,,0000,0000,0000,,Player 1 moves first,\NPlayer 2 moves second.
Dialogue: 0,0:18:40.05,0:18:44.52,Default,,0000,0000,0000,,Let's suppose that if Player 2\Ndoes this, then 1 only has
Dialogue: 0,0:18:44.52,0:18:48.81,Default,,0000,0000,0000,,little choice here,\Nup here then one has a more
Dialogue: 0,0:18:48.81,0:18:53.85,Default,,0000,0000,0000,,complicated choice,\Nand perhaps 2 could move again.
Dialogue: 0,0:18:53.85,0:18:55.87,Default,,0000,0000,0000,,So this is quite a complicated\Nlittle game up here,
Dialogue: 0,0:18:55.87,0:18:58.30,Default,,0000,0000,0000,,and down here let's make it a\Nlittle bit less complicated.
Dialogue: 0,0:18:58.30,0:19:02.50,Default,,0000,0000,0000,,Here the game looks like this\Nand then comes to an end,
Dialogue: 0,0:19:02.50,0:19:06.06,Default,,0000,0000,0000,,so the tree looks like this.\NI haven't put the end,
Dialogue: 0,0:19:06.06,0:19:09.56,Default,,0000,0000,0000,,I haven't put the outcomes on\Nit but the tree looks like this.
Dialogue: 0,0:19:09.56,0:19:12.28,Default,,0000,0000,0000,,So how long is this tree first\Nof all?
Dialogue: 0,0:19:12.28,0:19:16.38,Default,,0000,0000,0000,,Well I claim that the longest\Npath in this tree,
Dialogue: 0,0:19:16.38,0:19:20.48,Default,,0000,0000,0000,,from the beginning to the end\Nhas four steps.
Dialogue: 0,0:19:20.48,0:19:23.41,Default,,0000,0000,0000,,Let's just check.\NSo one, two,
Dialogue: 0,0:19:23.41,0:19:27.65,Default,,0000,0000,0000,,three, four that's what I claim\Nis the longest path.
Dialogue: 0,0:19:27.65,0:19:33.11,Default,,0000,0000,0000,,Any path going down this way\Nonly has three moves in it,
Dialogue: 0,0:19:33.11,0:19:36.58,Default,,0000,0000,0000,,so this is a game of length\Nfour.
Dialogue: 0,0:19:36.58,0:19:42.06,Default,,0000,0000,0000,,So we can apply it to our\Nclaim, let's assume that the
Dialogue: 0,0:19:42.06,0:19:47.44,Default,,0000,0000,0000,,theorem holds for all trees\Nlength three or fewer,
Dialogue: 0,0:19:47.44,0:19:51.59,Default,,0000,0000,0000,,so that N + 1 is 4 for the\Npurpose of our example.
Dialogue: 0,0:19:51.59,0:19:57.94,Default,,0000,0000,0000,,So in this example--I don't\Nwant to put it here,
Dialogue: 0,0:19:57.94,0:20:03.34,Default,,0000,0000,0000,,let's put it here--in this\Nexample N = 3,
Dialogue: 0,0:20:03.34,0:20:09.70,Default,,0000,0000,0000,,so that N + 1 = 4.\NEveryone happy with this in the
Dialogue: 0,0:20:09.70,0:20:12.95,Default,,0000,0000,0000,,example?\NNow what I want to observe
Dialogue: 0,0:20:12.95,0:20:17.47,Default,,0000,0000,0000,,about this is the following:\Ncontained in this N + 1,
Dialogue: 0,0:20:17.47,0:20:21.81,Default,,0000,0000,0000,,or the game of length 4 are\Nsome smaller games.
Dialogue: 0,0:20:21.81,0:20:23.60,Default,,0000,0000,0000,,You could think of them as\Nsub-games.
Dialogue: 0,0:20:23.60,0:20:26.83,Default,,0000,0000,0000,,They're games within the game,\Nis that right?
Dialogue: 0,0:20:26.83,0:20:31.81,Default,,0000,0000,0000,,So let's have a look.\NI claim, in particular--draw
Dialogue: 0,0:20:31.81,0:20:40.02,Default,,0000,0000,0000,,around them in pink--there's a\Ngame here that follows Player 1
Dialogue: 0,0:20:40.02,0:20:47.56,Default,,0000,0000,0000,,choosing Up and there's a game\Nhere that follows Player 1
Dialogue: 0,0:20:47.56,0:20:53.41,Default,,0000,0000,0000,,choosing Down,\Nis that right?
Dialogue: 0,0:20:53.41,0:20:58.64,Default,,0000,0000,0000,,Okay, so these are both games,\Nand what do we have here?
Dialogue: 0,0:20:58.64,0:21:02.13,Default,,0000,0000,0000,,So this little game in\Nhere--the game in the top
Dialogue: 0,0:21:02.13,0:21:06.37,Default,,0000,0000,0000,,circle, the game that follows\NPlayer 1 moving up--that's a
Dialogue: 0,0:21:06.37,0:21:10.57,Default,,0000,0000,0000,,game and it has a length.\NSo this little thing is a game
Dialogue: 0,0:21:10.57,0:21:14.53,Default,,0000,0000,0000,,and I'm going to call it a\Nsub-game, some jargon that we'll
Dialogue: 0,0:21:14.53,0:21:17.73,Default,,0000,0000,0000,,be getting used to later on in\Nthe semester.
Dialogue: 0,0:21:17.73,0:21:25.34,Default,,0000,0000,0000,,It's a game within the game,\Nbut it's basically just a game:
Dialogue: 0,0:21:25.34,0:21:32.82,Default,,0000,0000,0000,,it's a sub-game and this is a\Nsub-game following 1 choosing
Dialogue: 0,0:21:32.82,0:21:38.37,Default,,0000,0000,0000,,Up--let's put Up in\Nhere--following up.
Dialogue: 0,0:21:38.37,0:21:41.81,Default,,0000,0000,0000,,And I claim that this game has\Na length--this sub-game has a
Dialogue: 0,0:21:41.81,0:21:44.02,Default,,0000,0000,0000,,length.\NSo we knew that we started from
Dialogue: 0,0:21:44.02,0:21:46.61,Default,,0000,0000,0000,,a game of length 4,\Nwe've taken one of the moves,
Dialogue: 0,0:21:46.61,0:21:50.07,Default,,0000,0000,0000,,and let's just make sure this\Nis actually a game of length 3.
Dialogue: 0,0:21:50.07,0:21:53.30,Default,,0000,0000,0000,,So the game started here,\Nthis would be a game of length
Dialogue: 0,0:21:53.30,0:21:55.89,Default,,0000,0000,0000,,3 because you could go one,\Ntwo, three moves,
Dialogue: 0,0:21:55.89,0:21:59.01,Default,,0000,0000,0000,,is that right?\NSo this is a game of length 3.
Dialogue: 0,0:21:59.01,0:22:08.08,Default,,0000,0000,0000,,So this is a sub-game following\N1 choosing Up and it,
Dialogue: 0,0:22:08.08,0:22:13.14,Default,,0000,0000,0000,,the sub-game,\Nhas length 3.
Dialogue: 0,0:22:13.14,0:22:21.00,Default,,0000,0000,0000,,Down here, this is also a\Nsub-game, it's a game that
Dialogue: 0,0:22:21.00,0:22:29.95,Default,,0000,0000,0000,,follows Player 1 choosing Down\Nand this little sub-game has
Dialogue: 0,0:22:29.95,0:22:39.36,Default,,0000,0000,0000,,length--now here we have to be a\Nlittle bit careful--you might
Dialogue: 0,0:22:39.36,0:22:48.30,Default,,0000,0000,0000,,think that since we started from\Na game of length 4,
Dialogue: 0,0:22:48.30,0:22:53.21,Default,,0000,0000,0000,,after the first move we must be\Nin a game of length 3.
Dialogue: 0,0:22:53.21,0:22:56.02,Default,,0000,0000,0000,,But actually that's not true,\Nand if we look carefully,
Dialogue: 0,0:22:56.02,0:22:58.88,Default,,0000,0000,0000,,we'll notice that this game\Ndown here, the game starting
Dialogue: 0,0:22:58.88,0:23:02.41,Default,,0000,0000,0000,,here actually isn't of length 3.\NIt's of length 2.
Dialogue: 0,0:23:02.41,0:23:04.45,Default,,0000,0000,0000,,Is that right?\NSo even though started from a
Dialogue: 0,0:23:04.45,0:23:06.72,Default,,0000,0000,0000,,game of length 4,\Nby going this way we put
Dialogue: 0,0:23:06.72,0:23:08.76,Default,,0000,0000,0000,,ourselves into a game of length\N2.
Dialogue: 0,0:23:08.76,0:23:16.02,Default,,0000,0000,0000,,Is that right?\NSo 1,2 or 1,2--whatever--it has
Dialogue: 0,0:23:16.02,0:23:20.71,Default,,0000,0000,0000,,length 2.\NOkay, all right so in this
Dialogue: 0,0:23:20.71,0:23:25.87,Default,,0000,0000,0000,,example N is 3 and N + 1 is 4,\Nand our assumption,
Dialogue: 0,0:23:25.87,0:23:29.66,Default,,0000,0000,0000,,our induction assumption is\Nwhat?
Dialogue: 0,0:23:29.66,0:23:38.36,Default,,0000,0000,0000,,We've assumed that the claim of\Nthe theorem holds for all games
Dialogue: 0,0:23:38.36,0:23:44.53,Default,,0000,0000,0000,,<= N, which in this case\Nmeans <= 3.
Dialogue: 0,0:23:44.53,0:23:47.40,Default,,0000,0000,0000,,So what does that tell us?\NThat tells us,
Dialogue: 0,0:23:47.40,0:23:51.59,Default,,0000,0000,0000,,by our assumption,\Nthis game, which I've put a
Dialogue: 0,0:23:51.59,0:23:56.91,Default,,0000,0000,0000,,pink circle around on the top,\Nthis is a game of length 3,
Dialogue: 0,0:23:56.91,0:24:02.32,Default,,0000,0000,0000,,this game has a solution.\NIt must have a solution because
Dialogue: 0,0:24:02.32,0:24:07.77,Default,,0000,0000,0000,,it's of length 3 or less.\NSo by the induction hypothesis
Dialogue: 0,0:24:07.77,0:24:14.65,Default,,0000,0000,0000,,as it's called--by the induction\Nhypothesis--this is a technical
Dialogue: 0,0:24:14.65,0:24:19.56,Default,,0000,0000,0000,,term, but what's the induction\Nhypothesis?
Dialogue: 0,0:24:19.56,0:24:29.69,Default,,0000,0000,0000,,It's this thing.\NBy the assumption that we made
Dialogue: 0,0:24:29.69,0:24:38.25,Default,,0000,0000,0000,,this game has a solution.\NSo it's a game of length 3,3
Dialogue: 0,0:24:38.25,0:24:40.82,Default,,0000,0000,0000,,<= N in this case.\NSo this game must have a
Dialogue: 0,0:24:40.82,0:24:44.54,Default,,0000,0000,0000,,solution.\NNow I don't immediately know by
Dialogue: 0,0:24:44.54,0:24:50.03,Default,,0000,0000,0000,,staring at it what it is,\Nbut let's suppose it was W,
Dialogue: 0,0:24:50.03,0:24:53.59,Default,,0000,0000,0000,,say it was W.\NAnd the game down below,
Dialogue: 0,0:24:53.59,0:24:57.56,Default,,0000,0000,0000,,this is also a game,\Nand it's a game of length 2 but
Dialogue: 0,0:24:57.56,0:25:00.60,Default,,0000,0000,0000,,2 is less than 3 as well,\N2 <= 3.
Dialogue: 0,0:25:00.60,0:25:06.29,Default,,0000,0000,0000,,So this game also has a\Nsolution.
Dialogue: 0,0:25:06.29,0:25:13.72,Default,,0000,0000,0000,,This game also,\Nby the same assumption,
Dialogue: 0,0:25:13.72,0:25:22.71,Default,,0000,0000,0000,,has a solution,\Nso its solution is say--I don't
Dialogue: 0,0:25:22.71,0:25:29.01,Default,,0000,0000,0000,,know--maybe its L.\NSo what does that mean to say
Dialogue: 0,0:25:29.01,0:25:33.08,Default,,0000,0000,0000,,that these games have solutions,\Nin this case we're going to
Dialogue: 0,0:25:33.08,0:25:35.76,Default,,0000,0000,0000,,assume W is this one,\Nand L is this one,
Dialogue: 0,0:25:35.76,0:25:38.23,Default,,0000,0000,0000,,what does it mean?\NIt means that,
Dialogue: 0,0:25:38.23,0:25:41.69,Default,,0000,0000,0000,,just as we did with the games\Nup there, we could put the
Dialogue: 0,0:25:41.69,0:25:44.27,Default,,0000,0000,0000,,solution at the beginning of the\Ngame.
Dialogue: 0,0:25:44.27,0:25:47.78,Default,,0000,0000,0000,,We know that if we get into\Nthis game, we're going to get
Dialogue: 0,0:25:47.78,0:25:51.24,Default,,0000,0000,0000,,the solution of this game;\Nand we know if we get into this
Dialogue: 0,0:25:51.24,0:25:54.10,Default,,0000,0000,0000,,game, we're going to get the\Nsolution of this game.
Dialogue: 0,0:25:54.10,0:25:58.84,Default,,0000,0000,0000,,So we can replace this one with\Nits solution which by assumption
Dialogue: 0,0:25:58.84,0:26:03.20,Default,,0000,0000,0000,,was W, and this one by its\Nsolution which by assumption was
Dialogue: 0,0:26:03.20,0:26:04.98,Default,,0000,0000,0000,,L.\NAnd here I want to be really
Dialogue: 0,0:26:04.98,0:26:08.01,Default,,0000,0000,0000,,careful, I need to keep track of\Nwhich person it is it's a win or
Dialogue: 0,0:26:08.01,0:26:10.82,Default,,0000,0000,0000,,loss for.\NSo this was a win for Player 1,
Dialogue: 0,0:26:10.82,0:26:14.87,Default,,0000,0000,0000,,hence it was a loss for Player\N2, and this was a loss for
Dialogue: 0,0:26:14.87,0:26:18.12,Default,,0000,0000,0000,,Player 1, hence it was a win for\NPlayer 2.
Dialogue: 0,0:26:18.12,0:26:22.06,Default,,0000,0000,0000,,So these games,\Neach of them have some
Dialogue: 0,0:26:22.06,0:26:28.35,Default,,0000,0000,0000,,solution, and this case I've\Nwritten down the solutions as W
Dialogue: 0,0:26:28.35,0:26:31.15,Default,,0000,0000,0000,,or L.\NSo now what could we do?
Dialogue: 0,0:26:31.15,0:26:33.35,Default,,0000,0000,0000,,Let me just bring down this\Nboard again.
Dialogue: 0,0:26:33.35,0:26:37.33,Default,,0000,0000,0000,,I can translate this game into\Na very simple game.
Dialogue: 0,0:26:37.33,0:26:40.93,Default,,0000,0000,0000,,I'm going to translate it up\Nhere, so this game can be
Dialogue: 0,0:26:40.93,0:26:47.13,Default,,0000,0000,0000,,translated as follows.\NPlayer 1 moves,
Dialogue: 0,0:26:47.13,0:27:06.61,Default,,0000,0000,0000,,if he goes Up then he hits a W\Nand if he goes Down he hits a L.
Dialogue: 0,0:27:06.61,0:27:09.96,Default,,0000,0000,0000,,So in this particular example,\NPlayer 1 is effectively
Dialogue: 0,0:27:09.96,0:27:13.75,Default,,0000,0000,0000,,choosing between going Up and\Nfinding himself in a game which
Dialogue: 0,0:27:13.75,0:27:16.80,Default,,0000,0000,0000,,has a solution,\Nand the solution is he wins it,
Dialogue: 0,0:27:16.80,0:27:20.01,Default,,0000,0000,0000,,or going Down and finding\Nhimself in a game which has a
Dialogue: 0,0:27:20.01,0:27:24.64,Default,,0000,0000,0000,,solution,\Nand the solution is he's toast.
Dialogue: 0,0:27:24.64,0:27:29.33,Default,,0000,0000,0000,,But that's what?\NThat's a one move game.
Dialogue: 0,0:27:29.33,0:27:31.94,Default,,0000,0000,0000,,So we know this has a solution,\Nand in particular,
Dialogue: 0,0:27:31.94,0:27:37.26,Default,,0000,0000,0000,,he's going to choose Up.\NThis one has a solution.
Dialogue: 0,0:27:37.26,0:27:55.82,Default,,0000,0000,0000,,This has a solution,\Nit is a game of length 1.
Dialogue: 0,0:27:55.82,0:27:59.78,Default,,0000,0000,0000,,So what do we do?\NSomewhat schematically,
Dialogue: 0,0:27:59.78,0:28:04.29,Default,,0000,0000,0000,,we took a game of length N + 1,\Nin this case that was 4;
Dialogue: 0,0:28:04.29,0:28:09.41,Default,,0000,0000,0000,,and we pointed out that once\NPlayer 1 has made her first move
Dialogue: 0,0:28:09.41,0:28:12.22,Default,,0000,0000,0000,,in this game,\Nwe are in a game,
Dialogue: 0,0:28:12.22,0:28:15.46,Default,,0000,0000,0000,,or in a sub-game if you like,\Nthat has length less than 4,
Dialogue: 0,0:28:15.46,0:28:17.22,Default,,0000,0000,0000,,it could be 3,\Nit could be 2,
Dialogue: 0,0:28:17.22,0:28:21.89,Default,,0000,0000,0000,,whatever.\NWhatever sub-game we're in,
Dialogue: 0,0:28:21.89,0:28:26.26,Default,,0000,0000,0000,,by assumption,\Nthat game has a solution.
Dialogue: 0,0:28:26.26,0:28:29.54,Default,,0000,0000,0000,,So it's really effectively,\NPlayer 1 is choosing between
Dialogue: 0,0:28:29.54,0:28:33.00,Default,,0000,0000,0000,,going into a game with solution\NW or going into a game with
Dialogue: 0,0:28:33.00,0:28:35.35,Default,,0000,0000,0000,,solution L.\NAnd if there were 15 other
Dialogue: 0,0:28:35.35,0:28:37.92,Default,,0000,0000,0000,,sub-games here,\Neach one would have a solution,
Dialogue: 0,0:28:37.92,0:28:41.32,Default,,0000,0000,0000,,and each one Player 1 would be\Nable to associate that solution
Dialogue: 0,0:28:41.32,0:28:44.56,Default,,0000,0000,0000,,with what he's going to\Nget--what she's going to get.
Dialogue: 0,0:28:44.56,0:28:49.65,Default,,0000,0000,0000,,So I claim that,\Nif it in fact is true that each
Dialogue: 0,0:28:49.65,0:28:55.71,Default,,0000,0000,0000,,of these sub-games of length 3\Nor less had a solution,
Dialogue: 0,0:28:55.71,0:28:59.29,Default,,0000,0000,0000,,then the game of length 4 must\Nhave a solution,
Dialogue: 0,0:28:59.29,0:29:03.52,Default,,0000,0000,0000,,which is what?\NIt's the solution which is:
Dialogue: 0,0:29:03.52,0:29:07.93,Default,,0000,0000,0000,,Player 1 should pick the best\Nsub-game.
Dialogue: 0,0:29:07.93,0:29:11.30,Default,,0000,0000,0000,,Are people convinced by that\Nstep?
Dialogue: 0,0:29:11.30,0:29:15.45,Default,,0000,0000,0000,,People are looking slightly\N"deer in the headlamps" now,
Dialogue: 0,0:29:15.45,0:29:20.30,Default,,0000,0000,0000,,so let me just say it again.\NWe started by assuming that all
Dialogue: 0,0:29:20.30,0:29:23.57,Default,,0000,0000,0000,,games of length 3 or less,\Nor N or less,
Dialogue: 0,0:29:23.57,0:29:27.62,Default,,0000,0000,0000,,have a solution.\NWe pointed out that any game
Dialogue: 0,0:29:27.62,0:29:32.88,Default,,0000,0000,0000,,that has length N + 1 can be\Nthought of as an initial move by
Dialogue: 0,0:29:32.88,0:29:37.35,Default,,0000,0000,0000,,Player 1 followed by a game of\Nlength N or less,
Dialogue: 0,0:29:37.35,0:29:41.29,Default,,0000,0000,0000,,N or fewer I should say.\NEach of those games of N or
Dialogue: 0,0:29:41.29,0:29:45.42,Default,,0000,0000,0000,,fewer steps has a solution,\Nso Player 1 is just going to
Dialogue: 0,0:29:45.42,0:29:49.85,Default,,0000,0000,0000,,choose the game that has the\Nbest solution for her and we're
Dialogue: 0,0:29:49.85,0:29:54.30,Default,,0000,0000,0000,,done.\NIn this particular example,
Dialogue: 0,0:29:54.30,0:30:02.39,Default,,0000,0000,0000,,Player 1 is going to choose Up\Nand therefore the solution to
Dialogue: 0,0:30:02.39,0:30:07.46,Default,,0000,0000,0000,,this parent game is Player 1\Nwins.
Dialogue: 0,0:30:07.46,0:30:11.58,Default,,0000,0000,0000,,Now the hard step I think in\Nproofs by induction is realizing
Dialogue: 0,0:30:11.58,0:30:15.47,Default,,0000,0000,0000,,that you're done.\NSo I claim we're now done,
Dialogue: 0,0:30:15.47,0:30:19.48,Default,,0000,0000,0000,,why are we done?\NWell we know that it was pretty
Dialogue: 0,0:30:19.48,0:30:23.14,Default,,0000,0000,0000,,easy that all games of length 1\Nhave a solution.
Dialogue: 0,0:30:23.14,0:30:27.10,Default,,0000,0000,0000,,That was pretty trivial.\NAnd we've shown that if any
Dialogue: 0,0:30:27.10,0:30:32.62,Default,,0000,0000,0000,,game of length of N or fewer has\Na solution, then games of N + 1
Dialogue: 0,0:30:32.62,0:30:35.42,Default,,0000,0000,0000,,have a solution.\NSo now let's see how we can
Dialogue: 0,0:30:35.42,0:30:38.05,Default,,0000,0000,0000,,proceed.\NWe know that games of length 1
Dialogue: 0,0:30:38.05,0:30:41.20,Default,,0000,0000,0000,,have a solution,\Nso let's consider games of
Dialogue: 0,0:30:41.20,0:30:43.22,Default,,0000,0000,0000,,length 2.\NGames of length 2,
Dialogue: 0,0:30:43.22,0:30:45.57,Default,,0000,0000,0000,,do games of length 2 have a\Nsolution?
Dialogue: 0,0:30:45.57,0:30:50.10,Default,,0000,0000,0000,,Well let's set N = 1.\NWe know that if games of length
Dialogue: 0,0:30:50.10,0:30:52.87,Default,,0000,0000,0000,,1 have a solution,\Nthen any game of length 2 could
Dialogue: 0,0:30:52.87,0:30:56.66,Default,,0000,0000,0000,,be thought of as an initial step\Nfollowed by a game of length 1,
Dialogue: 0,0:30:56.66,0:30:59.37,Default,,0000,0000,0000,,but that has a solution,\Nso therefore games of length 2
Dialogue: 0,0:30:59.37,0:31:01.59,Default,,0000,0000,0000,,have a solution.\NNow let's think of games with
Dialogue: 0,0:31:01.59,0:31:04.38,Default,,0000,0000,0000,,length 3, we've shown that games\Nwith length 1 have a solution
Dialogue: 0,0:31:04.38,0:31:06.34,Default,,0000,0000,0000,,and games with length 2 have a\Nsolution.
Dialogue: 0,0:31:06.34,0:31:09.48,Default,,0000,0000,0000,,Any game of length 3 can be\Nthought of as a game in which
Dialogue: 0,0:31:09.48,0:31:13.00,Default,,0000,0000,0000,,there's an initial step followed\Nby either a game of length 1 or
Dialogue: 0,0:31:13.00,0:31:16.36,Default,,0000,0000,0000,,a game of length 2,\Neach of which have a solution,
Dialogue: 0,0:31:16.36,0:31:20.43,Default,,0000,0000,0000,,so once again a game of length\N3 has a solution and so on.
Dialogue: 0,0:31:20.43,0:31:23.70,Default,,0000,0000,0000,,So games of induction,\Nthey work by building up on the
Dialogue: 0,0:31:23.70,0:31:26.54,Default,,0000,0000,0000,,length of the game,\Nand we're ending up knowing
Dialogue: 0,0:31:26.54,0:31:29.92,Default,,0000,0000,0000,,that we're done.\NFor those people who have never
Dialogue: 0,0:31:29.92,0:31:34.22,Default,,0000,0000,0000,,seen a proof by induction don't\Nworry I'm not going to test you
Dialogue: 0,0:31:34.22,0:31:37.06,Default,,0000,0000,0000,,on a proof with induction on the\Nexam,
Dialogue: 0,0:31:37.06,0:31:39.07,Default,,0000,0000,0000,,I just wanted you to see one\Nonce.
Dialogue: 0,0:31:39.07,0:31:43.17,Default,,0000,0000,0000,,Let's all take a deep breath\Nand try and digest this a little
Dialogue: 0,0:31:43.17,0:31:48.66,Default,,0000,0000,0000,,bit by playing a game.\NI'll leave it up there so you
Dialogue: 0,0:31:48.66,0:31:51.44,Default,,0000,0000,0000,,can stare at it.\NWe'll want it down again later.
Dialogue: 0,0:31:51.44,0:31:57.55,Default,,0000,0000,0000,,
Dialogue: 0,0:31:57.55,0:32:04.04,Default,,0000,0000,0000,,Let's try and actually play a\Ngame and see if we can actually
Dialogue: 0,0:32:04.04,0:32:07.99,Default,,0000,0000,0000,,throw any light on this.\NSo I'm going to pick out
Dialogue: 0,0:32:07.99,0:32:10.29,Default,,0000,0000,0000,,volunteers like I did last time,\Nbut first of all,
Dialogue: 0,0:32:10.29,0:32:11.98,Default,,0000,0000,0000,,let me tell you what the game\Nis.
Dialogue: 0,0:32:11.98,0:32:14.73,Default,,0000,0000,0000,,So once again I'm going to have\Nrocks in this game,
Dialogue: 0,0:32:14.73,0:32:17.76,Default,,0000,0000,0000,,and once again I'm going to\Napproximate those rocks with
Dialogue: 0,0:32:17.76,0:32:23.36,Default,,0000,0000,0000,,marks on the blackboard.\NSo here's an example.
Dialogue: 0,0:32:23.36,0:32:29.16,Default,,0000,0000,0000,,The example is this.\NThe game involves an array of
Dialogue: 0,0:32:29.16,0:32:37.50,Default,,0000,0000,0000,,rocks, so here the array has\Nfive rows and three columns.
Dialogue: 0,0:32:37.50,0:32:41.16,Default,,0000,0000,0000,,So the rocks are not arranged\Nas they were before in piles,
Dialogue: 0,0:32:41.16,0:32:43.94,Default,,0000,0000,0000,,but rather in a sort of in a\Npretty array.
Dialogue: 0,0:32:43.94,0:32:45.97,Default,,0000,0000,0000,,I should have made it more even\Nbut this is: one,
Dialogue: 0,0:32:45.97,0:32:47.24,Default,,0000,0000,0000,,two, three, four,\Nfive rows;
Dialogue: 0,0:32:47.24,0:32:49.02,Default,,0000,0000,0000,,and one, two,\Nthree columns,
Dialogue: 0,0:32:49.02,0:32:59.19,Default,,0000,0000,0000,,at least in this example.\NBut in general there's an array
Dialogue: 0,0:32:59.19,0:33:04.71,Default,,0000,0000,0000,,of rocks, N x M.\NWe're going to play
Dialogue: 0,0:33:04.71,0:33:10.27,Default,,0000,0000,0000,,sequentially with the players.\NAnd the way the game is going
Dialogue: 0,0:33:10.27,0:33:17.16,Default,,0000,0000,0000,,to work is this--is when it's\Nyour turn to move,
Dialogue: 0,0:33:17.16,0:33:21.76,Default,,0000,0000,0000,,you have to point to one of\Nthese rocks and whichever rock
Dialogue: 0,0:33:21.76,0:33:26.17,Default,,0000,0000,0000,,you point to I will remove.\NI will delete that rock and all
Dialogue: 0,0:33:26.17,0:33:29.24,Default,,0000,0000,0000,,the rocks that lie above or to\Nthe right of it:
Dialogue: 0,0:33:29.24,0:33:32.51,Default,,0000,0000,0000,,all the rocks that lie to the\Nnortheast of it.
Dialogue: 0,0:33:32.51,0:33:36.80,Default,,0000,0000,0000,,So for example,\Nif you pointed to this rock,
Dialogue: 0,0:33:36.80,0:33:41.39,Default,,0000,0000,0000,,then I will remove this rock\Nand also this one,
Dialogue: 0,0:33:41.39,0:33:46.34,Default,,0000,0000,0000,,this one, and this one.\NIf the next person comes along
Dialogue: 0,0:33:46.34,0:33:50.01,Default,,0000,0000,0000,,and chooses this one,\Nthen I will remove this one,
Dialogue: 0,0:33:50.01,0:33:53.19,Default,,0000,0000,0000,,and also that one.\NOkay, everyone understand?
Dialogue: 0,0:33:53.19,0:34:00.30,Default,,0000,0000,0000,,All right and the game is\Nlost--this is important--the
Dialogue: 0,0:34:00.30,0:34:08.62,Default,,0000,0000,0000,,game is lost by the person who\Nends up taking the last rock.
Dialogue: 0,0:34:08.62,0:34:18.79,Default,,0000,0000,0000,,The loser is the person who\Nends up removing the last rock.
Dialogue: 0,0:34:18.79,0:34:24.79,Default,,0000,0000,0000,,Could I have some volunteers?\NCan I volunteer people then?
Dialogue: 0,0:34:24.79,0:34:27.100,Default,,0000,0000,0000,,How about the guy with the\Nwhite t-shirt with the yellow on
Dialogue: 0,0:34:27.100,0:34:31.46,Default,,0000,0000,0000,,there?\NOkay, come on up front,
Dialogue: 0,0:34:31.46,0:34:36.97,Default,,0000,0000,0000,,and who else can I volunteer.\NEveryone's looking away from
Dialogue: 0,0:34:36.97,0:34:39.10,Default,,0000,0000,0000,,me, desperately looking away\Nfrom me.
Dialogue: 0,0:34:39.10,0:34:42.86,Default,,0000,0000,0000,,How about the guy with the Yale\Nsweatshirt on,
Dialogue: 0,0:34:42.86,0:34:46.20,Default,,0000,0000,0000,,the Yale football sweatshirt\Non, okay.
Dialogue: 0,0:34:46.20,0:34:47.90,Default,,0000,0000,0000,,So come on up.\NYour name is?
Dialogue: 0,0:34:47.90,0:34:53.28,Default,,0000,0000,0000,,I should get a mike,\Nlet me get a mike up here,
Dialogue: 0,0:34:53.28,0:34:55.85,Default,,0000,0000,0000,,thank you.\NGreat, your name is?
Dialogue: 0,0:34:55.85,0:34:57.24,Default,,0000,0000,0000,,Student: Noah.\NProfessor Ben Polak:
Dialogue: 0,0:34:57.24,0:34:58.81,Default,,0000,0000,0000,,Noah and your name is?\NStudent: Koran.
Dialogue: 0,0:34:58.81,0:34:59.57,Default,,0000,0000,0000,,Professor Ben Polak:Say\Nit into the mike.
Dialogue: 0,0:34:59.57,0:35:00.97,Default,,0000,0000,0000,,Student: Koran.\NProfessor Ben Polak:
Dialogue: 0,0:35:00.97,0:35:02.80,Default,,0000,0000,0000,,Koran okay.\NSo Noah and Koran are our
Dialogue: 0,0:35:02.80,0:35:05.11,Default,,0000,0000,0000,,players.\NEveryone understand the rules?
Dialogue: 0,0:35:05.11,0:35:06.72,Default,,0000,0000,0000,,Do you understand the rules?\NYeah?
Dialogue: 0,0:35:06.72,0:35:08.59,Default,,0000,0000,0000,,So why don't we make Noah go\Nfirst.
Dialogue: 0,0:35:08.59,0:35:10.67,Default,,0000,0000,0000,,So Noah which rock are you\Ngoing to remove?
Dialogue: 0,0:35:10.67,0:35:14.61,Default,,0000,0000,0000,,Remember the last rock loses.\NStudent: That one.
Dialogue: 0,0:35:14.61,0:35:15.13,Default,,0000,0000,0000,,Professor Ben Polak:\NThat one.
Dialogue: 0,0:35:15.13,0:35:19.65,Default,,0000,0000,0000,,Okay, so Noah chose this one.\NSo I'm going to remove this one
Dialogue: 0,0:35:19.65,0:35:22.29,Default,,0000,0000,0000,,and the one above it.\NStudent: So all the
Dialogue: 0,0:35:22.29,0:35:23.35,Default,,0000,0000,0000,,rocks to the north and east are\Ndeleted, right?
Dialogue: 0,0:35:23.35,0:35:27.11,Default,,0000,0000,0000,,Professor Ben Polak: All\Nthe rocks to the north and east
Dialogue: 0,0:35:27.11,0:35:32.58,Default,,0000,0000,0000,,of it are deleted.\NThat means you--last rock loses.
Dialogue: 0,0:35:32.58,0:35:47.55,Default,,0000,0000,0000,,Okay good.\NStudent: That one.
Dialogue: 0,0:35:47.55,0:35:49.17,Default,,0000,0000,0000,,Professor Ben Polak:\NThat one okay.
Dialogue: 0,0:35:49.17,0:36:00.52,Default,,0000,0000,0000,,So now we have an L shape.\NStudent: That one.
Dialogue: 0,0:36:00.52,0:36:05.22,Default,,0000,0000,0000,,Professor Ben Polak:\NThat one, all right.
Dialogue: 0,0:36:05.22,0:36:06.72,Default,,0000,0000,0000,,Student: That one.\NProfessor Ben Polak:
Dialogue: 0,0:36:06.72,0:36:07.46,Default,,0000,0000,0000,,That one okay,\Nokay.
Dialogue: 0,0:36:07.46,0:36:10.68,Default,,0000,0000,0000,,All right so we're done.\NOkay, everyone understand how
Dialogue: 0,0:36:10.68,0:36:14.37,Default,,0000,0000,0000,,that worked?\NRound of applause for our
Dialogue: 0,0:36:14.37,0:36:17.71,Default,,0000,0000,0000,,players please,\Nthank you.
Dialogue: 0,0:36:17.71,0:36:19.56,Default,,0000,0000,0000,,Let me get two more volunteers\Nnow that everyone has seen it.
Dialogue: 0,0:36:19.56,0:36:23.20,Default,,0000,0000,0000,,These guys had the hard job,\Nthey had to figure it out cold.
Dialogue: 0,0:36:23.20,0:36:26.52,Default,,0000,0000,0000,,Two more volunteers?\NOh I don't have to pick
Dialogue: 0,0:36:26.52,0:36:28.39,Default,,0000,0000,0000,,volunteers--this is Yale,\Nsomebody volunteer.
Dialogue: 0,0:36:28.39,0:36:29.77,Default,,0000,0000,0000,,Are you volunteering?\NGreat.
Dialogue: 0,0:36:29.77,0:36:35.96,Default,,0000,0000,0000,,I have one volunteer.\NYou can pick an opponent if you
Dialogue: 0,0:36:35.96,0:36:38.77,Default,,0000,0000,0000,,like.\NThere you go thank you.
Dialogue: 0,0:36:38.77,0:36:43.46,Default,,0000,0000,0000,,Your name is,\Nlet's just wait until the mikes
Dialogue: 0,0:36:43.46,0:36:45.57,Default,,0000,0000,0000,,are here.\NSo your name is?
Dialogue: 0,0:36:45.57,0:36:47.08,Default,,0000,0000,0000,,Student: Peter.\NProfessor Ben Polak:
Dialogue: 0,0:36:47.08,0:36:50.84,Default,,0000,0000,0000,,Peter and your name is Justin.\NStudent: Justin.
Dialogue: 0,0:36:50.84,0:36:56.90,Default,,0000,0000,0000,,Professor Ben Polak: Let\Nme put a new array up here.
Dialogue: 0,0:36:56.90,0:36:59.39,Default,,0000,0000,0000,,So let's put a new array up\Nhere and this time let's make
Dialogue: 0,0:36:59.39,0:37:01.62,Default,,0000,0000,0000,,it--it doesn't have to be odd.\NSo let's make it this time a
Dialogue: 0,0:37:01.62,0:37:08.08,Default,,0000,0000,0000,,little bit more complicated.\NSo we'll have five--let's have
Dialogue: 0,0:37:08.08,0:37:15.19,Default,,0000,0000,0000,,four rows and five columns this\Ntime.
Dialogue: 0,0:37:15.19,0:37:21.40,Default,,0000,0000,0000,,Okay so last time I had five\Nrows and three columns,
Dialogue: 0,0:37:21.40,0:37:27.50,Default,,0000,0000,0000,,and this time I have four rows\Nand five columns.
Dialogue: 0,0:37:27.50,0:37:30.34,Default,,0000,0000,0000,,Away you go,\Nlet me move out of the way.
Dialogue: 0,0:37:30.34,0:37:32.06,Default,,0000,0000,0000,,Why don't you stand a bit\Nnearer to the board--make it a
Dialogue: 0,0:37:32.06,0:37:33.53,Default,,0000,0000,0000,,little easier for people to see\Nwhat's going on,
Dialogue: 0,0:37:33.53,0:37:36.30,Default,,0000,0000,0000,,there you go.\NSo Peter you want to go first?
Dialogue: 0,0:37:36.30,0:37:39.18,Default,,0000,0000,0000,,Student: Sure, that one.\NProfessor Ben Polak:
Dialogue: 0,0:37:39.18,0:37:41.81,Default,,0000,0000,0000,,That one okay.\NSo this one goes,
Dialogue: 0,0:37:41.81,0:37:46.94,Default,,0000,0000,0000,,which means all of these go as\Nwell.
Dialogue: 0,0:37:46.94,0:37:48.32,Default,,0000,0000,0000,,Anyone got any advice from the\Nfloor?
Dialogue: 0,0:37:48.32,0:37:50.52,Default,,0000,0000,0000,,Shout things out, not too loud.
Dialogue: 0,0:37:50.52,0:37:54.01,Default,,0000,0000,0000,,
Dialogue: 0,0:37:54.01,0:37:55.11,Default,,0000,0000,0000,,Student: I'll try going\Nhere.
Dialogue: 0,0:37:55.11,0:37:55.55,Default,,0000,0000,0000,,Professor Ben Polak:\NThere.
Dialogue: 0,0:37:55.55,0:38:10.44,Default,,0000,0000,0000,,Okay we're back to our L shape\Nagain here.
Dialogue: 0,0:38:10.44,0:38:15.26,Default,,0000,0000,0000,,Now people can see what's going\Non all right.
Dialogue: 0,0:38:15.26,0:38:16.58,Default,,0000,0000,0000,,Student: I'll go here\Nand speed it up.
Dialogue: 0,0:38:16.58,0:38:18.59,Default,,0000,0000,0000,,Professor Ben Polak: All\Nright thank you.
Dialogue: 0,0:38:18.59,0:38:26.00,Default,,0000,0000,0000,,So a round of applause again.\NThank you guys.
Dialogue: 0,0:38:26.00,0:38:27.64,Default,,0000,0000,0000,,So here's what I claim about\Nthis game.
Dialogue: 0,0:38:27.64,0:38:30.62,Default,,0000,0000,0000,,First, and this isn't a formal\Nclaim, this is a lot harder than
Dialogue: 0,0:38:30.62,0:38:32.44,Default,,0000,0000,0000,,the game we played last time,\Nright?
Dialogue: 0,0:38:32.44,0:38:34.45,Default,,0000,0000,0000,,Everyone is convinced by that\Nall right.
Dialogue: 0,0:38:34.45,0:38:37.78,Default,,0000,0000,0000,,So here's going to be an\Nexercise, or something that's a
Dialogue: 0,0:38:37.78,0:38:40.17,Default,,0000,0000,0000,,challenge.\NI may even put it formally on
Dialogue: 0,0:38:40.17,0:38:43.44,Default,,0000,0000,0000,,the problem set this week,\Nbut let me just say if I do put
Dialogue: 0,0:38:43.44,0:38:45.56,Default,,0000,0000,0000,,this on the problem set this\Nweek,
Dialogue: 0,0:38:45.56,0:38:47.57,Default,,0000,0000,0000,,I don't expect you all to solve\Nit.
Dialogue: 0,0:38:47.57,0:38:49.75,Default,,0000,0000,0000,,So if I do put it on the\Nproblem set, it's an optional
Dialogue: 0,0:38:49.75,0:38:53.51,Default,,0000,0000,0000,,problem.\NBut here's the challenge,
Dialogue: 0,0:38:53.51,0:38:59.68,Default,,0000,0000,0000,,the challenge is,\NI know from Zermelo's theorem
Dialogue: 0,0:38:59.68,0:39:06.26,Default,,0000,0000,0000,,that no matter what N is,\Nand no matter what M is,
Dialogue: 0,0:39:06.26,0:39:16.23,Default,,0000,0000,0000,,this game has a solution.\NSo Zermelo's theorem tells us
Dialogue: 0,0:39:16.23,0:39:22.81,Default,,0000,0000,0000,,this game has a solution.\NNow, notice it could have a
Dialogue: 0,0:39:22.81,0:39:24.98,Default,,0000,0000,0000,,different solution depending on\Nthe N and the M,
Dialogue: 0,0:39:24.98,0:39:27.15,Default,,0000,0000,0000,,depending on how many rows and\Nhow many columns,
Dialogue: 0,0:39:27.15,0:39:31.42,Default,,0000,0000,0000,,is that right?.\NSo depending on N and M,
Dialogue: 0,0:39:31.42,0:39:38.39,Default,,0000,0000,0000,,each such game has a\Nsolution--is that right--which
Dialogue: 0,0:39:38.39,0:39:45.65,Default,,0000,0000,0000,,could depend on N and on M,\Non the number of rows and
Dialogue: 0,0:39:45.65,0:39:48.91,Default,,0000,0000,0000,,columns.\NSo just as in Nim,
Dialogue: 0,0:39:48.91,0:39:52.47,Default,,0000,0000,0000,,it depended on how those piles\Nstarted out.
Dialogue: 0,0:39:52.47,0:39:55.44,Default,,0000,0000,0000,,So what's going to be the\Nhomework assignment?
Dialogue: 0,0:39:55.44,0:40:13.75,Default,,0000,0000,0000,,Find the solution.\NHomework- what is the solution?
Dialogue: 0,0:40:13.75,0:40:19.61,Default,,0000,0000,0000,,So I claim, let me give you a\Nhint, I claim it is useful to
Dialogue: 0,0:40:19.61,0:40:23.25,Default,,0000,0000,0000,,remember that there is a\Nsolution.
Dialogue: 0,0:40:23.25,0:40:24.56,Default,,0000,0000,0000,,It turns out to be useful to\Nremember that.
Dialogue: 0,0:40:24.56,0:40:26.45,Default,,0000,0000,0000,,That wasn't much of a hint.\NYou knew that already,
Dialogue: 0,0:40:26.45,0:40:30.89,Default,,0000,0000,0000,,but let me just emphasize that.\NOkay, so I want to do a bit of
Dialogue: 0,0:40:30.89,0:40:35.89,Default,,0000,0000,0000,,a transition now away from these\Ngames like chess and like
Dialogue: 0,0:40:35.89,0:40:38.45,Default,,0000,0000,0000,,checkers,\Nand like this game with the
Dialogue: 0,0:40:38.45,0:40:40.79,Default,,0000,0000,0000,,rocks or Nim,\Nand I want to be a little bit
Dialogue: 0,0:40:40.79,0:40:43.33,Default,,0000,0000,0000,,formal for a while.\NSo one thing that we haven't
Dialogue: 0,0:40:43.33,0:40:45.44,Default,,0000,0000,0000,,done for a while,\Nactually since the mid-term,
Dialogue: 0,0:40:45.44,0:40:47.37,Default,,0000,0000,0000,,is write down some formal\Ndefinitions.
Dialogue: 0,0:40:47.37,0:40:52.65,Default,,0000,0000,0000,,So I'm going to do that now.\NI want at least one of these
Dialogue: 0,0:40:52.65,0:40:52.98,Default,,0000,0000,0000,,boards back.
Dialogue: 0,0:40:52.98,0:41:16.37,Default,,0000,0000,0000,,
Dialogue: 0,0:41:16.37,0:41:19.71,Default,,0000,0000,0000,,So as I warned very early in\Nthe class, there are some points
Dialogue: 0,0:41:19.71,0:41:23.06,Default,,0000,0000,0000,,of the day when we have to stop\Nand do some work and the next
Dialogue: 0,0:41:23.06,0:41:25.34,Default,,0000,0000,0000,,twenty minutes or so is such a\Npoint.
Dialogue: 0,0:41:25.34,0:41:41.66,Default,,0000,0000,0000,,
Dialogue: 0,0:41:41.66,0:41:48.51,Default,,0000,0000,0000,,So what is this?\NThis is formal stuff.
Dialogue: 0,0:41:48.51,0:41:51.67,Default,,0000,0000,0000,,The first thing I want to do is\NI want to give you a formal
Dialogue: 0,0:41:51.67,0:41:54.67,Default,,0000,0000,0000,,definition of something I've\Nalready mentioned today and
Dialogue: 0,0:41:54.67,0:41:57.01,Default,,0000,0000,0000,,that's the idea of perfect\Ninformation.
Dialogue: 0,0:41:57.01,0:42:00.32,Default,,0000,0000,0000,,What we've been looking at,\Nor at least since the mid-term,
Dialogue: 0,0:42:00.32,0:42:02.32,Default,,0000,0000,0000,,are games of perfect\Ninformation.
Dialogue: 0,0:42:02.32,0:42:20.10,Default,,0000,0000,0000,,So a game of perfect\Ninformation is one in which at
Dialogue: 0,0:42:20.10,0:42:41.44,Default,,0000,0000,0000,,every node, or at each node in\Nthe game the player whose turn
Dialogue: 0,0:42:41.44,0:43:02.07,Default,,0000,0000,0000,,it is to move at that node knows\Nwhich node she is at.
Dialogue: 0,0:43:02.07,0:43:04.70,Default,,0000,0000,0000,,So it's a very simple idea.\NEvery game we've seen since the
Dialogue: 0,0:43:04.70,0:43:08.05,Default,,0000,0000,0000,,mid-term has this property.\NWhen you're playing this game
Dialogue: 0,0:43:08.05,0:43:13.62,Default,,0000,0000,0000,,you know where you are.\NSo you know which node you're
Dialogue: 0,0:43:13.62,0:43:21.16,Default,,0000,0000,0000,,at, you know what your choices\Nare and what that means
Dialogue: 0,0:43:21.16,0:43:27.32,Default,,0000,0000,0000,,implicitly is she must know how\Nshe got there.
Dialogue: 0,0:43:27.32,0:43:30.22,Default,,0000,0000,0000,,So the whole history of the\Ngame is observed by everybody.
Dialogue: 0,0:43:30.22,0:43:32.83,Default,,0000,0000,0000,,When I get to move I know what\Nyou did yesterday,
Dialogue: 0,0:43:32.83,0:43:35.28,Default,,0000,0000,0000,,I know what I did the day\Nbefore yesterday,
Dialogue: 0,0:43:35.28,0:43:38.47,Default,,0000,0000,0000,,and if I'm playing with a third\Nperson I know what they did the
Dialogue: 0,0:43:38.47,0:43:41.82,Default,,0000,0000,0000,,day before that.\NSo a very simple idea but it
Dialogue: 0,0:43:41.82,0:43:46.99,Default,,0000,0000,0000,,turns out to be an idea that\Nactually allows us to use things
Dialogue: 0,0:43:46.99,0:43:50.36,Default,,0000,0000,0000,,like backward induction very\Nsimply.
Dialogue: 0,0:43:50.36,0:43:54.02,Default,,0000,0000,0000,,Now so far all we've been doing\Nis thinking about such games,
Dialogue: 0,0:43:54.02,0:43:57.40,Default,,0000,0000,0000,,games like perfect competition,\Nsorry games like quantity
Dialogue: 0,0:43:57.40,0:44:00.49,Default,,0000,0000,0000,,competition between firms or\Ngames like the games where we
Dialogue: 0,0:44:00.49,0:44:03.10,Default,,0000,0000,0000,,were setting up incentives or\Ngames like Nim,
Dialogue: 0,0:44:03.10,0:44:05.83,Default,,0000,0000,0000,,and we've basically been\Nsolving these games by backward
Dialogue: 0,0:44:05.83,0:44:09.12,Default,,0000,0000,0000,,induction, rather informally.\NWhat I want to add in now is
Dialogue: 0,0:44:09.12,0:44:11.68,Default,,0000,0000,0000,,the notion of a strategy in\Nthese games.
Dialogue: 0,0:44:11.68,0:44:14.57,Default,,0000,0000,0000,,So when we had simultaneous\Nmove games, strategies were
Dialogue: 0,0:44:14.57,0:44:17.33,Default,,0000,0000,0000,,really unproblematic.\NIt was obvious what strategies
Dialogue: 0,0:44:17.33,0:44:19.44,Default,,0000,0000,0000,,were.\NBut when we have games which
Dialogue: 0,0:44:19.44,0:44:22.14,Default,,0000,0000,0000,,are sequential,\Nthat go on over a period of
Dialogue: 0,0:44:22.14,0:44:24.44,Default,,0000,0000,0000,,time,\Nand information is emerging
Dialogue: 0,0:44:24.44,0:44:27.86,Default,,0000,0000,0000,,over a period of time,\Nwe need to be a little careful
Dialogue: 0,0:44:27.86,0:44:31.88,Default,,0000,0000,0000,,what we mean by a strategy.\NSo what I want to do is I want
Dialogue: 0,0:44:31.88,0:44:35.08,Default,,0000,0000,0000,,to define a pure strategy at\Nleast as follows.
Dialogue: 0,0:44:35.08,0:44:47.22,Default,,0000,0000,0000,,So a pure strategy for Player i\Nin a game of perfect
Dialogue: 0,0:44:47.22,0:45:00.56,Default,,0000,0000,0000,,information--so in the games\Nwe've been talking about,
Dialogue: 0,0:45:00.56,0:45:03.81,Default,,0000,0000,0000,,games which we can represent by\Ntrees is what?
Dialogue: 0,0:45:03.81,0:45:25.54,Default,,0000,0000,0000,,It's a complete plan of action.\NSo in other words,
Dialogue: 0,0:45:25.54,0:45:35.02,Default,,0000,0000,0000,,what it does is it specifies\Nwhich action I should
Dialogue: 0,0:45:35.02,0:45:46.04,Default,,0000,0000,0000,,take--let's not make it should\Ntake--let's say will
Dialogue: 0,0:45:46.04,0:45:52.61,Default,,0000,0000,0000,,take,\Nat each of i's nodes,
Dialogue: 0,0:45:52.61,0:46:00.11,Default,,0000,0000,0000,,each of i's decision nodes.\NSo when you first read this
Dialogue: 0,0:46:00.11,0:46:03.25,Default,,0000,0000,0000,,definition it seems completely\Nuninteresting and unproblematic.
Dialogue: 0,0:46:03.25,0:46:07.05,Default,,0000,0000,0000,,A pure strategy for Player i\Njust tells you in this game
Dialogue: 0,0:46:07.05,0:46:09.89,Default,,0000,0000,0000,,whenever you might be called\Nupon to move,
Dialogue: 0,0:46:09.89,0:46:12.79,Default,,0000,0000,0000,,it tells you how you're going\Nto move.
Dialogue: 0,0:46:12.79,0:46:14.63,Default,,0000,0000,0000,,So if you're going to move\Nthree times in the game,
Dialogue: 0,0:46:14.63,0:46:16.66,Default,,0000,0000,0000,,it tells you how you're going\Nto move the first time;
Dialogue: 0,0:46:16.66,0:46:18.45,Default,,0000,0000,0000,,it tells you how you're going\Nto move the second time;
Dialogue: 0,0:46:18.45,0:46:23.82,Default,,0000,0000,0000,,and it tells you how you're\Ngoing to move the third time.
Dialogue: 0,0:46:23.82,0:46:27.21,Default,,0000,0000,0000,,So, so far none of this seems\Ndifficult but actually it's a
Dialogue: 0,0:46:27.21,0:46:29.26,Default,,0000,0000,0000,,bit more difficult than it\Nlooks.
Dialogue: 0,0:46:29.26,0:46:29.66,Default,,0000,0000,0000,,So let's have a look.
Dialogue: 0,0:46:29.66,0:46:41.51,Default,,0000,0000,0000,,
Dialogue: 0,0:46:41.51,0:46:44.10,Default,,0000,0000,0000,,What I want to do is I want to\Nlook at an example,
Dialogue: 0,0:46:44.10,0:46:46.96,Default,,0000,0000,0000,,and this example I'm hoping is\Ngoing to illustrate some
Dialogue: 0,0:46:46.96,0:46:48.92,Default,,0000,0000,0000,,subtleties about this\Ndefinition.
Dialogue: 0,0:46:48.92,0:46:57.33,Default,,0000,0000,0000,,
Dialogue: 0,0:46:57.33,0:46:57.90,Default,,0000,0000,0000,,So here's an example.
Dialogue: 0,0:46:57.90,0:47:04.05,Default,,0000,0000,0000,,
Dialogue: 0,0:47:04.05,0:47:08.32,Default,,0000,0000,0000,,In this example Player 1 moves\Nfirst and they can choose in or
Dialogue: 0,0:47:08.32,0:47:12.53,Default,,0000,0000,0000,,out, or if you like let's call\Nit up or down since that's the
Dialogue: 0,0:47:12.53,0:47:16.63,Default,,0000,0000,0000,,way we've drawn it.\NSo they can choose down or
Dialogue: 0,0:47:16.63,0:47:20.66,Default,,0000,0000,0000,,up--and I'll use capital letters\NU and D.
Dialogue: 0,0:47:20.66,0:47:29.28,Default,,0000,0000,0000,,If Player chooses U then Player\N2 gets to move and Player 2 can
Dialogue: 0,0:47:29.28,0:47:34.18,Default,,0000,0000,0000,,choose L or R.\NIf Player 1 moves U followed by
Dialogue: 0,0:47:34.18,0:47:38.40,Default,,0000,0000,0000,,Player 2 choosing L,\Nthen Player 1 gets to move,
Dialogue: 0,0:47:38.40,0:47:41.19,Default,,0000,0000,0000,,in which case Player 1 could\Nmove up or down and I'll use
Dialogue: 0,0:47:41.19,0:47:45.48,Default,,0000,0000,0000,,little letters this time,\Nu and d.
Dialogue: 0,0:47:45.48,0:47:48.25,Default,,0000,0000,0000,,Let's put some payoffs in this\Ngame.
Dialogue: 0,0:47:48.25,0:48:00.74,Default,,0000,0000,0000,,So the payoffs are 1,0 here,\N0,2 here, 3,1 here and 2,4
Dialogue: 0,0:48:00.74,0:48:03.63,Default,,0000,0000,0000,,here.\NSo on paper--it's on the
Dialogue: 0,0:48:03.63,0:48:06.75,Default,,0000,0000,0000,,board--when you first look at\Nit, this is a perfectly simple
Dialogue: 0,0:48:06.75,0:48:07.98,Default,,0000,0000,0000,,game.\NIt's just like many of the
Dialogue: 0,0:48:07.98,0:48:09.47,Default,,0000,0000,0000,,games we've been looking at\Nsince the mid-term.
Dialogue: 0,0:48:09.47,0:48:12.29,Default,,0000,0000,0000,,It has a tree.\NWe could analyze it by backward
Dialogue: 0,0:48:12.29,0:48:15.18,Default,,0000,0000,0000,,induction, and in a moment we\Nwill analyze it by backward
Dialogue: 0,0:48:15.18,0:48:18.00,Default,,0000,0000,0000,,induction.\NBut what I want to do first is
Dialogue: 0,0:48:18.00,0:48:21.74,Default,,0000,0000,0000,,I want to say what are the\Nstrategies in this game?
Dialogue: 0,0:48:21.74,0:48:27.45,Default,,0000,0000,0000,,So let's start with Player 2\Nsince it's easier.
Dialogue: 0,0:48:27.45,0:48:34.63,Default,,0000,0000,0000,,Player 2's strategies here are\Nwhat?
Dialogue: 0,0:48:34.63,0:48:37.91,Default,,0000,0000,0000,,Pretty simple:\Nplayer 2 only has one decision
Dialogue: 0,0:48:37.91,0:48:42.46,Default,,0000,0000,0000,,node--here's Player 2's decision\Nnode--and the strategy has to
Dialogue: 0,0:48:42.46,0:48:47.09,Default,,0000,0000,0000,,tell Player 2 what he's going to\Ndo at that decision node.
Dialogue: 0,0:48:47.09,0:48:49.47,Default,,0000,0000,0000,,So there's only two choices,\NL or R.
Dialogue: 0,0:48:49.47,0:48:57.34,Default,,0000,0000,0000,,So Player 2's strategies are\Neither L or R.
Dialogue: 0,0:48:57.34,0:49:00.47,Default,,0000,0000,0000,,Notice, however,\Nalready one slight subtlety
Dialogue: 0,0:49:00.47,0:49:05.07,Default,,0000,0000,0000,,here.\NPlayer 2 may never get to make
Dialogue: 0,0:49:05.07,0:49:08.56,Default,,0000,0000,0000,,this choice.\NSo Player 2 is choosing L or R,
Dialogue: 0,0:49:08.56,0:49:11.39,Default,,0000,0000,0000,,but Player 2 may not ever get\Nto make this choice.
Dialogue: 0,0:49:11.39,0:49:14.30,Default,,0000,0000,0000,,In particular,\Nif 1 chose D it's really
Dialogue: 0,0:49:14.30,0:49:17.97,Default,,0000,0000,0000,,irrelevant whether Player 2 has\Nchosen L or R.
Dialogue: 0,0:49:17.97,0:49:21.95,Default,,0000,0000,0000,,Nevertheless,\Nthe strategy has to specify
Dialogue: 0,0:49:21.95,0:49:28.23,Default,,0000,0000,0000,,what Player 2 would do were he\Ncalled upon to make that move.
Dialogue: 0,0:49:28.23,0:49:29.27,Default,,0000,0000,0000,,Now let's look at Player 1's\Nstrategies.
Dialogue: 0,0:49:29.27,0:49:37.58,Default,,0000,0000,0000,,
Dialogue: 0,0:49:37.58,0:49:45.33,Default,,0000,0000,0000,,So what are Player 1's\Nstrategies in this game?
Dialogue: 0,0:49:45.33,0:49:54.30,Default,,0000,0000,0000,,Any takers?\NAnyone want to guess?
Dialogue: 0,0:49:54.30,0:49:59.21,Default,,0000,0000,0000,,So I claim it's tempting,\Nbut it turns out to be wrong,
Dialogue: 0,0:49:59.21,0:50:03.67,Default,,0000,0000,0000,,to say that Player 1 has three\Nstrategies here.
Dialogue: 0,0:50:03.67,0:50:08.82,Default,,0000,0000,0000,,It's tempting to say either\NPlayer 1 moves D,
Dialogue: 0,0:50:08.82,0:50:14.44,Default,,0000,0000,0000,,in which case we're done,\Nor Player 1 moves U,
Dialogue: 0,0:50:14.44,0:50:19.63,Default,,0000,0000,0000,,in which case at some later\Ndate she may be called upon to
Dialogue: 0,0:50:19.63,0:50:23.47,Default,,0000,0000,0000,,choose u or d again.\NSo it's very tempting to think
Dialogue: 0,0:50:23.47,0:50:26.28,Default,,0000,0000,0000,,that Player 1 has just three\Nstrategies here,
Dialogue: 0,0:50:26.28,0:50:34.31,Default,,0000,0000,0000,,D in which case we're done,\Nor U followed by either u or d,
Dialogue: 0,0:50:34.31,0:50:39.44,Default,,0000,0000,0000,,if she's reached that point.\NBut actually,
Dialogue: 0,0:50:39.44,0:50:43.90,Default,,0000,0000,0000,,if we follow this definition\Ncarefully, we notice that Player
Dialogue: 0,0:50:43.90,0:50:46.80,Default,,0000,0000,0000,,1 actually has four strategies\Nhere.
Dialogue: 0,0:50:46.80,0:50:49.90,Default,,0000,0000,0000,,So let me say what they are and\Nyou'll see why it's a little
Dialogue: 0,0:50:49.90,0:50:52.16,Default,,0000,0000,0000,,odd.\NSo here's one of the strategies
Dialogue: 0,0:50:52.16,0:50:54.17,Default,,0000,0000,0000,,we talked about,\NU followed by u,
Dialogue: 0,0:50:54.17,0:50:56.81,Default,,0000,0000,0000,,and here's another one we\Ntalked about,
Dialogue: 0,0:50:56.81,0:51:03.96,Default,,0000,0000,0000,,U followed by d,\Nbut I claim there are two
Dialogue: 0,0:51:03.96,0:51:11.99,Default,,0000,0000,0000,,others, D followed by u and D\Nfollowed by d.
Dialogue: 0,0:51:11.99,0:51:13.77,Default,,0000,0000,0000,,So what's a little weird about\Nthis?
Dialogue: 0,0:51:13.77,0:51:18.25,Default,,0000,0000,0000,,What's weird is we know\Nperfectly well that if Player 1
Dialogue: 0,0:51:18.25,0:51:22.48,Default,,0000,0000,0000,,chooses D she's not going to get\Nto make the choice,
Dialogue: 0,0:51:22.48,0:51:27.28,Default,,0000,0000,0000,,the second choice u or d.\NBut nevertheless the strategy
Dialogue: 0,0:51:27.28,0:51:31.08,Default,,0000,0000,0000,,has to tell us what she would do\Nat every node,
Dialogue: 0,0:51:31.08,0:51:35.88,Default,,0000,0000,0000,,regardless of whether that node\Nactually is reached by that
Dialogue: 0,0:51:35.88,0:51:38.64,Default,,0000,0000,0000,,strategy.\NLet me say it again,
Dialogue: 0,0:51:38.64,0:51:43.27,Default,,0000,0000,0000,,the strategy has to tell you\Nwhat Player 1 would do at that
Dialogue: 0,0:51:43.27,0:51:46.54,Default,,0000,0000,0000,,node,\Nregardless of whether that node
Dialogue: 0,0:51:46.54,0:51:50.45,Default,,0000,0000,0000,,is actually reached by playing\Nthat strategy.
Dialogue: 0,0:51:50.45,0:51:54.59,Default,,0000,0000,0000,,So a little weird.\NThere's a bit of redundancy
Dialogue: 0,0:51:54.59,0:52:02.03,Default,,0000,0000,0000,,here.\NIt's a bit redundant.
Dialogue: 0,0:52:02.03,0:52:05.44,Default,,0000,0000,0000,,Now why?\NWell we'll see why in a second.
Dialogue: 0,0:52:05.44,0:52:09.95,Default,,0000,0000,0000,,Let's first of all consider how\Nthis game will be played
Dialogue: 0,0:52:09.95,0:52:13.90,Default,,0000,0000,0000,,according to backward induction.\NSo how do we play this game
Dialogue: 0,0:52:13.90,0:52:18.65,Default,,0000,0000,0000,,according to backward induction?\NWhere do we start?
Dialogue: 0,0:52:18.65,0:52:21.99,Default,,0000,0000,0000,,Shouldn't be a trick question,\Nwhere do we start the game
Dialogue: 0,0:52:21.99,0:52:25.05,Default,,0000,0000,0000,,according to backward induction?\NAt the end okay.
Dialogue: 0,0:52:25.05,0:52:32.01,Default,,0000,0000,0000,,So the end here is Player 1 and\NPlayer 1 will choose here to go
Dialogue: 0,0:52:32.01,0:52:36.64,Default,,0000,0000,0000,,d, is that right?\NBecause 3 is bigger than 2.
Dialogue: 0,0:52:36.64,0:52:40.90,Default,,0000,0000,0000,,So if we roll back to Player\N2's move, Player 2 if she
Dialogue: 0,0:52:40.90,0:52:46.21,Default,,0000,0000,0000,,chooses L she knows that she'll\Nbe followed by Player 1 going d,
Dialogue: 0,0:52:46.21,0:52:51.78,Default,,0000,0000,0000,,in which case she'll get 1,\Nbut if she chooses R she'll get
Dialogue: 0,0:52:51.78,0:52:56.10,Default,,0000,0000,0000,,2.\NSo Player 2 will choose R.
Dialogue: 0,0:52:56.10,0:53:01.40,Default,,0000,0000,0000,,So Player 1 here,\Nif she chooses U then Player 2
Dialogue: 0,0:53:01.40,0:53:07.93,Default,,0000,0000,0000,,will choose R and Player 1 will\Nget 0, and if she chooses D
Dialogue: 0,0:53:07.93,0:53:12.89,Default,,0000,0000,0000,,she'll get 1,\Nso Player 1 will choose D.
Dialogue: 0,0:53:12.89,0:53:18.79,Default,,0000,0000,0000,,So, backward induction suggests\Nthat Player 1 will choose D;
Dialogue: 0,0:53:18.79,0:53:22.36,Default,,0000,0000,0000,,and followed by Player 2--if\NPlayer 2 did get to move--she'd
Dialogue: 0,0:53:22.36,0:53:25.36,Default,,0000,0000,0000,,choose R;\Nfollowed by Player 1--if she
Dialogue: 0,0:53:25.36,0:53:28.78,Default,,0000,0000,0000,,did get to move again--choosing\Nd again.
Dialogue: 0,0:53:28.78,0:53:35.09,Default,,0000,0000,0000,,Notice that backward induction\Nhad to tell us what Player 2
Dialogue: 0,0:53:35.09,0:53:39.22,Default,,0000,0000,0000,,would have done had she got to\Nmove.
Dialogue: 0,0:53:39.22,0:53:43.34,Default,,0000,0000,0000,,Backward induction had to\Nconsider what Player 2 would
Dialogue: 0,0:53:43.34,0:53:47.84,Default,,0000,0000,0000,,think that Player 1 would have\Ndone were Player 1 to get to
Dialogue: 0,0:53:47.84,0:53:51.37,Default,,0000,0000,0000,,move again.\NSo to do backward induction,
Dialogue: 0,0:53:51.37,0:53:56.27,Default,,0000,0000,0000,,Player 1 has to ask herself\Nwhat Player 2 is going to do;
Dialogue: 0,0:53:56.27,0:54:00.10,Default,,0000,0000,0000,,and Player 2 has to therefore\Nask herself what Player 1 would
Dialogue: 0,0:54:00.10,0:54:02.14,Default,,0000,0000,0000,,have done;\Nwhich means Player 1 has to ask
Dialogue: 0,0:54:02.14,0:54:04.40,Default,,0000,0000,0000,,herself what Player 2 thinks\NPlayer 1 would have done;
Dialogue: 0,0:54:04.40,0:54:09.26,Default,,0000,0000,0000,,which means we actually needed\Nto say what Player 1 did over
Dialogue: 0,0:54:09.26,0:54:10.88,Default,,0000,0000,0000,,here.\NLet me say that again.
Dialogue: 0,0:54:10.88,0:54:13.88,Default,,0000,0000,0000,,So backward induction here\Ntells us that Player 1 chooses D
Dialogue: 0,0:54:13.88,0:54:17.62,Default,,0000,0000,0000,,in which case the game is over.\NBut to do backward induction,
Dialogue: 0,0:54:17.62,0:54:21.48,Default,,0000,0000,0000,,to think through backward\Ninduction, we really needed to
Dialogue: 0,0:54:21.48,0:54:25.76,Default,,0000,0000,0000,,consider not just what Player 2\Nwas going to do were he to get
Dialogue: 0,0:54:25.76,0:54:28.76,Default,,0000,0000,0000,,to move,\Nbut also what Player 2 would
Dialogue: 0,0:54:28.76,0:54:33.23,Default,,0000,0000,0000,,think Player 1 would do were\NPlayer 2 to get to move and were
Dialogue: 0,0:54:33.23,0:54:37.23,Default,,0000,0000,0000,,to do choose L.\NSo all of these redundant moves
Dialogue: 0,0:54:37.23,0:54:41.18,Default,,0000,0000,0000,,were actually part of our\Nbackward induction.
Dialogue: 0,0:54:41.18,0:54:45.67,Default,,0000,0000,0000,,We need them there so we can\Nthink about what people are
Dialogue: 0,0:54:45.67,0:54:49.24,Default,,0000,0000,0000,,thinking.\NSo backward induction tells us
Dialogue: 0,0:54:49.24,0:54:54.40,Default,,0000,0000,0000,,that the outcome of the game is\ND, but it tells in terms of
Dialogue: 0,0:54:54.40,0:54:57.37,Default,,0000,0000,0000,,strategies,\NPlayer 1 chooses D and,
Dialogue: 0,0:54:57.37,0:55:01.34,Default,,0000,0000,0000,,were she to get to move again,\Nwould choose D again.
Dialogue: 0,0:55:01.34,0:55:12.34,Default,,0000,0000,0000,,And Player 2 chooses R.\NNow let's analyze this game a
Dialogue: 0,0:55:12.34,0:55:16.27,Default,,0000,0000,0000,,totally different way.\NWe now know what the strategies
Dialogue: 0,0:55:16.27,0:55:19.20,Default,,0000,0000,0000,,are in the game:\NPlayer 2 has two strategies,
Dialogue: 0,0:55:19.20,0:55:23.76,Default,,0000,0000,0000,,L and R;\Nand Player 1 has four
Dialogue: 0,0:55:23.76,0:55:30.14,Default,,0000,0000,0000,,strategies: U/u,\NU/d, D/u and D/d.
Dialogue: 0,0:55:30.14,0:55:35.60,Default,,0000,0000,0000,,So let's write up the matrix\Nfor this game,
Dialogue: 0,0:55:35.60,0:55:40.94,Default,,0000,0000,0000,,so here it is.\NIt must be a 4 x 2 matrix,
Dialogue: 0,0:55:40.94,0:55:48.46,Default,,0000,0000,0000,,Player 2 is choosing between L\Nand R and Player 1 is choosing
Dialogue: 0,0:55:48.46,0:55:58.08,Default,,0000,0000,0000,,between her four strategies Uu,\NUd, Du and Dd and we can put
Dialogue: 0,0:55:58.08,0:56:07.03,Default,,0000,0000,0000,,all the payoffs in.\NSo (Uu,L) gets us here which is
Dialogue: 0,0:56:07.03,0:56:15.56,Default,,0000,0000,0000,,(2,4).\N(Uu,R) gets us here which is
Dialogue: 0,0:56:15.56,0:56:23.67,Default,,0000,0000,0000,,(0,2).\N(Ud,L) gets us here which is
Dialogue: 0,0:56:23.67,0:56:29.75,Default,,0000,0000,0000,,(3,1).\N(Ud,R) gets us here again which
Dialogue: 0,0:56:29.75,0:56:32.56,Default,,0000,0000,0000,,is (0,2).\NAnd Du gets us,
Dialogue: 0,0:56:32.56,0:56:37.71,Default,,0000,0000,0000,,going right out of the game\Nimmediately, so we're going to
Dialogue: 0,0:56:37.71,0:56:42.32,Default,,0000,0000,0000,,go to (1,0).\NAnd in fact that's also true
Dialogue: 0,0:56:42.32,0:56:49.17,Default,,0000,0000,0000,,for (Du,R), and it's also true\Nfor (Dd,L) and it's also true
Dialogue: 0,0:56:49.17,0:56:52.71,Default,,0000,0000,0000,,for (D/d,R).\NSo all of these four strategies
Dialogue: 0,0:56:52.71,0:56:55.49,Default,,0000,0000,0000,,at the bottom started off by\NPlayer 1 choosing D,
Dialogue: 0,0:56:55.49,0:56:59.17,Default,,0000,0000,0000,,in which case the game is over.\NSo once again in this matrix
Dialogue: 0,0:56:59.17,0:57:02.60,Default,,0000,0000,0000,,you can kind of see the\Nredundancy I was talking about.
Dialogue: 0,0:57:02.60,0:57:06.28,Default,,0000,0000,0000,,In this matrix,\Nthe third row,
Dialogue: 0,0:57:06.28,0:57:11.62,Default,,0000,0000,0000,,the Du row looks the same as\Nthe Dd row.
Dialogue: 0,0:57:11.62,0:57:17.92,Default,,0000,0000,0000,,Everyone happy with that?\NSo when we've had matrices in
Dialogue: 0,0:57:17.92,0:57:20.80,Default,,0000,0000,0000,,the past how have we solved the\Ngame?
Dialogue: 0,0:57:20.80,0:57:22.100,Default,,0000,0000,0000,,Well we've been doing this\Nbackward induction stuff for a
Dialogue: 0,0:57:22.100,0:57:23.90,Default,,0000,0000,0000,,couple of weeks,\Nbut,
Dialogue: 0,0:57:23.90,0:57:27.94,Default,,0000,0000,0000,,prior to the mid-term--if I had\Ngiven you this on the mid-term
Dialogue: 0,0:57:27.94,0:57:31.45,Default,,0000,0000,0000,,what would you have done?\NYou'd look for a Nash
Dialogue: 0,0:57:31.45,0:57:33.97,Default,,0000,0000,0000,,Equilibrium right?\NSo let's do that:
Dialogue: 0,0:57:33.97,0:57:35.83,Default,,0000,0000,0000,,let's look for Nash\NEquilibrium.
Dialogue: 0,0:57:35.83,0:57:45.73,Default,,0000,0000,0000,,So if Player 2 chooses L then\NPlayer 1's best response is Uu;
Dialogue: 0,0:57:45.73,0:57:53.17,Default,,0000,0000,0000,,and if Player 2 chooses R,\Nthen Player 1's best response
Dialogue: 0,0:57:53.17,0:57:58.87,Default,,0000,0000,0000,,is either Du or Dd.\NConversely, if Player 1 chooses
Dialogue: 0,0:57:58.87,0:58:02.47,Default,,0000,0000,0000,,Uu then Player 2's best response\Nis L.
Dialogue: 0,0:58:02.47,0:58:09.47,Default,,0000,0000,0000,,If Player 1 chooses Ud then\NPlayer 2's best response is R.
Dialogue: 0,0:58:09.47,0:58:13.94,Default,,0000,0000,0000,,If Player 1 chooses Du then\NPlayer 2 doesn't care because
Dialogue: 0,0:58:13.94,0:58:19.43,Default,,0000,0000,0000,,they're getting 0 anyway;\Nand if Player 1 chooses Dd then
Dialogue: 0,0:58:19.43,0:58:25.02,Default,,0000,0000,0000,,again Player 2 doesn't care\Nbecause they're getting 0
Dialogue: 0,0:58:25.02,0:58:28.43,Default,,0000,0000,0000,,anyway.\NSo the Nash Equilibria in this
Dialogue: 0,0:58:28.43,0:58:33.59,Default,,0000,0000,0000,,game are what?\NSo one of them is here,
Dialogue: 0,0:58:33.59,0:58:44.07,Default,,0000,0000,0000,,so that's one Nash Equilibrium.\NOne of them is Dd followed by
Dialogue: 0,0:58:44.07,0:58:54.42,Default,,0000,0000,0000,,R, and that's a Nash Equilibrium\Nwe actually found by backward
Dialogue: 0,0:58:54.42,0:58:59.80,Default,,0000,0000,0000,,induction.\NThe Nash Equilibrium (Dd,R)
Dialogue: 0,0:58:59.80,0:59:06.26,Default,,0000,0000,0000,,corresponds to the one we found\Nby backward induction.
Dialogue: 0,0:59:06.26,0:59:08.97,Default,,0000,0000,0000,,But there's another Nash\NEquilibrium in this game.
Dialogue: 0,0:59:08.97,0:59:14.68,Default,,0000,0000,0000,,The other Nash Equilibrium in\Nthis game is this one.
Dialogue: 0,0:59:14.68,0:59:17.54,Default,,0000,0000,0000,,That's also a Nash Equilibrium.\NWhat does it involve?
Dialogue: 0,0:59:17.54,0:59:35.98,Default,,0000,0000,0000,,It involves Du and R--sorry Du\Nand R.
Dialogue: 0,0:59:35.98,0:59:38.23,Default,,0000,0000,0000,,So what happened in that\Nequilibrium?
Dialogue: 0,0:59:38.23,0:59:41.45,Default,,0000,0000,0000,,Player 1 went down which made\Neverything else kind of
Dialogue: 0,0:59:41.45,0:59:45.72,Default,,0000,0000,0000,,irrelevant.\NPlayer 2 played R and Player 1
Dialogue: 0,0:59:45.72,0:59:52.19,Default,,0000,0000,0000,,in their plan of action was\Nactually going to choose u.
Dialogue: 0,0:59:52.19,0:59:55.60,Default,,0000,0000,0000,,Say it again,\NPlayer 1 in fact went D,
Dialogue: 0,0:59:55.60,1:00:01.23,Default,,0000,0000,0000,,Player 2 had they got to move\Nwould have chosen R and Player 1
Dialogue: 0,1:00:01.23,1:00:07.22,Default,,0000,0000,0000,,had they got to move at this\Nsecond time would have chosen u.
Dialogue: 0,1:00:07.22,1:00:08.66,Default,,0000,0000,0000,,So how can that be a Nash\NEquilibrium?
Dialogue: 0,1:00:08.66,1:00:11.14,Default,,0000,0000,0000,,It doesn't correspond to\Nbackward induction.
Dialogue: 0,1:00:11.14,1:00:15.63,Default,,0000,0000,0000,,In particular,\NPlayer 1 up here is choosing a
Dialogue: 0,1:00:15.63,1:00:21.14,Default,,0000,0000,0000,,strategy that seems silly.\NThey're choosing u rather than
Dialogue: 0,1:00:21.14,1:00:24.24,Default,,0000,0000,0000,,d which gets them 2 rather than\N3.
Dialogue: 0,1:00:24.24,1:00:28.02,Default,,0000,0000,0000,,So how could it possibly be\Nthat that's an equilibrium
Dialogue: 0,1:00:28.02,1:00:30.32,Default,,0000,0000,0000,,strategy?\NThe reason is--the reason it
Dialogue: 0,1:00:30.32,1:00:33.69,Default,,0000,0000,0000,,can be an equilibrium strategy\Nis it doesn't really matter what
Dialogue: 0,1:00:33.69,1:00:37.01,Default,,0000,0000,0000,,Player 1 chooses up here from\NPlayer 1's point of view because
Dialogue: 0,1:00:37.01,1:00:39.35,Default,,0000,0000,0000,,it's never going to be reached\Nanyway.
Dialogue: 0,1:00:39.35,1:00:43.44,Default,,0000,0000,0000,,As long as Player 2 is going to\Nchoose R here,
Dialogue: 0,1:00:43.44,1:00:49.27,Default,,0000,0000,0000,,it really doesn't matter what\NPlayer 1 decides to do up there.
Dialogue: 0,1:00:49.27,1:00:51.23,Default,,0000,0000,0000,,From Player 1's point of view,\Nit doesn't make a difference.
Dialogue: 0,1:00:51.23,1:00:56.94,Default,,0000,0000,0000,,It isn't reached anyway.\NSo we're highlighting here a
Dialogue: 0,1:00:56.94,1:01:01.82,Default,,0000,0000,0000,,danger, and the danger is this.\NIf you just mechanically find
Dialogue: 0,1:01:01.82,1:01:06.62,Default,,0000,0000,0000,,the Nash Equilibria in a game,\Nyou're going to find people
Dialogue: 0,1:01:06.62,1:01:12.04,Default,,0000,0000,0000,,choosing actions that,\Nif they ever were called upon
Dialogue: 0,1:01:12.04,1:01:14.91,Default,,0000,0000,0000,,to make them,\Nare silly.
Dialogue: 0,1:01:14.91,1:01:17.06,Default,,0000,0000,0000,,Say it again,\Nif you just mechanically find
Dialogue: 0,1:01:17.06,1:01:19.97,Default,,0000,0000,0000,,the Nash Equilibria in the game,\Njust as we did here,
Dialogue: 0,1:01:19.97,1:01:23.35,Default,,0000,0000,0000,,you're going to select some\Nactions, in this case an action
Dialogue: 0,1:01:23.35,1:01:26.15,Default,,0000,0000,0000,,by Player 1,\Nthat were she called upon to
Dialogue: 0,1:01:26.15,1:01:29.03,Default,,0000,0000,0000,,take that action would be a\Nsilly action.
Dialogue: 0,1:01:29.03,1:01:33.99,Default,,0000,0000,0000,,The reason it's surviving our\Nanalysis is because in fact she
Dialogue: 0,1:01:33.99,1:01:38.51,Default,,0000,0000,0000,,isn't called upon to make it.\NNow to make that more concrete,
Dialogue: 0,1:01:38.51,1:01:42.04,Default,,0000,0000,0000,,let's take this to an economic\Nexample, this same idea.
Dialogue: 0,1:01:42.04,1:01:57.15,Default,,0000,0000,0000,,
Dialogue: 0,1:01:57.15,1:02:02.22,Default,,0000,0000,0000,,So what I want you to imagine\Nis a market, and in this market
Dialogue: 0,1:02:02.22,1:02:06.28,Default,,0000,0000,0000,,there is a monopolist who\Ncontrols the market,
Dialogue: 0,1:02:06.28,1:02:10.88,Default,,0000,0000,0000,,but there's an entrant who is\Nthinking of entering into this
Dialogue: 0,1:02:10.88,1:02:14.21,Default,,0000,0000,0000,,market.\NSo right now this market has a
Dialogue: 0,1:02:14.21,1:02:17.62,Default,,0000,0000,0000,,monopoly in it,\Nand the monopolist is an
Dialogue: 0,1:02:17.62,1:02:22.08,Default,,0000,0000,0000,,incumbent--let's call him\NInc--and an entrant who is
Dialogue: 0,1:02:22.08,1:02:27.43,Default,,0000,0000,0000,,trying to decide whether or not\Nto enter the market or whether
Dialogue: 0,1:02:27.43,1:02:31.11,Default,,0000,0000,0000,,to stay out.\NIf they stay out then the
Dialogue: 0,1:02:31.11,1:02:35.47,Default,,0000,0000,0000,,entrant gets nothing and the\Nincumbent continues to get
Dialogue: 0,1:02:35.47,1:02:40.63,Default,,0000,0000,0000,,monopoly profits.\NSo think of this as 3 million a
Dialogue: 0,1:02:40.63,1:02:43.59,Default,,0000,0000,0000,,year.\NIf the entrant enters then the
Dialogue: 0,1:02:43.59,1:02:46.32,Default,,0000,0000,0000,,incumbent can do one of two\Nthings.
Dialogue: 0,1:02:46.32,1:02:49.42,Default,,0000,0000,0000,,The incumbent could choose to\Nfight the entrant,
Dialogue: 0,1:02:49.42,1:02:52.71,Default,,0000,0000,0000,,by which I mean charge low\Nprices, advertise a lot,
Dialogue: 0,1:02:52.71,1:02:55.35,Default,,0000,0000,0000,,try and drive him out of the\Nmarket.
Dialogue: 0,1:02:55.35,1:02:58.25,Default,,0000,0000,0000,,He could play very\Ncompetitively,
Dialogue: 0,1:02:58.25,1:03:02.88,Default,,0000,0000,0000,,in which case the entrant will\Nactually make losses,
Dialogue: 0,1:03:02.88,1:03:08.14,Default,,0000,0000,0000,,and the incumbent will drive\Nher profits down to zero.
Dialogue: 0,1:03:08.14,1:03:13.16,Default,,0000,0000,0000,,Conversely, the incumbent could\Nchoose not to fight.
Dialogue: 0,1:03:13.16,1:03:17.16,Default,,0000,0000,0000,,If they don't fight then\Nthey'll simply share the market
Dialogue: 0,1:03:17.16,1:03:20.79,Default,,0000,0000,0000,,and they'll both make,\Nlet's say Cournot profits or
Dialogue: 0,1:03:20.79,1:03:23.55,Default,,0000,0000,0000,,duopoly profits of a million\Neach.
Dialogue: 0,1:03:23.55,1:03:25.64,Default,,0000,0000,0000,,So in this game,\Nlet's just say again,
Dialogue: 0,1:03:25.64,1:03:29.02,Default,,0000,0000,0000,,there's a market there.\NThe monopolist is in the market
Dialogue: 0,1:03:29.02,1:03:32.56,Default,,0000,0000,0000,,and the monopolist is making 3\Nmillion a year which seems
Dialogue: 0,1:03:32.56,1:03:36.57,Default,,0000,0000,0000,,pretty nice for the monopolist.\NThe entrant is trying to decide
Dialogue: 0,1:03:36.57,1:03:40.44,Default,,0000,0000,0000,,whether to invade this market.\NIf she invades this market,
Dialogue: 0,1:03:40.44,1:03:44.47,Default,,0000,0000,0000,,if she's fought she's in\Ntrouble, but if the monopolist
Dialogue: 0,1:03:44.47,1:03:47.96,Default,,0000,0000,0000,,accommodates her,\Nthen they just go to duopoly
Dialogue: 0,1:03:47.96,1:03:51.73,Default,,0000,0000,0000,,profits and the entrant does\Nvery well, gets a million
Dialogue: 0,1:03:51.73,1:03:55.13,Default,,0000,0000,0000,,dollars in profit.\NLet's have a look at this game.
Dialogue: 0,1:03:55.13,1:03:58.98,Default,,0000,0000,0000,,Analyze--first of all this\Ntime, let's analyze it by Nash
Dialogue: 0,1:03:58.98,1:04:02.11,Default,,0000,0000,0000,,Equilibrium.\NSo I claim in this game,
Dialogue: 0,1:04:02.11,1:04:07.09,Default,,0000,0000,0000,,this is pretty simple:\Nthe entrant has two strategies.
Dialogue: 0,1:04:07.09,1:04:08.89,Default,,0000,0000,0000,,I'll put it straight into the\Nmatrix.
Dialogue: 0,1:04:08.89,1:04:19.17,Default,,0000,0000,0000,,The entrant has two strategies,\Nthey're either to go in or to
Dialogue: 0,1:04:19.17,1:04:24.39,Default,,0000,0000,0000,,stay out;\Nand the incumbent has two
Dialogue: 0,1:04:24.39,1:04:32.01,Default,,0000,0000,0000,,strategies, they are either to\Nfight the entrant or not to
Dialogue: 0,1:04:32.01,1:04:34.59,Default,,0000,0000,0000,,fight.\NThe payoffs of this game are as
Dialogue: 0,1:04:34.59,1:04:38.54,Default,,0000,0000,0000,,follows--let's put them in.\NIn and fight was (-1,0),
Dialogue: 0,1:04:38.54,1:04:44.74,Default,,0000,0000,0000,,in and not fight was (1,1) and\Nout led to the incumbents
Dialogue: 0,1:04:44.74,1:04:48.80,Default,,0000,0000,0000,,maintaining the monopoly\Nprofits.
Dialogue: 0,1:04:48.80,1:04:52.55,Default,,0000,0000,0000,,Let's have a look at the Nash\NEquilibria of this game.
Dialogue: 0,1:04:52.55,1:04:56.23,Default,,0000,0000,0000,,So the first thing to do is to\Nlook at the best responses for
Dialogue: 0,1:04:56.23,1:04:59.64,Default,,0000,0000,0000,,the entrant.\NSo if the incumbent chooses
Dialogue: 0,1:04:59.64,1:05:04.92,Default,,0000,0000,0000,,fight, then the entrant's best\Nresponse is to stay out.
Dialogue: 0,1:05:04.92,1:05:11.23,Default,,0000,0000,0000,,If the incumbent chooses not\Nfight, then the entrant's best
Dialogue: 0,1:05:11.23,1:05:15.52,Default,,0000,0000,0000,,response is to enter.\NHow about for the incumbent?
Dialogue: 0,1:05:15.52,1:05:20.18,Default,,0000,0000,0000,,If the entrant chooses to come\Nin then the incumbent's best
Dialogue: 0,1:05:20.18,1:05:24.52,Default,,0000,0000,0000,,response is not to fight because\N1 is bigger than 0.
Dialogue: 0,1:05:24.52,1:05:30.08,Default,,0000,0000,0000,,But if the entrant stays out it\Nreally doesn't matter what the
Dialogue: 0,1:05:30.08,1:05:34.00,Default,,0000,0000,0000,,incumbent does,\Nthey'll get 3 either way.
Dialogue: 0,1:05:34.00,1:05:42.19,Default,,0000,0000,0000,,So the Nash Equilibria here are\Neither in followed by not
Dialogue: 0,1:05:42.19,1:05:50.09,Default,,0000,0000,0000,,fighting, you end up with a\Nduopoly, or out followed by
Dialogue: 0,1:05:50.09,1:05:54.57,Default,,0000,0000,0000,,fighting.\NOf course the fight doesn't
Dialogue: 0,1:05:54.57,1:05:59.93,Default,,0000,0000,0000,,take place: out followed by "we\Nwould have fought had you
Dialogue: 0,1:05:59.93,1:06:02.08,Default,,0000,0000,0000,,entered."\NSo these are the Nash
Dialogue: 0,1:06:02.08,1:06:04.78,Default,,0000,0000,0000,,Equilibria.\NLet's analyze this game by
Dialogue: 0,1:06:04.78,1:06:08.96,Default,,0000,0000,0000,,backward induction.\NFrom the incumbent's point of
Dialogue: 0,1:06:08.96,1:06:14.41,Default,,0000,0000,0000,,view, if the incumbent gets to\Nmove then is she going to choose
Dialogue: 0,1:06:14.41,1:06:19.34,Default,,0000,0000,0000,,fight or not fight?\NShe's going to choose not
Dialogue: 0,1:06:19.34,1:06:23.90,Default,,0000,0000,0000,,fight, so the entrant should do\Nwhat?
Dialogue: 0,1:06:23.90,1:06:25.95,Default,,0000,0000,0000,,Somebody?\NThe entrant should enter,
Dialogue: 0,1:06:25.95,1:06:28.81,Default,,0000,0000,0000,,because if she enters she gets\N1, if she stays out she gets 0.
Dialogue: 0,1:06:28.81,1:06:41.66,Default,,0000,0000,0000,,So backward induction just\Ngives us this equilibrium.
Dialogue: 0,1:06:41.66,1:06:44.85,Default,,0000,0000,0000,,Now the question is what do we\Nthink is going on with this
Dialogue: 0,1:06:44.85,1:06:48.42,Default,,0000,0000,0000,,other equilibrium?\NLet's talk it through.
Dialogue: 0,1:06:48.42,1:06:50.41,Default,,0000,0000,0000,,So here you are,\Nyou're about to enter the
Dialogue: 0,1:06:50.41,1:06:52.88,Default,,0000,0000,0000,,market, you leave Yale,\Nyou set up your business,
Dialogue: 0,1:06:52.88,1:06:56.22,Default,,0000,0000,0000,,and your business is\Nchallenging some monopolist or
Dialogue: 0,1:06:56.22,1:06:58.82,Default,,0000,0000,0000,,quasi-monopolist like Microsoft\Nsay.,
Dialogue: 0,1:06:58.82,1:07:01.58,Default,,0000,0000,0000,,And you go out there and you're\Nabout to put out your new
Dialogue: 0,1:07:01.58,1:07:04.38,Default,,0000,0000,0000,,operating system.\NAnd you know that your new
Dialogue: 0,1:07:04.38,1:07:07.98,Default,,0000,0000,0000,,operating system will make\Nplenty of money provided
Dialogue: 0,1:07:07.98,1:07:12.15,Default,,0000,0000,0000,,Microsoft doesn't retaliate and\Ndrop its prices by half and
Dialogue: 0,1:07:12.15,1:07:16.19,Default,,0000,0000,0000,,advertise you out of the market.\NSo what does Bill Gates do?
Dialogue: 0,1:07:16.19,1:07:17.68,Default,,0000,0000,0000,,Bill Gates is the head of\NMicrosoft.
Dialogue: 0,1:07:17.68,1:07:21.57,Default,,0000,0000,0000,,He says, wait a second before\Nyou graduate from Yale and go
Dialogue: 0,1:07:21.57,1:07:24.93,Default,,0000,0000,0000,,set up this company,\Nlet me just tell you I'm going
Dialogue: 0,1:07:24.93,1:07:30.15,Default,,0000,0000,0000,,to fight.\NIf you enter I'm going to fight.
Dialogue: 0,1:07:30.15,1:07:34.22,Default,,0000,0000,0000,,And if you believe him,\Nif you believe that he's going
Dialogue: 0,1:07:34.22,1:07:37.41,Default,,0000,0000,0000,,to fight, what should you do?\NYou're not going to bother to
Dialogue: 0,1:07:37.41,1:07:39.41,Default,,0000,0000,0000,,enter his market.\NAnd if you believe that you're
Dialogue: 0,1:07:39.41,1:07:42.25,Default,,0000,0000,0000,,going to get fought by Bill\NGates then you believe that if
Dialogue: 0,1:07:42.25,1:07:44.30,Default,,0000,0000,0000,,you enter you're going to make\Nlosses,
Dialogue: 0,1:07:44.30,1:07:49.77,Default,,0000,0000,0000,,so you choose to stay out.\NAnd this threat that Bill Gates
Dialogue: 0,1:07:49.77,1:07:55.02,Default,,0000,0000,0000,,makes here it doesn't cost him\Nanything, provided you go out,
Dialogue: 0,1:07:55.02,1:07:58.87,Default,,0000,0000,0000,,he doesn't actually have to\Nfight at all.
Dialogue: 0,1:07:58.87,1:08:02.37,Default,,0000,0000,0000,,That's why it is in fact an\Nequilibrium to imagine you
Dialogue: 0,1:08:02.37,1:08:06.00,Default,,0000,0000,0000,,staying out believing that\Nyou're going to get fought if
Dialogue: 0,1:08:06.00,1:08:08.98,Default,,0000,0000,0000,,you enter,\Nand it is a best response for
Dialogue: 0,1:08:08.98,1:08:12.94,Default,,0000,0000,0000,,the guy to fight knowing that\Nyou're going to stay out.
Dialogue: 0,1:08:12.94,1:08:17.12,Default,,0000,0000,0000,,But this doesn't sound right.\NWhy doesn't this sound right?
Dialogue: 0,1:08:17.12,1:08:21.40,Default,,0000,0000,0000,,It doesn't sound right because\Nyou really shouldn't believe the
Dialogue: 0,1:08:21.40,1:08:25.62,Default,,0000,0000,0000,,guy who says he's going to fight\Nyou when you know that if you
Dialogue: 0,1:08:25.62,1:08:29.35,Default,,0000,0000,0000,,did enter fighting would cost\Nthe incumbent money.
Dialogue: 0,1:08:29.35,1:08:32.98,Default,,0000,0000,0000,,If you did enter,\Nif he fights you he gets 0,
Dialogue: 0,1:08:32.98,1:08:36.94,Default,,0000,0000,0000,,if he doesn't fight he gets a\Nmillion dollars.
Dialogue: 0,1:08:36.94,1:08:41.80,Default,,0000,0000,0000,,So this threat that the guy is\Ngoing to fight you,
Dialogue: 0,1:08:41.80,1:08:51.08,Default,,0000,0000,0000,,this threat is not credible.\NThis is an equilibrium but it
Dialogue: 0,1:08:51.08,1:09:00.20,Default,,0000,0000,0000,,relies on believing an\Nincredible threat.
Dialogue: 0,1:09:00.20,1:09:10.53,Default,,0000,0000,0000,,
Dialogue: 0,1:09:10.53,1:09:13.58,Default,,0000,0000,0000,,It's true that if you think\Nabout entering the market that
Dialogue: 0,1:09:13.58,1:09:15.88,Default,,0000,0000,0000,,Microsoft is in,\Nyou're very likely to get a
Dialogue: 0,1:09:15.88,1:09:18.100,Default,,0000,0000,0000,,little email from Bill Gates.\N(But it won't be an email
Dialogue: 0,1:09:18.100,1:09:21.69,Default,,0000,0000,0000,,because that can be taken to\NCourt, but some little
Dialogue: 0,1:09:21.69,1:09:24.93,Default,,0000,0000,0000,,threatening remark in your ear\Nfrom Bill Gates.) It's true if
Dialogue: 0,1:09:24.93,1:09:28.22,Default,,0000,0000,0000,,you entered into the market that\Nthe people who build aircraft
Dialogue: 0,1:09:28.22,1:09:30.58,Default,,0000,0000,0000,,in,\Nthe head of Boeing might pay
Dialogue: 0,1:09:30.58,1:09:33.18,Default,,0000,0000,0000,,you a call one day or send\Nsomeone round,
Dialogue: 0,1:09:33.18,1:09:36.18,Default,,0000,0000,0000,,but these threats are not\Ncredible threats.
Dialogue: 0,1:09:36.18,1:09:38.60,Default,,0000,0000,0000,,Is that right?\NThey're not credible threats
Dialogue: 0,1:09:38.60,1:09:42.58,Default,,0000,0000,0000,,because we know that if you did\Nenter, it isn't in their
Dialogue: 0,1:09:42.58,1:09:46.19,Default,,0000,0000,0000,,interest to fight.\NThey're making a lot of noise
Dialogue: 0,1:09:46.19,1:09:49.28,Default,,0000,0000,0000,,about it but you know that if\Nyou did enter,
Dialogue: 0,1:09:49.28,1:09:53.46,Default,,0000,0000,0000,,backward induction tells us\Nthey're not going to fight.
Dialogue: 0,1:09:53.46,1:09:57.11,Default,,0000,0000,0000,,But now we're in slightly an\Nodd situation,
Dialogue: 0,1:09:57.11,1:10:01.01,Default,,0000,0000,0000,,why are we in an odd situation?\NTwo things.
Dialogue: 0,1:10:01.01,1:10:06.64,Default,,0000,0000,0000,,One, we seem to be finding that\Nthere are Nash Equilibria in
Dialogue: 0,1:10:06.64,1:10:11.88,Default,,0000,0000,0000,,games--we found one here and one\Nup here--there are Nash
Dialogue: 0,1:10:11.88,1:10:17.60,Default,,0000,0000,0000,,Equilibria that are not\Nsupported by backward induction.
Dialogue: 0,1:10:17.60,1:10:21.46,Default,,0000,0000,0000,,That's the first reason we're a\Nlittle worried here,
Dialogue: 0,1:10:21.46,1:10:25.94,Default,,0000,0000,0000,,and the second reason we're\Nworried is even the economics of
Dialogue: 0,1:10:25.94,1:10:29.47,Default,,0000,0000,0000,,this doesn't quite smell right.\NFor example,
Dialogue: 0,1:10:29.47,1:10:31.73,Default,,0000,0000,0000,,if you in fact did\Nenter--sorry,
Dialogue: 0,1:10:31.73,1:10:35.89,Default,,0000,0000,0000,,if you did in fact announce you\Nwere going to operate,
Dialogue: 0,1:10:35.89,1:10:38.92,Default,,0000,0000,0000,,you were going to build a new\Noperating system and got a
Dialogue: 0,1:10:38.92,1:10:42.34,Default,,0000,0000,0000,,threatening phone call from Bill\NGates--there might be a reason
Dialogue: 0,1:10:42.34,1:10:44.82,Default,,0000,0000,0000,,why you might actually believe\Nthat call.
Dialogue: 0,1:10:44.82,1:10:52.83,Default,,0000,0000,0000,,Why might you believe that call?\NCan we get a mike out,
Dialogue: 0,1:10:52.83,1:10:56.00,Default,,0000,0000,0000,,I'll do it.\NSo why might you believe a call
Dialogue: 0,1:10:56.00,1:10:59.30,Default,,0000,0000,0000,,from Bill Gates saying he's\Ngoing to beat you up--not beat
Dialogue: 0,1:10:59.30,1:11:02.71,Default,,0000,0000,0000,,you up but he's going to charge\Nlow prices if you produce an
Dialogue: 0,1:11:02.71,1:11:05.34,Default,,0000,0000,0000,,operating system?\NStudent: If you look at
Dialogue: 0,1:11:05.34,1:11:07.96,Default,,0000,0000,0000,,the future revenue streams,\Nlike for the next ten years and
Dialogue: 0,1:11:07.96,1:11:10.90,Default,,0000,0000,0000,,he consistently gets 1 million\Ndollars for the next ten years,
Dialogue: 0,1:11:10.90,1:11:13.72,Default,,0000,0000,0000,,he would be better off if he\Njust drove you out of the market
Dialogue: 0,1:11:13.72,1:11:16.58,Default,,0000,0000,0000,,for the first year and then get\N3 million dollars for the next
Dialogue: 0,1:11:16.58,1:11:17.81,Default,,0000,0000,0000,,nine years.\NProfessor Ben Polak:
Dialogue: 0,1:11:17.81,1:11:18.69,Default,,0000,0000,0000,,That wasn't quite what I wasn't\Nthinking of.
Dialogue: 0,1:11:18.69,1:11:22.25,Default,,0000,0000,0000,,Okay, it's true if we cheat a\Nbit and make one of the--Okay,
Dialogue: 0,1:11:22.25,1:11:25.51,Default,,0000,0000,0000,,so what you're saying is I\Ncould get 3 forever versus 1
Dialogue: 0,1:11:25.51,1:11:27.64,Default,,0000,0000,0000,,forever,\Nassume these are both present
Dialogue: 0,1:11:27.64,1:11:29.73,Default,,0000,0000,0000,,discounted values of future cash\Nearnings.
Dialogue: 0,1:11:29.73,1:11:33.57,Default,,0000,0000,0000,,So we've done the future cash\Nflow analysis of this.
Dialogue: 0,1:11:33.57,1:11:37.40,Default,,0000,0000,0000,,So this isn't an accounting\Nmistake, not for accounting
Dialogue: 0,1:11:37.40,1:11:40.00,Default,,0000,0000,0000,,reasons.\NThere's some other reason when
Dialogue: 0,1:11:40.00,1:11:43.22,Default,,0000,0000,0000,,Gates threatens you,\Nyou might want to believe it.
Dialogue: 0,1:11:43.22,1:11:45.84,Default,,0000,0000,0000,,Let's try up here first.\NStudent: He can afford
Dialogue: 0,1:11:45.84,1:11:48.24,Default,,0000,0000,0000,,to make an example of you so no\Nother people will invade.
Dialogue: 0,1:11:48.24,1:11:50.78,Default,,0000,0000,0000,,Professor Ben Polak:\NRight, so one thing that's in
Dialogue: 0,1:11:50.78,1:11:54.55,Default,,0000,0000,0000,,Bill Gates' mind is right now,\Nhe's thinking about competing
Dialogue: 0,1:11:54.55,1:11:59.00,Default,,0000,0000,0000,,with you but down the road\Nthere's a lot more of you guys
Dialogue: 0,1:11:59.00,1:12:02.51,Default,,0000,0000,0000,,coming--whatever it is,\N280 of you in this room and
Dialogue: 0,1:12:02.51,1:12:05.28,Default,,0000,0000,0000,,there's another 280 in next\Nyear's class and so on.
Dialogue: 0,1:12:05.28,1:12:08.68,Default,,0000,0000,0000,,And Bill Gates knows that each\Nof you might come out and
Dialogue: 0,1:12:08.68,1:12:11.65,Default,,0000,0000,0000,,threaten his monopoly,\Nhis Microsoft monopoly.
Dialogue: 0,1:12:11.65,1:12:15.54,Default,,0000,0000,0000,,And he might think that by\Nsetting an example to one of you
Dialogue: 0,1:12:15.54,1:12:18.36,Default,,0000,0000,0000,,he might be able to keep the\Nothers out.
Dialogue: 0,1:12:18.36,1:12:22.81,Default,,0000,0000,0000,,And somewhere that kind of\Nargument, the argument of making
Dialogue: 0,1:12:22.81,1:12:25.73,Default,,0000,0000,0000,,an example of somebody is\Nmissing here:
Dialogue: 0,1:12:25.73,1:12:29.50,Default,,0000,0000,0000,,missing completely.\NBut it's got to be important,
Dialogue: 0,1:12:29.50,1:12:31.84,Default,,0000,0000,0000,,it's got to be an important\Nidea.
Dialogue: 0,1:12:31.84,1:12:35.35,Default,,0000,0000,0000,,So we're going to come back and\Nspend the first half of
Dialogue: 0,1:12:35.35,1:12:39.00,Default,,0000,0000,0000,,Wednesday's class picking up\Njust precisely that idea.
Dialogue: 0,1:12:39.00,9:59:59.99,Default,,0000,0000,0000,,