策梅洛定理

如果就是策梅洛原文针对的那种游戏的话，那么策梅洛定理的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；

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

3. 如果某一个倒数第二的节点对应着玩家1行动的回合，但是它连着的所有末端节点都标记为2，那么我们把它标记为2

4. 类似地，如果某一个倒数第二的节点对应着玩家2行动的回合，但是它连着的所有末端节点都标记为1，那么我们把它标记为1

如此类推。抽象一般地来说，我们根据规则为末端节点标记后，一步步往回开始标记，每步都根据已有的节点标记来决定要标什么，直到标记上原点为止。也就是说，如果我们准备标记玩家i 行动回合的一个节点 p ，而该节点紧连着一个已经标了 i 的节点，那么我们给 p 标上 i （意味着在 p 的局面时 i 占优） ；而如果 p 所有紧接的节点都标的是 i 的对手，那么我们就给 p 标上 i 的对手（意味着在 p 的局面时 i 的对手占优）.

这个标记法能够一路标记到原点，也就是游戏初始状态。此时原点根据递归规则标记的是谁，那么这局游戏就是谁有必胜策略（证明：如果初始状态是玩家1行动，并且标注是1，那么根据递归定义玩家1有办法一直将游戏局面保持在标注1的局面上直到终局；而如果是玩家1行动并且标注是2，这就意味着无论玩家1如何行动，接下来玩家2都有办法一直将局面保持在标注2的局面上直到终局。 如果初始状态是玩家2行动的话思路类似）。

这样的算法能够帮助我们在有穷游戏中判定先手还是后手必胜，只不过它很慢就是了，需要遍历完整个game tree。

参考

1. 严格来说策梅洛本人只考虑了国际象棋，但是现在说到策梅洛定理说的都是finite games

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。