Welcome Guest ( Log In | Register )

欢迎访问本站。游客仅能浏览首页新闻、版块主题、维基条目与资源信息,需登录后方可获得内容发布、话题讨论、维基编辑与资源下载等权限。若无账号请先完成注册流程。
 
Reply to this topicStart new topic
> 囚徒困境 - 纳什均衡
每周虎
2008-03-25, 15:30
Post #1


以两头下注开局背刺盟友收场还自认不够drow的MADCAT
Group Icon
 796
   2

Group: Planer
Posts: 540
Joined: 2007-02-17
Member No.: 10595


博弈论(Game Theory)对人的基本假定是:人是理性的(Rational), 在具体策略选择时的目的是使自己的利益最大化,通常的理解就是——自私的。自私博弈论研究的是理性的人之间如何进行策略选择的。

纳什(John Nash)编制的博弈论经典故事“囚徒的困境”,说明了非零和博弈及其均衡解的成立,故称"纳什平衡"。纳什均衡是指这样一种均衡:在这一均衡中,每个博弈参与人都确信,在给定其他参与人策略(strategies)决定的情况下,他选择了支配性策略以(Dominant Strategy,又称优势策略)回应对手的策略。也就是说,所有人的策略都是“最优的”。而讲解“纳什均衡”的最著名的案例就是“囚徒的困境”。


-----------------------囚徒的困境(Prison Dilemma)--------------------------------------

1950年,由就职于兰德公司的梅里尔•弗勒德(Merrill Flood)和梅尔文•德雷希尔(Melvin Dresher)拟定出相关困境的理论,后来由顾问艾伯特•塔克(Albert Tucker)以囚徒方式阐述,并命名为“囚徒困境”。经典的囚徒困境如下:

  警方逮捕甲、乙两名嫌疑犯(players),但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯,分别和二人见面,并向双方提供以下相同的选择:

  若一人认罪并作证检控对方(背叛,betray),而对方保持沉默,此人将即时获释,沉默者将判监10年。

  若二人都保持沉默(合作,cooperate),则二人同样判监半年。

  若二人都互相检举(背叛),则二人同样判监2年。

  用表格概述如下:

  甲沉默(合作) 甲认罪(背叛)

  乙沉默(合作) 二人同服刑半年 甲即时获释;乙服刑10年

  乙认罪(背叛) 甲服刑10年;乙即时获释 二人同服刑2年

  解说如下:
  如同博弈论的其他例证,囚徒困境假定每个参与者(即囚徒)都是利己的,即都寻求最大自身利益,而不关心另一参与者的利益。参与者某一策略所得利益,如果在任何情况下都比其他策略要低的话,此策略称为“严格劣势策略”(Strictly inferior strategy),理性的参与者绝不会选择。另外,没有任何其他力量干预个人决策,参与者可完全按照自己意愿选择策略。

  囚徒到底应该选择哪一项策略,才能将自己个人的刑期缩至最短?两名囚徒由于隔绝监禁,并不知道对方选择;而即使他们能交谈,还是未必能够尽信对方不会反口。就个人的理性选择而言,检举背叛对方所得刑期,总比沉默要来得低。试设想困境中两名理性囚徒会如何做出选择:

  若对方沉默、背叛会让我获释,所以会选择背叛。

  若对方背叛指控我,我也要指控对方才能得到较低的刑期,所以也是会选择背叛。

  二人面对的情况一样,所以二人的理性思考都会得出相同的结论——选择背叛。背叛是两种策略之中的支配性策略。因此,这场博弈中唯一可能达到的纳什均衡,就是双方参与者都背叛对方,结果二人同样服刑2年。

  这场博弈的纳什均衡,显然不是顾及团体利益的帕累托最优(Pareto Optimality)解决方案。以全体利益而言,如果两个参与者都合作保持沉默,两人都只会被判刑半年,总体利益更高,结果也比两人背叛对方、判刑2年的情况较佳。但根据以上假设,二人均为理性的个人,且只追求自己个人利益。均衡状况会是两个囚徒都选择背叛,结果二人判决均比合作为高,总体利益较合作为低。这就是“困境”所在。例子漂亮地证明了:非零和博弈中,帕累托最优和纳什均衡是相冲突的。

然而,实际情况并非如此简单,我们很快将证明在重复的囚徒困境(IPD)中,纳什均衡会趋向于帕累托最优。

-------------------------------重复的囚徒困境(IPD)---------------------------

罗伯特•阿克塞尔罗德(Robert Axelrod)在其著作《合作的进化》中,探索了经典囚徒困境情景的一个扩展,并把它称作“重复的囚徒困境”(IPD)。在这个博弈中,参与者(实际为计算机程序)必须反复地选择他们彼此相关的策略,并且记住他们以前的对抗,并用单循环赛的方式将参赛程序两两博弈,以找出什么样的策略得分最高。

积分方法为:A和B各表示一个人,他们的选择是完全无差异的。选择C代表合作,选择D代表不合作。如果AB都选择C合作,则两人各得3分;如果一方选C,一方选D,则选C的得零分,选D的得5分;如果AB都选D,双方各得1分。

符号 分数 英文 中文(非术语) 解释
T 5 Temptation 背叛诱惑 单独背叛成功所得
R 3 Reward 合作报酬 共同合作所得
P 1 Punishment 背叛惩罚 共同背叛所得
S 0 Suckers 受骗支付 被单独背叛所获

若以个人选择得分而言,可得出以下不等式:T>R>P>S;若以整体获分而言,将得出以下不等式:2R>T+S或2R>2P。也就是说合作在团体而言是支配性策略。而重复博弈或重复的囚徒困境将会使参与者从注重T>R>P>S转变成注重2R>T+S。

第一轮游戏有14个程序参加,再加上阿克塞尔罗德自己的一个随机程序(即以50%的概率选取合作或不合作),运转了300次。结果得分最高的程序是加拿大学者阿纳托尔•拉波波特(Anatol Rapoport)写的“以牙还牙”(tit for tat)。这个程序的特点是,第一次对局采用合作的策略,以后每一步都跟随对方上一步的策略,你上一次合作,我这一次就合作,你上一次不合作,我这一次就不合作。

阿克塞尔罗德还发现,得分排在前面的程序有三个特点:第一,从不首先背叛,即“友善(Nice)”;第二,对于对方的背叛行为一定要报复,不能总是合作,即“报复(Retaliating)”;第三,不能人家一次背叛,你就没完没了的报复,以后人家只要改为合作,你也要合作,即“宽容(Forgiving)”。还有一点就是不嫉妒(Non-envious),就是说不去争取得到高于对手的分数(对于“友善”的策略来说这也是不可能的)。

为了进一步验证上述结论,阿克塞尔罗德决定邀请更多的人再做一次游戏,并把第一次的结果公开发表。第二次征集到了62个程序,加上他自己的随机程序,又进行了一次 竞赛。结果,第一名的仍是“以牙还牙”。阿克塞尔罗德总结这次游戏的结论是:第一,“以牙还牙”仍是最优策略。第二,前面提到的三个特点仍然有效,因为63人中的前15名里,只有第8名的哈灵顿程序是“不友善”,后15名中,只有1个总是合作的是“友善”。可激怒性和宽容性也得到了证明。此外,好的策略还 必须具有的一个特点是“清晰性”,能让对方在三、五步对局内辨识出来,太复杂的对策不见得好。“以牙还牙”就有很好的清晰性,让对方很快发现规律,从而不得不采取合作的态度。

阿克塞尔罗德又设计了一个实验,假设63个对策者中,谁在第一轮中的得分高,他在第二轮的群体中所占比例就越高,而且是他的得分的正函数。这样,群体的结构就会在进化过程中改变,由此可以看出群体是向什么方向进化的。
实验结果很有趣。“以牙还牙”原来在群体中占1/63,经过1000代的进化,结构稳定下来时,它占了24%。另外,有一些程序在进化过程中消失了。其中有一个值得研究的程序,即原来前15名中唯一的那个“不友善”哈灵顿程序,它的对策方案是,首先合作,当发现对方一直在合作,它就突然来个不合作,如果对方立刻报复它,它就恢复合作,如果对方仍然合作,它就继续背叛。这个程序一开始发展很快,但等到除了“以牙还牙”之外的其它程序开始消失时,它就开始下降了。因此,以合作系数来测量,群体是越来越合作的。

------------------------------多重通道策略-----------------------------------------------

尽管以牙还牙始终被认为是最可靠的基本策略,但是在重复囚徒困境的20周年纪念赛中,来英国南安普敦大学的一个小组(由尼古拉斯•詹宁斯(Nicholas Jennings)领导,包括了拉蒂普•达什(Rajdeep Dash)、萨瓦帕里•拉姆琼(Sarvapali Ramchurn)、亚历克斯•罗杰斯(Alex Rogers)斯和皮鲁克里士南•维特林根(Perukrishnen Vytelingum))介绍了一个新的策略,这个策略证明了它比以牙还牙更成功。这个策略依赖于程序之间的合作,为单一程序中获得了最高的点数。南安普敦大学提交了60个程序参与竞赛,这些程序的开头被设计成通过一组5到10个的动作去彼此识别。一旦这些识别被作出,一个程序将总是合作,其他程序则总是背叛,保证背叛者得到最大的点数。如果程序识别出它在操作一个非南安普敦参与者,这程序将持续地背叛,企图去最小化竞争程序的得分。结果,这个策略以获得前3位结束了竞赛,也得到了大量接近底部的位置。



最后,重复博弈在现实中是很难完全实现的。一次性博弈的大量存在,引发了很多不合作的行为,而且,对策的一方在遭到对方背叛之后,往往没有机会也没有还手之力去进行报复。比如,资本积累阶段的违约行为,国家之间的核威慑。在这些情况下,社会要使交易能够进行,并且防止不合作行为,必须通过法制手段,以法律的惩罚代替个人之间的“以牙还牙”,规范社会行为。这是阿克塞尔罗德的研究对制度学派的一个重要启发。





补充说明:

支配性策略:又称为优势策略(dominant Strategy)。在一个博弈当中,无论对手采取什么策略,你若有几个策略,而其中一个策略可以使你得到比采取其他策略更好的结果,那么,这个策略就是你的优势策略。

零和博弈:又称零和游戏(zero sum game),与非零和博弈相对,是博弈论的一个概念,属非合作博弈,指参与博弈的各方,在严格竞争下,一方的收益必然意味着另一方的损失,博弈各方的收益和损失相加总和永远为“零”。双方不存在合作的可能。

非零和博弈:非零和博弈(non-zero sum game)是一种非合作下的博弈,博弈中各方的收益或损失的总和不是零值,它区别于零和博弈。在这种状况时,自己的所得并不与他人的所失的大小相等,连自己的幸福也未必建立在他人的痛苦之上,即使伤害他人也可能“损人不利己”,所以博弈双方存在“双赢”的可能,进而合作。

帕累托最优:帕累托最优(PO)是指资源分配的一种理想状态。假定固有的一群人和可分配的资源,如果从一种分配状态到另一种状态的变化中,在没有使任何人境况变坏的前提下,使得至少一个人变得更好,这就是帕累托改善。帕累托最优的状态就是不可能再有更多的帕累托改善的状态;换句话说,不可能再改善某些人的境况,而不使任何其他人受损。

比赛:2004年度囚徒困境锦标赛结果显示高波•拉姆琼的南安普敦大学策略位于前3名,尽管与GRIM策略相比,有较少的胜利和更多的失败。(注意,在囚徒困境锦标赛中,博弈的目标不是“赢得”比赛——通过经常背叛,这很容易就能达到。)同样需要指出的是,即使在软件策略(由南安普敦大学的小组开发)之间没有隐 含结论,以牙还牙也不总是任何既定竞赛的绝对赢家。说得更确切些,它在一系列竞赛中的最终结果胜过它的对手。(在任何项目中,给定的策略能稍微比以牙还牙 更适应竞赛,但是以牙还牙更稳固)。这同样适用于附加宽恕变量的以牙还牙和其他最佳策略:在任何一天,它们可能无法“赢得”一个对抗策略的特别组合。



(IMG:style_emoticons/default/sleep.gif) 我本来还写了多边囚徒困境在强权外交中应用,不过想想还是不发的好~~

This post has been edited by 每周虎: 2008-03-26, 08:26
TOP
ywis
2008-03-25, 16:45
Post #2


主物质者
Group Icon
 43
   2

Group: Primer
Posts: 92
Joined: 2007-11-25
Member No.: 17587


发吧...我之前也想过写类似的,不过懒= =

本来还想推荐《自私的基因》后来考虑大家未必有兴趣.成书似乎比《合作的进化》早.和《合作的进化》有些类似,里面也是这样大量的例子.基本意思都是说一个基因的占有率增降直接和其他基因占有率是关联的,长久运行的话可以形成一个马尔可夫链(MARKOV CHAIN),从而达到多个可行的稳定状态中的某一个稳定状态.

《自私的基因》/《合作的进化》里的模型本可以适用于DIPLOMACY,但是DIPLOMACY的玩家不能很好的符合模型要求.最根本的一点就是在大多数模型中对利益分值的分派对每个个体都是一样的(比如TRPS的5310分配),这个在玩家身上很可能就不是这个情况.

另外就是每个玩家水平有差异,对局势的观察不同,造成对同一个局面的不同理解,无法符合"每个人都足够聪明的意识到自己行为有可能导致的若干连带效应"这个大多数模型里的假设.

最后一点就是人是有感情的,感情因素很可能导致他们的"非自私"行为.就如人类中存在舍己为人的个体一样,用搏弈学无法解释,只能尝试从种群基因方面解释.

尽管如此,《自私的基因》/《合作的进化》确实已经可以基本解释DIPLOMACY中出现的一些常见现象了.
TOP
auyeung
2008-03-25, 20:56
Post #3


主物质者
Group Icon
 -37
   0

Group: Primer
Posts: 48
Joined: 2006-10-07
Member No.: 9089


。。。
都搞起理論研究了
這哪個玩得贏
TOP
ywis
2008-03-25, 21:49
Post #4


主物质者
Group Icon
 43
   2

Group: Primer
Posts: 92
Joined: 2007-11-25
Member No.: 17587


尽管以牙还牙始终被认为是最可靠的基本策略,但是在重复囚徒困境的20周年纪念赛中,来英国南安普敦大学的一个小组(由尼古拉斯•詹宁斯(Nicholas Jennings)领导,包括了拉蒂普•达什(Rajdeep Dash)、萨瓦帕里•拉姆琼(Sarvapali Ramchurn)、亚历克斯•罗杰斯(Alex Rogers)斯和皮鲁克里士南•维特林根(Perukrishnen Vytelingum))介绍了一个新的策略,这个策略证明了它比以牙还牙更成功。这个策略依赖于程序之间的合作,为单一程序中获得了最高的点数。南安普敦大学提交了60个程序参与竞赛,这些程序的开头被设计成通过一组5到10个的动作去彼此识别。一旦这些识别被作出,一个程序将总是合作,其他程序则总是背叛,保证背叛者得到最大的点数。如果程序识别出它在操作一个非南安普敦参与者,这程序将持续地背叛,企图去最小化竞争程序的得分。结果,这个策略以获得前3位结束了竞赛,也得到了大量接近底部的位置。
----------------------------------------

这个很像我流……不过看来命不好,要去底部的位置了。
TOP
每周虎
2008-03-26, 01:44
Post #5


以两头下注开局背刺盟友收场还自认不够drow的MADCAT
Group Icon
 796
   2

Group: Planer
Posts: 540
Joined: 2007-02-17
Member No.: 10595


QUOTE(ywis @ 2008-03-25, 16:45) *

另外就是每个玩家水平有差异,对局势的观察不同,造成对同一个局面的不同理解,无法符合"每个人都足够聪明的意识到自己行为有可能导致的若干连带效应"这个大多数模型里的假设.

(IMG:style_emoticons/default/sleep.gif) 这个确实是个很头痛的事情,水平的差异和情报的不同,造成对局势的不同理解,从而影响沟通……
TOP
tigerrabbit
2008-03-26, 07:32
Post #6


经群众长期全面细致考察而认定的光荣团员,授予头衔“公开的好人”
Group Icon
 573
   4

Group: Avatar
Posts: 1232
Joined: 2007-09-05
Member No.: 15895


上面的人已经分析了那么多,于是我就不过多分析了。

囚徒困境是一个值得推荐的话题,因为它简单而实用,不仅仅是dip,更甚至于生活中还是有相当多的地方可以用到或者解释这个问题.

我转到纸上谈兵去了,经典文章大家共赏!!!
TOP
seeme
2008-04-29, 21:15
Post #7


主物质者
Group Icon
 -4
   0

Group: Primer
Posts: 19
Joined: 2008-04-21
Member No.: 20750


在一局游戏中以牙还牙貌似没什么意义,多局游戏中也许存在一定的意义
TOP
Fast ReplyReply to this topicStart new topic
 


Time is now: 2020-10-29, 03:57