海纳百川
登录 | 登录并检查站内短信 | 个人设置 网站首页 |  论坛首页 |  博客 |  搜索 |  收藏夹 |  帮助 |  团队  | 注册  | RSS
主题: 【博弈论漫谈】自动机与博奕策略 by云儿
回复主题   printer-friendly view    海纳百川首页 -> 罕见奇谈
阅读上一个主题 :: 阅读下一个主题  
作者 【博弈论漫谈】自动机与博奕策略 by云儿   
秋实
[博客]
[个人文集]

游客
文章标题: 【博弈论漫谈】自动机与博奕策略 by云儿 (972 reads)      时间: 2001-12-20 周四, 上午4:17
作者：Anonymous 在 罕见奇谈 发贴, 来自 http://www.hjclub.org

【博弈论漫谈·囚犯博弈】



自动机与博奕策略



·云 儿·





　　现在开侃无限重复博奕理论。所谓无限次重复博奕，其实并不是说，

人们可以将博弈无穷无尽无休无止地玩下去。打个比方，尽管人的寿命是

有限的，但在某种意义上，我们却也可说人活的天数是没有限制的。普通

人过了今天，还有明天。明天死亡概率虽然不是０，可也不是１。哪怕死

亡的几率再接近于１，只要我不能肯定我明天必死无疑，明天就永远有意

义。无限次重复博奕，也可在这个意义上理解：每玩一次之后，下一次再

玩的几率都不是０。我永远都无法肯定，这次以后，就一定没有下一次了

。在这个意义上，我们可以说，人生博奕更接近于无限重复博奕模型。



　　重复博奕不同于一次性博奕的地方在于，个人的策略，不再是具体的

行为，而是一套行为规则。具体的行为，一般要通过不同行为规则的互动，

才能产生。我们知道，二次重复博奕有８种博奕策略，三次重复则有６４

种策略。随着重复次数增加，个人可选策略的集合以指数增长。一旦重复

博奕次数变为无穷，可选择的策略便成了一个不可数集合。这个集合太大，

我们目前还没有办法去描述他的结构。重复博奕理论就把注意力集中在它

的一个可数子集－－那些可以用有限状态自动机来描述的策略。



　　这里，以博奕论普及读物里谈得较多的几种策略为例，看看自动机是

如何描述行为规则的。先从最简单的自动机谈起。



　　一元自动机有两种。其特点，都是只有一种状态，一门心思到底，不

是永远的傻客，就是永远的恶棍。如下图所示：



　　　　┌──┐　　　　　　　┌──┐

　　　　↓　　│ＨＤ　　　　　↓　　│ＨＤ

　　　┌─┐　│　　　　　　┌─┐　│

　　→│Ｈ├─┘　　　　　→│Ｄ├─┘

　　　└─┘　　　　　　　　└─┘

　ａ、固执的傻客　　　　ｂ、固执的恶棍



　　图ａ描述固执的傻客。方框Ｈ代表合作心态。方框上的循环箭头表示，

无论对方玩合作（Ｈ）还是欺骗（Ｄ），他自己永远都停留在合作心态之

中，坚持玩合作不动摇。类似地，图ｂ代表固执的恶棍，满脑子都是欺骗

（Ｄ），合作的事儿，想都不想。



　　二元自动机，顾名思义有两种心态。个人根据对方前几次选择行为的

不同，可以在这两种心态间跳来跳去。这类机器共有２４种，我们介绍几

种好玩的。





１、冷血报复策略。



　　　　┌──┐　　　　┌──┐

　　　　↓　　│Ｈ　　　↓　　│ＨＤ

　　　┌─┬─┘　　　┌─┐　│

　　→│Ｈ├────→│Ｄ├─┘

　　　└─┘　Ｄ　　　└─┘



　　图中每个方框代表一种心态。最左面的空箭头代表入口。博奕开始，

这个策略首先进入方框Ｈ，选择合作。此后，如方框上的循环箭头所示，

只要对方上一次玩合作Ｈ，我就保持合作心态Ｈ，仍跟他玩合作。然而，

倘若他上一次玩欺骗Ｄ，我就进入方框Ｄ。这是一种报复心态。此后无论

对方玩什么，我都不为所动，只跟他玩欺骗。



　　我们可以把心态Ｄ解读为“决不饶恕对手”：只要你欺骗一次，我就

再也不同你玩合作；那怕你此后次次玩合作，向我百般讨好，也不能使我

改变主意。给它取名“冷血报复”，原因就在于此。





２、仁厚恕道策略



　　　　┌──┐　　　　┌──┐

　　　　↓　　│Ｈ　　　↓　　│Ｄ

　　　┌─┬─┘　　　┌─┬─┘

　　→│Ｈ├────→│Ｄ│

　　　└─┘　Ｄ　　　└┬┘

　　　　↑　　　　　　Ｈ│

　　　　└───────┘



　　这就是著名的“一报还一报（ｔｉｔ　ｆｏｒ　ｔａｔ）”。古代墨

子鼓吹的“吾先从事”和“投桃报李”，可说是对它的最佳概括。它有一

个非常仁厚的起点：我先玩合作。然后，就是“以德报德，以直报怨”。

你玩合作我下次也合作，如果你玩欺骗，那么我就进入心态Ｄ，下次也玩

欺骗。而且，只要你继续玩欺骗，我就继续以欺骗相报复。但此策略与冷

血报复策略不同，不会永远停留在报复心态。在心态Ｄ，只要对方玩一次

合作Ｈ，就可以取得谅解，又回到合作心态Ｈ，重新玩过。



　　允许犯错误，也允许改正错误，以忠恕之心待人，所以叫恕道策略。





３、流氓侠义策略



　　　　┌──┐　　　　┌──┐

　　　　↓　　│Ｈ　　　↓　　│Ｄ

　　　┌─┬─┘　　　┌─┬─┘

　　　│Ｈ├────→│Ｄ│←

　　　└─┘　Ｄ　　　└┬┘

　　　　↑　　　　　　Ｈ│

　　　　└───────┘



　　此策略与上面的仁厚恕道策略相同，唯一的差别，是入口在右面的方

框上。它假定别人是恶棍，所以首先进入心态Ｄ，耍流氓玩欺骗。但是，

如果对方玩一次合作Ｈ，证明自己不是恶棍，他也就进入合作心态Ｈ，以

仁厚恕道待人。可见，既耍流氓，又不失侠义，这是它的特点。



　　不难看出，仁厚恕道与流氓侠义互为镜象。仁厚恕道策略遇到一次欺

骗行为，便转入了流氓侠义策略。相反，流氓侠义策略遇到一次合作行为，

便转入仁厚恕道策略。记住这一点，对于了解这两个策略的稳定性，会有

帮助。





４、流氓主义策略



　　　　┌──┐　　　　┌──┐

　　　　↓　　│Ｈ　　　↓　　│Ｈ

　　　┌─┬─┘　　　┌─┬─┘

　　→│Ｄ├────→│Ｈ│

　　　└─┘　Ｄ　　　└┬┘

　　　　↑　　　　　　Ｄ│

　　　　└───────┘



　　与前三种策略相比，这个策略极为不善。它的入口，方框Ｄ，代表一

种“宰客”的心态：它首先玩欺骗，然后，只要对方傻乎乎地仍然玩合作，

他就接着大玩欺骗，继续宰客抢便宜。只有当对方玩一次欺骗，证明自己

不是傻客之后，它才进入合作心态，方框Ｈ。然后就是以合作对合作。假

如对方不跟着玩合作，玩欺骗宰客的话，则又回到宰客心态Ｄ，彼此对宰，

看谁宰得过谁。



　　见傻客就欺负，见强者就合作。我觉得这个很象某些网上热血激愤之

士提倡的国际流氓主义，所以给它取了这个名字。





　　以上讲的是二元自动机。三元自动机的数目更多，咱们只介绍一个作

为样品。下面这个摇摆策略，有点象流氓主义与冷血报复的杂交品种：



　　　　┌──┐　　　　　　　┌──┐

　　　　↓　　│Ｈ　　　　　　↓　　│ＨＤ

　　　┌─┬─┘　┌─┐　　┌─┐　│

　　→│Ｄ├──→│Ｈ├─→│Ｄ├─┘

　　　└─┘Ｄ　　└┬┘Ｄ　└─┘

　　　　↑　　　　Ｈ│

　　　　└─────┘



　　首先进入第一个方框，宰客心态Ｄ，大宰玩合作的傻客。直到遇见玩

欺骗不受宰的，就约好下一次都玩合作，转入第二个方框，合作心态Ｈ。

如果对方违约欺骗，则进入第三个方框，冷血报复心态Ｄ。否则，回到第

一方框，继续宰客。



　　除此以外，还有各种更多状态的有限自动机，可以描述更复杂的行为

规则。事实上，凡是我们能够设想出来的行为规则，绝大多数都可用某个

有限自动机来描述。有兴趣的朋友不妨自己去画框图，我就不一一列举了。



２０００年１０月１７日草





作者：Anonymous 在 罕见奇谈 发贴, 来自 http://www.hjclub.org
返回顶端
显示文章:     
回复主题   printer-friendly view    海纳百川首页 -> 罕见奇谈 所有的时间均为 北京时间


 
论坛转跳:   
您不能在本论坛发表新主题
您不能在本论坛回复主题
您不能在本论坛编辑自己的文章
您不能在本论坛删除自己的文章
您不能在本论坛发表投票
您不能在这个论坛添加附件
您不能在这个论坛下载文件


based on phpbb, All rights reserved.
[ Page generation time: 6.619624 seconds ] :: [ 27 queries excuted ] :: [ GZIP compression enabled ]