噪音水平和交互频次对策略演化的影响

2017-01-11赵小薇夏昊翔大连理工大学系统工程研究所软件学院辽宁大连116024

复杂系统与复杂性科学 2016年4期

赵小薇，夏昊翔，张潇(1. 大连理工大学.系统工程研究所；2. b.软件学院,辽宁大连 116024)

噪音水平和交互频次对策略演化的影响

赵小薇a,b，夏昊翔a，张潇a
(1. 大连理工大学a.系统工程研究所；2. b.软件学院,辽宁大连 116024)

囚徒困境是研究合作策略演化的重要工具，重复囚徒困境下的博弈者可以通过合作实现长期利益的最大化。采用生态演化模拟实验的方法研究在重复囚徒困境中初始环境设定的噪音水平和个体间交互频次对博弈策略演化的影响。研究结果表明，噪声水平和个体间交互频次对最终系统中优胜的博弈策略有决定性作用，这说明环境的初始设定条件是影响博弈策略演化的重要因素。

囚徒困境；合作演化；噪音；策略演化

0 引言

从单细胞生物到复杂的高级哺乳动物，从蚂蚁社会到高等动物种群，合作现象无论在自然界还是人类社会都无处不在。但是根据达尔文的适者生存的理论，如果群体中的个体都追求自身生存利益的最大化，那么群体内甚至群体间广泛的合作是如何形成的呢？这引发了关于“合作演化”问题的研究。过去几十年间，在多个学科领域，如生物学，社会学、心理学，经济学和管理学，以及复杂性科学等，合作演化问题引起了极大的学术关注[1-8]。学界围绕亲缘选择、团队选择、直接互惠、间接互惠、空间互惠等可能的合作机理开展了很多研究[2]。其中，演化博弈论为研究合作演化提供了方便的数学框架。在基于演化博弈论的合作演化研究中，Axelrod和Hamilton 围绕重复囚徒困境博弈问题所开展的博弈策略研究是一项经典的开拓性工作[1]。他们的研究表明，针对重复囚徒困境博弈，一个简单的“一报还一报”(Tit-For-Tat，TFT)策略在很多场景下是一个极为有效的合作策略。Axelrod和Hamilton的研究成果引发了针对博弈环境下合作策略的很多后续研究。

重复囚徒困境博弈的一个重要研究情景是有噪音的重复囚徒困境(Noisy Iterated Prisoners’ Dilemma，NIPD)。噪音是在系统处理过程中自行产生的影响，这些影响与系统输入无关，它阻碍或误导个体对原本事实的理解和原本意图的执行。在现实世界中噪音无处不在，噪音的水平反映了环境的嘈杂程度。在博弈的过程中，噪音表现为随机意外因素，是小概率事件，个体策略会因为“意外因素”产生的随机干扰导致原有的策略不能正确执行，即，博弈中的噪音就是个体在行使合作行为时可能会产生的背叛的结果，或者在行使背叛的行为时产生合作的结果[9]。博弈中噪音的存在对博弈人的决策产生很大影响，从而进一步影响下一轮的行动。研究表明，对无噪音条件下的重复囚徒困境博弈有效的TFT策略是一个对噪音极为敏感的策略，在有噪音的条件下，博弈群体很难通过TFT策略达成合作[10]。这一问题引发了学界对噪音环境下有效合作策略的进一步探讨。在噪音的环境中，“宽容”的行为能够促进合作。对此，人们提出新的策略，例如，在“两报还一报”策略(Tit-for-Two-Tat，TFTT)下，参与人仅在收到两次连续的背叛后才惩罚博弈对手。Nowak与 Sigmund提出“包容的一报还一报”策略(Generous Tit-for-Tat，GTFT)，这种策略具有较小的概率能够无视对方的背叛[11]。上述两种策略本质上都属于宽容策略，即以一定方式“原谅”对方的背叛。这类宽容策略易于达成合作，但缺点是易于受到欺骗性策略的欺诈。另一类在噪音的环境中改进TFT的方法是使用“悔悟”。“悔悟的一报还一报”策略(Contrite Tit-for-Tat，CTFT)能够在发现自己背叛对手后及时纠正错误，继续单方面执行合作行为[12-13]。CTFT善于纠正自身的错误，但这一策略的缺点是不能及时原谅对手犯的错误。第三类策略称为巴甫洛夫策略(Pavlov)或者叫做赢留输变策略(Win Stay Lose Shift，WSLS)[14-16]。当因噪音导致对手间报复性相互背叛发生时，Pavlov策略可以在比TFT系列策略迭代更少次后恢复合作。然而，Pavlov策略因为存在参与者一直都可以从背叛对方这一行动中获得奖励这一缺陷，所以鲁棒性不强[9]。此外在文献[17]中还提出了另一种“灵活互惠利他策略”(Flexible reciprocity Altrisum，FRAM)，在这一策略下，博弈者对背叛保持一定程度的容忍，并能够为了长期回报而继续采取合作的策略。采用FRAM策略的个体，其决策基于与对手长期交互的历史，噪音带来的意外影响不会立即打破两个参与者之间的长期合作关系。

上述一系列策略的提出引发了如下研究课题：在混合多种策略的人群中，最终哪个或哪些策略在有噪音的重复囚徒困境博弈中会取得优势？在文献[9][16]和[18]中，学界对其中一些策略的表现进行了比较研究。然而，之前对策略演化的研究大都是将系统的噪音设置为常数，研究噪音水平较低的情况下(通常小于1%)合作策略的演化现象，即在多次重复囚徒困境博弈中加入极少次随机干扰。噪音水平是单位时间内博弈策略受到干扰的频率，该指数反映了环境的嘈杂程度，可以想见，不同的噪音水平可能影响不同策略在混合策略群体中的总体表现。当前学界对噪音水平对策略演化的影响研究不够充分。另一方面，目前对策略演化的研究都是将系统的个体间交互频次设置为较低的常数，忽略了交互频次对策略演化的影响。个体间交互频次是描述交互强度以及博弈个体间关联紧密程度的指标，反映了个体在一定的时间尺度内相互博弈的次数，该值越大，个体间的博弈进行得越频繁，积累的交互历史越多，反之，个体间的博弈进行不频繁，积累的交互历史较少。在自然界中，有的生物种群内个体间交互频繁，而有的交互次数稀少；在人类社会中，有些社会文化中个体间互动频繁，而有些文化更加崇尚个体独立性。这种交互频次及其背后的社会关联紧密程度必然对合作策略的演化产生影响。基于以上考虑，本文针对有噪音的重复囚徒困境博弈情景，采用生态演化模拟实验的方法研究不同的噪音水平和不同的个体间交互频次对合作策略演化的影响。

1 问题情景和生态演化实验设定

1.1 有噪音的重复囚徒困境博弈

在原始的囚徒困境博弈中，参与博弈的每个个体都采用纯策略，即个体的策略选择只有两种：合作(cooperation，C)或背叛(defection，D)。参与博弈的个体根据自己和对手采用的策略获得不同的收益。如果两个个体都采取C策略，那么双方都获得合作的奖励R；如果两个个体都采用D策略，那么双方都得到背叛的惩罚P；如果一个采用C策略，另一个采用D策略，那么背叛者获得收益T，合作者得到S，其中T>R>P>S，且2R>T+S。对于单次囚徒困境博弈，众所周知，背叛策略必然是博弈者的最优策略。在这一情景下，合作不可能在理性博弈者之间产生。但在博弈者事先不知道重复次数的重复囚徒困境(Iterated Prisoners’ Dilemma，IPD)博弈情景中，合作策略有可能成为有效的策略。Axelrod和Hamilton的研究表明，“一报还一报”策略(TFT)是针对这一情景的一种极为有效的策略[1,19]。TFT策略可描述为：第一步使用C策略，之后每一步都重复对手的策略。

如果在上述的重复囚徒困境博弈中加入随机噪音的因素，就形成了有噪音的囚徒困境博弈(Noisy Iterated Prisoners’ Dilemma，NIPD)。博弈中的噪音结果是导致个体原本策略被干扰成为相反的策略，即参与博弈者在某时间点决定采用C策略，如果没有受到随机噪音干扰，则该博弈者实际执行的策略仍然是C，反之如果受到噪音的干扰则执行相反策略D。噪音的存在对简单TFT策略的有效性产生了显著的影响。在有噪音的条件下，两个采用TFT策略的博弈者很容易由于一次对合作行为的扭曲解读导致彼此的反复背叛。Molander的研究表明，在噪音率很低的条件下，两个TFT博弈者的长期收益同两个持随机策略的博弈者的长期收益没有显著差异[20]。正因如此，人们针对NIPD情景分别提出了GTFT、CTFT、WLSL等策略。本文试图通过生态演化模拟实验对这些策略在不同噪音水平以及不同交互频次条件下的表现进行检查。本文的基本研究问题是：是否存在在不同噪音水平和不同交互频次下都适合的合作策略。

1.2 生态演化实验设定

本文使用生态演化模拟实验来检测持有各自不同的多种策略的群体在进行有噪音的重复囚徒困境博弈时，各种策略在不同的噪音水平下和不同的交互频次下各自的长期表现如何。对此，本文采用与Wu与Axelrod[9]的“生态学模拟”一致的思路开展生态演化实验研究。在实验的初始阶段，参与实验的各种策略的持有者在整个生态群体按等比例均匀混合。演化开始后，参与者之间根据各自所持的策略彼此进行博弈。本研究采用全博弈的方式，即在每一代(每一模拟轮次)中，每一个体要与所有其他个体两两博弈k次，k代表了个体间博弈次数，k越大个体间交互越频繁。博弈时个体行为受噪音影响，即个体在行使合作行为时可能会产生的背叛的结果，或者在行使背叛的行为时产生合作的结果。一代结束后，每个参与者统计各自的收益。采用相同策略的参与者的收益加和作为这一策略在这一代的适应度。为了体现“生态进化”，在下一代具有高适应度的策略种群个体数量增加，具有低适应度的策略种群个体数量减少。为了体现生态演化中的随机突变，每代中都有极少比例的个体放弃原来的策略，从其他的策略中随机选择一种策略作为自己的策略，这个较小的概率为“随机突变率(m)”。代代往复，以此类推，每一代记为g。经过这一系列的策略演化过程(选择、博弈和突变)，产生的新一代种群的数量不同于上一代，并一代代向增加整体适应度的方向发展，因为最好的策略总是具有更大的可能性被选择去产生下一代，而适应度低的策略逐渐被淘汰，直到当某一策略的适应度达到饱和，也就是生态系统继续演化也不会产生适应度更高的个体时，生态演化将终止。这一生态演化模拟实验的算法如表1所示。

表1 生态演化模拟实验的算法流程
Tab.1 Alogorithm of ecological evolution simulation

个体i持某一种初始策略；do{ 交互频次=0； while(交互频次

在参与模拟的初始策略的选择上，本文分别选取原始TFT、CTFT、GTFT及FRAM策略进行混合实验，并加入FREE-RIDER用以检验其他策略对抗背叛者入侵的能力，加入Random策略用于对比策略收益。Wu与Axelrod的工作[9]表明巴甫洛夫策略(WSLS策略)在这种多策略混合群体的生态模拟实验情景下的总体表现不佳，本文的实验中没有加入该策略。参与模拟实验的各种策略简述为：

1)原始一报还一报策略(TFT)。博弈者在时间步t=1时无条件执行C策略，在t>1时复制对手t-1时的策略。

2)宽容的一报还一报策略(GTFT)。博弈者在大部分的时间执行一报还一报策略，对于对手的D策略以小概率(10%)进行宽容而不采取报复性背叛，执行C策略。

3)悔悟的一报还一报策略(CTFT)。博弈者在大部分的时间执行一报还一报策略，如发现自己在t-1阶段因噪音执行了D策略，则在t阶段纠正错误，继续执行C策略。

4)灵活互惠利他策略(FRAM)。博弈者对于对手的背叛行为可以适度宽容，宽容等级分别为1至4级，使用FRAM1，FRAM2，FRAM3和FRAM4分别代表FRAM中宽容等级1，2，3和4[17]。

5)搭便车策略(FREE-RIDER)。博弈者在每一次博弈中都无条件执行D策略。

6)随机策略。博弈者在每一个时间步t都以定值50%的概率采取C或者D的策略。

2 仿真与结果分析

本文设定生态演化实验初始时系统内有上述9种不同博弈策略，每种策略的个体数量均为30，参与博弈的个体总数为270。策略的随机突变率m为1%，在演化实验的每一代中，每个个体要与所有其他个体两两博弈k次，系统共演化g=20 000代。所有博弈者具有相同的博弈矩阵T=5，R=3，P=1，S=0。为了研究噪音水平的影响，选取3个n值：n=5%，15%和30%。当噪音水平达到50%，个体博弈两次中就有一次受到干扰，此时所有策略均接近随机策略，因此本研究选取50%以下3个典型值来进行研究：n=5%时，100次博弈有5次受到噪音干扰，受干扰程度较低；n=30%时，100博弈有30次受到噪音干扰，受干扰程度较高，15%居于二者中间。为了研究不同的个体间交互频次k对合作策略演化的影响，选取从小到大3种不同的代内交互次数k=5，15和55。为了获得稳定的仿真结果，最终的数据是50次模拟的平均，即对每一次特定初始演化设定运行50次。

图1显示了9种策略在交互频次较小(k=5)时，系统在3种不同水平的噪音影响下策略随时间演化的结果。从图1可见，当每代个体交互频次较低时，不同水平的噪音对不同策略人数的变化趋势影响很大，表现为低噪音环境(n=5%)中TFT策略占优，类TFT策略(GTFT和CTFT策略)人数紧随其后，说明TFT策略群在噪音影响较小的情况下依然是系统的最优策略，GTFT因为能够宽容较低比例的背叛，平衡了部分噪音影响，从而成为低噪音环境中的次优策略。在低噪音环境中，FREE-RIDER策略表现极差，种群人数几乎为0，因为这个策略能够被TFT及类TFT策略立即发现其背叛性，因此无法生存。当n取值增大后，CTFT策略的优势逐渐显现，成为最优策略，TFT对噪音敏感，因此表现受噪音影响较大，GTFT策略对噪音的宽容上限低于实际噪音，因此在高噪音环境中表现要受到影响。图1说明在每代个体交互频次较低的系统中，噪音等级对最后占优策略有决定性影响；而根据个体之间交互历史决定博弈行为的4种FRAM策略在k值较小的系统中不占优势。

图2显示了9种策略在中等交互频次下(k=15)，系统在3种不同水平的噪音影响下策略随时间演化的结果。从图2可见，在每代交互频次居中时，噪音水平对策略演化的影响较小，变化趋势非常接近，CTFT策略最终在系统中成为占优策略。这种情况的成因在于k值居中时，每代内个体间交互的次数既不会太频繁也不会太稀少，CTFT策略既可以通过多次与对手交互相互合作积累收益，又具有较高的抗噪能力。TFT策略对背叛行为反应过于敏感，在多轮次博弈中容易因为噪音影响进入轮流报复性背叛的困境，而GTFT策略的随机宽容性不利于该策略在多轮次博弈中识别对手的主动背叛行为。

图3显示了9种策略在交互频次较高(k=55)时，系统在3种不同水平的噪音影响下策略随时间演化的结果。从图3中可见，噪音水平较低和居中时，策略演化趋势非常接近，与图2的策略演化的情况非常类似，表现为CTFT策略最终在系统中占据大多数。当噪音水平较高时，系统最优策略发生了变化，FRAM1表现出了最高的适应度，FRAM2是次优策略，说明高噪音环境下，当个体间交互异常频繁时，具有可控的容忍度并且能够根据交互历史容忍对手的非恶意背叛的个体，可以通过与对手建立长期互惠的合作关系获利，最终成为系统的统治性策略。

对比图1、图2和图3，当k值不同时，噪音等级对合作策略演化的影响有差异。当k值较小时，系统中对背叛行为反应迅速的策略占有优势，此时噪音等级对最终系统最优策略影响较大。随着k值增大，系统中对背叛行为具有宽容和悔悟的策略表现出优势，噪音等级对合作策略演化的影响降低。当k值增大到50以上时，系统中对背叛行为宽容度更高的FRAM策略的优势逐渐显现，噪音越大，FRAM策略的优势越明显。同时图1、图2和图3表明，噪音等级和每代交互频次是两个重要的系统参数，在合作策略的演化上起决定性作用。

k噪音n5%15%30%1，2FREE⁃RIDERFREE⁃RIDERFREE⁃RIDER3，4TFTTFTTFT5TFTCTFTCTFT6⁃38CTFTCTFTCTFT39⁃50CTFTCTFTFRAM151⁃89CTFTFRAM1FRAM190⁃100FRAM1FRAM1FRAM2

表2显示了在不同的噪音等级设定下，交互次数k取值从1到100，系统内最终优胜策略的情况。从表2中可见，当k为1和2时博弈的赢家始终是FREE-RIDER，此时博弈本质上是“一次性博弈”，交互次数极少时，善良的策略无法识别出背叛者。当k是3和4时，TFT是系统演化后的胜出策略，TFT策略遇到FREE-RIDER时在第二步可以进行反击，同时TFT也能够与其他善良的策略相互合作。当k是5时，低噪音系统内TFT依然表现良好，当噪音较高时CTFT成为了系统内的最优策略，原因在于TFT的抗噪音能力较低，CTFT是带有悔悟的TFT策略，可以在发现自己的失误性背叛行为后及时悔悟，重新恢复合作关系。当k介于6到38时，CTFT几乎是系统运行完毕后唯一留存的策略。当k介于39到50时，在高噪声的系统内，FRAM1的表现超越了CTFT，成为系统最优策略，并且随着k的增加，FRAM策略的优势越来越明显。FRAM是容忍程度更高的策略，当每代内交互频次很高时，FRAM策略能够平衡掉噪音的影响。当k增大到77以上时，FRAM2策略超越了FRAM1策略，FRAM2是比FRAM1更具有容忍程度的策略。

一个显著的结果是，在重复囚徒困境中，在不同的代内交互频次设定下，噪声等级对博弈策略的演化具有影响。研究表明，GTFT，CTFT和FRAM策略都是具有抗噪能力的策略，交互频次越高，CTFT和FRAM策略的优势越明显。当交互频次较低时，高噪音环境中CTFT策略的优势较为突出，低噪音环境中TFT策略依然是系统内的最优策略。

3 结论

本文研究了在重复囚徒困境中噪声水平和个体间交互频次对博弈策略演化的影响。通过基于Agent的仿真实验分别研究了在一定k值设定下的噪音等级对系统内博弈策略的影响。在实验中发现，FRAM和CTFT策略在噪音等级高的环境中容易胜出，TFT策略在噪音等级低的环境中容易胜出。这说明噪音越大的环境越需要参与者的容忍和悔悟，而在噪音较低的环境下，迅速反击对手的背叛行为才是最好的选择。研究同时发现每代内个体间交互频次对系统博弈策略演化具有影响。从实验结果中发现，当博弈参与者交互频繁时，FRAM系列的策略是最优策略，CTFT策略次之；当参与者交互频次较低时，FRAM和CTFT策略在最后不会成为生态演化实验的留存策略。在极端情况下，如交互频次小于3时，博弈成为一次性博弈，FREE-RIDER是最优策略。个体间交互频次体现了人群在一定时间内的相遇次数，也就是人群熟悉程度。当人群熟悉程度较高时，环境就是“熟人的村落”，那么具有容忍的策略(如FRAM策略)和具有悔悟的策略(如CTFT策略)就是人们会采取的策略。当人群熟悉程度较低时，个体间的相遇就是陌生人的游戏，那么“不合作”就成为理性人容易采取的策略。

从本研究的结论可知，环境对博弈策略的影响是巨大的。不考虑环境因素去研究合作策略是不全面的。一些研究认为博弈策略应具有学习对手策略的能力从而调整自身的策略，本文的研究表明，博弈策略还应具有感知环境因素的能力，诸如噪声等级和人群熟悉程度等。因此，本文的一项后续工作是研究具有环境感知能力的博弈策略。

[1]Hamilton A R. The evolution of cooperation [J]. Science，1981，211(3)：1390-1396.

[2]Nowak M. Five rules for the evolution of cooperation [J]. Science，2006，314(5805)：1560-1563.

[3]Huberman B A，Glance N S. Evolutionary games and computer simulations [J]. Proceedings of the National Academy Sciences，1993，(3)：7716-7718.

[4]Doz Y L. The evolution of cooperation in strategic alliances: initial conditions or learning processes? [J]. Strategic Management Journal，1996，17(s1)：55-83.

[5]Gómez-Gardenes J，Reinares I，Arenas A，et al. Evolution of cooperation in multiplex networks [J]. Scientific Reports，2012，2:620.

[6]Santos F C，Pinheiro F L，Lenaerts T，et al. The role of diversity in the evolution of cooperation [J]. Journal of Theoretical Biology，2011，299：88-96.[7]王先甲，全吉，刘伟兵. 有限理性下的演化博弈与合作机制研究 [J]. 系统工程理论与实践，2011, 31(S1): 82-93. Wang Xianjia,Quan Ji,Liu Weibing.Research on evolutionary garne and cooperation mechanism under bounded rationality[J].System Engineering Theory & Practice,2011,31(S1):82-93.

[8]杨阳，荣智海，李翔. 复杂网络演化博弈理论研究综述 [J]. 复杂系统与复杂性科学，2008，5(4)：47-55. Yang Yang,Rong Zhihai,Li Xiang,A review of the evolution game theory of complex networks[J].Complex Systems and Complexity Science,2008,5(4):47-55.

[9]Wu J，Axelrod R. How to cope with noise in the Iterated Prisoner’s Dilemma [J]. The Journal of Conflict Resolution，1995，39(1)：183-189.

[10] Axelrod R，Dion D. The further evolution of cooperation [J]. Science，1988，242(4884)：1385-1390.

[11] Nowak M，Sigmund K. Tit for tat in heterogeneous populations [J]. Nature，1992，355(6357)：250-253.

[12] Sugden R. The Evolution of Rights, Co-operation and Welfare[M]. Oxford: Blackwell，1986.

[13] Boyd, R. Mistakes allow evolutionary stability in the repeated prisoner's dilemma game [J]. Journal of Theoretical Biology，1989，136(1)：47-56.[14] Kraines D，Kraines V. Pavlov and the prisoner’s dilemma [J]. Theory and Decision，1989，26(3)：47-79.

[15] Kraines D，Kraines V. Learning to cooperate with pavlov an adaptive strategy for the iterated prisoner’s dilemma with noise [J]. Theory and Decision，1993，35：107-150.

[16] Imhof L A，Fudenberg D，Nowak M. Tit-for-tat or Win-stay, Lose-shift? [J]. Theory of Bioloyg，2007，247(3)：574-580.

[17] Zhao X，Xia H，Yu H，et al. Agents’ cooperation based on long-term reciprocal altruism[C]//Proceedings of the 25th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems，2012，689-698.

[18] Nowak M，Sigmund K. A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner's Dilemma game [J]. Nature，1993，364(6432)：56-58.

[19] Hamilton A R.The Evolution of Cooperation[M]. New York：Basic Books，1984.

[20] Molander P. The optimal level of generosity in a selfish, uncertain environment [J]. The Journal of Conflict Resolution，1985，29(4)：611-618.

[21] Zhang G Q，Sun Q B，Wang L. Noise-induced enhancement of network reciprocity in social dilemmas [J]. Chaos Solitons & Fractals，2013，3(3)：31-35.

[22] Yao Y，Chen S S. Multiplicative noise enhances spatial reciprocity [J]. Physica A，2014，413：432-437.

(责任编辑耿金花)

Effects of Noise and Interaction Frequency on the Evolution of Cooperative Strategies

ZHAO Xiaoweia,b，XIA Haoxianga，ZHANG Xiaob

(a.Institute of Systems Engineering; b．School of Software Technology,Dalian University of Technology,Dalian 116024,China)

Prisoner’s dilemma is an important tool to study the adaptation of cooperative strategies. Individuals can maximize their profits by cooperating with each other. In this paper, the method of ecological simulation is adopted to study the effects of noise and interaction frequency on the evolution of cooperative strategies in the context of the Noisy Iterated Prisoner’s Dilemma (NIPD), a version of the Iterated Prisoner’s Dilemma (IPD). The results illustrate that noise and interaction frequency are important factors to the surviving strategies.

prisoner’s dilemma；evolution of cooperation；noise；evolution of strategies