耶鲁大学博弈论公开课 - 第8集 落后的感应-国际象棋，战略和可信的威胁

视频全文转录（中英双语）

以下为完整中英双语转录，已加标点。英文在前，中文在后，逐段对照。

由 Groq Whisper 转录 → M2.7 B 方案整文标点 + 分段 → M2.7 段号保留翻译 → 逐段对照。

[段 1]

So last time we finished up by playing the game of NIMH. And you’ll remember, I hope, that the game of NIMH was a game where there was two piles of stones. We made do with lines on the board. And the winner was the person who picked up the last stone. Remember, you have to pick piles. And I want to use the game of NIMH to make a transition here. So what we pointed out about the game of NIMH game was it illustrated very nicely for us that games can have first mover advantages or they can have second mover advantages. A very small change in the game, essentially a very small change in where we started from could switch a game from a game with a first mover advantage to a game with a second mover advantage. Alright? Now today I want to make, just draw a slightly grander lesson out of that game. So not only was it the case that the game sometimes has first mover advantages and sometimes has second mover advantages. But moreover, we could tell when it had a first mover advantage and we could tell when it had a second mover advantage. Is that right? When we actually looked at the initial setup of those stones we knew immediately that a game in which player 1 is going to win or alternatively we knew immediately that a game in which player 2 is going to win Alright?

[译文 1]

上一次我们玩了尼姆（NIM）游戏。希望你们还记得，尼姆游戏是一种有两个石堆的游戏。我们用棋盘上的线条来代替石子。胜利者是捡起最后一颗石子的人。记住，你必须选择石堆。我想用尼姆游戏在这里做一个过渡。我们之前指出，尼姆游戏很好地说明了一个问题：游戏可能具有先手优势，也可能具有后手优势。游戏的一个非常小的变化，本质上是一个非常小的起始位置的变化，就能把一个具有先手优势的游戏变成一个具有后手优势的游戏。好的？现在我想从这个游戏中得出一个稍微宏大一点的教训。也就是说，不仅仅是在某些情况下游戏具有先手优势，在某些情况下具有后手优势，而且我们能够判断什么时候它具有先手优势，什么时候它具有后手优势。真的吗？当我们实际观察这些石子的初始设置时，我们立即就能知道一个游戏玩家一会赢，或者说我们立即就能知道一个游戏玩家二会赢。好的？

[段 2]

Now it turns out that that idea is very general, and actually has a name attached to it, and that name is Zemillo. So today we’ll start off by talking about a theorem due to a guy called Zermelo and the idea of this theorem is this we’re going to look at games more general than just NIM and we’re going to ask the question under what circumstances would you know about a game either that player 1, the person who goes first can force a win or that player 2 can force a win or will allow a third possibility which is it’s going to be a tie. All right? So here’s the theorem. Suppose there are two players in this game, like the games we looked at last time, and suppose, I won’t define this formally now, but suppose the game is a game of perfect information. So what I mean by perfect information, I’ll define this later on in the class, but for now all I mean is that whenever a player has his turn to move that player knows exactly what has happened prior in the game So for example all these sequential move games we been looking at are moves of perfect information. When I get to move, I know exactly what you did yesterday, I know what I did the day before yesterday, and so on.

[译文 2]

现在结果表明这个想法非常通用，实际上有一个名字与之相关，这个名字就是泽莫洛。所以今天我们首先来讨论一个由一个叫泽莫洛的人提出的定理，这个定理的想法是这样的：我们将研究比尼姆更一般的游戏，我们会问在什么情况下你会知道一个游戏的结果，即第一个玩家先走的人能够强制获胜，或者第二个玩家能够强制获胜，或者允许第三种可能性，那就是这将是一场平局。好的？这里有一个定理。假设这个游戏有两个玩家，就像我们上次看的游戏一样，假设我不会在这里正式定义，但假设这个游戏是一个完美信息的游戏。我所说的完美信息是什么意思，我以后在课堂上会定义，但现在我的意思是每当一个玩家轮到他们移动时，那个玩家完全知道之前在游戏中发生了什么。例如，我们一直在看的所有这些顺序移动游戏都是完美信息的移动。当我轮到移动时，我完全知道你昨天做了什么，我知道我前天做了什么，等等。

[段 3]

Alright, so it’s a game of perfect information. I’m going to assume that the game has a finite number of nodes. So, two things here. It can’t go on forever, this game, and also there’s no point at which it branches in an infinite way. All right, so there’s a finite number of nodes. And we’ll assume that the game has three possible outcomes. And actually there’s a more general version of this theorem, but this will do for now. The three possible outcomes are either a win for player one, so I’ll call it W sub 1, or a loss for player one, which is obviously a win for player two, or a tie. So the game, like NEM last time, we only had two outcomes, so here we’re going to go up to three outcomes, or three or fewer outcomes, I should say. So these are the conditions, and here’s the result. So I said three it could be three but it could also be two here I just allowing for 3 1 is true All right So under these conditions the following is true Either player 1 can force a win. So either it’s the case that this game is a game that if player 1 plays as well as they can, they’re going to win the game. All right?

[译文 3]

好的，所以这是一个完美信息的游戏。我假设游戏有有限数量的节点。所以，这里有两件事。它不能永远持续下去，这个游戏，而且也没有一个点会以无限的方式分支。好的，所以有有限数量的节点。我们假设游戏有三种可能的结果。实际上这个定理有一个更通用的版本，但这对我们现在来说已经足够了。三种可能的结果要么是玩家一赢，我称之为W1，要么是玩家一输，这显然是玩家二赢，要么是平局。所以这个游戏，就像上次一样，我们只有两个结果，所以这里我们要上升到三个结果，或者三个或更少的结果，我应该说。所以这些是条件，这里是结果。所以我说三个它可能是三个但它也可能是两个我只是允许3 1是真的好的在这些条件下以下是真的要么玩家一可以强制获胜。所以要么这个情况是这个游戏是一个如果玩家一尽可能发挥得好他们就会赢得游戏。

[段 4]

No matter what player 2 does. or two sorry or one can at least force a tie alright which means player one can play in such a way that they can assure themselves of a tie regardless of what player two does or it could be a game in which two can force a loss on one so win for one alright so this theorem when you first look at it it doesn’t seem to say very much when you’re staring at this thing you might think we already knew that we’re looking at games that only have three possible outcomes, win loss or tie alright, so it doesn’t seem so surprising We already knew that we’re looking at games that only have three possible outcomes, win, loss, or tie. So it doesn’t seem so surprising if you look at this theorem. It says whether you’re going to end up with a win or a loss or a tie. But that’s not quite what the theorem says. The theorem says not only are you going to end up there, we knew that already, but games of this form divide themselves into those games in which player one has a way of winning regardless of what player two does. right or games which player one has a way of forcing a tie regardless of what player one does player two does or player two has a way of winning regardless of what player one does.

[译文 4]

不管玩家二做什么。或者两个抱歉或者一至少可以强制平局好的这意味着玩家一可以以这样一种方式玩他们可以确保自己获得平局无论玩家二做什么或者它可能是一个其中二可以强制一输的游戏所以一赢好的所以这个定理当你第一次看它时它似乎没有说很多当你盯着这个东西时你可能认为我们已经知道了我们正在看的游戏只有三种可能的结果赢输或平局好的所以它似乎不那么令人惊讶我们已经知道了我们正在看的游戏只有三种可能的结果赢输或平局所以它似乎不那么令人惊讶如果你看这个定理它说你最终会得到赢输或平局但这不是定理所说的全部定理说的不仅仅是你会到达那里我们已经知道了但这种形式的游戏分为那些玩家一有一种方式的游戏无论玩家二做什么都能获胜。

或者玩家一有一种方式的游戏可以强制平局无论玩家一做什么玩家二做什么或者玩家二有一种方式的游戏无论玩家一做什么都能为玩家二获胜。

[段 5]

These games all have a solution let’s go back to NIM to illustrate the point alright so in NIM actually there’s no tie so we can forget the middle of these and in NIM under certain circumstances it is the case that player one can force a win. Who remembers what the case was for when player one can force a win. Anybody? People who played last time? No? Yes? Ali there somebody here Yeah shout it out Ensuring that the piles are equal for the other player All right so if the piles start unequal if the piles start unequal, then player one can actually force a win. So in NIM, in NIM, if the piles are unequal at the start, then one can force a win. it really doesn’t matter what 2 does, 2 is toast. All right? Or the alternative case is the piles are equal at the start, and if they’re equal at the start, then it’s player 1 who’s toast. Right? Player 2 is going to force a loss on 1. So 2 can force a loss on 1, i.e. a win for player 2. All right? Right? Does everyone remember that from last time? Yeah? It’s just before the weekend, shouldn’t be so far long ago. All right? So this theorem applies to all games of this form. So what games are of this form?

[译文 5]

这些游戏都有一个解。让我们回到尼姆来说明这一点。好的，所以在尼姆中实际上没有平局所以我们可以忘记这些中间的情况在尼姆中在某些情况下玩家一可以强制获胜。谁记得玩家一可以强制获胜的情况是什么？有人吗？上次玩过的人？没有？是的？阿里在那里有人喊出来确保石堆对其他玩家相等。好的所以如果石堆开始时不相等如果石堆开始时不相等那么玩家一实际上可以强制获胜。所以在尼姆中在尼姆中如果石堆在开始时不相等那么一可以强制获胜。

真的不管二做什么二是输定了。好的？或者另一种情况是石堆在开始时相等，如果它们在开始时相等，那么玩家一就输定了。玩家二将强制玩家一输。也就是说玩家二获胜。好的？你们每个人都记得上次的事吧？是的？就在周末之前，不应该离得太远。好的？所以这个定理适用于所有这种形式的游戏。那么什么游戏是这种形式的呢？

[段 6]

Let’s think of some other examples. So one example is tic All right Everyone know the rules of tic In England we call it noughts and crosses but you guys call it tic is that right Everyone know what tic is Yeah So in tic which category is tic Is it a game in which player one can force a win, or is it a category in which player one can only force a tie, or is it a category in which you’d rather go second, and player two can force a win for player two, or a loss for player one? Which is tic-tac-toe? Let’s have a show of hands here. Who thinks tic-tac-toe is a game in which player one can force a win? Who thinks Tic-Tac-Toe is a game which player one can only force a tie? And who thinks player two is going to win? Most of you are right. It’s a game in which if people play correctly, then it’ll turn out to be a tie. So Tic-Tac-Toe is a game that leads to a tie. Player one can still make a mistake, in which case they can lose. Player two can make a mistake, in which case they would lose. but there is a way of playing that forces a tie. All right? So these are fairly simple games. Let’s talk about more complicated games.

[译文 6]

让我们想想其他一些例子。一个例子是井字游戏。好的，大家都知道井字游戏的规则。在英国我们叫它 noughts and crosses，但你们叫它井字游戏对吗？大家都知道井字游戏是什么吗？是的，所以在井字游戏中属于哪一类？它是一个玩家一可以强制获胜的游戏，还是玩家一只能强制平局的游戏，还是你宁愿第二个走，玩家二可以强制玩家二获胜或玩家一输的游戏？哪个是井字游戏？让我们举手表决。谁认为井字游戏是一个玩家一可以强制获胜的游戏？谁认为井字游戏是一个玩家一只能强制平局的游戏？谁认为玩家二会赢？大多数你们都是对的。如果人们玩得正确，它最终会是一场平局。所以井字游戏是一个导致平局的游戏。玩家一仍然可能犯错，在这种情况下他们会输。玩家二可能犯错，在这种情况下他们会输，但有一种玩的方法可以强制平局。好的？这些都是相当简单的游戏。让我们谈谈更复杂的游戏。

[段 7]

So what about the game of checkers? So the game of checkers meets these conditions. It’s a two-player game. You always know all the moves prior to your move It finite All right So there some rules and checkers that prevent it going on forever And there are two or three outcomes I guess there a third outcome if you get into a cycle you could tie Alright so Chequers fits all these descriptions and what this theorem tells us is that Chequers has a solution. Right, I’m not sure I know what that solution is, or I think actually somebody did compute it quite recently, even in the last few months. I just forgot to Google it this morning to remind myself. But what this theorem tells us, even before those people have computed it, checkers has a solution. All right? Let’s be a bit more ambitious. What about chess? So chess meets this description, right? Chess is a two-player game. Everybody knows all the moves before them. It’s sequential. All right? It has finite number of moves. It’s a very large number, but it is finite. All right? And it has three possible outcomes, a win, a loss, or a tie. Let’s be careful. The reason it’s finite is that if you cycle, I forget what it is, three times, times, then the game is declared a draw, declared a tie.

[译文 7]

那么西洋跳棋这个游戏呢？西洋跳棋符合这些条件。它是一个双人游戏。在你走棋之前，你总是知道所有的走法它是有限的，好的。那么西洋跳棋有一些规则，防止游戏无限进行下去。而且它有两个或三个结果，我想如果你陷入循环，还有第三个结果，那就是平局。好的，所以西洋跳棋符合所有这些描述，而这个定理告诉我们的是，西洋跳棋是有解的。对吗？我不确定我知道那个解是什么，或者实际上我想最近有人确实计算出来了，就在过去的几个月里。我今天早上忘了Google一下提醒自己。但这个定理告诉我们，即使在那些人计算出来之前，西洋跳棋是有解的。好的？让我们更有野心一点。国际象棋怎么样？所以国际象棋符合这个描述，对吗？国际象棋是一个双人游戏。每个人都知道他们之前所有的走法。它是顺序进行的。好的吗？它有有限的步数。这是一个非常大的数字，但它是有限的。好的？而且它有三种可能的结果，赢、输或平局。让我们仔细看一下。它是有限的原因是这样的，如果你循环三次，三次，然后游戏就被宣布为平局，宣布为和棋。

[段 8]

So what’s this theorem telling us? It’s telling us that there is a way to solve chess. It tells us there is a way to solve chess. Chess has a solution. We don’t know what that solution is. It could be that solution is that player one, who’s the player with the white pieces, can force a win. It could be that player one can only force a tie, and it could even be that player two can force a win. We don’t know which it is, but there is a solution. There’s a catch to this theorem. What’s the catch? The catch is it doesn’t actually tell us, this theorem is not going to tell us, what that solution is. It doesn’t tell us how to play. This theorem in and of itself doesn’t tell us how to play chess. It just says there is a way to play chess. All right? All right. So we’re going to try and prove this. We don’t often do proofs in class. But the reason I want to prove this particular one is because I think the proof is instructive as part of sort of QR at Yale. All right? So here’s another example here and some other examples you could think of chess as being the most dramatic example. All right. All right so the reason I want to actually spend some time proving this today is because we going to prove it by induction We’re going to prove it by induction.

[译文 8]

那么这个定理告诉我们什么？它告诉我们有一种方法可以解象棋。它告诉我们有一种方法可以解象棋。象棋是有解的。我们不知道那个解是什么。它可能是这样的：先手，就是执白棋的玩家，可以迫使胜利。也可能是先手只能迫成和棋，甚至还可能是后手可以迫使胜利。我们不知道是哪种情况，但确实存在一个解。这个定理有一个陷阱。什么陷阱？陷阱就是它实际上不会告诉我们，这个定理不会告诉我们那个解是什么。它不会告诉我们怎么下棋。这个定理本身不会告诉我们怎么下象棋。它只是说有下象棋的方法。好的？好的，所以我们将尝试证明这一点。我们不经常在课堂上做证明。但我想证明这一个的原因是因为我认为这个证明作为耶鲁QR的一部分是有启发性的。好的？那么这里还有另一个例子，你们可以想到的其他例子，国际象棋是最引人注目的例子。好的，好的。那么我今天想花时间证明这一点的原因是因为我们将用归纳法来证明它。我们将用归纳法来证明它。

[段 9]

And I’m going to sketch the proof. I’m not going to go through every possible step, but I want to give people here a feeling for what a proof by induction looks like. And the reason for that is, my guess is, well, let’s find out, how many of you have seen a proof by induction before? How many have not? Right? So for those who haven’t, I think it’s a good thing in life, at one point in your life, to see a proof by induction. And for those who have, my guess is you saw it in some awful math class in high school, and it just went, you know, didn’t take over your head, but it kind of, the excitement of it doesn’t catch on. I’m hoping to make, that this is a context where it might appeal. All right. So proof by induction. We’re going to prove this by induction on the maximum length of the game. And we’ll call that n. We’ll call n the maximum length of the game. So what do I mean by this? If I write down a tree I can always look at all the paths from the beginning of the tree all the way through to the end of the tree I should do that your way from the beginning of the tree all the way through to the end of the tree and I going to look at the path in that particular tree that has the largest length and I call that the length of the gain the maximum length of the gain So we’re going to do induction on the maximum length of the gain.

[译文 9]

我将概述这个证明。我不会遍历每一个可能的步骤，但我想让这里的人感受一下归纳证明是什么样子。这样做的原因是，我的猜测是，嗯，让我们看看，你们中间有多少人以前见过归纳证明？有多少人没见过？好的？所以对于那些没见过的，我认为人生中有一件事是好的，就是在人生中的某个时刻，看一次归纳证明。而对于那些见过的，我猜测你们是在高中某个糟糕的数学课上学到的，然后就过去了，你知道，它没有真正理解，但它有点，兴奋感没有抓住你们。我希望创造一种氛围，让这可能吸引人。好的。所以归纳证明。我们将根据游戏的最大长度n来证明这一点。我们将称n为游戏的最大长度。那么这是什么意思？如果我画一棵决策树，我总是可以看看从树的开头到树的结尾的所有路径，我会从树的开头一直走到树的结尾，我会看看那棵特定的树中具有最大长度的路径，我称之为增益的长度，增益的最大长度。所以我们将根据增益的最大长度进行归纳证明。

[段 10]

So how do we start a proof by induction? let’s remind ourselves, those people who’ve seen them before, we’re going to prove that this theorem is true, the claim in the theorem is true, for the easy case when the game is only one move long. Alright, that’s the first step. And then we’re going to try and show that if it’s true for all games of length less than or equal to n, whatever n is, then it must therefore be true for games of length n plus 1. Alright, that’s the way you do a proof by induction. So let’s just see how that works in practice. So start with the easy step, and we’ll do it in some detail, more detail than you really need to in a math class. So if n equals 1, what do these games look like? Well, let’s look at some examples here. So here’s a… I claim it’s pretty trivial if n is equal to 1, but let’s do it anyway. So the game might look like this. Player 1 is going to move Here player 1 moving The game is only length 1 so player 1 is the only player who ever gets to move So the game might look like this Let’s put in a fifth branch. It might look like this. And at the end of this game, rather than putting payoffs, let me just put the outcome.

[译文 10]

那么我们如何开始归纳证明呢？让我们提醒自己，那些以前见过归纳证明的人，我们要证明这个定理成立，定理中的论断成立，对于简单的情况，当游戏只有一步长时。好的，这是第一步。然后我们将尝试证明，如果它对所有长度小于或等于n的游戏成立，无论n是多少，那么它必然对长度为n加1的游戏成立。好的，这就是做归纳证明的方式。那么让我们看看在实践中这是如何工作的。所以从简单的步骤开始，我们会详细地做它，比你在数学课中真正需要的更详细。如果n等于1，这些游戏是什么样的？嗯，让我们看看这里的一些例子。那么这里有一个……我声称如果n等于1，这是相当简单的，但我们还是做一下。那么游戏可能是这样的。玩家1将走棋，这里玩家1走棋。游戏只有长度1，所以玩家1是唯一有机会走棋的人。所以游戏可能是这样的。让我们在这里加一个分支。它可能是这样的。在这个游戏结束时，而不是放收益，让我只放结果。

[段 11]

So the outcome must either be a win or a tie or a loss. So suppose it looks like this. Suppose it’s a win, or here we could have a tie, or here we could have a win again. Or here we could have a loss. And here we could have a tie. All right? So in this particular game, in this particular game, I claim it’s pretty clear this game has a solution. It’s pretty clear what one should do. All right, what should one do? One should pick one of her choices that leads to a win. To be careful, I’ll put one in here just to distinguish who it is who’s actually winning and losing. All right? So in this game, I claim that this game has a pretty obvious solution. Either player one is going to choose this branch that leads to a win, or this branch that leads to a win, and either way, player one is going to win. Right? Is that obvious? It’s obvious, it’s kind of painful. All right? So I claim this game, we can actually replace this first node with what’s going to happen. which is player one’s going to win. Is that right? That was easy. Let’s look at a different example. We’ll do three. All right? So here’s another possible example, and this again, player one is going to move here, and this time the possible outcomes are a tie, or a loss, or a loss.

[译文 11]

所以结果必须是赢、和或输。那么假设它看起来是这样的。假设它是赢，或者这里我们可以是和棋，或者这里我们可以又是赢。或者这里我们可以是输。这里我们可以是和棋。好的？那么在这个特定的游戏中，在这个特定的游戏中，我声称这个游戏显然是有解的。显然应该怎么做是清楚的。好的，应该怎么做？应该选择导致赢的那个选择。为了更仔细一点，我在这里放一个1来区分谁实际上是赢谁输。好的？那么在这个游戏中，我声称这个游戏有一个非常明显的解。要么玩家1将选择这个导致赢的分支，要么这个导致赢的分支，无论哪种方式，玩家1都将赢。对吗？这很明显，有点痛苦。好的？我声称这个游戏，我们实际上可以用实际将要发生的事情来替换这第一个节点，那就是玩家1将赢。对吗？那很容易。让我们看另一个例子。我们做三个。好的？所以这是另一个可能的例子，而且这一次，玩家1将在这里走棋，而这一次可能的结果是和棋，或者是输，或者是输。

[段 12]

All right, once again, it’s a one-player game. This time he has three choices, and the three choices lead to a tie or he loses. So I claim, once again, this is simple. What player one should do is what? Choose the tie, since there’s no way of winning. But in that case, he can actually force it. He can actually choose the tie, in which case he’s going to tie. So this game has a solution called choose the tie, and again, we could replace the first node of the game with what’s actually going to happen, which is a tie. Everyone happy? And there’s one other possibility, I guess. The other possibility is that here player 1 has a lot of choices, maybe four choices in this case. Once again player 1 is going to move but in each case unfortunately for player one in each case the outcome is that player one loses So this is a game in which player one is going to lose no matter what they do. Once again, it has a solution. The solution is player one is toast and is going to lose. alright so I claim this has really captured all the possibilities of games of length 1 alright, I mean you could imagine that there could be more branches on them, but basically there are these three possibilities, either it’s the case that one of those branches leads to a win, in which case the solution is player 1 wins, or it’s the case that none of the branches have wins in them but one of them has a tie in which case player 1 is going to tie or it’s the case that all the branches have loss in them in which case player 1 is going to lose.

[译文 12]

好的，这又是一个单人游戏。这一次他有三个选择，而三个选择导致和棋或者他输。那么我声称，这又很简单。玩家1应该做什么？选择和棋，因为没有办法赢。但在这种情况下，他实际上可以迫使它。他实际上可以选择和棋，在这种情况下他将和棋。所以这个游戏有一个解，叫做选择和棋，同样地，我们可以用实际将要发生的事情来替换游戏的第一个节点，那就是和棋。大家都清楚了吗？还有一种可能性，我想。还有另一种可能性是，这里玩家1有很多选择，也许在这种情况下有四个选择。同样地，玩家1将走棋，但在每种情况下不幸的是，对玩家1来说，在每种情况下，结果都是玩家1输。所以这是一个无论玩家1怎么做都将输的游戏。同样地，它有一个解。解就是玩家1完蛋了，将会输。好的，我声称这真正捕捉到了长度为1的游戏的所有可能性，我的意思是你们可以想象可能有更多的分支，但基本上有这三种可能性，要么是这些分支中有导致赢的，在这种情况下解就是玩家1赢，要么是没有分支有赢但其中一个有和棋，在这种情况下玩家1将和棋，要么是所有分支都是输，在这种情况下玩家1将输。

[段 13]

So I claim I’m done for games of length 1. Everyone okay? So that step is deceptively easy but there it is. Alright, now we do the inductive step, the big step. What we’re going to do is we’re going to assume that the statement of the theorem which I’ve now hidden unfortunately let me unhide it if I can it not going would be easy All right Is it now visible Good. So now let’s assume that the statement of this theorem is true for all games length less than or equal to n. All right? Suppose that’s the case. suppose the claim is true for all games of this type of length less than or equal to some n alright what we need to show is what we’re going to try and show is therefore it will be true for all games of length n plus 1 What we want to show is we claim therefore it will be true for games of length n plus 1 That a key step in inductive proofs Alright so how are we going to do that Well let have a look at a game of length n plus 1 Alright, obviously I can’t use thousands here, so let me choose some relatively small numbers, but the idea will go through. So let’s have a look at a game. Alright, so here’s a game in which player 1 moves first, player two moves second.

[译文 13]

所以我声称对于长度为1的博弈已经证明完毕。大家都明白吗？这一步看似简单但就是这样。好，现在我们进行归纳步骤，这是重要的一步。我们要做的，是我们将要假设这个定理的陈述——我刚才不幸把它隐藏了，让我把它显示出来如果可以的话——这不是太难。好，现在可见了吗？好的。所以现在让我们假设这个定理的陈述对于所有长度小于等于n的博弈都是成立的。好吗？假设对于所有这类长度小于等于某个n的博弈，这个论断都是成立的，我们要证明的是什么，我们要努力证明的是因此它对于长度为n+1的所有博弈也都成立。我们要证明的是我们声称因此它对于长度为n+1的博弈成立这是归纳证明中的一个关键步骤好，那么我们要怎么做呢？好，让我们来看一个长度为n+1的博弈。显然我不能用上千这样的数字，所以我选择一些相对较小的数字，但思路是一样的。好，让我们来看一个博弈。好，这里有一个博弈，其中玩家1先走，玩家2后走。

[段 14]

Let’s suppose if player two does this, then one only has a little choice here. Up here, then one has a more complicated choice. Perhaps two could move again. One, two, okay. All right, so this is quite a complicated little game up here. And down here, let’s make it a little bit less complicated. Here, the game looks like this and then comes to an end. All right, so the tree looks like this. I haven’t put the outcomes on it, but the tree looks like this. All right? So how long is this tree, first of all? Well, I claim that the longest path in this tree from the beginning to the end has four steps. Let’s just check. All right? So one, two, three, four. So I claim it’s the longest path. Any path going down this way only has three Let’s just check. All right. So 1, 2, 3, 4. That’s what I claim is the longest path. Any path going down this way only has three moves in it. All right. So this is a game of length 4. All right. All right. This is a game of length 4. So we can apply it to our claim. Let’s assume that the theorem holds for all trees length 3 or fewer, so that n plus 1 is 4 for the purpose of our example. All right?

[译文 14]

假设如果玩家2这样走，那么玩家1只有很少的选择。在上面这里，然后玩家1有更复杂的选择。也许玩家2可以再走一次。一，二，好吧。好，所以这是一个相当复杂的博弈在上面。而在下面，让我们让它稍微简单一些。这里，博弈是这样的然后结束。好，所以这棵树看起来是这样的。我没有把结果标上去，但这棵树看起来是这样的。好吧。那么这棵树的深度是多少，首先？好，我声称从起点到终点的最长路径有四步。让我们来检验一下。好。一，二，三，四。所以我声称这是最长路径。任何走这边下去的路径只有三步。让我们来检验一下。好。所以1，2，3，4。这是我声称的最长路径。任何走这边下去的路径只有三步。好。所以这是一个长度为4的博弈。好。好。这是一个长度为4的博弈。所以我们可以把它应用到我们的论断上。假设定理对于所有长度为3或更短的树都成立，所以对于我们的例子来说n+1等于4。好吗？

[段 15]

All right? So here’s, in this example, in this example, I don’t want to put it here, let’s put it here. In this example, n equals 3, so that n plus 1 equals 4. All right? Everyone happy with this in the example? All right. Now what I want to observe about this is the following. Contained in this n plus 1, or a game of length four, are some smaller games. You could think of them as sub-games. They’re games within the game. Is that right? So let’s have a look. I claim in particular let draw around them in pink there a game here that follows player one choosing up and there’s a game here that follows player one choosing down. Is that right? All right. Okay, so these are both games. All right. And what do we have here? so this little game in here, the game in the top circle the game that follows player one moving up that’s a game and it has a length so this little thing is a game this is a game and I’m going to call it a sub-game some jargon we’ll be getting used to later on in the semester it’s a game within the game but it’s basically a game, this is a sub-game and this is a sub-game following one choosing up, let’s put up in here, following up, and I claim that this game has a length, this subgame has a length.

[译文 15]

好吗？所以在这个例子中，在这个例子中，我不想把它放在这里，让我们把它放在这里。在这个例子中，n等于3，所以n+1等于4。好吗？大家对这个例子都清楚吗？好。现在关于这个我要观察的是以下内容。包含在这个n+1，或者说长度为4的博弈中的，是一些更小的博弈。你可以认为它们是子博弈。它们是博弈中的博弈。对吗？好，让我们来看。我特别声称——让我用粉色把它们圈出来——这里有一个博弈，它在玩家1选择上面之后；这里有一个博弈，它在玩家1选择下面之后。对吗？好。所以这两个都是博弈。好。这里我们有什么？所以这里面这个小博弈，上面圆圈里的博弈，玩家1向上移动后接着的博弈，这是一个博弈，它有一个长度，所以这个小东西是一个博弈，这是一个博弈，我要把它叫做子博弈——一些术语，我们在这学期的后面会逐渐熟悉——它是一个博弈中的博弈，但基本上它就是一个博弈，这是子博弈，这是跟随玩家1选择上面的子博弈，让我们在这里写上"上面"，跟随上面，我声称这个博弈有长度，这个子博弈有长度。

[段 16]

So we knew that we started from a game of length 4 we taken one of the moves and let make sure this is actually a game of length 3 The game started here this would be a game of length 3 because you could go 1 2 3 moves Is that right So this is a game of length 3. So this is a sub-game following one choosing up, and it, the sub-game, has length 3. All right, and down here, down here, this is also a sub-game. It’s a game that follows player one choosing down. Following one choosing down. and this little sub game has length, now here we have to be a little bit careful you might think that since we started from a game of length 4 after the first move we must be in a move of length 3 but actually that’s not true and if we look carefully we’ll notice that this game down here, the game starting here actually isn of length 3 it of length 2 is that right so even though we started from a game of length 4 by going this way we put ourselves into a game of length 2 Is that right Right So 1 2 or 1 2 or whatever All right It has length 2 Okay All right So in this example, n is 3, and n plus 1 is 4, and our assumption, our induction assumption, is what? we’ve assumed that the claim of the theorem holds for all games less than or equal to a, which in this case means less than or equal to 3.

[译文 16]

所以我们从长度为4的博弈开始，我们取其中一步，确保这实际上是一个长度为3的博弈。博弈从这里开始，这将是一个长度为3的博弈，因为你可以走1、2、3步。对吗？所以这是一个长度为3的博弈。所以这是跟随玩家1选择上面的子博弈，它的长度是3。好，在下面，在下面，这也是一个子博弈。这是一个在玩家1选择下面之后的博弈。跟随玩家1选择下面。这个小子博弈有长度，现在这里我们需要稍微小心一点，你可能会认为因为我们从一个长度为4的博弈开始，走完第一步后我们一定处于长度为3的博弈中，但事实上这不是真的，如果我们仔细观察，我们会注意到下面这个博弈，从这里开始的博弈实际上不是长度为3而是长度为2，对吗？所以尽管我们从一个长度为4的博弈开始，走这条路我们把自己带到了一个长度为2的博弈中。对吗？好，所以1、2或者1、2什么的。好，它的长度是2。好。所以在例子中，n是3，n+1是4，而我们的假设，我们的归纳假设是什么？我们假设定理的论断对于所有小于等于a的博弈成立，在这种情况下意味着小于等于3。

[段 17]

All right? So what does that tell us? That tells us, by our assumption, by our assumption, this game, which I’ve put a pink circle around on the top, this is a game of length 3, this game has a solution. It must have a solution because it’s of length 3 or less. So by the induction hypothesis, as it’s called, by the induction hypothesis, this is a technical term, but what’s the induction hypothesis? It’s this thing. By the assumption that we made, this game has a solution. This game has a solution. It’s a game of length 3. 3 is less than or equal to n in this case, so this game must have a solution. Now I don’t immediately know by staring at it what it is, but let’s suppose it was W. Say it was W. And the game down below, this is also a game, and it’s a game of length 2, but 2 is less than 3 as well. 2 is less than or equal to 3. So this game also has a solution. this game also, by the same assumption, has a solution. So its solution is say I don know maybe it L So what does that mean to say that these games have solutions In this case we going to assume W is this one and L is this one Now, what does it mean?

[译文 17]

好吗？那么这告诉我们什么？这告诉我们，根据我们的假设，根据我们的假设，这个博弈，我在上面用粉色圆圈圈出来的，这是一个长度为3的博弈，这个博弈有一个解。它必定有一个解，因为它长度为3或更少。所以根据归纳假设——这是一个技术术语——根据归纳假设，这个博弈有一个解。这个博弈有一个解。它是长度为3的博弈。3在这个情况下小于等于n，所以这个博弈必定有一个解。现在我盯着它看并不能立刻知道它是什么，但假设它是W。假设它是W。下面这个博弈，这也是一个博弈，它的长度为2，但2也小于3。2小于等于3。所以这个博弈也有一个解。这个博弈，根据同样的假设，也有一个解。所以它的解是比如说，我不知道，也许是L。那么说这些博弈有解是什么意思？在这种情况下我们要假设这个是W那个是L。那么这意味着什么？

[段 18]

It means that just as we did with the games up there, we could put the solution at the beginning of the game. We know that if we get into this game, we’re going to get the solution of this game. and we know if we get into this game we’re going to get the solution of this game. So we can replace this one with its solution which by assumption was W and this one by its solution which by assumption was L and here I want to be really careful I need to keep track of which person it is it’s a win or a loss for. So this was a win for player 1 hence it was a loss for player 2 and this was a loss for player 1 hence it was a win for player 2. All right? All right, so these games, each of them have some solution. In this case, I’ve written down the solutions as W or L. All right? So now what can we do? Let me just bring down this board again I can translate this game into a very simple game I going to translate it up here So this game can be translated as follows Player 1 moves If he goes up then he hits a W And if he goes down, he hits a loss. So in this particular example, player one is effectively choosing between going up and finding himself in a game which has a solution, and the solution is he wins it, or going down and finding himself in a game which has a solution, and the solution is he’s toast.

[译文 18]

这意味着，正如我们之前对上面的博弈所做的那样，我们可以把解放在博弈的开头。我们知道如果我们进入这个博弈，我们就会得到这个博弈的解，而且我们知道如果我们进入这个博弈我们就会得到这个博弈的解。所以我们可以用它的解来替换这个——根据假设是W——这个用它的解来替换——根据假设是L——在这里我要非常小心，我需要追踪这是谁赢谁输。这是一个玩家1的胜利所以是玩家2的失败，而这是玩家1的失败所以是玩家2的胜利。好吗？好，这些博弈，每一个都有某个解。在这种情况下，我写下的解是W或L。好吗？那么现在我们可以做什么？让我把这个黑板再放下来我可以把这个博弈转化成一个非常简单的博弈我要把它转化到这里所以这个博弈可以如下转化玩家1移动如果他往上走那么他就遇到一个W如果他往下走他就遇到一个L。所以在这个特定的例子中，玩家1实际上是在选择往上走然后发现自己处于一个有解的博弈中，而解是他赢，或者往下走然后发现自己处于一个有解的博弈中，而解是他完蛋了。

[段 19]

But that’s what? That’s a one-move game. That’s a one-move game. So we know this is a solution. In particular, he’s going to choose up. This one has a solution. All right? This has a solution. It is a game of length 1 So what do we do All right so much schematically we took a game of length n plus 1 in this case that was 4, and we pointed out that once player 1 has made her first move in this game, we are in a game, or in a sub-game if you like, that has length less than 4. It could be 3, it could be two, whatever. Whatever sub-game we’re in, by assumption, that game has a solution. So it’s really effectively, player one is choosing between going into a game with solution win or going into a game with solution loss, and if there were 15 other sub-games here, each one would have a solution, and each one, player one would be able to associate that solution with what he’s going to get. What she’s going to get. All right? So I claim that if it in fact is true that each of these sub-games of length 3 or less had a solution, then the game of length 4 must have a solution, which is what? It’s the solution which is player 1 should pick the best sub-game.

[译文 19]

但这是什么意思？这是一步游戏。这是一步游戏。所以我们知道这是一个解。具体来说，他会选择上。这个有解。对吧？这有解。它是一个长度为1的游戏。那么我们该怎么做？好，下面我们用图示说明：我们取一个长度为 n+1 的游戏，这里是 4，并且指出，一旦玩家1在这局游戏中做出她的第一步，我们就进入了一个长度小于4的游戏，或者如果你愿意称之为子游戏。它可能是 3，可能是 2，等等。无论我们处于哪个子游戏，依据假设，那个游戏是有解的。所以实际上，玩家1 是在选择进入一个有解（赢）的游戏，还是一个有解（输）的游戏之间进行抉择；如果这里还有 15 个其他子游戏，每一个都有解，而且每一个，玩家1 都能把那个解与她将得到的结果对应起来。她将得到什么。对吧？所以我声称，如果事实上每个长度为 3 或更短的子游戏都有解，那么长度为 4 的游戏必定有解，这是什么？这就是玩家1 应该选择最佳子游戏的解。

[段 20]

People convinced by that step? Yeah. It’s the solution which is player 1 should pick the best sub game. Alright? People convinced by that step? People looking slightly dear in the headlamps now, so let me just say it again. Alright? We started by assuming that all games of length 3 or less, or n or less, have a solution. we pointed out that any game that has length n plus 1 can be thought of as an initial move by player 1 followed by a game of length n or less n or fewer I should say each of those games of n or fewer steps has a solution so player 1 is just going to choose the game that has the best solution for her and we’re done in this particular example player 1 is going to choose up And therefore, the solution to this parent game is player one wins. All right? Now the hard step I think in proofs by induction is realizing that you done So I claim we now done Why are we done Well we know that was pretty easy that all games of length 1 have a solution That was pretty trivial. And we’ve shown that if any game of length n or fewer has a solution, then games of n plus 1 have a solution. So now let’s see how we proceed.

[译文 20]

大家被这一步说服了吗？是的。这就是玩家1 应该选择最佳子游戏的解。对吧？大家被这一步说服了吗？现在大家看起来有点困惑，所以我再说一遍。好吧？我们一开始假设所有长度为 3 或更短的游戏，或者 n 或更短的游戏都有解。我们指出，任何长度为 n+1 的游戏都可以看作是玩家1 的第一步，紧接着一个长度为 n 或更少的游戏——应该说，每个长度为 n 或更少的步数都有解，所以玩家1 只会选择对她来说解最好的那个游戏，这样就完成了。在这个例子中，玩家1 会选择上。因此，这个父游戏的解是玩家1 获胜。对吧？现在，我认为归纳证明中最难的一步是意识到你已经完成了。所以我声称我们现在完成了。为什么我们完成了？嗯，我们知道这非常容易，所有长度为 1 的游戏都有解，这很 trivial。我们已经证明，如果任何长度为 n 或更少的游戏有解，那么长度为 n+1 的游戏也有解。那么现在我们来看看我们接下来该怎么做。

[段 21]

We know that games of length 1 have a solution, so let’s consider games of length 2. Right? Games of length 2 do games of length 2 have a solution? Well let’s set N equal to 1. We know that if games of length 1 have a solution then any game of length 2 can be thought of as an initial step followed by a game of length 1 but that has a solution. So therefore games of length 2 have a solution. But now let’s think about games of length 3. We’ve shown that games of length 1 have a solution and games of length 2 have a solution right? Any game of length 3 can be thought of as a game in which there’s an initial step, followed by either a game of length 1 or a game of length 2, each of which have a solution. So once again, a game of length 3 has a solution, and so on. All right? So games of induction, they work by building up on the length of the game, and we ending up knowing that we done All right For those people who never seen a proof by induction don worry I not going to test you on a proof by induction on the exam I just want you to see one once and let’s all take a deep breath and try and digest this a little bit by playing a game.

[译文 21]

我们知道长度为 1 的游戏有解，所以让我们考虑长度为 2 的游戏。对吧？长度为 2 的游戏有解吗？好，让我们把 N 设为 1。我们知道，如果长度为 1 的游戏有解，那么任何长度为 2 的游戏可以看作是一步初始步后接一个长度为 1 的游戏，而后者有解。因此，长度为 2 的游戏有解。但现在让我们想想长度为 3 的游戏。我们已经证明了长度为 1 的游戏有解，长度为 2 的游戏有解，对吧？任何长度为 3 的游戏可以看作是一步初始步后接一个长度为 1 或长度为 2 的游戏，这两个都有解。于是，长度为 3 的游戏再次有解，以此类推。对吧？所以归纳游戏的做法是通过逐步增加游戏的长度来进行，最终我们认识到已经完成。对吧？对于那些从未见过归纳证明的人，别担心，我不会再考试中考察归纳证明，我只是想让大家看一次，大家深呼吸一下，尝试通过玩游戏来消化这一点。

[段 22]

All right, so I’ll leave it up there, I’ll leave it up there so you can stare at it. I want it down again later. and let’s try and actually play a game and see if we can actually throw any light on this. All right, so I’m going to pick out volunteers like I did last time, but first of all, let me tell you what the game is. So once again, I’m going to have rocks in this game, and once again, I’m going to approximate those rocks with marks on the blackboard. All right, so here’s an example. And the example is this. the game involves an array of rocks so here the array has 1, 2, 3, 4, 5 rows and three columns so the rocks are not arranged as they were before in piles but rather in a sort of pretty array I actually made it more even but this is one two three four five rows and one two three columns That in this example But in general, there’s an array of rocks, n times m. And we’re going to play sequentially with the players, and the way the game’s going to work is this. This is meant to be in this row. the way the game’s going to work is when it’s your turn to move you have to point to one of these rocks and whichever rock you point to I will remove, I will delete that rock and all the rocks that lie above or to the right of it all the rocks that lie to the north east of it so for example, if you pointed to this rock then I will remove this rock and also this one, this one, and this one.

[译文 22]

好，我就把它留在那里，你们可以盯着看。我稍后会把它再放下。让我们试着实际玩一个游戏，看看能否对此有所启示。好，我像上次一样挑选志愿者，但首先让我告诉你们这个游戏是什么。同样，这个游戏里有石头，我同样用黑板上的记号来近似这些石头。好，这里有一个例子。这个例子是这样的。游戏涉及一个石头阵列，这里阵列有 1、2、3、4、5 行，三列，所以石头不像以前那样堆在一起，而是排列成一种相当整齐的阵列。我实际上把它做得更均匀了，但这是 1、2、3、4、5 行和 1、2、3 列的例子。一般来说，石头阵列是 n 乘 m。我们将按顺序让玩家进行游戏，游戏规则如下。这条规则是在这一行。游戏规则是：当轮到你走时，你必须指向其中一块石头，无论你指向哪块，我都会删除那块石头以及所有位于它上方或右侧的石头，也就是所有位于东北方向的石头。例如，如果你指向这块石头，那么我将删除这块石头以及这块、这块和这块。

[段 23]

All right? If the next person comes along and chooses this one, then I will remove this one and also that one. Okay, everyone understand? All right. And the game is… Okay, everyone understand? Alright, and the game is… The game is lost, let’s be clear, this is important, the game is lost by the person who ends up taking the last rock. The loser is the person who ends up removing the last rock. Alright? Alright? Perhaps some volunteers? Can I volunteer people one? How about the guy with the white t-shirt with the yellow on there? All right, okay, can you come on up front? All right, and who else can I volunteer? Everyone’s looking away from me, desperately looking away from me. Okay, how about the guy with the Yale sweatshirt on? The Yale, yeah, the Yale football sweatshirt on, okay? All right, so come on up. Your name is, I should get a, let me get a mic up here. Thank you. Great. Your name is? Noah. Noah. And your name is? Quran. Say it into the mic so we can hear Quran Quran Okay So Noah and Quran are our players All right Everyone understand the rules You understand the rules Yeah Alright so why don we let Noah go first So Noah which rock are you going to remove Remember, the last rock loses.

[译文 23]

好？如果下一个人来并选择这块，那么我将删除这块和那块。好，大家明白吗？好。大家明白吗？好，游戏是……好，游戏是……游戏是输的，让我们说清楚，这一点很重要，游戏由取走最后一块石头的人输掉。输家是取走最后一块石头的人。好？好？要不要几位志愿者？我可以叫几个人上来吗？那边穿白色 T 恤、上面有黄色图案的家伙怎么样？好，你可以上前吗？好，我还能叫谁？大家都在躲避我，死命地躲。好，穿耶鲁运动衫的那位呢？耶鲁，是的，耶鲁足球运动衫，好吧？好，上来吧。你叫什么名字，我应该拿个麦克风。谢谢。好的。你叫什么名字？Noah。Noah。你叫什么名字？Quran。请对着麦克风说，这样我们可以听到 Quran。好，Noah 和 Quran 是我们的玩家。好，大家明白规则吗？你明白规则吗？好，那我们为什么不让 Noah 先走？Noah，你打算移走哪块石头？记住，最后一块石头会输。

[段 24]

That one? That one. Okay, so Noah chose this one, so I’m going to remove this one and the one above it. All the rocks to the north and east of it are deleted. Wait, wait, that means you… Anyway, last rock loses, okay? Last rock… Okay, okay. Okay, okay, good. All right. So… All right. That one. That one, okay. So now we have an L shape. That one. All right. That one. Okay, okay, okay. All right, so we’re done. All right, okay, everyone understand how that works? All right, round of applause for our players please All right thank you Let me get two more volunteers now everyone seen it These guys had the hard job there to figure it out cold Two more volunteers Oh I don have to volunteer There somebody volunteering Are you volunteering Great I have one volunteer. You can pick an opponent if you like. There you go. Okay, thank you. Your name, well let’s just wait until the mics are here. so your name is Peter and your name is Justin alright let me put a new array up here alright so let’s put a new array up here so let’s make it this time a little bit more complicated so we’ll have 5 I said four rows and five columns this time. Alright, so this time last time I had five rows and three columns and this time I have four rows and five columns.

[译文 24]

那块？那块。好，Noah 选了那一块，所以我将删除那一块以及它上面的一块。所有位于它北面和东面的石头都被删除。等一下，等一下，这意味着你……总之，最后一块石头会输，好吗？最后一块石头……好，好。好。好了。于是……好。那块。那块，好。于是我们现在得到一个 L 形。那块。好。那块。好，好，好。于是我们结束了。好，大家都明白怎么运作了吗？好，请为我们的玩家鼓掌。好，谢谢。现在让我再找两位志愿者，大家都看到了吧？这两位刚才的任务很艰难，需要现场想出来。再来两位志愿者。哦，我不必自告奋勇，有人已经在举手了。你是自愿的吗？太好了，我有一位志愿者。你可以挑选对手，如果你愿意的话。好，谢谢。你的名字，嗯让我们等麦克风过来。你的名字是 Peter，你的名字是 Justin，好吧？让我在这里放一个新的阵列，好，让我们在这里放一个新的阵列，这次让它稍微复杂一点，我们会有 5 行，我说四行五列。好，这次上次是五行三列，这次是四行五列。

[段 25]

Four rows and five columns. Alright. Away you go. Move out the way. Why don you stand a bit nearer to the board and make it a little easier for people to see what going on There you go Peter you want to go first That one Okay so this one goes which means all of these go as well. Alright. Anyone got any advice from the floor? Anyone want to shout things out? Not too loud, right? I’ll try to go in here. In there. Okay, well we’re back to our L shape again. here. Ah! All right. All right, now people can see what’s going on, all right? I’ll go here and speed it up. All right, all right, good. All right, all right, thank you. All right, so a round of applause again. All right, thank you guys. So here’s my claim about this game. First, and this is the formal claim, this is a lot harder than the game we played last time, right? Everyone convinced by that, all right? So here’s going to be an exercise. I’ll set it as a challenge. I may even put it formally on the problem set this week. But that means to say, if I do put this on the problem set this week, I don’t expect you all to solve it, all right? If I do put it on the problem set, it’s an optional problem, all right? this week, but let me just say, if I do put this on the problem set this week, I don’t expect you all to solve it, alright?

[译文 25]

四行五列。好的。开始吧。让一下。你们站到板子附近一点吧，让人们更容易看清正在发生什么。就这样 Peter，你先来吗？那个？好，这个放这里意味着所有这些也都放这里。好的。有什么建议吗？有人想喊出来吗？别太大声，对吧？我试着放这里。这里。好的，我们又回到 L 形了。这里。啊！好的，好的，现在人们能看到正在发生什么了，对吧？我放这里，加快速度。好的，好的，很好。好的，好的，谢谢。好的，再来一轮掌声。好的，谢谢大家。关于这个游戏，我的论断是这样的。首先，这是正式的论断，这个游戏比我们上次玩的那个难多了，对吧？大家都认可吧？那么这将是一个练习。我会把它作为一个挑战。我甚至可能会正式地把它放到这周的作业里。但这意味着，如果我真的把它放到这周的作业里，我不期望你们都能解出来，好吗？如果我真的把它放到作业里，这是一个可选的问题，好吗？这周，但让我这么说，如果我真的把它放到这周的作业里，我不期望你们都能解出来，好吗？

[段 26]

If I do put it on the problem set, it’s an optional problem, alright? But here’s the challenge. The challenge is, I claim, I know from Zemalo’s theorem that no matter what n is, and no matter what m is, this game has a solution, alright? So Zermelo’s theorem tells us this game has a solution. And notice, it could have a different solution depending on the n and the m, depending on how many rows and how many columns. Is that right? So depending on n and m, each such game has a solution. Is that right? Is that right? Right? Right? So which could depend on n and on m, on the number of rows and columns. So just as in NIM it depended on how those piles started out All right So what going to be the homework assignment Find the solution Find the solution Homework what is the solution All right So I claim let me give you a hint I claim it is useful to remember that there is a solution. Alright? It turns out to be useful to remember. That wasn’t much of a hint, you knew that already, but I just emphasised that. Okay. Okay, so I want to do a bit of a transition now, away from these games like chess and like checkers and like this game with the rocks or NIMH.

[译文 26]

如果我真的把它放到作业里，这是一个可选的问题，好吗？但这就是挑战。挑战是，我声称，我从泽莫洛定理知道，无论 n 是什么，无论 m 是什么，这个游戏都有一个解，对吧？泽莫洛定理告诉我们这个游戏有一个解。注意，它可能有一个不同的解，取决于 n 和 m，取决于有多少行和多少列。对吗？所以取决于 n 和 m，每个这样的游戏都有一个解。对吗？对吗？是的。是的，这可能取决于 n 和 m，取决于行数和列数。就像在尼姆游戏中，它取决于那些堆是如何开始的。好的，那么作业是什么？找到解。找到解。作业：解是什么？好的，所以我的论断是，让我给你一个提示，我声称记住有一个解是有用的。好吗？记住这一点是有用的。这不算什么提示，你们已经知道了，但我只是强调了一下。好的，好的，我现在想做一个转换，摆脱这些游戏，比如象棋、跳棋、这个用石头的游戏或尼姆。

[段 27]

And I want to be a little bit formal for a while. Alright? So one thing we haven’t done for a while, actually really since the midterm, is write down some formal definitions. So I’m going to do that now. I want at least one of these boards back. All right All right All right So as I warned very early in the class, there are some points of the day when we have to stop and do some work, and the next 20 minutes or so is such a point. All right. So, okay, what is this? This is formal stuff. And the first thing I want to do is I want to give you a formal definition of something I’ve already mentioned today, and that’s the idea of perfect information. So what we’ve been looking at really since the midterm are games of perfect information. So a game of perfect information is one in which at every node or at each node at each node in the game the player whose turn it is to move at that node the player whose turn it is to move knows which node she is at. Alright? So it’s a very simple idea. Every game we’ve seen since the midterm has this property. When you’re playing this game, you know where you are. You know where you are. So you know which node you’re at, you know what your choices are, and what that means implicitly is She must know how she got there.

[译文 27]

我想现在稍微正式一点。好？实际上我们从期中考试以来就没有做过的事情，就是写下一些正式的定义。所以我现在要这么做。我至少要把其中一个棋盘拿回来。好的，好的，好的。就像我很早就在课上警告过的那样，有些时候我们必须停下来做一些工作，接下来的二十分钟左右就是这样的时候。好的，好，这是什么？这是正式的东西。首先我想做的是给出一个我已经今天提到过的概念的正式定义，那就是完美信息的概念。所以我们从期中考试以来一直在看的是完美信息的游戏。所以完美信息的游戏是指在游戏的每个节点，在每个节点，当轮到该节点移动的玩家时，该玩家知道她所在的节点。好？这是一个非常简单的想法。我们从期中考试以来看到的每个游戏都有这个属性。当你玩这个游戏时，你知道你在哪里。你知道你在哪里。所以你知道你在哪个节点，你知道你有哪些选择，这隐含的意思是她一定知道她是怎么到那里的。

[段 28]

All right, so the whole history of the game is observed by everybody. When I get to move, I know what you did yesterday, I know what I did the day before yesterday. If I’m playing with a third person, I know what they did the day before that. All right, so a very simple idea, but it turns out to be an idea that actually allows us to use things like backward induction very simply. All right, now so far, all we’ve been doing is thinking about such games, games like perfect competition, or games like quantity competition between firms or games like the games where we were setting up incentives or games like NIM and we’ve basically been solving these games by backward induction rather informally. What I want to add in now is the notion of a strategy in these games. When we had simultaneous move games strategies were really unproblematic. It was obvious what strategies were but when we have games which are sequential that go on over a period of time and information is emerging over a period of time we need to be a little careful what we mean by a strategy. So what I want to do is I want to define a pure strategy, at least, as follows. So a pure strategy… a pure strategy for player I in a game of perfect information So in the games we’ve been talking about, games which we can represent by trees, is what?

[译文 28]

好的，所以游戏的整个历史都被每个人观察着。当我轮到移动时，我知道你昨天做了什么，我知道我前天做了什么。如果我和第三个人玩，我知道他们在那之前的一天做了什么。好的，所以这是一个非常简单的想法，但事实证明这个想法确实允许我们非常简单地使用倒推归纳法。好，到目前为止，我们所做的都是思考这样的游戏，比如完美竞争的游戏，或者企业之间的数量竞争的游戏，或者我们设置激励的游戏，或者像尼姆这样的游戏，我们基本上是通过倒推归纳法相当不正式地解这些游戏。现在我想加入的是这些游戏中的策略概念。当我们有同时行动的游戏时，策略真的是没有问题的。什么是策略很明显，但当我们有按顺序进行的游戏时，这些游戏会持续一段时间，信息在一段时间内逐渐出现，我们需要稍微小心我们所说的策略是什么意思。所以我想做的是，我想至少定义一个纯策略如下。一个纯策略……一个纯策略，对于完美信息游戏中的玩家 I，在我们一直在谈论的可以用树表示的游戏中，是什么？

[段 29]

It’s a complete plan of action. in other words what it does is it specifies which action I should take should take let’s not make it should take let’s say will take will take at each of I’s nodes, each of I’s decision nodes. So when you first read this definition it seems completely uninteresting and unproblematic A pure strategy for player I just tells you in this game whenever you might be called upon to move, it tells you how you’re going to move. Right? So you’re going to move three times in the game, it tells you how you’re going to move the first time, it tells you how you’re going to move the second time, and it tells you how you’re going to move the third time. All right? All right? So, so far, none of this seems difficult, but actually it’s a bit more difficult than it looks. So let’s have a look. What I want to do is I want to look at an example, and this example, I’m hoping, is going to illustrate some subtleties about this definition. So here’s an example. In this example, player one moves first and they can choose in or out or if you like let call it up or down since that the way we drawn it So they can choose down or up and I use capital letters U and D If player chooses up then player two gets to move and player two can choose left or right.

[译文 29]

它是一个完整的行动计划。换句话说，它做的是指定我在我的每个节点，我的每个决策节点应该采取什么行动。所以当你第一次读这个定义时，它看起来完全无趣也没有问题。玩家 I 的一个纯策略只是告诉你在这个游戏中无论何时你可能被要求移动，它告诉你你将如何移动。对吧？所以你在这个游戏中要移动三次，它告诉你第一次你将如何移动，它告诉你第二次你将如何移动，它告诉你第三次你将如何移动。好吗？好吗？到目前为止，这些看起来都不难，但实际上它比看起来要难一些。让我来看一下。我想做的是我想看一个例子，我希望这个例子能说明这个定义的一些微妙之处。好了，这是一个例子。在这个例子中，玩家一先移动，他们可以选择进入或退出，或者如果你喜欢的话叫它向上或向下，因为我们画的是这样。所以他们可以选择向下或向上，我用大写字母 U 和 D。如果玩家选择向上，那么玩家二可以移动，玩家二可以选择向左或向右。

[段 30]

And if player one moves up, followed by player two choosing left, then player 1 gets to move in which case player 1 can move up or down. I’ll use little letters this time. Little u and d. Right? Let’s put some payoffs in this game. So the payoffs are 1, 0 here. 0, 2 here. 3, 1 here. And 2, 4 here. Alright. So on paper, on the board when you first look at it, this is a perfectly simple game. It’s just like many of the games we’ve been looking at since the midterm. It has a tree. We could analyze it by backward induction. In a moment, we will analyze it by backward induction. All right? But what I want to do first is I want to say, what are the strategies in this game? All right? So let’s start with player two, since it’s easier. Here, player two’s strategies… All right, so let’s start with player two, since it’s easier. Player two’s strategies here are what? Pretty simple. Player two only has one decision node. Here’s player two’s decision node. And the strategy has to tell player two what he’s going to do at that decision node. So there’s only two choices, left or right. So player 2’s strategies are either left or right. Notice, however, already one slight subtlety here. Player 2 may never get to make this choice.

[译文 30]

如果玩家一向上移动，然后玩家二选择向左，那么玩家一可以移动，在这种情况下玩家一可以向上或向下。这次我用小写字母。小写 u 和 d。对吧？让我给这个游戏放一些支付。所以支付是 1,0 在这里。0,2 在这里。3,1 在这里。2,4 在这里。好。所以在纸上，在板子上，当你第一次看它，这是一个完全简单的游戏。它就像我们从期中考试以来一直在看的许多游戏一样。它有树。我们可以用倒推归纳法来分析它。很快，我们就会用倒推归纳法分析它。好？但我想首先做的是我想说，这个游戏中的策略是什么？好的？让我们从玩家二开始，因为它更容易。在这里，玩家二的策略是什么？相当简单。玩家二只有一个决策节点。这是玩家二的决策节点。策略必须告诉玩家二他在这个决策节点要做什么。所以只有两个选择，向左或向右。所以玩家 2 的策略要么向左要么向右。注意，然而，这里已经有一个轻微的微妙之处。玩家 2 可能永远不会有机会做这个选择。

[段 31]

So player 2 is choosing left or right, but player 2 may not ever get to make this choice. In particular, if one shows down, it’s really irrelevant whether player 2 has chosen left or right. right nevertheless a strategy has to specify what play out two would do were he called upon to make that move all right now let’s look at player one strategies so what a player one strategies in this game What are player one strategies? Any takers? Anyone want to guess? So I claim it’s tempting, it’s tempting but it turns out to be wrong to say that player one has three strategies here. It’s tempting to say either player one moves down, in which case we’re done, or player one moves up, in which case at some later date she may be called upon to choose up or down again. So it’s very tempting to think that player one has just three strategies here. Down, in which case we’re done, or up followed by either up or down depending on what, sorry, followed by either up or down if she’s reached to that point. Right?

[译文 31]

所以玩家2是在选择左还是右，但玩家2可能根本没有机会做出这个选择。特别地，如果有人选择摊牌，那么玩家2是否选择了左或右就完全无关紧要了。尽管如此，一个策略必须规定如果玩家2被要求做出那个移动，他会怎么做。好，现在让我们来看看玩家1的策略。那么在这个游戏中，玩家1的策略是什么？玩家1的策略有哪些？有自告奋勇的吗？有人想猜一猜吗？我认为，虽然很诱人，但说玩家1在这里有三个策略是错误的。之所以诱人，是因为可以说要么玩家1向下移动，在这种情况下游戏就结束了，要么玩家1向上移动，在这种情况下在之后的某个时点她可能需要再次选择向上还是向下。所以很容易认为玩家1在这里只有三个策略。向下，这种情况游戏就结束了；或者向上，然后在到达那个点时选择向上或向下。对吧？

[段 32]

But actually if we follow this definition carefully we notice that player one actually has four strategies here Let me say what they are and you see why it a little odd So here one of the strategies we talked about up followed by up And here another one we talked about up followed by down But I claim there are two others, down followed by up and down followed by down. so what’s a little weird about this what’s weird is we know perfectly well that if player 1 chooses down she’s not going to get to make the choice the second choice up or down but nevertheless the strategy has to tell us what she would do at every node regardless of whether that node actually is reached by that strategy Let me say it again. The strategy has to tell you what player 1 would do at that node, regardless of whether that node is actually reached by playing that strategy. It’s a little weird, right? There’s a bit of redundancy here. It’s a bit redundant. Alright Now why Well we see why in a second Let first of all consider how this game will be played according to backward induction All right So how do we play this game according to backward induction? Where do we start? Shouldn’t be a trick question, right? Where do we start the game according to backward induction?

[译文 32]

但是如果我们仔细遵循这个定义，我们会注意到player 1实际上有4个策略。让我说说这些策略是什么，你们会看到为什么有点奇怪。这里我们讨论的其中一个策略是上接上。另一个是上接下。但我声称还有2个，分别是下接上和下接下。那么这件事有点奇怪的地方是什么呢？奇怪之处在于我们很清楚，如果player 1选择下，她就不会有第二次选择上或下的机会，但尽管如此，策略必须告诉我们她在每个节点会做什么，不管该节点是否实际上通过该策略被达到。让我再说一遍。策略必须告诉你player 1在该节点会做什么，无论该节点是否实际上通过执行该策略而被达到。这有点奇怪，对吧？这里有点冗余。有点冗余。好吧，那么为什么呢？我们马上会看到原因。首先考虑这个游戏按照逆向归纳会怎么进行。好吧，那么我们按照逆向归纳玩这个游戏从哪里开始？应该不是个脑筋急转弯，对吧？按照逆向归纳，我们从哪里开始游戏？

[段 33]

At the end. Okay. So the end here is player 1, and player 1 will choose here to go down. Is that right? Because 3 is bigger than 2. So if we roll back to player 2’s move, player 2, if she chooses left, she knows that she’ll be followed by player 1 going down, in which case she’ll get 1, but if she chooses right, she’ll get 2. So player 2 will choose right. So player 1 here, if she chooses up, then player 2 will choose right and player 1 will get 0. And if she chooses down, she’ll get 1. So player 1 will choose down. so backward induction suggests that player 1 will choose down and followed by player 2 if player 2 did get to move, she’d choose right. Followed by player 1, if she did get to move again, choosing down again. Notice that backward induction had to tell us what player 2 would have done had she got to move. and backward induction had to consider what player 2 would think that player 1 would have done were player 1 to get to move again so to do backward induction player 1 has to ask herself what player 2 is going to do and player 2 has to therefore ask herself what player 1 would have done which means player 1 has to ask herself what player 2 thinks player 1 would have done which means we actually needed to say what player one did over here.

[译文 33]

At the end. Okay. So the end here is player 1, and player 1 will choose here to go down. Is that right? Because 3 is bigger than 2. So if we roll back to player 2’s move, player 2, if she chooses left, she knows that she’ll be followed by player 1 going down, in which case she’ll get 1, but if she chooses right, she’ll get 2. So player 2 will choose right. So player 1 here, if she chooses up, then player 2 will choose right and player 1 will get 0. And if she chooses down, she’ll get 1. So player 1 will choose down. So backward induction suggests that player 1 will choose down and followed by player 2 if player 2 did get to move, she’d choose right. Followed by player 1, if she did get to move again, choosing down again. Notice that backward induction had to tell us what player 2 would have done had she got to move. And backward induction had to consider what player 2 would think that player 1 would have done were player 1 to get to move again. So to do backward induction player 1 has to ask herself what player 2 is going to do and player 2 has to therefore ask herself what player 1 would have done which means player 1 has to ask herself what player 2 thinks player 1 would have done which means we actually needed to say what player one did over here.

[段 34]

Let me say it again. So backward induction here tells us that player one chooses down in which case the game is over. But to do backward induction, to think through backward induction we really needed to consider not just what player two was going to do were he to get to move but also what player two would think player one would do were player two to get to move and were to choose left So all of these redundant moves were actually part of our backward induction. We need them there so we can think about what people are thinking. All right, so backward induction tells us that the outcome of the game is down. All right, but it tells us in terms of strategies, player one chooses down and were she to get to move again, would choose down again. And player two chooses right. All right. Now let’s analyze this game a totally different way. we now know what the strategies are in the game player 2 has 2 strategies left and right sorry, player 2 has 2 strategies left and right and player 1 has 4 strategies up, up, up, down down, up, and down, down alright so let’s write up the matrix for this game alright so here it is it must be a 4 by 2 matrix player 2 is choosing between left and right and player 1 is choosing between her four strategies up-up, up-down, down-up, and down-down.

[译文 34]

让我再说一遍。所以反向 induction 告诉我们，玩家一选择 down，在这种情况下游戏结束。但是为了进行 backward induction，为了思考 backward induction，我们真的需要考虑不仅玩家二在他得到行动机会时会做什么，而且还有玩家二会认为玩家一在玩家二得到行动机会并选择 left 时会做什么。所以所有这些冗余的移动实际上是我们 backward induction 的一部分。我们需要它们在那里，这样我们才能思考人们在思考什么。好的，所以 backward induction 告诉我们游戏的结果是 down。好的，但它以策略的形式告诉我们，玩家一选择 down，如果她再次得到行动机会，她会再次选择 down。玩家二选择 right。好的。现在让我们用一种完全不同的方式分析这个游戏。我们现在知道这个游戏中的策略是什么，玩家二有 2 个策略 left 和 right，抱歉，玩家二有 2 个策略 left 和 right，玩家一有 4 个策略 up-up、up-down、down-up 和 down-down。好的，让我们为这个游戏写出矩阵。好的，就是这样，它必须是一个 4 乘 2 的矩阵，玩家二在 left 和 right 之间选择，玩家一在她的四个策略 up-up、up-down、down-up 和 down-down 之间选择。

[段 35]

And we can put all the payoffs in. So up, up, left gets us to here, which is 2, 4. Up, up, up, right gets us here, which is 0, 2. Up, down, left gets us here, which is 3, 1. Up, down, right gets us here again, which is 0, 2. And down up gets us going right out of the game immediately, so we’re going to go to 1, 0. And in fact, that’s also true for down up right. And it’s also true for down down left. And it also true for down down right So all of these four strategies at the bottom started off by player 1 choosing down in which case the game is over So once again in this matrix you can kind of see the redundancy I was talking about In this matrix, the third row, the down-up row, looks the same as the down-down row. Everyone’s happy with that? All right. So we’ve had matrices in the past. How have we solved the game? Now we’ve been doing this backward induction stuff for a couple of weeks, but prior to the midterm, if I’d simply given you this on the midterm, what would you have done? You’d just looked for Nash equilibrium, right? So let’s do that. Let’s look for Nash equilibrium. So if player 2 chooses left, then player 1’s best response is up, up.

[译文 35]

我们可以把所有的收益填进去。所以，上、上、左把我们带到这里，也就是2, 4。上、上、上、右把我们带到这里，也就是0, 2。上、下、左把我们带到这里，也就是3, 1。上、下、右又把我们带到这里，也就是0, 2。而下上让我们立即退出游戏，所以我们会得到1, 0。实际上，下右上也是一样的。下下左也是一样的。下下右也是一样的。所以这四个底部策略都始于player 1选择下，此时游戏结束。所以在这种情况下，参与者1的收益是1, 0。一旦参与者的收益被确定，我们就完成了这个策略分析。矩阵中的冗余反映了博弈中的对称性和均衡策略。理解了这一点有助于简化复杂的博弈场景。纳什均衡是我们分析的关键，每个参与者都在寻找最优策略。 So once again in this matrix you can kind of see the redundancy I was talking about. So in this matrix, the third row, the down-up row, looks the same as the down-down row. Everyone’s happy with that? All right. So we’ve had matrices in the past. How have we solved the game? Now we’ve been doing this backward induction stuff for a couple of weeks, but prior to the midterm, if I’d simply given you this on the midterm, what would you have done? You’d just looked for Nash equilibrium, right? So let’s do that. Let’s look for Nash equilibrium. So if player 2 chooses left, then player 1’s best response is up, up.

[段 36]

And if player 2 chooses right, then player 1’s best response is either down up or down down alright conversely if player 1 chooses up up then player 2’s best response is left if player 1 chooses up down then player 2’s best response is right if player best response is left. If player 1 chooses up-down, then player 2’s best response is right. If player 1 chooses down-up, then player 2 doesn’t care because they’re getting 0 anyway. And if player 1 chooses down-down, then again player 2 doesn’t care because they’re getting 0 anyway. so the Nash Equilibrium in this game are what? so one of them is here so that’s one Nash Equilibrium so one of them is down, down followed by right and that’s a Nash Equilibrium we actually found by backward induction. The Nash equilibrium down, down, right corresponds to the one we found by backward induction. But there’s another Nash equilibrium in this game. The other Nash equilibrium in this game is this one That also a Nash equilibrium And what does it involve It involves down up and right Down, up, and right. Sorry, down, up, and right. Down, up, and right. So what happened in that equilibrium? him. Player one went down, which made everything else kind of irrelevant. Player two played right, and player one, in their plan of action, was actually going to choose up.

[译文 36]

如果 player 2 选择右边，那么 player 1 的最优反应是 down up 或者 down down。好的，相反地，如果 player 1 选择 up up，那么 player 2 的最优反应是 left。如果 player 1 选择 up down，那么 player 2 的最优反应是 right。如果 player 最佳反应是 left。如果 player 1 选择 up down，那么 player 2 的最优反应是 right。如果 player 1 选择 down up，那么 player 2 无所谓，因为他们反正得到 0。如果 player 1 选择 down down，那么 player 2 同样无所谓，因为他们反正得到 0。所以这个博弈中的纳什均衡是什么？所以其中一个在这里，所以这是一个纳什均衡。其中一个是 down, down 然后 right，这是一个纳什均衡，我们实际上是通过逆向归纳法找到的。纳什均衡 down, down, right 对应我们通过逆向归纳法找到的那个。但这个博弈中还有另一个纳什均衡。这个博弈中的另一个纳什均衡是这一个，这也是一个纳什均衡。它涉及什么？它涉及 down, up 和 right。抱歉，down, up 和 right。down, up 和 right。那么在这个均衡中发生了什么？他。Player 1 选择了 down，这使得其他一切都变得无关紧要了。Player 2 选择了 right，而 player 1 在他们的行动计划中实际上是打算选择 up 的。

[段 37]

Let’s say it again. Player one, in fact, went down. Player two, had they got to move, would have chosen right, right? And player one, had they got to move at this second time, would have chosen up. So how can that be a Nash equilibrium? It doesn’t correspond to backward induction. In particular, player one, player one up here, is choosing a strategy that seems silly. They’re choosing up rather than down, which gets them two rather than three. So how could it possibly be that that an equilibrium strategy The reason it can be an equilibrium strategy is it doesn really matter what player one chooses up here from player one’s point of view, because it’s never going to be reached anyway. As long as player two is going to choose little right here, as long as player two is choosing right, it really doesn’t matter what player one decides to do up there. From player one’s point of view, it doesn’t make a difference, it isn’t reached anyway. All right? So we’re highlighting here a danger. And the danger is this. If you just mechanically find the Nash Equilibria in a game, you’re going to find people choosing actions that if they ever were called upon to make them, are silly. Say that again. If you just mechanically find the Nash Equilibria in the game, just as we did here, you’re going to select some actions, in this case an action by player one, that were she called upon to take that action would be a silly action.

[译文 37]

再重复一遍。玩家一实际上选择了down。玩家二，如果轮到他走，他会选择right，对吧？而玩家一，如果第二次轮到他走，他会选择up。那怎么可能是一个Nash均衡呢？它并不符合逆向归纳。尤其值得注意的是，玩家一，处在上方的玩家一，选择了一个看起来很愚蠢的策略。他选择up而不是down，这样只能得到2而不是3。那怎么可能是一个均衡策略呢？它之所以可能是一个均衡策略，是因为从玩家一的角度看，他在那里选什么其实根本无关紧要，因为它根本就不会被达到。只要玩家二打算在这里选择right，只要玩家二选择right，玩家一在那里决定做什么真的无所谓。从玩家一的角度看，这没有区别，因为它反正不会被达到。明白了吗？这里我们要强调的是一个危险。这个危险就是：如果你们只是机械地找出博弈中的Nash均衡，你们会发现人们选择的行动——如果真的需要他们做出那些行动的话——是愚蠢的。再说一遍。如果你们只是机械地找出博弈中的Nash均衡，就像我们这里做的一样，你们会挑选出一些行动，在这个例子中是一个玩家一的行动，如果真的让她采取那个行动，那会是一个愚蠢的行动。

[段 38]

And the reason it’s surviving our analysis is because in fact she isn’t called upon to make it. Alright. Now to make that more concrete, let take this to an economic example This same idea Alright. So what I want you to imagine is a market. And in this market, there is a monopolist who controls the market, but there’s an entrant who is thinking of entering into this market. So right now, this market has a monopoly in it. And the monopolist is an incumbent. Let’s call him Inc. And there’s an entrant who is trying to decide whether or not to enter the market or whether to stay out. If they stay out, then the entrant gets nothing and the incumbent continues to get monopoly profits. Think of this as 3 million a year. If the entrant enters, then the incumbent can do one of two things. The incumbent could choose to fight the entrant, by which I mean charge low prices, advertise a lot, try and drive him out of the market. He could pay very competitively, in which case the entrant will actually make lots which I mean charge low prices, advertise a lot, try and drive them out of the market. It could pay very competitively, in which case the entrant will actually make losses and the incumbent will drive her profits down to zero.

[译文 38]

它之所以在我们的分析中存活下来，是因为实际上她根本不需要采取那个行动。好吧。现在为了让这个更具体，我们把这个带到经济例子中同样的想法。好吧。我想让你们想象的是一个市场。在这个市场中，有一个垄断者控制着市场，但有一个进入者正在考虑进入这个市场。所以现在，这个市场里有一个垄断者。这个垄断者是一个在位者。我们叫他Inc。有一个进入者正在试图决定是否进入这个市场还是留在外面。如果他们留在外面，那么进入者什么都得不到，而在位者继续获得垄断利润。把这想象成每年300万美元。如果进入者进入，那么在位者可以做两件事之一。在位者可以选择与进入者战斗，我的意思是收取低价、大量做广告、试图把他赶出市场。他可以非常有竞争力地定价，这样进入者实际上会亏损，而在位者会把她的利润压到零。

[段 39]

Conversely, the incumbent could choose not to fight. If they don’t fight, then they’ll simply share the markets and they’ll both make, let’s say, corno profits or duopoly profits of a million each. So in this game, let’s just say again, there’s a market there, the monopolist is in the market and the monopolist is making three million a year, which seems pretty nice for the monopolist. The entrant is trying to decide whether to invade this market. If she invades this market, if she’s fought, she’s in trouble, but if the monopolist accommodates her, then they just go to duopoly profits and the entrant does very well, gets a million dollars in profit. Alright, let’s have a look at this game, analyzed, first of all this time, let’s analyze it by Nash Equilibrium. Alright so I claim in this game this is pretty simple the entrant has strategies I put it straight into the matrix The entrant has two strategies They are either to go in or to stay out. And the incumbent has two strategies. They are either to fight the entrant or not to fight. All right. And the payoffs of this game are as follows. Let’s put them in. In and fight was minus 1, 0. In and not fight was 1, 1. And out led to the incumbents maintaining monopoly profits. Let’s have a look at the Nash Equilibria of this game.

[译文 39]

反过来，在位者可以选择不战斗。如果他们不战斗，那么他们就简单地分享市场，他们都获得，比如，cornor利润或双头垄断利润各100万美元。所以在这个博弈中，我们再说一遍，有一个市场，垄断者在市场中，垄断者每年赚300万美元，这对垄断者来说看起来很不错。进入者正在试图决定是否入侵这个市场。如果她入侵这个市场，如果遭到战斗，她就麻烦了，但如果垄断者容纳她，那么他们就进入双头垄断利润，进入者做得很好，赚100万美元。好吧，让我们看看这个博弈，首先用Nash均衡来分析。好吧，我声称在这个博弈中这很简单，进入者有策略我把它直接放进矩阵。进入者有两个策略。他们要么进入，要么留在外面。在位者有两个策略。他们要么与进入者战斗，要么不战斗。好吧。这个博弈的收益如下。让我们把它们放进去。进入且战斗是负1，0。进入且不战斗是1，1。退出导致在位者维持垄断利润。让我们看看这个博弈的Nash均衡。

[段 40]

All right. So the first thing to do is to look at the best responses for the entrance. so if the incumbent chooses fight, then the entrance best response is to stay out. If the incumbent chooses not fight, then the entrance best response is to enter. All right how about for the incumbent If the entrant chooses to come in then the incumbent best response is not to fight because 1 is bigger than 0 But if the entrant stays out it really doesn matter what the incumbent does They’ll get 3 either way. All right? So the Nash equilibria here are either in followed by not fighting. You end up with a duopoly. Or, out followed by fighting. Of course, the fight doesn’t take place. Out followed by, we would have fought had you entered. All right? So these are the Nash Equilibria. Let’s analyze this game by backward induction. All right? From the incumbent’s point of view, if the incumbent gets to move, then is she going to choose fight or not fight? She’s going to choose not fight. So the entrant should do what? Somebody? The entrant should enter because if she enters she gets 1, if she stays out she gets 0. So backward induction backward induction just gives us this equilibrium All right Now the question is, what do we think is going on at this other equilibrium?

[译文 40]

好吧。首先要做的是看进入者的最佳反应。所以如果在位者选择战斗，那么进入者的最佳反应是留在外面。如果在位者选择不战斗，那么进入者的最佳反应是进入。好吧，在位者呢？如果进入者选择进入，那么在位者的最佳反应是不战斗，因为1大于0。但如果进入者留在外面，在位者做什么真的无所谓。他们两种情况都会得到3。好吧？所以这里的Nash均衡要么是进入后跟着不战斗。你们最终得到一个双头垄断。或者，退出后跟着战斗。当然，战斗并没有发生。退出后跟着，我们会说如果你进入我们就会战斗。好吧？这些就是Nash均衡。让我们用逆向归纳分析这个博弈。好吧？从在位者的角度来看，如果轮到在位者走，她会选择战斗还是不战斗？她会选择不战斗。所以进入者应该做什么？有人回答吗？进入者应该进入，因为她如果进入得到1，如果留在外面得到0。所以逆向归纳逆向归纳给我们的就是这个均衡好吧。现在的问题是，我们认为在另一个均衡上会发生什么？

[段 41]

Let’s talk it through. All right, so here you are, and you’re about to enter the market. You leave Yale, you set up your business, and your business is challenging some monopolist or quasi-monopolist like Microsoft, say, and you go out there and you’re about to put out your new operating system. And you know that your new operating system will make plenty of money provided Microsoft doesn’t retaliate and drop its prices by half and advertise you out of the market. So what does Bill Gates do? Bill Gates, the head of Microsoft. He says, wait a second, before you graduate from Yale and go and set up this company, let me just tell you, I’m going to fight. If you enter, I’m going to fight. And if you believe him, if you believe that he’s going to fight, what should you do? You’re not going to bother to enter his market. If you believe that you’re going to get fought by Bill Gates, then you believe that if you enter, you’re going to make losses, so you choose to stay out. And this threat, this threat that Bill Gates makes here, it doesn’t cost him anything, provided you go out, he doesn’t actually have to fight at all. That’s why it is in fact an equilibrium to imagine you staying out, believing that you’re going to get fought if you enter. and it is the best response for the guy to fight knowing that you’re going to stay out.

[译文 41]

让我们来谈谈这个。好吧，所以你现在在这里，你即将进入市场。你离开耶鲁，创办你的公司，而你的公司正在挑战一些垄断者或准垄断者，比如微软，你走出去即将推出你的新操作系统。你知道只要微软不反击、不把价格减半、不用广告把你挤出市场，你的新操作系统会赚很多钱。那比尔·盖茨会怎么做？比尔·盖茨，微软的负责人。他说，等一下，在你从耶鲁毕业去创办这家公司之前，让我告诉你，我会战斗。如果你进入，我会战斗。如果你相信他，如果你相信他将要战斗，你应该做什么？你不会去费心进入他的市场。如果你相信你会被比尔·盖茨战斗，那么你相信如果你进入，你会亏损，所以你选择留在外面。而这个威胁，比尔·盖茨在这里发出的这个威胁，只要你不进入，他根本不需要真的战斗，所以这对他没有任何成本。这就是为什么想象你留在外面、相信你如果进入就会被战斗实际上是一个均衡，而战斗是知道你会留在外面的那个人的最佳反应。

[段 42]

But this doesn’t sound right. Why doesn’t this sound right? It doesn’t sound right because you really shouldn’t believe the guy who says he’s going to fight you when you know that if you did enter fighting would cost the incumbent money. If you did enter, if he fights you he gets zero if he doesn’t fight he gets a million dollars. So this threat that the guy is going to fight you, this threat is not credible. This is an equilibrium but it relies on believing an incredible threat It’s true that if you think about entering the market that Microsoft is in, you’re very likely to get a little email from Bill Gates, and it won’t be an email because that can be taken to court, but some little threatening remark in your ear from Bill Gates. It’s true if you entered into the market that the people who build aircraft in, the head of Boeing, might pay you a call one day or send someone round. But these threats are not credible threats. Is that right? They’re not credible threats because we know that if you did enter, it isn’t in their interest to fight. They’re making a lot of noise about it, but you know that if you did enter, backward induction tells us they’re not going to fight. All right? But now we’re in slightly an odd situation.

[译文 42]

但这听起来不对。为什么这听起来不对？这听起来不对是因为你真的不应该相信那个说你要进入时他会战斗的人，当你知道如果你真的进入，战斗会让在位者损失金钱。如果你真的进入，如果他战斗他得到零，如果他不战斗他得到一百万。所以这个人要战斗你这个威胁，这个威胁是不可信的。这是一个均衡，但它依赖于相信一个不可信的威胁。确实，如果你考虑进入微软所在的市场，你很可能会收到来自比尔·盖茨的一封邮件，那不会是邮件因为那可以被带上法庭，但会是来自比尔·盖茨在你耳边的一句威胁性的话。确实，如果你进入飞机制造商所在的市场，波音的负责人可能有一天会拜访你或派人来。但这些威胁不是可信的威胁。对吗？它们不是可信的威胁，因为我们知道如果你真的进入，战斗并不符合他们的利益。他们在制造很多噪音，但你知道如果你真的进入，逆向归纳告诉我们他们不会战斗。好吧？但现在我们处于一个稍微奇怪的情况。

[段 43]

All right? Why are we in an odd situation? Two things. One we seem to be finding that there are Nash equilibria in games We found one here and one up here There are Nash equilibria that are not supported by backward induction That’s the first reason we’re a little worried here. And the second reason we’re worried is even the economics of this doesn’t quite smell right. right? For example if you in fact did enter, sorry if you did in fact announce you were going to operate you were going to build a new operating system and got a threatening call from Bill Gates, there might be a reason why you might actually believe that call. Why might you believe that call? Why might you believe that call? Can we get a mic out? Let me try, I’ll do it So why might you believe a call from Bill Gates saying he’s going to beat you up not beat you up, but he’s going to charge low prices if you produce an operating system. If you look at the future revenue streams, like for the next 10 years, and he consistently gets $1 million for the next 10 years, he would be better off if he just drove you out of the market for the first year and then get $3 million for the next nine years. All right.

[译文 43]

好的？为什么我们处于一个奇怪的境况？两个原因。一个是我们似乎发现博弈论中存在纳什均衡。我们在这里找到一个，在那里也找到一个。有些纳什均衡不能通过逆向归纳法来支撑，这是我们在这里有点担心的第一个原因。我们担心的第二个原因是，这其中的经济学原理也有些不对劲，对吧？例如，如果你真的进入市场，对不起，如果你真的宣布你要运营，你要开发一个新的操作系统，然后接到比尔·盖茨的威胁电话，你可能就有理由相信那个电话。你为什么可能会相信那个电话？你为什么可能会相信那个电话？有人能递个麦克风吗？让我试试，我来。那么，你为什么可能会相信比尔·盖茨的电话呢？他说他不是要揍你，而是如果你开发操作系统，他要收取低价。如果你看未来的收入流，比如未来10年，他连续10年每年获得100万美元，但如果他在第一年就把你赶出市场，然后接下来的9年每年获得300万美元，他会更划算。好的。

[段 44]

Yeah, okay, that wasn’t quite what I was thinking. Okay it true if we cheat a bit and make one of the Okay so what you saying is I could get three forever versus one forever Assume these are both present discounted values of future cash earnings all right So we done the future cash flow analysis of this right So this isn an accounting mistake, all right? Not for accounting reasons. There’s some other reason why Gates, when Gates threatens you, you might want to believe it. Let me try up here first. You can afford to make an example of you so no other people will invade. Right, right. So one thing that’s in Bill Gates’ mind is he’s right now he’s thinking about competing with you, right? But down the road, there’s a lot more of you guys coming, right? There’s whatever it is, 280 of you in this room, and there’s another 280 in next year’s class and so on. And Bill Gates knows that each of you might come out and threaten his monopoly, his Microsoft monopoly. And he might think that by setting an example to one of you, he might be able to keep the others out. And somewhere, that kind of argument, the argument of making an example of somebody, is missing here. Missing completely. But it’s got to be important, right?

[译文 44]

是的，好的，那不是我刚才想的。好的，如果我们在一定程度上作弊，把其中一个 OK 所以你说的意思是，我可以永久获得三而不是永久获得一 假设这些都是未来现金收益的现值，好的 所以我们做了这个未来现金流分析，对吧？所以这不是会计错误，对吧？不是因为会计原因。比尔·盖茨在威胁你时，你可能想要相信他有其他原因。让我先试试这边的人。你能负担得起拿一个人开刀，这样就没有其他入侵者了。对，对。所以比尔·盖茨脑子里想的一件事是，他现在正在考虑和你竞争，对吧？但在未来，有更多的你们会出现，对吧？这间教室里不管有多少人，你们有280人，明年还有280人在下一个班级，等等。比尔·盖茨知道你们每个人可能都会出来威胁他的垄断，他的微软垄断。他可能会认为，通过拿你们其中一个人开刀，他可能能够让其他人被挡在外面。在某种程度上，这种拿某人开刀的论点，这里完全缺失了。完全缺失了。但它一定很重要，对吧？

[段 45]

It’s got to be an important idea. All right? So we’re going to come back and spend the first half of Wednesday’s class picking up just precisely that idea.

[译文 45]

它一定是一个重要的想法。好的？所以我们下周三前半节课会回来专门讨论这个想法。