“进化稳定策略”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第250行： 第250行：
  
 
== 编者推荐 ==
 
== 编者推荐 ==
 +
===集智课程===
 +
====[https://campus.swarma.org/play/coursedetail?id=10954  周亚：演化博弈与机制设计]====
 +
北京师范大学系统科学学院周亚副教授将结合自己的研究工作介绍应用博弈相关方法解释合作行为及相应的机制设计。
 +
 +
 
===集智文章===
 
===集智文章===
 
* [https://swarma.org/?p=23643 进化计算前沿综述：值得算法学习的6个生物进化特征]
 
* [https://swarma.org/?p=23643 进化计算前沿综述：值得算法学习的6个生物进化特征]

2022年1月20日 (四) 22:37的版本

  • 建议将后文全文中的game的翻译改为“博弈”,玩家可改为参与者/生物/种群（中的）个体/进化的参与者——似乎是具有比喻义的词语

进化稳定策略 Evolutionarily Stable Strategy（ESS）是指一个种群在特定环境下采用的策略或策略组，它具有不可渗透性，即该群体的进化策略不可能受到初期占比小的其他策略或策略组的影响。这与 博弈论 Game Theory， 行为生态学 Behavioural Ecology和进化心理学 Evolutionary Psychology有关。进化稳定策略是 纳什稳定 Nash equilibrium的细化，相当于是稳定进化的纳什稳定：一旦该种群固定了所采用的策略，仅依靠自然选择过程就足以防止其他策略（如变异）的成功入侵。该理论并非通过有目的性地处理外部环境可能发生的变化，来引入新的种群进化选择力。 The theory is not intended to deal with the possibility of gross external changes to the environment that bring new selective forces to bear.这一理论想要阐述的不是处理外部环境发生重大变化的可能性，而是这种变化会带来新的选择性力量。


在1972年约翰·梅纳德·史密斯 John Maynard Smith出版的书中，[1] 进化稳定策略首次作为一个特定的术语出现并被广泛应用于行为生态学和经济学之中。如今在人类学、进化心理学、哲学和政治学中，这一概念也已得到使用。


发展历史

进化稳定策略是由约翰·梅纳德·史密斯 John·Maynard·Smith和乔治·R·普赖斯 George·R·Price 在1973年的《Nature》杂志上提出并定义的。[2]但是由于同行评审《Nature》中的论文花费了大量时间，导致在此之前，Maynard·Smith就在1972年的一本论文集《On Evolution》[1] 中发表了另一篇论文，因此有时学者们会选择引用他在1972年出版的《论进化论》.上发表的论文而非1973年《Nature》杂志上的，尽管通常《Nature》杂志上的论文很短，但是大学图书馆可能收藏有《Nature》的副本；随后1974年，Maynard·Smith在《理论生物学》杂志上又发表了一篇更长的论文。[3] Maynard·Smith在1982年的新著作《演化与博弈论 Evolution and the Theory of Games》中，他又进一步解释了这个概念。[4]之后该版本的解释时常被引用。实际上，虽然往往没有引证给出，但是因为引用者已经假定了读者是熟悉它的，因此进化稳定策略已经成为了博弈论的核心。


Maynard·Smith在同行评审普莱斯论文的时候读到了这个论点，随后他将这个口头论点数学形式化。之后Smith意识到Price并没有准备好去修改并发表他的文章，于是他就提出在文末加上Price名字让其成为作为合著者。


事实上“进化稳定”这个概念源自于麦克阿瑟 R·H·MacArthur[5]和汉密尔顿 W·D·Hamilton[6]关于性别比例的研究，以及费雪原理 Fisher's principle，尤其是汉密尔顿（1967）提出的“ 无敌战略Unbeatable Strategy”。随后1999年，Maynard·Smith因其对“进化稳定策略”概念的发展以及“行为进化博弈论“的应用研究做出了杰出贡献，与以上学者共同获得了著名的Crafoord奖。.[7]


进化稳定策略的应用：

  • 进化稳定策略是理查德·道金斯 Richard Dawkins1976年最畅销的著作《自私的基因 The Selfish Gene》中用来分析进化的主要元素。
  • 由罗伯特·阿克塞尔罗德 Robert Axelrod在1984年创作出版的《合作的进化 The Evolution of Cooperation》一书中首次将进化稳定策略用于社会科学领域。从那时起，它就被广泛用于社会科学，包括人类学、经济学、哲学和政治学。
  • 在社会科学中，人们最主要的兴趣不是将进化稳定策略作为生物进化的终点，而是将其作为文化进化或个体学习的终点。[8]
  • 在进化心理学中，进化稳定策略主要被用作人类生物学进化的模型。


策略的假设与动机

在博弈论中，纳什稳定 Nash equilibrium相当于一种传统的解决方案概念，而这依赖于玩家的对它的认知。它假定玩家知道游戏的结构并且会有意识地尝试预测对手的行动以期最大程度地提高自己的收益。另外，纳什稳定也假定所有玩家都知道以下规则（请参阅 常识性知识 Common Knowledge）。后来这些假设又被用于解释为什么游戏参与者们会选择纳什稳定策略。


进化稳定策略的动机则完全不同。在这一语境下玩家的策略被假定为具有生物编码性而且可遗传至下一代。玩家个人并不能控制自己的策略，也无需了解游戏规则。他们繁殖并服从自然选择，而游戏的收益则代表着繁衍成功（生物适应性）。同时可以想象，在繁衍生息过程中，游戏策略偶尔会通过类似基因突变而无计划地发生变异，产生其方案策略。之后他们会通过互相抵制直到出现最优势的策略，即进化稳定策略。


考虑到本质上全然不同的动机假设，进化稳定策略和纳什稳定偶然的一致性令人感到惊讶。实际上，每个进化稳定策略都有对应的纳什稳定，但是某些纳什稳定却不同于进化稳定策略。


纳什稳定 Nash equilibrium

进化稳定策略是纳什稳定的改进式（关于两者的对比见下一节）。在纳什稳定中，如果所有参与者都采用各自的策略方案，且都无法通过改用任何其他策略以获益，那么在这两人的游戏中，我们将此看作一个策略对。令E(S,T)表示策略S对策略T的收益。当且仅当双方都成立且所有T≠S时，策略对(S, S) 为该两人游戏中的纳什稳定：


E(S,S) ≥ E(T,S)


在这个定义中，策略 T 可以成为 S 的中性替代（即最后得分相同，但这已经是最好的结果了）。


即使采用 T 后其得分相等，纳什稳定也被认为是稳定的，当然前提是假设不存在长期动机去鼓励玩家采用 T 而不是 S。


Smith和Price为策略 S 指定了两个条件，使其成为进化稳定策略，对于所有的 T≠S，两个选其一：

1. E(S,S) > E(T,S)
2. E(S,S) = E(T,S) 且 E(S,T) > E(T,T)


第一个条件有时称为严格纳什稳定。[9] 而第二个有时称为梅纳德·史密斯第二条件，它意味着，尽管策略 T 在对抗策略 S 时收益不变，但继续使用策略 S 的玩家在对抗策略T时收益具有明显优势。


后来伯恩哈德·托马斯 Bernhard Thomas在他的论文《On evolutionarily stable sets》中提出了更大胆的定义。[10] 它不同于纳什稳定概念在进化稳定策略中的作用。根据上面第一个定义中给出的术语，此处要求对所有 T≠S：

1. E(S,S) ≥ E(T,S)，并且
2. E(S,T) > E(T,T)，


在这两个公式中，第一个指定了该策略采取纳什稳定，而第二则是指定满足梅纳德·史密斯第二条件。请注意，这两个定义并不完全相等：例如，在接下来的协调游戏中的每个独立策略都是第一个定义的进化稳定策略，而非第二个。


换句话说，此定义还可以这么理解，当两个玩家都使用策略 S 时：第一个玩家的收益要高于（或等于）当第一个玩家更改为策略T而第二个玩家保持策略S时的收益；当第一个玩家的对手将策略更改为T时，第一个玩家自身的收益要大于他们两者都更改为策略T。


这种表述更清楚地强调了纳什稳定条件在进化稳定策略中的作用。同时还考虑到对相关概念进行自然定义，例如 弱进化稳定策略 Weak evolutionarily stable strategy或 进化稳定集合 Evolutionarily stable set。[10]


纳什稳定与进化稳定策略之间差异的示例

囚徒困境 prisoner's dilemma
合作 Cooperate 叛变 Defect
合作 Cooperate 3, 3 1, 4
叛变 Defect 4, 1 2, 2
以邻为壑 Harm thy neighbor
A B
A 2,2 1,2
B 2,1 2,2

在大多数简单的游戏中，进化稳定策略和纳什稳定完全重合。例如，在游戏 《囚徒困境 Prisoner's Dilemma》中，只有一个纳什稳定，其策略（叛变 Defect）也是一种进化稳定策略。


还有一些游戏可能具有非进化稳定策略的纳什稳定。例如，在游戏 《以邻为壑 Harm thy neighbor》中（此处显示为回报矩阵），(A, A)和(B, B)都是纳什稳定，因为玩家无法通过选择放弃任一个来做得更好。但是，只有B是进化稳定策略（也是强纳什）。A不是进化稳定策略，因此B可以中立地入侵A策略的群体并占据优势地位，因为B对B的得分要比A对B的得分高。由于E(A, A) = E(B, A)，因此可以通过梅纳德·史密斯的第二个条件来捕获此动态，但是 E(A,B) > E(B,B)并非如此。


伤害大家 Harm everyone
C D
C 2,2 1,2
D 2,1 0,0
小鸡博弈 The Game of Chicken
转身离开 Swerve 留下 Stay
转身离开 Swerve 0,0 -1,+1
留下 Stay +1,-1 -20,-20


纳什稳定以及同等评分的策略都可以是进化稳定策略。例如，在游戏 《伤害大家 Harm everyone》中， C 是进化稳定策略，因为它满足了梅纳德·史密斯第二条件。 D 策略可以暂时入侵C策略群体，因为D策略可以获得和 C 策略一样的评分。但是当他们开始互相对抗时，他们会付出一定的代价；C 对 D 的得分比D对D的得分高。因此，尽管 E(C, C) = E(D, C)，但 E(C,D) > E(D,D)。因此，最后C是最终进化稳定策略。


还有一些游戏即使具有纯粹的纳什稳定策略，但可能它们都不是进化稳定策略。比如游戏 《小鸡博弈 The Game of Chicken》,该游戏中有两种纯粹的纳什稳定策略（转身离开Swerve，留下Stay）和（留下Stay，转身离开Swerve）。但是，在<font color="#ff8000"无关联不对称 Uncorrelated Asymmetry缺失的情况下，Swerve和Stay都不是进化稳定策略。此时存在第三种纳什稳定，它属于混合策略并且是该游戏的进化稳定策略（详情请参见 《鹰鸽博弈 Hawk-dove》游戏和 《最佳响应 Best Response》）。


最后一个示例指出了纳什稳定与进化稳定策略之间的重要区别。纳什稳定是在策略集（每个参与者的策略规范）上定义的，而进化稳定策略是根据策略本身定义的。进化稳定策略定义的平衡必须始终是对称的，因此其平衡点更少。

与进化稳定状态的比较

在种群生物学中，进化稳定策略和 进化稳定状态Evolutionarily Stable State这两个概念密切相关，但却描述了不同的情况。


在进化稳定策略中，如果所有种群的成员都采用它，那么任何突变策略都无法入侵。无形中只要所有成员都使用了这种策略，就不再有“理性”的选择。进化稳定策略是经典博弈论的一部分。


在进化稳定状态下，如果干扰不太大的话，即使受到冲击，种群的基因组成通过策略选择同样能够进行恢复。而这就是是种群的动态特性，即使受到初始状态的干扰，它们的状态会通过使用策略或混合策略组进行恢复。它是 群体遗传学Population Genetics， 动力学系统Dynamical System或 演化博弈论Evolutionary Game Theory的一部分。这现在被称为 收敛稳定性Convergent Stability。[11]


B. Thomas将“进化稳定策略”这一术语应用于可混合的独立策略，并将“进化稳定种群状态”应用于采取纯策略的混合种群，该应用在形式上可能等同于混合的“进化稳定策略”。[12]


种群是否在进化过程中处于稳定状态与它的基因多样性无关，因为在遗传上它可以是单态或多态的。


随机进化稳定策略

在进化稳定策略的经典定义中，没有任何突变策略可以入侵。然而在有限种群中，尽管可能性很小，但是任意一种突变体原则上是可能入侵的，这就意味着在这个种群中绝对没有进化稳定策略的存在。如果在无限种群中，存在一个概率为P的新突变策略入侵，此时，正如对冲交易的进化过程所描述的那样，进化稳定策略就被认为是具有概率大于p的策略方案且开始反击最初入侵的新突变策略个体。[13]


囚徒困境

囚徒困境 prisoner's dilemma
合作 Cooperate 叛变 Defect
合作 Cooperate 3, 3 1, 4
叛变 Defect 4, 1 2, 2

利他主义和社会合作的普遍模式就是囚徒困境 Prisoner's dilemma。在这里，如果一群玩家选择“合作”，那么他们这个集体就会生活的更好，但是由于“背叛”为个人带来的利益更大，因此每个玩家都有动机去选择“背叛”。解决该问题的一个可能方案是通过让个体反复与同一玩家来对战，由此引入报复机制。在所谓的囚徒困境迭代过程中，相同的两个人一遍又一遍地扮演着他们的角色。尽管囚犯的困境只有两种策略（合作和背叛），但迭代的囚徒困境游戏却具有大量可能的策略。由于个体对于每个历史可以具有不同的应急计划，并且游戏可以无限次重复，因此实际上可能有无限个此类应急计划。


其备受关注的三个简单的应急计划是：“始终背叛 Always Defect”，“始终合作 Always Cooperate”和“针锋相对 Tit for Tat”。前两种策略会始终执行相同的操作，而不受另一方行为的影响，而后一种策略则是通过上一轮中执行的操作来对下一轮中的对象做出响应，即“合作对合作”或“背叛对背叛”。


如果整个种群都选择“针锋相对”，并且出现了一个变异者选择了“始终背叛”，那么“针锋相对”将战胜“始终背叛”。如果该变异者的种群太大，则它所占的百分比将保持很小。因此，就这两种策略而言，“针锋相对”就是一种进化稳定策略。另一方面，“始终背叛”的玩家群体可以稳定地抵御少数“针锋相对”玩家的入侵，但不能抵御大量的入侵。.[14] 但如果我们使用“始终合作”，那么“针锋相对”就不再是进化稳定策略了。由于大量的“针锋相对”玩家转向选择保持合作，因此“始终合作”策略在这一群体中的表现相同。最终，“始终合作”的变异者将不会被淘汰。当然，即使“始终合作”和“针锋相对”的人群可以共存，但是如果“始终背叛”的玩家只占总量的一小部分时，那么策略选择压力会对“始终合作”不利。而由于合作带来的利益要比背叛来的低，玩家们会倾向于选择“针锋相对”。


这证明了要想将进化稳定策略的正式定义应用于具有较大策略空间的游戏中，是非常困难的，这就促使了一些人去思索替代方案。

人类行为

社会生物学和进化心理学领域试图通过进化稳定策略来解释动物和人类的行为以及社会的结构。反社会人格（长期的反社会或犯罪行为）被认为可能是这两种策略结合的后果。[15]


进化稳定策略最初被认为是用于解释生物进化论的，但是它们也可以应用于其他场景。实际上，一大类自适应动力学都具有稳定状态。因此，它们可以用来解释缺乏不受任何基因影响的人类行为。


参见


参考文献

  1. ↑ 1.0 1.1 Maynard Smith, J. (1972). "Game Theory and The Evolution of Fighting". On Evolution. Edinburgh University Press. ISBN 0-85224-223-9. https://archive.org/details/onevolution0000mayn. 
  2. ↑ Maynard Smith, J.; Price, G.R. (1973). "The logic of animal conflict". Nature. 246 (5427): 15–8. Bibcode:1973Natur.246...15S. doi:10.1038/246015a0.
  3. ↑ Maynard Smith, J. (1974). "The Theory of Games and the Evolution of Animal Conflicts" (PDF). Journal of Theoretical Biology. 47 (1): 209–21. doi:10.1016/0022-5193(74)90110-6. PMID 4459582.
  4. ↑ Maynard Smith, John (1982). Evolution and the Theory of Games. ISBN 0-521-28884-3. 
  5. ↑ MacArthur, R. H. (1965). Waterman T.. ed. Theoretical and mathematical biology. New York: Blaisdell. 
  6. ↑ Hamilton, W.D. (1967). "Extraordinary sex ratios". Science. 156 (3774): 477–88. Bibcode:1967Sci...156..477H. doi:10.1126/science.156.3774.477. JSTOR 1721222. PMID 6021675.
  7. ↑ Press release for the 1999 Crafoord Prize
  8. ↑ Alexander, Jason McKenzie (23 May 2003). "Evolutionary Game Theory". Stanford Encyclopedia of Philosophy. Retrieved 31 August 2007.
  9. ↑ Harsanyi, J (1973). "Oddness of the number of equilibrium points: a new proof". Int. J. Game Theory. 2 (1): 235–50. doi:10.1007/BF01737572.
  10. ↑ 10.0 10.1 Thomas, B. (1985). "On evolutionarily stable sets". J. Math. Biology. 22: 105–115. doi:10.1007/bf00276549.
  11. ↑ Apaloo, J.; Brown, J. S.; Vincent, T. L. (2009). "Evolutionary game theory: ESS, convergence stability, and NIS". Evolutionary Ecology Research. 11: 489–515. Archived from the original on 2017-08-09. Retrieved 2018-01-10.
  12. ↑ Thomas, B. (1984). "Evolutionary stability: states and strategies". Theor. Popul. Biol. 26 (1): 49–67. doi:10.1016/0040-5809(84)90023-6.
  13. ↑ King, Oliver D.; Masel, Joanna (1 December 2007). "The evolution of bet-hedging adaptations to rare scenarios". Theoretical Population Biology. 72 (4): 560–575. doi:10.1016/j.tpb.2007.08.006. PMC 2118055. PMID 17915273.
  14. ↑ Axelrod, Robert (1984). The Evolution of Cooperation. ISBN 0-465-02121-2. 
  15. ↑ Mealey, L. (1995). "The sociobiology of sociopathy: An integrated evolutionary model". Behavioral and Brain Sciences. 18 (3): 523–99. doi:10.1017/S0140525X00039595.


进一步阅读

  • Weibull, Jörgen (1997). Evolutionary game theory. MIT Press. ISBN 978-0-262-73121-8.  Classic reference textbook.
  • Parker, G. A. (1984) Evolutionary stable strategies. In Behavioural Ecology: an Evolutionary Approach (2nd ed) John Krebs & Davies N.B., eds. pp 30–61. Blackwell, Oxford.


相关链接

编者推荐

集智课程

周亚：演化博弈与机制设计

北京师范大学系统科学学院周亚副教授将结合自己的研究工作介绍应用博弈相关方法解释合作行为及相应的机制设计。


集智文章


本中文词条由Jie翻译，CecileLi审校，薄荷编辑欢迎在讨论页面留言。


本词条内容源自公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=进化稳定策略&oldid=28622”