策梅洛定理 (2-1)

如果就是策梅洛原文针对的那种游戏的话，那么策梅洛定理的backwards induction证明基本上就相当于提供了一个算法（文献中也常常叫Zermelo's algorithm）。

Algorithm 3.9 (Subgame perfect equilibrium) Input: An extensive game. Output:A subgame perfect Nash equilibrium of the game. Method:Consider, in increasing order of inclusion, each subgame of the game, find a Nash equilib- rium of the subgame, and replace the subgame by a new terminal node that has the equilibrium payoffs.

REDUCED STRATEGIC FORM 69

In a game with perfect information,every node is the root of a subgame. Then Algo- rithm 3.9 is the well-known, linear time bαckwαrd induction method, also sometimes known as“Zermelo's algorithm.”Because the subgame involves only one player in each iteration, a deterministic move is optimal,which shows that any game with perfect information has a (subgame perfect) Nash equilibrium where every player uses a pure strategy.

中文翻译：算法3.9（子游戏完美平衡）输入：一个广泛的游戏。输出：游戏的子游戏完美纳什均衡。方法：按照包含的递增顺序，考虑游戏的每个子游戏，找到该子游戏的纳什均衡，并用具有均衡收益的新终端节点替换该子游戏。缩减战略形式69在具有完美信息的游戏中，每个节点都是子游戏的根。算法3.9是众所周知的线性时间bαckwαrd归纳法，有时也称为“Zermelo算法”。因为子游戏在每次迭代中只涉及一个玩家，所以确定性移动是最优的，这表明任何具有完美信息的游戏都有（子游戏完美）纳什均衡，每个玩家都使用纯策略。

策梅洛考虑[1]的那些游戏的共同点就是它们的game tree是有穷的。也就是说，想象一棵数从游戏初始状态出发，下一个节点列举了第一个玩家行动回合的所有可能性，然后每一个节点都跟着第二玩家行动回合的所有可能性... 如此类推。然后整个树一共有有穷个节点。这时候，只要我们知道了规则，我们就可以可计算地根据规则的规定画出完整的game tree。

然后从每个终局（也就是最末端的节点）开始，根据1还是玩家2赢给该节点标上1或2。因为定理要求了没有平局，所以每个末端节点都标记上了1或2.

现在每个末端节点都标记上了1或2，我们来看倒数第二的节点。我们分情况讨论：

1. 如果某一个倒数第二的节点对应着玩家1行动的回合，并且它连着的某个末端节点标记为1，那么我们也把它标记为1；

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。