博弈论之子博弈完美均衡

《博弈论之子博弈完美均衡》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六讲子博弈完美均衡本章是对上一章的补充和总结。我们首先讲解了NIM和Hex的求解方法，说明了虽然都是“后推求解法”，但是，这两种游戏的求解方法，与普通的“博弈树”死画到底不一样，它需要巧妙的分析。当然，这种“巧妙”来自于数学家们的成就。同学们可能会提出“为什么”这样的问题。为什么NIM会采取二进制的方法？为什么Hex会采取“策略小偷”的方法？这些都是不重要的，我们给出了文献的出处，供同学们参考。重要的是我们要知道“后推求解法”可以有多种多样的表现，并不是一成不变的，并不是生搬硬套的。在本章里，我们还给出了“鞍点策略”的定义。在这里，我们只要关注“鞍点策略”的位置及“鞍点”的形状。在后面，

2、我们还会联系最大最小定理来分析它。但是，在这里，我们给出的直观图形，能使同学们更加清楚地掌握“纳什均衡”在标准型博弈（即矩阵式表示）上的特征。理所当然地，我们对“鞍点策略”（纳什均衡）与“子博弈精炼均衡”的定义进行了比较，说明了它们之间的差别。很显然，正文中所举的《论持久战》的例子，是我个人的观点。它有助于说明了这两者的不同。第一节各种求解方法本节讨论了NIM游戏的玩法，也讨论了Hex游戏的玩法。这两个游戏的求解方法，都是“后推求解法”，尤其是NIM的二进制求解法。Hex的求解，本质上来说，我们是利用“纳什均衡”定理来求解的。不过，我们没有在这一部分深化它，我们利用Gale的论证，说明了“

3、Hex与布劳威尔不动点定理是一致的”，我们又利用汪丁丁老师的论证，说明了“布劳威尔不动点定理与纳什均衡定理是一致的”，所以，Hex有解，就意味着纳什均衡定理成立。这像是一个绕口令。同学们在学习这一节的时候，最好的方法，当然是自己设计一些例题来做一下。像NIM可以多做几组数字；像Hex可以做1414的情况。因为都是游戏，所以，是不必要专门设计题目的。总之，这里给出的方法，已经被数学家们检验过好多遍了。16.1“NIMWIN”游戏的解法上一章里，我们讨论的是“玫瑰博弈”，规定“谁拿到最后一支玫瑰，谁就算输”。我们采取的是“博弈树”的“后推求解法”。现在，我们把这个博弈向前推进一步，设计为下

4、面的题目：奥数6.1（NIM）三堆火柴分别有2001根、2002根、2003根。甲、乙两人轮流从中取火柴。规则是：每人每次只能从其中的一堆取，最少要取一根，最多可以全部取走，可以任意选择，谁取完最后一堆的最后一根就获胜。如果甲先取，要保证获胜，他应该制定怎样的策略。历史6.2(为什么叫NIM?)NIM游戏，可有不少种，古早时候就有了。有人说，这种游戏来自中国（它跟中国的“捡石子”游戏很相似）。但是，我们很难说得清它的起源。在欧洲，NIM的最早记录，可以追溯到16世纪去。就现代而言，NIM这个词是由CharlesL.Bouton创造出来的，他在1901年时，还研究出了全套的“相关的博弈理论”

5、。但是，NIM这个词，究竟来源于何处，还真是一直没说清楚过呢。可能吧，它来自德语里的nimm，意思是“拿”；也许吧，它来自英语里的那个废词nim。谁知道呢？说不定大家看到了，把WIN反过来，就看到了NIM!对于这样的一个“博弈”，依然是适用“倒推求解法”的。但是，如果用前面的画博弈树的形式，会让我们全班的人死在阵地上。我自己做过监考的老师，每次我看到一大堆的数值计算，就觉得该让那些出题的老师来做我的这个题，而2且，要求他们画这个题的博弈树，看他们想不想死！现代的科技已经发展到这一步了，很多计算只要知道原理就可以了，怎么还让学生来一个键一个键地按数字呢？因此，对于这个“博弈”，我们要想一下，

6、要再想一下，不要急于做出来。特例6.3（NIM的思维第一步）解答这类问题应从最基本的特例开始分析。我们用N表示石头的堆数，M表示总的石头数目。当N=1时，即只有一堆石头——显然无论你放多少石头，你的对手都能一次全拿光，你不能这样摆。好！再向前推进一步：关键6.4（安全策略的特征：NIM第二步）当N=2时，即有两堆石头，最简单的情况是每堆石头中各有一个石子（1，1）——先让对手拿，无论怎样你都可以获胜。我们把这种在双方理性走法下，你一定能够赢的局面叫作安全局面。推理6.5(不安全策略的特征：NIM第三步)当NM2,2时：既然(1,1)是安全局面，那么(1,x)都不是安全局面，因为对手只要

7、经过一次转换，就能把(1,x)变成(1,1)，然后该你走，你就输了。推理6.6（寻找安全策略：NIM第四步）既然(1,x)不安全，那么（2,2）如何？经过分析，（2，2）是安全的，因为它不能一步变成（1，1）这样的安全局面。这样我们似乎可以推理（3,3）、（4,4），一直到（X,X）都是安全局面。小结6.7(“安全策略”的简单命题)3于是我们初步总结，如果石头的数目是偶数，就把它们分为两堆，每堆有同样多的数目。这样无论对