[读书笔记] 当重复囚徒困境遇到自然选择

囚徒困境的故事太出名了,应该不用详细介绍吧……可能唯一值得说的是,如果令两个囚徒都合作的收益为R (reward),都背叛的收益为P (punishment),一方合作一方背叛则合作方得到 S (sucker)、背叛方得到T (temptation),那么一个经典囚徒困境必须是T > R > P > S. 不满足这个的就不是囚徒困境。

重复囚徒困境的故事这些年也慢慢出名了……如果是单次博弈,那么显然背叛永远优于合作。但是如果这个博弈要重复多次,那么合作就有了出头的机会。

Axelrod 做了一个名垂青史的实验:向全世界同行征集重复囚徒困境的策略,然后在计算机里让它们相互搏斗。第一次他征集到14个参赛者,最后获胜的出乎所有人意料是最简单的策略——Rapoport 提交的【“一报还一报” (TFT, tit for tat)】。它只有两条规则:开场先合作,然后重复对方上一次的策略。它单独出现时没用,但一群TFT相遇时,它们相互之间会合作获益、而对外则背叛不让别人占便宜。

做出来之后 Axelrod 把结果写成了一篇文章,附上了详细的分析,并邀请人们在研究过第一轮的经验教训后参加第二轮。第二轮他获得了63个参赛者,只有一个人原样提交了TFT策略——就是Rapoport本人。结果TFT又取得了胜利。

网上很多文章就讲到这里为止了,但是故事其实没有完。Axelrod 的实验里每个策略都是定死的,而对方的行为也是明确无误的,但自然界有突变、有噪音。如果把这些因素引入进来会如何?

————————————

所以 Nowak 做了一套新的实验,不是邀请全世界专家提交策略了,而是设一个大小合理的策略空间,允许每个个体在里面随机突变来选择策略。此外每次行为有一定概率产生噪音,比如对方明明应该出合作,但实际打出来变成了背叛。

起始值的策略是随机的。不出意外,这个一锅粥很快被【ALLD (永远背叛)】占据了。

但一段时间后会出现一小群抱团的个体,它们采用十分类似于TFT的策略,站住了脚跟。TFT永远是合作出现最好的催化剂,如果这个TFT群体足够大,那么合作会很快横扫整个群体。

可是TFT不是最后的胜利者,因为它无法应付噪音——两个本来合作得很好的TFT如果不小心遭遇一次误判,就会陷入一连串的背叛当中而失去优势。事实证明在TFT占主体的基础上,会产生一种新策略将TFT取代——也即【 GTFT(慷慨的一报还一报)】。它的特点是,即使对方出了背叛,下一轮也有一定的概率选择合作,这样就可以挽救陷入无穷背叛的可能。此所谓“自然选择发现了宽恕”。

还没完。在GTFT 一统天下之后,【ALLC (永远合作)】就会出现。在一个所有人都是好人的社会里,反击坏人的能力会变得失去意义。随机漂变的作用使得ALLC比例上升。而且ALLC比GTFT更能应对噪音——GTFT还要等几回合才会宽容,ALLC当即就能拉回合作的“正轨”。

前提是正轨必须存在。当GTFT让位于ALLC之后,就为永远背叛的 ALLD 入侵敞开了大门。ALLD 一旦出现就会掌握巨大的优势,凭借它的背叛将所有ALLC打趴下,迅速占据了主导地位。于是新一轮的循环开始。

这个ALLD - TFT - GTFT - ALLC - ALLD 的循环是极其普遍的,而且它的普遍不止存在于博弈论模型里——好人合作打败了坏人,多年以后好人放松了警惕、坏人于是东山再起,这个叙事模型在各种故事传说里都太普遍了(《魔戒》就是个好例子)。至于这能否作为现实人类历史上战争和平循环的抽象表述,那就见仁见智了。

——————————————

但是有一种办法可以打破这个循环,那就是引入“反思”机制。在扩大了策略空间之后, Nowak 等人意外发现了一个新的策略可以长期稳定存在——【“输则改之,赢则加勉” ( WSLS, win-stay, lose-shift )】。这个策略也很简单,如果我上一轮赚了便宜、获得了T或者R的结果(不记得这两个字母请回开头复习) ,那么这一轮我继续刚才的策略。如果我上一轮吃了亏、获得了S或者P,那么这一轮我就换成另一种策略。

如果两个 WSLS 相遇,它们大部分时间都合作。万一遭遇了噪音,那么下一轮双方都背叛;再下一轮双方又合作了。纠错延迟只有1回合。这一点比GTFT更强,只比ALLC 弱一点点。

但是WSLS有个王牌,使得它不怕ALLC。那就是在和ALLC交手一段时间后,它会发现ALLC完全不懂得背叛。WSLS只要发生一次偶然背叛,之后就是永久背叛,使得老好人 ALLC 遭受惨无人道的剥削。 这样一个WSLS不会随着时间推移而“放松警惕”变成ALLC,当然也就不会遭受ALLD的后续必然入侵。

唯一略微纠结的是面对ALLD。如果R > (T+P) / 2 ,那么WSLS不怕ALLD。如果不满足,那么实验表明最后稳定的是WSLS的一个变体——遭遇双方背叛 P 的时候不必然改变策略,而只是以一定概率改变策略。无论如何,这个反思策略一旦出现,就很难会落入前面提到的那个恶性循环了。
————————————


虽然以上只是一个极其粗糙的模型,但说实话,面对现实社会中的现象,真的很难不联想啊。

本文由Ent授权(果壳网)发表,文章著作权为原作者所有。
15条评论

  • 1楼
    2013-06-27 00:32 曹小喵回来了

    社会学的建模真是不直观啊……

    评论
  • 2楼
    2013-06-27 02:30 __INT

    我记得在看Axelrod的论文的时候,特意强调了,囚徒困境的参数要求有两条:
    1) T > R > P > S
    2) R > (T+P) / 2
    貌似wiki上也有类似的说法:https://zh.wikipedia.org/wiki/%E5%9B%9A%E5%BE%92%E5%9B%B0%E5%A2%83
    https://zh.wikipedia.org/wiki/%E5%9B%9A%E5%BE%92%E5%9B%B0%E5%A2%83

    ---------------------------------------------------------------------------------------------------------

    还有,“读书笔记”是指的哪本书?

    评论
  • 3楼
    2013-06-27 08:55 太平天国呜喵王薛顶饿

    求书名。
    或者Nowak的论文题目。

    评论
  • 4楼
    2013-06-27 10:10 Ent
    引用@__INT 的话:记得在看Axelrod的论文的时候,特意强调了,囚徒困境的参数要求有两条:1) T > R > P > S2) R > (T+P) / 2貌似wiki上也有类似的说法:---------...


    对于囚徒困境本体来说,没有第二项要求……
    第二项要求是在重复囚徒困境里的额外可选项。如果不满足R > (T+P) / 2的话,那么重复囚徒困境里的赢家就不会是TFT,而是合作/背叛相交替。

    书是Theoretical Ecology。

    评论
  • 5楼
    2013-06-28 21:49 __INT
    引用@Ent 的话:对于囚徒困境来说,没有第二项要求……第二项要求是在囚徒困境里的额外可选项。如果不满足R > (T+P) / 2的话,那么重复囚徒困境里的赢家就不会是TFT,而是合作/背叛相交替。书是Theo...

    我又重新读了一遍"How to Cope with Noise in the Iterated Prisoner's Dilemma",里面对WSLS的策略会占优进行了反驳,在噪音比例从0.1%到10%的区间内,GTFT=CTFT(悔悟的以牙还牙)>宽容的WSLS>WSLS。
    然后还有一个实验,在Axelord最初64中策略的状态中新加入 GTFT,CTFT,WSLS和宽容的 WSLS,67种策略共同演化,同样是1%的噪音水平(Nowak的论文中也是1%的噪音水平),CTFT远远优于其他策略。
    我个人认为这个反驳比较有力。

    然后我又翻回头看Nowak,看的是他的书Evolutionary Dynamics,其中第五章就是讲述的这个囚徒困境的演变。我猜测两者说法相矛盾的原因是因为有限种群,很容易由于漂变结果掉一个策略。相对于数学推导的结果来说,我个人还是对计算机模拟结果表示更为信服。

    评论
  • 6楼
    2013-06-28 23:48 Ent
    引用@__INT 的话:我又重新读了一遍"How to Cope with Noise in the Iterated Prisoner's Dilemma",里面对WSLS的策略会占优进行了反驳,在噪音比例从0.1%到1...

    67种策略共同演化这个模型里有突变吗?
    Nowak的模型和Axelord当年的那个模型是不一样的,除了噪声,策略本身也会突变,并且是在固定的策略空间里。如果是拿Axelord的64模型的话,不可能是固定策略空间突变,只能是固定策略组合……因为他当初征集到了一些超级超级复杂的策略,是没有办法放在一个合理的策略空间里的……

    评论
  • 7楼
    2013-06-29 07:46 __INT
    引用@Ent 的话:67种策略共同演化这个模型里有突变吗?Nowak的模型和Axelord当年的那个模型是不一样的,除了噪声,策略本身也会突变,并且是在固定的策略空间里。如果是拿Axelord的64模型的话,不可能是...

    嗯,的确。
    Axelord在The Complexity of Cooperation第一章讲述了策略空间中演化的算法,我以为他在第二章讲噪音也是这么用的。

    评论
  • 8楼
    2013-12-19 09:12 橡胶万岁

    目测对于现实生活有指导意义

    评论
  • 9楼
    2014-09-16 22:04 逆曦

    WSLS只要发生一次偶然背叛,之后就是永久背叛,使得老好人 ALLC 遭受惨无人道的剥削。 这样一个WSLS不会随着时间推移而“放松警惕”变成ALLC,当然也就不会遭受ALLD的后续必然入侵。

    这样的话,wsls不是会变成alld么?

    评论
  • 10楼
    2014-09-29 17:39 囧了个Orz
    引用@逆曦 的话:WSLS只要发生一次偶然背叛,之后就是永久背叛,使得老好人 ALLC 遭受惨无人道的剥削。 这样一个WSLS不会随着时间推移而“放松警惕”变成ALLC,当然也就不会遭受ALLD的后续必然入侵。 这样的...

    当然不是,它是什么取决于策略而不是表现。

    TFT遇到TFT时还是TFT而不是ALLC,因为它有ALLC之外的能力。同理WSLS也保留了变化策略的能力,所以即使外在表现是变成了ALLD,本质上也还是WSLS,只要有机会还是会从背叛变为合作。

    评论
  • 11楼
    2014-09-30 21:40 逆曦
    引用@囧了个Orz 的话:当然不是,它是什么取决于策略而不是表现。 TFT遇到TFT时还是TFT而不是ALLC,因为它有ALLC之外的能力。同理WSLS也保留了变化策略的能力,所以即使外在表现是变成了ALLD,本质上也还是WS...

    所以,比如,这个机会是?

    评论
  • 12楼
    2014-10-23 19:16 核桃中的大脑
    引用@逆曦 的话:所以,比如,这个机会是?

    WSLS碰了钉子就会改变策略,之所以表现为ALLD只因为它碰的都是ALLC的老好人,碰上真.ALLD就只能重复“俯身献菊花”-“硬碰硬头破血流”-“俯身献菊花”……这样一个循环而被吊打,只不过相比毫无还手之力的ALLC来说损失不那么大而已。没有噪音的情况下,在对抗ALLD方面WSLS显然不如TFT。

    脑子里预先排演一下就可以找到这个机会。如果对这些策略的表述理解不清,可以直接去看Axelrod的原文How to Cope with Noise in the Iterated Prisoner's Dilemma

    评论
  • 13楼
    2014-10-27 23:20 逆曦
    引用@离尽 的话:WSLS碰了钉子就会改变策略,之所以表现为ALLD只因为它碰的都是ALLC的老好人,碰上真.ALLD就只能重复“俯身献菊花”-“硬碰硬头破血流”-“俯身献菊花”……这样一个循环而被吊打,只不过相比毫无...

    好的,谢谢

    评论
  • 14楼
    2015-06-12 12:49 伊卡鲁斯二号

    我觉得人类在处理国际关系、防止世界战争的过程中做的就是最合理的解决方案:

    首先是势力均衡,任何一个强权会有其他强权制约。

    然后是集体安全,任何一个侵犯他国的个体会被当成是对全体的侵犯。

    后来是国际组织,成立联合国,鼓励其他国际组织、跨国企业、国际合作的建立,使得主权之上有了仲裁者和调停者。

    评论
  • 15楼
    2016-03-07 22:57 pumpkinhu
    引用@Ent 的话:对于囚徒困境本体来说,没有第二项要求……第二项要求是在重复囚徒困境里的额外可选项。如果不满足R > (T+P) / 2的话,那么重复囚徒困境里的赢家就不会是TFT,而是合作/背叛相交替。 书是Theo...

    应该是R>(T+S)/2吧。

    另外单次囚徒困境中也有上述要求,因为要保证cc状态的社会收益(R+R)是全局最优。

    评论

你的评论

回复请先登录
Ent 古生物学博士生,科学松鼠会成员 Ent的新浪微博 发表于 2013-06-27 00:12

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区