基于先进控制技术的竖炉燃烧室温度优化控制

Transcription

1 演化动力学与合作复杂性 王龙伏锋 ( 北京大学系统与控制研究中心, 北京 ) 摘要 : 阐述了复杂系统与复杂网络研究的基本背景, 指出演化博弈论是复杂系统研究的一个新方向, 介绍了演化博弈论的基本概念和常用模型方法, 着重探讨了自组织合作涌现的演化机制 总结展望了演化博弈论的未来的一些发展方向 关键词 : 复杂系统, 复杂网络, 演化博弈动力学, 自组织合作, 囚徒困境, 雪堆博弈中图分类号 :TP 文献标识码 :A Complexity of Self-Organizing Cooperation WANG Long FU Feng (Center for Systems and Control, Peking University, Beijing , China) Abstract: We introduce the basic concepts and background in study of complex systems and complex networks. We point out that evolutionary game dynamics is an emerging research direction of complex systems. We also introduce the fundamental concepts and modelling methods of evolutionary game theory, and focus our discussion on the mechanisms for the emergence of self-organizing cooperation. Finally we draw our concluding remarks and outlooks about future development and direction of evolutionary game dynamics. Key words: Complex Systems; Complex Networks; Evolutionary Game Dynamics; Self-Organizing Cooperation; Prisoner s Dilemma; Snowdrift Game 1 复杂性科学 复杂性科学 (Complexity Science) 被誉为 21 世纪的科学 [17] 复杂性科学主要研究复杂系统 (Complex System) 与其复杂性 (Complexity)[194] 作为一门多学科交叉综合的研究方法, 复杂系统理论研究涉及到数学 生物学 经济学 物理学 人工智能 神经科学 心理学 社会学 计算机科学 复杂性理论 (Complexity Theory) 系统生态学 系统论 (System Theory) 信息论 控制论(Cybernetics) 等 一个复杂系统通常由多个独立的个体 ( 或子系统 ) 组成, 个体之间存在局部相互作用而相互适应 Strogatz 在他的 Sync 一书中[167], 总结各个时代的研究热点, 归结为 C- 理论, 具体的,20 世纪 60 年代是控制论 (Cybernetics) 70 年代是突变理论 (Catastrophe Theory) 80 年代是混沌理论 (Chaos Theory ) 90 年代是复杂性理论 (Complexity Theory) 复杂性思想方法首先由法国哲学家 Edgar Morin 提出 这里, 复杂 不是 简单 的对立面, 而是一种新的方法论 这种方法论认为某种事物规律之所以简单并不是本身简单而是经过了人为的简化, 并且承认世界的不可知性 Morin 反对用经典科学的还原论及机械决定论来认识世界, 并认为世界的基本性质是有序性与无序性的统一 比利时诺 贝尔化学奖获得者 Ilya Prigogine 在 1979 年提出了复杂性科学的概念 他提出耗散结构理论 (Dissipative Structure) 并研究了物理 化学中的 导致复杂过程的自组织现象 [104, 136], 认为在非平衡态系统中, 系统内各要素之间存在复杂的非线性相干效应时才能产生自组织 (Self-Organization) 现象 复杂性科学研究兴起的标志性事件是 1984 年美国圣达菲研究所 (Santa Fe Institute, SFI) 的建立 该所是在美国诺贝尔物理学奖得主 Gell-Mann 的倡议下, 并在诺贝尔物理学奖得主 Anderson 和诺贝尔经济学奖获得者 Arrow 等人的支持下创立的 该所把复杂性作为研究的中心议题, 旨在世界范围内促进对复杂系统理论的多学科研究 圣达菲研究所是国际复杂性科学研究的中心, 也是复杂性科学研究者的朝圣地, 许多国际著名物理学家 经济学家都曾在那里工作过 在我国也有许多学者长期推动和支持复杂系统与复杂性科学研究, 其中包括我国著名科学家钱学森教授和戴汝为教授 [1] 由于复杂系统中的个体具有自适应性 (Adaptation), 即个体能够依据环境进行自我反馈调节, 因此复杂系统有时又被称为复杂自适应系统 (Complex Adaptive System,CAS) 遗传算法的创 - 1 -

2 始人 Holland 认为这种适应性造就了复杂性 [81] 现实中的许多系统, 如股票市场 (Stock Market) 社会性昆虫 (Social Insects) 生态系统(Ecological System) 大脑 免疫系统(Immunological System) 细胞及人类社会 文化系统中群体行为 (Group Behavior) 等都是典型的复杂自适应系统 涌现 ( Emergence ) 和自组织行为 (Self-Organization Behavior) 是复杂系统重要的宏观表现行为 在复杂系统中, 个体与个体之间通过特定的相互作用关系, 在一定的条件下, 有序的集体组织行为 (Collective Behavior) 会涌现出来 [15] 这种涌现行为通常是 > 2 的, 也就是整体的行为大于部分之和 由于复杂系统研究的难点在于对其建模和仿真, 因此, 研究者通常只专注被研究系统的某一种属性并对其进行简化分析 例如, 习及自适应的个体组成 个体不具有全局信息, 并且系统是分布式的, 即不存在一个中心控制个体 多智能体系统可以用来研究软件系统, 智能交通, 机器人协作, 人工社会等 在 Vicsek 的自驱粒子 (Self-Driven Particle) 模型 [190] 及 Reynolds 的 Boid 模型 [141] 的启发下, 多智能体的合作控制 (Cooperative Control), 如一致性 (Consensus) 群集行为 (Swarming Behavior) 等问题得到了很好的研究 [126, 140] 2 复杂网络在 20 世纪末, 复杂网络 (Complex Network) 的研究掀起了复杂性科学研究的新热潮 复杂网络本身也成了一门新的科学 网络科学 (Network Science)[16] 实际上, 复杂自适应系统中个体之 Von Neumann 等人对元胞自动机 (Cellular 间的相互作用关系可以看成是一个动态网络 [82], Automata) 的早期研究,Conway 的生命游戏 (Game of Life), 以及 Wolfram 的相关研究都揭示了复杂性可以通过系统中个体的局部相互作用而产生 但在更多的情况下, 系统往往会出现混沌振荡等表现行为, 即系统处于 混沌的边缘 (Edge of Chaos) 复杂系统研究早期揭示的在开放系统中远离平衡态的自组织现象的理论除前面已介绍的 Prigogine 的耗散结构理论, 还包括 Haken 的协同论 (Synergetics) [61] 和 Thom 的突变论 (Catastrophe Theory)[177] 与复杂性研究密切相关的是自组织临界性 (Self-Organized Criticality,SOC) 的发现 [13, 14], 这是 20 世纪后半叶在统计物理学中非常重要的发现 当系统逐渐演化到自组织临界状态时, 系统的时空动力学行为不再具有特征时间和特征空间尺度, 而表现出满足幂律 (Power Law) 分布的时空关联, 包括突变事件的规则性 分形 1/ f 噪声及标度律 1989 年,Bak 等人提出的沙堆模型, 很好地阐释了出现自组织临界性的机理 [14] 自组织临界性是具有临界点吸引子的动力系统的一类性质, 因此它们的宏观行为在相变临界点附近表现出时空上的标度不变性 自组织临界现象的产生, 则是由于内在的自发动力学机制驱使系统达到临界状态造成的, 与控制参数的取值无关 [13] 这被认为是自然界中导致复杂性出现的一种机理, 并被广泛应用于不同学科中, 如进化生物 ( 物种大爆发 ) 森林火灾预测 生态学 经济学 社会学 神经生物学等 因而可用复杂网络方便地对复杂系统进行描述和刻画 系统中的个体是网络中的节点, 个体之间的相互作用关系是网络中的边 传统的思想认为个体之间相互作用的拓扑关系是随机的, 可用一个随机网络来刻画 例如 1960 年 Erdos 和 Renyi 提出的随机图论 (Random Graph Theory)[42], 就得到了广泛的应用与发展 [25] 现代意义上的复杂网络理论起源于对人际关系网络的定量研究 对于无处不在的人际关系网络的认识, 最早美国著名社会心理学家 Milgram 在美国通过一系列连锁信实验, 证实了社会关系网络的小世界现象 (Small-World Phenomenon), 即所谓的六度分离 (Six Degrees of Separation) 数据统计表明平均只需通过 6 个中间人就可以联系任何两个互不相识的美国人 [98] 1998 年, 时为 Cornell 大学力学系研究生的 Watts 和他的导师 Strogatz 合作提出了小世界网络模型 (Small-World Network Model), 并用实际网络数据证实了真实世界网络拓扑具有 小世界性, 并且是介于完全随机与完全确定性之间的, 也就是说真实网络的拓扑形成是这两种力量相互作用的结果 [197] 论文一经 Nature 发表, 立刻在全世界范围内引起了广泛的关注 [195] 1999 年, 时任美国 Notre Dame 大学物理学教授的 Barabási 与他当时的研究生 Albert 合作在 Science 发表了一个具有划时代意义的重大发现 : 绝大多数真实世界网络拓扑统计性质满足一个幂律, 即网络中任选一个节点的邻居数 作为一类自组织系统, 多智能体系统 γ ( 节点度,k ) 的分布满足 p ( k) k [19], 通常 γ (Multi-Agent System,MAS) 的研究近年来引起了 计算机科学界 控制理论界的兴趣, 得到了广泛的关注 多智能体系统是由多个相互作用的具有自学 介于 2 3 之间 在这类网络中, 大部分节点只占有少数几条连接 ( 边 ), 而一小部分节点却占有网络大 - 2 -

3 部分的边 ( 这类节点被称为 Hubs) 他们把满足这研究 [18] 目前, 复杂网络研究的一个瓶颈是如何一特性的网络称为无标度网络 (Scale-Free 获取及分析真实的海量数据 21 世纪的研究已经从 Network) 并基于增长(Growth) 和优先连接一般简单模型分析逐渐变化到处理自然和人类社会 (Preferential Attachment) 的思想提出了一个网络模活动中大量存在的实际数据 [196] 这种数据驱使的型, 可以生成这种无标度网络 (Data-Driven) 研究, 是复杂系统研究者共同面对实际上, 优先连接 现象大量存在于社会经济的一个挑战 [43] 系统中, 这是现实世界中一些统计量满足长尾分布 3 演化博弈动力学 (Long-Tailed Distribution) 或幂律的根本原因 如语言中的词频对其排名的 Zipf 分布 (Zipf s Law), 复杂自适应系统的一些概念和研究模型实质上城市大小与其排名的分布, 个人财富的 Pareto 分布与达尔文主义 ( 基于自然选择的进化论 ) 具有紧密 (Pareto Distribution), 发表文章的引用次数分布的联系, 并建立在当代演化生物学对适应与演化 (Price s Cumulative Advantage ) 等 这些幂律 (Adaptation and Evolution) 的普遍认同的基础之在不同的背景下, 被冠以不同的名字, 像 Yule 过程上 复杂系统中的个体可以适应 通讯 合作 (Yule Process) Gibrat 律 (Gibrat s Law) 累计优 (Cooperation) 分工( 或分化,Specialization) 势 (Cumulative Advantage) 富者越富(The Rich Get 时空组织和复制 个体之间的通讯与合作在实际系 Richer), 成比例效应 (Proportionate Effect),Bradford 统的不同层次上不断发生 在复杂系统中, 个体之分布 (Bradford Distribution),Lotka 定律 (Lotka s 间出现合作的驱动力 (Driving Force) 可用演化博 Law),Taylor 定律 (Taylor s Law), 和 Matthew 效弈论 (Evolutionary Game Theory) 进行建模分析 [161, 应 (Matthew Effect) 在 Yule 工作的基础上 [205], 162] 演化博弈论作为研究复杂系统的重要手段和 Simon 首先利用主方程的方法分析求解了优先连接工具, 它不仅便于定性和定量地研究个体间的合作, 导致的幂律 [157], 即实现了一类 Zipf 律, 又被称为而且便于建立简洁优美的模型, 能够体现一般复杂 Yule-Simon 分布 (Yule-Simon Distribution) 关于幂系统所具有的自组织和涌现行为等特性 因此, 作律研究的进一步综述, 可参见文献 [34] 为一个复杂性科学研究领域, 演化博弈动力学引起小世界网络模型及无标度网络模型是复杂网络了复杂系统研究者的极大关注 研究中的两个重要里程碑 [16], 复杂网络从而成为演化博弈动力学作为多学科交叉研究的一个结复杂系统研究的重要工具与手段 目前复杂网络的合点, 在数学 生物学 社会学 经济学 政治学 拓扑结构已得到了细致的研究 有关度分布 (Degree 心理学 计算机科学 人工智能等领域均得到了广 Distribution), 聚集系数 (Clustering Coefficient), 泛的研究与应用 [20, 22, 36, 41, 49, 55, 57, 80, 107, 平均度 (Average Degree ), 同配 / 异配性 154, 156, 191, 199] 作为演化博弈动力学研究的主 ( Dis/assortative Mixing ), 度相关性 (Degree 旨之一, 合作的涌现 (Emergence of Cooperation) Correlation), 社团结构 (Community Structure) 等和演化机制 (Mechanisms for Evolution of 网络拓扑结构统计性质的论述可参见综述文献 [3, Cooperation) 自上世纪 70 年代以来, 一直备受关注 103,166] [12, 9, 11, 10, 162, 161, 108] 复杂网络的拓扑结构终究是为其实现的功能服演化博弈中所指的合作是广义上的, 包括个体务的, 因此复杂网络上的各类动力学研究, 像疾病 的利他行为 (Altruistic Behavior ), 平等主义谣言传播 ( 参见综述 [24]) 同步( 参见综述 [8]) (Egalitarianism), 互利共生关系 (Mutualism) 等 观点动力学及更一般的社会动力学 (Social 合作现象在自然界和人类社会中普遍存在 自然界 Dynamics, 参见综述 [33]) 演化博弈动力学( 参见中的实际例子包括 : 微生物, 如噬菌体 (Phage)[188] 综述 [168]) 等, 引起了许多学者的兴趣, 得到了系和酵母菌 [2, 58, 94, 163]; 社会性昆虫, 如蜜蜂和蚂统的发展 真实的网络拓扑结构并不是静态的 一蚁 [204]; 动物, 如蜥蜴 (Lizard)[158], 棘鱼 (Stickle 成不变的, 而是在持续的动态演化之中 网络拓扑 Fish)[99], 清洁鱼 [30, 31], 吸血蝙蝠 (Vampire Bat) 与网络上的动力学相互作用并彼此影响 共同演化 [201], 猫鼬 (Meerkat) [35]; 高等灵长类哺乳动这种复杂网络的共演化 (Coevolutionary Network) 物如大猩猩 [86] 人类社会中也普遍存在合作行为是近年来的一个研究热点 ( 参见综述 [59]) [45, 48, 44], 如非洲原始部落中的狩猎者与收集者 2009 年是 Barabási 等人发表无标度网络论文, (Hunter-Gatherer)[26] 即复杂网络理论研究开展十周年 为此 Science 杂个体的合作行为很容易被其他自私个体的作弊志特地推出一期专栏, 总结与展望复杂系统与网络行为所利用 [39, 46, 64] 研究者在实验中发现, - 3 -

4 Myxococcus xanthus 细菌群落中就存在作弊行为 [189] 2009 年是 Darwin 诞辰 200 周年, 也是他的 物种起源理论 (On the Origin of Species) 发表 150 周年 尽管 Darwin 学说成功地解释了很多自然现 象, 然而关于合作的涌现与维持始终是困惑 Darwin 的一个问题 [131] 在生命演化过程中, 合作产生了 的个体 (Population) 都采取策略 I, 那么所有采用策略 I 的个体的适应度要比任何可能的变异策略要大 如不满足这些条件, 变异策略可以入侵种群, 那么 I 将会消减, 即变得不稳定 有了 ESS 的概念, 就可以判断策略的稳定性 由于经典博弈中最重要的概念是收益矩阵 (Payoff 具有不同层次的复杂生命组织结构 从基因到 DNA, 从单细胞生物到多细胞生物, 从社会性昆虫到人类社会, 可以说合作是物种演化的重要条件之一 除 Darwin 所认为的演化的两种驱动力 : 变异和自然选择之外, 哈佛大学 Nowak 教授认为合作是演化过程中的第三个原动力 [108] 经典博弈论是研究依据其他参与者的效用 (Utility) 情况, 理性参与者策略之间相互作用的一门科学 博弈论的要素有两点 : 参与博弈者的目标或利益的相互冲突, 以及博弈者为理性人 现代博弈论已成为一门横跨数学 生物 心理学 计算机科学 运筹学 经济学 哲学 政治学 军事科学等领域的交叉学科 公认的现代博弈论起源于数 Matrix) 和收益, 因此可以把经典博弈中的想法应用到 ESS 中来 假设生物的适应度跟收益成简单的线性关系, 并且经典博弈中参与者理性 (Rationality) 选择的策略就对应于 ESS 与传统的 Nash 均衡相比,ESS 这个概念要更加严格一些, 因此可用于平衡点选择 因为所有的 ESS 必定是 Nash 均衡, 但只有严格对称的 Nash 均衡才有可能是 ESS 值得一提的是, 这里的 ESS 是一个 静态 的概念, 其假设只要求表现更好的策略具有更快的复制 ( 增长 ) 速率, 并不涉及具体的博弈动力学 1978 年,Taylor 和 Jonker 引入了复制动力学的概念 (Replicator Dynamics), 进一步拓展了演化动力学的研究 [176] 复制动力学的主要假设为给定的 学家 John Von Neumann 和经济学家 Morgenstern 在 ρ& i 1944 年的合著 : 博弈论和经济行为 [192] 尽管当策略类型的单位复制率正比于适应度之差 : ρi 时这本著作中博弈论的理论框架只适用于一些有限 的特例, 如零和非合作博弈问题, 但这本著作第一 ρ& i 次将数学方法引入博弈问题的研究之中, 对博弈论 = fitness of type i ρi 研究的发展起到了至关重要的作用 经过许多学者 average fitness. (1) 的努力, 特别是 Nash 在非合作博弈理论中创造性地引入策略均衡的概念之后 [102], 博弈论日渐成为一种应用性极强的分析工具, 被各学科研究者广泛使用 所谓 Nash 均衡 (Nash Equilibrium) 是指给定博弈中其他个体 (Player) 的策略时, 任何一个个体都不能依靠单方面地改变自己的策略来增加自己的收益 (Payoff) 的情形 换言之, 在 Nash 均衡中, 固定其他个体的策略, 个体所选策略已经是最佳的反应, 此时 Nash 均衡成为一致解的概念 基于经典博弈论, 演化博弈论为研究自然界及人类社会经济系统中的合作行为提供了一个方便的数学框架 [161, 107] 1973 年,Maynard-Smith 和 Price 开创性的将博弈论成功地应用到研究动物之间的争斗行为中 [162] 他们提出了鹰鸽博弈(Hawk-Dove Game) 模型 ( 又叫雪堆博弈 (Snowdrift Game) [70] 或胆小鬼博弈 (Chicken Game) [168]) 其主要思想就是采用依赖于接触频率的适应度 (Frequency-Dependent Fitness)( 对应博弈论中的效用或收益 ) 的策略选择更新方法 演化博弈论放弃了经典博弈中 Nash 均衡的概念, 而引入了演化稳 复制动力学是关于博弈动力学 ( 策略更新 ) 的连续确定性方程, 从而可以赋予前面介绍的 ESS 这一静态的概念以动力学含义 复制方程在不动点附近的稳定性将对应于策略的演化稳定性 (ESS) 尽管博弈论研究成果颇丰, 但作为研究合作行为的范例, 囚徒困境博弈 (Prisoner s Dilemma Game) 和雪堆博弈最为著名, 且使用最为广泛的两种模型 [38] 囚徒困境博弈是非零和博弈中较具代表性的例子, 反映了个体最佳选择并非团体最佳选择 1950 年就职于美国兰德公司 (RAND) 的 Flood 和 Dresher 提出相关困境 (Dilemma) 的理论, 并由 Tucker 以囚徒的方式进行阐述, 并因此命名为囚徒困境博弈 [133] 经典的囚徒困境如下: 警方逮捕 A B 两名犯罪嫌疑人, 但缺乏足够证据指控二人 于是警方隔离 A B 两人, 并分别和二人见面, 同时向双方提供以下选择 : 若一人招供并作证指控对方 ( 背叛对方 ), 而对方保持沉默, 此人将立刻无罪获释, 沉默者将判刑 10 年 ; 若二人都保持沉默 ( 相互合作 ), 则二人各被判刑半年 ; 若二人相互指证对方 ( 互相背叛 ), 则两人各被监禁 2 年 ( 如表 1 所示 ) 定策略 (Evolutionarily Stable Strategy, ESS) 的概念 假设策略 I 为 ESS, 则必须满足条件 : 如几乎所有 - 4 -

5 囚徒 B : 沉默 ( 合作 ) 囚徒 A : 两人各服刑半年沉默 ( 合作 ) 囚徒 A : A 立刻获释 ; 招供 ( 背叛 ) B 服刑 10 年 囚徒 B : 招供 ( 背叛 ) A 服刑 10 年 ; B 立刻获释 两人各服刑 2 年 表 1: 原始囚徒困境中的背叛与合作 Tab. 1: Defection and cooperation in the original Prisoner s Dilemma 由表 1 可见, 无论对手采取什么策略, 采取背叛总能获得较大的收益, 因而总是个体最好的选择 因此, 囚徒 A B 最终相互背叛, 各服刑 2 年 但是如果两人相互合作, 保持沉默, 就能获得更少的刑罚 ( 各半年 ) 这充分刻画了个体利益和团体利益的冲突, 体现了两难境地 (Dilemma) 刻画团体利益, 常用帕累托最优 (Pareto Optimum) 这个概念 帕累托最优是指在此状态下系统中所有个体的收益总和获得最高 因此, 用经典博弈论的纳什均衡理论来分析, 得到的均衡是二人都相互背叛对方, 但此时 Nash 均衡导致了系统的次优点 (Suboptimal), 并不是帕累托最优的 在一般形式的囚徒困境博弈中, 每个纯策略的个体 (Pure Strategist ) 都有两种选择 : 合作 (Cooperation,C) 与作弊 (Defection,D) D 策略个体利用 C 策略个体, 获得收益 T, 而被利用的 C 获得 S 双方都合作各获得 R, 都作弊各获得 P, 其中 T > R > P > S, 写成收益矩阵 M 为 C D C R S. (2) D T P 囚徒困境可以简化为只具有两个参数 b 和 c, 即捐赠 - 受益者的形式 (Donor-Recipient Version), 并具有恰当的生物学上的意义 [12,63] 此时合作行为意味着个体付出代价 c, 给另外一个个体带来 b 的收益, 通常 b > c 作弊( 背叛 ) 行为既不付出代价, 也不给其他个体带来任何收益 此时, 囚徒困境的收益矩阵元素分别为 R = b c, S = c, T = b 和 P = 0, 即 C D C b c c. (3) D b 0 由此可见, 合作是一种积极策略 (Active) 且 是建设性的 (Constructive), 作弊是一种消极被动 策略 (Passive) 并且, 囚徒困境的 ESS 是全部作 弊 (All Defection) 一般形式的雪堆博弈定义与囚徒困境博弈非常类似, 区别在于定义合作与背叛收益矩阵元素中 S 和 P 的排列顺序不同, 即 T > R > S > P 此时, 个体的最佳策略取决于对手的策略 : 当对手采取 C 策略时, 采取 D; 当对手采取 D 策略时, 采取 C 由此可以看出, 在雪堆博弈中, 个体的两难境地被弱化了, 此时永远作弊等纯策略并不是个体的最佳策略 同样地, 雪堆博弈存在一种简化形式 顾名思义, 两个汽车司机 A B 因大雪封路被困在回家途中 如两个司机相互合作, 都下车进行铲雪, 分担铲雪的总代价 c, 从而得以回家, 获得收益 b, 此时两个合作者的收益都是 b c / 2 但是当只有一个司机下车进行铲雪, 于是两人都能回家, 获得收益 b, 此时下车铲雪者独自承担铲雪的总代价 c, 获得净收益 b c, 而另外的作弊者不花任何代价获得收益 b 当两人都不主动下车铲雪, 都回不了家, 被困雪地, 都一无所获, 收益定义为 0 写成矩阵的形式为 C C b c / 2 D b D b 0 c. (4) 此时, 系统中存在三个纳什均衡 (Nash equilibria): (0, 1), (1, 0) 和 ( x *, 1 x * ) 其中纯策 略纳什均衡 (pure strategy) (0, 1) 和 (1, 0) 是演化不 稳定的, 而唯一的混合策略 (mixed strategy)nash 均衡为 x * = ( b c) /( b c / 2) 是演化稳定的, 即个 * * 体的最佳策略是以概率 x 采取合作, 以 1 x 的概 率采取作弊 换言之, 在无限大, 混合均匀人口中的复制动力学中 [80], 系统最终收敛到唯一内部平 * 衡点, 此时合作者的平衡稳定比例为 x 这个平衡 * 点 x 也是雪堆博弈中的唯一的 ESS 在雪堆博弈 中, 尽管系统中的合作者与作弊者可以共存, 但是此时所有个体的收益总和仍然少于所有个体都合作时的收益总和 因此, 雪堆博弈和囚徒困境一样, 揭示了关于合作的社会两难问题的实质 [37, 72] 值得一提的是, 定量评估现实世界中个体之间 - 5 -

6 的相互作用 ( 博弈活动 ) 中的收益矩阵非常不易 [70] 囚徒困境和雪堆博弈, 表面上看起来很相似的两类博弈, 在对合作的产生发展却有着许多本质不同的地方 如 Hauert 发现 [70], 与空间囚徒困境中合作水平得到了加强和提高的情况不同 [111], 空间结构却对雪堆博弈中的合作演化常常起到抑制作用 实验发现在共同入侵宿主细胞过程中, 噬菌体 (Phage) 之间策略行为常常是囚徒困境关系 [117, 188] 实验又发现, 一种酵母菌必须付出一定代价分泌一种酶来消化糖分获得它的生命活动能量, 而这种酶不但给分泌者带来了利益, 也给一些不分泌酶者带来了好处, 他们直接可以利用这些酶而获得能量 因此, 这类酵母菌之间的策略行为是雪堆博弈类型的 [58] 在研究社会两难问题的二人博弈 (Two-Person Game) 中, 除囚徒困境和雪堆博弈这两种常用的模型之外, 还有猎鹿博弈 (Stag-Hunt Game) 这种博弈充分揭示了自保 ( 独自狩猎, 但收获比较小 ) 和社会公共合作 ( 共同打猎, 可扑捉到鹿等大型动物 ) 的本质问题 [159] 其博弈矩阵元素排列顺序为 R > T > P > S 在这种博弈中, 个体的最佳策略是和对手保持一致, 因此又称为协调博弈 (Coordination Game)[168] 在协调博弈中, 两个纯策略都是 Nash 均衡 在复制动力学中, 这种系统有一个内部不稳定平衡点, 而两个边界点都是稳定平衡点, 因此被称为双稳博弈 (Bistability Game) [118] 有关二人博弈依据收益矩阵元素 T,R,S, P 之间大小排列顺利进行更详细的分类和描述, 请参见文献 [66, 67,132] 和综述 [168] 除二人博弈外, 多人博弈 ( N -Person Game), 如公用品博弈 (Public Goods Game, PGG), 为研究公共合作行为中的行为模式提供了十分有用的工具 [130] 在经济学行为实验中, 实验组织者分别给参 是搭便车者 (All Free-Riding) 很显然, 这造成了公用品悲剧 (The Tragedy of the Commons)[65], 由此可以得出, 即凡是属于最多数人的公共财产往往是最少受人照顾的 现实中有很多这样的例子, 包括公海渔业 全球气候变暖 [100] 温室气体排放 环境保护等 实际上, 当 N = 2 时, 公用品博弈退化为囚徒困境博弈 当 N > 2 时, 公用品博弈可以等价于多人参与的囚徒困境博弈 因而, 在没有其他有效促进合作机制的作用下, 公用品博弈中个体之间的合作局面比囚徒困境中更难涌现和维持 [45] 4 自组织合作涌现机制在研究个体之间的合作行为的涌现机制时, b c 参数的囚徒困境是最常用的范例之一 [9, 12, 63, 108] 这是因为这种囚徒困境博弈形式简单, 且能充分反映个体利益与群体利益相冲突的特点 自然界中的合作行为一般是有代价的, 因此通过分析收益与代价的比率 (Benefit-to-Cost Ratio), 可以研究这种合作的代价对合作行为的影响 作为二人囚徒困境的推广形式, 公用品博弈在人类经济行为学实验和模型分析中得到了广泛的应用与发展 [45, 76] 因此, 在进一步论述合作机制之前, 有必要对有关囚徒困境中合作演化和促进机制的国际前沿研究进行回顾和总结 容易看出, 在任何混合均匀的种群中, 作弊者的收益总是高于合作者 因此, 在缺乏充分合作机制的环境中, 种群将在自然选择作用下向完全作弊者慢慢演化, 直到合作者消失 为了解释自然界无处不在的合作行为, 自二十世纪六十年代以来, 一些可能的合作机理, 如亲缘选择 (Kin Selection)[63, 200] 直接( 间接 ) 互惠 (Direct/Indirect Reciprocity) [30, 116, 187, 198] 空间互惠(Spatial Reciprocity) 与实验的 N 个个体 c 金额的资金 [111, 112, 109, 120, 175] 群体选择(Group [68,71,74,76,77,78] 每个个体独立地并同时决定是否向公共库 (Common Pool) 中进行投资 公共库中募集到的资金增值 r 倍后 ( 1 < r < N 1), 再平均分给参与实验的 N 个个体, 而不论他们是否进行了投资 容易看出, 如果每个个体都进行投资, 那么所有个体的收益总和将最大化 此时每个个体的净收益为 ( r 1)c 但是, 在这种环境之下, 每个个体都面临着搭便车 (Free-Riding) 的诱惑, 即分享公共库中其他人的投资, 而自己不付出任何贡献 因为, 对于每个个体的单位投资额, 实际只有 r / N < 1 返还给投资个体 因此, 完全理性的个体绝对不投资, 这导致了公用品博弈的 Nash 均衡全 Selection) [164, 181,186, 202, 203] 等得到了一定的探讨 ( 参见综述 [108, 173]) 传统的演化分析方法是基于固定选择 (Constant Selection) 的, 个体的适应度只取决于个体的表现型 (Phenotype), 跟周围作用的个体无关 在这种假设下, 适应度景象 (Fitness Landscape) 是固定不变的 如 Fisher 自然选择基本定理 (Fisher s Fundamental Theorem of Natural Selection) 说明个体的适应度总是随着演化过程的深入而逐渐增加 [47] 这与上文所述的, 在取决于频率的选择的情况下, 个体的适应度随着对作弊者的自然选择而逐渐减小是相互矛盾的 因此, 固定选择的方法并不适合用来研究合作行为的演化 之后,Price 对 Fisher - 6 -

7 的理论进行了修正, 整合了演化和自然选择 (Evolution and Natural Selection) 因素, 统一了演化动力学理论 他的研究成果被命名为 Price 方程 (Price s Equation)[134, 135] 但是, 一些学者认为, 在合作行为机制研究中采用演化博弈动力学的思想和方法更为合适和简便 [107,161] 理论分析是基于静态的 单轮博弈 (One-Shot Game), 因此适合使用 Nash 均衡的概念 分析直接互惠的理论框架是迭代囚徒困境博弈 (Iterated Prisoner s Dilemma) 当囚徒困境博弈在两个个体之间进行多次时, 每个个体都可以根据上次博弈的结果选择进行下次博弈的策略 Boyd 等人指出迭代囚 徒困境博弈中不存在纯策略的 ESS [27] 在 亲缘选择与群体选择亲缘选择的思想首先由 Fisher [47] 和 Haldane [62] 提出并引起讨论, 但是由 Hamilton 首次进行了数学模型定量描述, 并得到了所谓的为 Hamilton 规则 (Hamilton s rule) 当合作行为的受益者和实施者具有基因关联 (Genetic Relationship) 时, 自然选择有利于合作行为 更精确地,Hamilton 规则指出, 个体之间的关系系数 r ( The Coefficient of Relatedness) 必须超过合作 ( 利他 ) 行为的代价与收益比 c / b, 即 r > c / b 合作行为增加的不是个体本身的适应度, 而是个体的广义适应度 (Inclusive Fitness) [161, 175, 200] 亲缘选择适用于具有基因关联的个体之间的合作行为, 但在人类社会中, 合作行为大量存在于非亲属 非相关 (Unrelated) 个体之间 [151] 这时 群体选择 机制促进了合作的产生与维持 显然, 一个全部由合作者组成的群体要比一个全由作弊者组成的全体要更成功, 更占优势 因此, 在多层次选择 (Multilevel Selection) 的情况下, 这群合作者将最终取代全为作弊者的群体 [202, 203] Traulsen 和 Nowak 的研究结果表明, 在弱选择和极少群体分裂的情况下, 合作演化的条件可以表示为一个简单规则 [181]: b / c > 1+ n / m, 这里 n 是群体所允许容纳的最大个体数, m 为群体的个数 遗憾的是, 关于亲缘选择学说和群体选择学说在国际演化生物理论界存在众多争论 [108] 虽然亲缘选择理论在实际应用中存在一些局限性, 如工蜂有时也会偷偷地产卵 ; 当受精过的蜂蛹有机会发育成蜂后时, 会竞相朝蜂后发育, 尽管一个蜂巢只能有一个蜂后 [137] 但是一些学者仍然相信可以通过一些理论修正使得亲缘选择学说成立 相比而言, 由于群体选择理论不涉及亲缘关系条件, 其应用范围相对广泛, 尤其能够解释人类社会活动中甚至是 年代末的 Axelrod 锦标赛 (Axelrod Tournament) 中 [9, 10,11, 12], 英国数学家 生物学家 Rapoport 提出的 针锋相对 (Tit-for-Tat,TFT) 策略脱颖而出, 打败了其它策略 所谓 TFT 是一个偏向合作的策略, 第一步采取合作, 然后重复其对手上一步的策略 然而,TFT 在有环境干扰时表现并不好, 两个采用 TFT 策略的个体在 颤抖的手 (Trembling Hands) 的效应的影响下, 容易走向相互作弊的极端 Nowak 等人在带有随机干扰噪声环境中的研究表明 TFT 是合作涌现的催化剂, 一旦 TFT 逐渐取代完全作弊者 (Always Defect), 一种慷慨的 TFT (Generous Tit-for-Tat,GTFT) 会涌现出来 [105, 114] 与 TFT 相比,GTFT 是一种具有宽恕性 (Forgiving) 的策略 : 即使对手作弊, 也以一定概率 ( 1 c / b ) 跟对手进行合作 [114] 在 GTFT 逐渐占优时, 由于随机漂变 (Random Drift), 整个种群会逐渐失去惩罚的能力 ( 即与对手针锋相对 ), 向全部合作 (Always Cooperate) 演化 然而, 全部合作又最终能够被全部作弊策略取代, 因此形成了合作与作弊的战争与和平的循环 (Cycles of War and Peace) [118] 进一步的研究表明赢留输变策略 (Win-Stay-Lose-Shift,WSLS) 比 TFT,GTFT 更鲁棒, 具有更好的表现 [115] WSLS 策略是指个体如果现在的策略获得的收益大于某个期望水平 (Aspiration Level), 那么下一步就保持这个策略不变, 否则就切换到另外一个策略 因此,WSLS 是一种形式比较简单的学习策略 [168] 当 TFT 策略建立了合作,WSLS 就能维持合作 [108] 在二人博弈中, 个体之间的博弈行为可以通过谈判的方式达成一致 合作博弈动力学中的谈判行为也引起了学者的兴趣 [97, 174] 对完全陌生人的合作帮助行为 4.3 间接互惠 4.2 直接互惠 间接互惠是指 今天我帮助了你, 那么明天将 直接互惠是指今天你帮助了我, 那么明天我会帮助你 [187] 要使得直接互惠在两个个体之间起作用, 这一对个体必须能够相遇多次并相互博弈, 且个体需要记住对方的 样子 (Face) 经典的合作 会有其他人来帮助我 [116] 一些实验观察研究表明间接互惠在动物和人类中普遍存在 [30, 198] 由于现实条件的限制, 当一个个体对另外一个个体进行了帮助, 但还没有等到这个受帮助的个体进行 - 7 -

8 回馈, 这个帮助的个体已经离开了 由于直接互惠 质网络 (Homogeneous Graphs ) 上, 得到了对 不太可能在同样两个个体之间得以实现, 间接互惠 b / c > k 规则的有限尺度修正公式 : 成了更为普遍的互惠形式 间接互惠中最重要的是个体通过合作帮助等行为建立良好的声望 (Reputation), 从而被其他人帮助 间接互惠发挥作用, 个体需要记住其他个体的名字 ( 及声望 ) 因此个体之间的交流沟通是必不可少的 这种交流沟通可能与语言的产生与高等智慧的演化具有直接关系 [106, 110, 119], 并导致了道德体系 (Moral System) 与社会范式 (Social Norm) 的演化与形成 [108] b / c > k( N 2) /( N 2k), 其中 N 为个体的数目 除上文已经介绍的常见的几种合作机制外 [108], 其他的一些机制 [32, 72, 71, 78, 96, 95, 143, 193], 如自愿参加博弈 [73, 74, 76, 77] 奖励与惩罚 [28, 29, 40, 76, 77, 121, 138, 155] 基于标签的合作 (Tag-Based Cooperation), 又称作合作的色动力学 (Chromodynamics of Cooperation) [4, 85,142, 163, 4.4 空间互惠另一种新型的互惠形式, 被称为空间互惠, 近 170, 182] 受成功驱使的迁徙(Success-Driven Migration) [79] 等也得到了比较深入的研究与探讨 一般地, 某种合作机制之所以能够促进合作的 年来引起了研究者的广泛关注 空间互惠理论是受 Nowak 等人的关于空间博弈 (Spatial Game) 经典论文启发所产生的 [109,111, 112] Nowak 等人发现当个体被放置在空间方格子上, 并只与周围最近邻居进行博弈和竞争时, 合作者会 抱团, 形成合作者的团簇 (Clusters of Cooperators), 从而合作者可以相互支持对方, 共同抵御周边作弊者的入侵 [111] 在空间博弈中这种合作者形成团簇从而维持合作的机制被称之为空间互惠 [108] 传统方法是用复制动力学分析无结构人口 (Non-Structured Population) 中的合作演化动力学 [80,107,118,162] 但是, 现实中个体之间的作用关系往往是有结构的 [91,92] 每个个体只占据一个空间方格(Spatial Lattice) 或社会网络中的一个节点, 且通常只与周围直接邻居有博弈作用关系 因此, 针对传统方法的弊端, 产生了演化图论 (Evolutionary Graph Theory) 这种以网络结构刻画个体之间的博弈关系的新的研究方法 [93, 120, 175] 这种方法又被称之为复杂网络上的演化博弈 (Evolutionary Games on Complex Networks)( 请参见综述 [168]) 虽然空间博弈会引发合作时空组织的有趣现象, 如合作的万花筒 (Kaleidoscope of Cooperation) [23, 66, 67, 69, 89, 90, 101, 111, 112, 129, 169], 但网络中个体策略空间配置关系纷繁复杂, 给严格的定量的数学分析带来了困难 因此, 对于空间格子等规则网络 (Regular Graphs), 一般用对估计 (Pair Approximation) 等方法进行近似分析 [75] Ohtsuki 等人利用对估计的方法 [120], 发现了在社会网络上自然选择利于合作行为产生的一个充分性判据 ( b / c > k 规则 ): b / c > k, 其中 b c 分别为合作行为的收益和代价, k 为网络的平均度 在此发现基础上,Taylor 等人利用广义适应度的计算方法 (Inclusive Fitness Analysis) [175], 在一类同 涌现和维持则是因为合作机制加强了合作者之间的 聚类 (Clustering of Cooperators and Assortment of Cooperators), 使得合作者之间的博弈关系比与其他作弊个体之间更为频繁 即使合作暂时受到作弊的压制, 但合作也能通过合作机制迅速地建立起来, 从而使得合作得到强化和维持 5 结论与展望近年来, 由于复杂系统和复杂性科学研究的蓬勃发展, 演化博弈动力学作为研究复杂系统的一个可行切入点, 在多学科交叉综合研究中发挥了重要的作用 合作涌现机制研究涉及多个学科的综合, 是一个很有发展前景的研究领域 由于当前合作复杂性及演化动力学研究的进展, 新的方向不断涌现, 也产生了一系列公开难题 (Open Problem) 与挑战 在 2009 年 9 月 9 日, 在哈佛大学举办的 Edward Wilson 和 James Waston 的对话上,Wilson 就表示合作的演化机制研究可作为青年科研工作者选择的一个研究方向 目前, 涉及合作机制的演化博弈动力学研究主要关注 2 2 博弈, 即以最简单的二人二策略博弈如囚徒困境和雪堆博弈为基本模型 在弱选择的条件下, 得到了一些理论结果 [6, 21, 56, 113, 172, 178, 179, 183, 185, 184, 186] 但对于强选择[186] 带有种群结构 (Population Structure)[123, 122, 125, 124, 171] 策略变异或试验(Strategy Mutation or Experimentation) 等情形下的研究 [87, 180], 还不够深入 对于多人多策略的博弈研究 [83], 如石头 - 剪刀 - 布博弈 (Rock-Scissors-Paper Game) 等循环博弈 (Cycling Game) [88, 139], 目前还处于理论探索的初级阶段 [7] 为了研究合作的演化, 许多学者将惩罚机制的研究作为破解合作机理难题的敲门砖 关于惩罚的 - 8 -

9 演化, 目前学术界存在一些争论 大量已有模型和实验研究表明 : 奖赏和惩罚都可以促进合作, 但惩罚比奖赏更有效些 [45, 60, 155] 然而最近实验研究结果表明 : 在真正的迭代博弈 (Repeated Games) 中, 具有代价的惩罚 (Costly Punishment) 虽然可以促进合作, 却不是一种十分有效的行为, 因为它浪费了社会资源 惩罚的成本几乎抵消了合作水平提高带来的好处, 并且赢者几乎不惩罚 [40] Rand 等人发现在促进合作上, 萝卜 ( 奖赏 ) 比 大棒 ( 惩罚 ) 更有效些 [121, 138] 因此有必要进一步从理论和实验上探讨惩罚行为的演化和产生机理 除了理论研究, 数值仿真实验日渐成为了一种重要的研究方式, 被广泛应用于合作行为的涌现与演化研究 由于复杂网络上的演化博弈过程在数学上很难严格的分析和证明, 只能依赖大量的数值仿真 因此, 只有大量的计算工作才能详尽地揭示复杂网络的拓扑性质, 如网络的小世界性 [148] 和异质性 [144] 等对合作演化的影响 ( 请参考综述文献 [168]) Santos 等人通过数值仿真发现异质的无标度网络拓扑能有效地促进合作 [149, 144, 145, 147, 150] 但是 Fu 等人发现在一些条件下, 网络的异质性并不总是利于合作 [51, 53] 因此, 有必要进一步发展新的数学理论和工具, 对一般网络上的演化博弈过程进行严格的数学分析 [5], 澄清并统一网络拓扑性质对合作演化影响的认识 网络和博弈动力学的共演化 (Coevolutionary Dynamics of Networks and Games) 是目前演化博弈研究中的一个热点问题 [84, 52, 50, 54, 128, 127, 146, 160, 165, 153, 152, 207, 206] 网络拓扑影响博弈结果, 而博弈结果反作用于网络拓扑, 调整网络拓扑 ( 或社会关系 ) 与静态网络上的博弈过程相比, 这种情形更符合实际 这类工作主要基于断边重连的思想 (Edge Rewiring) [207], 研究自适应网络上的演化博弈过程 (Games on Adaptive Networks) 目前大部分的结论都是基于数值仿真结果, 由于模型的复杂性, 在理论研究上进展缓慢 因此, 完善理论工具 进一步探索共演化过程中出现的极其丰富的动力学行为, 是一个很有发展前景的研究方向 - 9 -

10 参考文献 (References): [1] 钱学森, 于景元, 戴汝为. 一个科学新领域 开放的复杂巨系统及其方法论. 自然杂志, 第 1 期, [2] M. Ackermann, B. Stecher, N. E. Freed, P. Songhet, W.-D. Hardt, and M. Doebeli. Self-destructive cooperation mediated by phenotypic noise. Nature, 454: , [3] R. Albert and A.-L. Barabasi. Statistical mechanics of complex networks. Rev. Mod. Phys., 74(1):47 97, [4] T. Antal, H. Ohtsuki, J. Wakeley, P. D. Taylor, and M. A. Nowak. Evolution of cooperation by phenotypic similarity. Proc. Natl. Acad. Sci. U.S.A., 106: , [5] T. Antal, S. Redner, and V. Sood. Evolutionary dynamics on degree-heterogeneous graphs. Phys. Rev. Lett., 96:188104, [6] T. Antal and I. Scheuring. Fixation of strategies for an evolutionary game in finite populations. Bull. Math. Biol., 68: , [7] T. Antal, A. Traulsen, H. Ohtsuki, C. E. Tarnita, and M. A. Nowak. Mutation-selection equilibrium in games with multiple strategies. J. Theor. Biol., 258: , [8] A. Arenas, A. Diaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou. Synchronization in complex networks. Phys. Rep., 469:93 153, [9] R. Axelrod. The evolution of cooperation. Basic Books, New York, [10] R. Axelrod. The complexity of cooperation. Princeton University Press, Princeton, NJ, [11] R. Axelrod and D. Dion. The further evolution of cooperation. Science, 242: , [12] R. Axelrod and W. D. Hamilton. The evolution of cooperation. Science, 211: , [13] P. Bak. How nature works: the science of self-organised criticality. Copernicus Press, New York, NY, [14] P. Bak, C. Tang, and K. Wiesenfeld. Self-organized criticality: An explanation of the 1/ f noise. Phys. Rev. Lett., 59:381, [15] Y. Bar-Yam. Dynamics of complex systems. Addison-Wesley, Reading, MA, [16] A.-L. Barabasi. Linked: the new science of networks. Perseus, Cambridge, MA, [17] A.-L. Barabasi. Taming complexity. Nature Physics, 1:68 70, [18] A.-L. Barabasi. Scale-free networks: a decade and beyond. Science, 325: , [19] A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286: ,1999. [20] K. Binmore. Playing fair. MIT Press, Cambridge, MA, [21] K. Binmore and L. Samuelson. Evolutionary drift and equilibrium selection. Rev. Econ. Stud., 66: , [22] K. G. Binmore. Game theory and the social contract: just playing. MIT Press, Cambridge, MA, [23] L. E. Blume. The statistical mechanics of strategic interaction. Games Econ. Behav., 5: , [24] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: structure and dynamics. Phys. Rep., 424: , [25] B. Bollobas. Random graphs. Academic Press, London, [26] S. Bowles. Did warfare among ancestral hunter-gatherers affect the evolution of human social behaviors. Science, 324: , [27] R. Boyd and J. P. Lorberbaum. No pure strategy is evolutionarily stable in the repeated prisoner s dilemma game. Nature, 327:58 59, [28] H. Brandt, C. Hauert, and K. Sigmund. Punishment and reputation in spatial public goods games. Proc. R. Soc. Lond. B, 270: , [29] H. Brandt, C. Hauert, and K. Sigmund. Punishing and abstaining for public goods. Proc. Natl. Acad. Sci. U.S.A., 103: , [30] R. Bshary and A. S. Grutter. Image scoring and cooperation in a cleaner fish mutualism. Nature, 441: , [31] R. Bshary, A. S. Grutter, A. S. T. Willener, and O. Leimar. Pairs of cooperating cleaner fish provide better service quality than singletons. Nature, 455: , [32] M. Burtsev and P. Turchin. Evolution of cooperative strategies from first principles. Nature, 440: , [33] C. Castellano, S. Fortunato, and V. Loreto. Statistical physics of social dynamics. Rev. Mod. Phys., 81:591, [34] A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. SIAM Review, In press, [35] T. H. Clutton-Brock, M. J. O Riain, P. N. M. Brotherton, D. Gaynor, R. Kansky, A. S. Griffin, and M. Manser. Selfish sentinels in cooperative mammals. Science, 284: , [36] A. M. Coleman. Game theory and its application in the social and biological sciences. Butterworth Heinemann Press, Oxford, [37] R. M. Dawes. Social dilemmas. Annu. Rev. Psychol., 31: , [38] M. Doebeli and C. Hauert. Models of cooperation based on the prisoner s dilemma and the snowdrift game. Ecol. Lett., 8: , [39] M. Doebeli, C. Hauert, and T. Killingback. The evolutionary origin of cooperators and defectors. Science, 306: , [40] A. Dreber, D. G. Rand, D. Fudenberg, and M. A. Nowak. Winners don t punish. Nature, 452: , [41] L. A. Dugatkin. Cooperation among animals: an evolutionary perspective. Oxford University Press, Oxford, [42] P. Erdos and A. Renyi. On the evolution of random

11 graphs. Publ. Math. Inst. Hung. Acad. Sci. Ser. A, 5: [43] D. Lazer et al. Computational social science. Science, 323: , [44] E. Fehr, H. Bernhard, and B. Rockenbach. Egalitarianism in young children. Nature, 454: , [45] E. Fehr and U. Fischbacher. The nature of human altruism. Nature, 425: , [46] F. Fiegna, Y.-T. N. Yu, S. V. Kadam, and G. J. Velicer. Evolution of an obligate social cheater to a superior cooperator. Nature, 441: , [47] R. A. Fisher. The genetical theory of natural selection. Clarendon Press, Oxford, [48] J. H. Fowler. Altruistic punishment and the origin of cooperation. Proc. Natl. Acad. Sci. U.S.A., 102: , [49] S. A. Frank. Foundations of social evolution. Princeton University Press, Princeton, NJ, [50] F. Fu, C. Hauert, M. A. Nowak, and L. Wang. Reputation-based partner choice promotes cooperation in social networks. Phys. Rev. E, 78:026117, [51] F. Fu, L.-H. Liu, and L. Wang. Evolutionary prisoner s ilemma game on heterogeneous Newman-Watts small-world network. Eur. Phys. J. B, 56: , [52] F. Fu and L. Wang. Coevolutionary dynamics of opinions and networks: from diversity to uniformity. Phys. Rev. E, 78:016104, [53] F. Fu, L. Wang, M. A. Nowak, and C. Hauert. Evolutionary dynamics on graphs: efficient method for weak selection. Phys. Rev. E, 79:046707, [54] F. Fu, T. Wu, and L. Wang. Partner switching stabilizes cooperation in coevolutionary prisoner s dilemma. Phys. Rev. E, 79:036101, [55] D. Fudenberg and D. K. Levine. The theory of learning in games. MIT Press, Cambridge, MA, [56] D. Fudenberg, M. A. Nowak, C. Taylor, and L. A. Imhof. Evolutionary game dynamics in finite populations with strong selection and weak mutation. Theor. Pop. Biol., 70: , [57] H. Gintis. Game theory evolving: a problem-centered introduction to modeling strategic interaction. Princeton University Press, Princeton, NJ, [58] J. Gore, H. Youk, and A. van Oudenaarden. Snowdrift game dynamics and facultative cheating in yeast. Nature, 459: , [59] T. Gross and B. Blasius. Adaptive coevolutionary networks: a review. J. R. Soc. Interface, 5: , [60] O. Gurerk, B. Irlenbusch, and B. Rockenbach. The competitive advantage of sanctioning institutions. Science, 312: , [61] H. Haken. Synergetics: an introduction : nonequilibrium phase transitions and self-organization in physics, chemistry, and biology. Springer-Verlag, New York, [62] J. B. S. Haldane. Population genetics. New Biology, 18:34 51, [63] W. D. Hamilton. The genetical evolution of social behaviour. I. J. Theor. Biol., 7:1 16, [64] S. K. Hansen, P. B. Rainey, J. A. J. Haagensen, and S. Molin. Evolution of species interactions in a biofilm community. Nature, 445: , [65] G. Hardin. The tragedy of the commons. Science, 162: , [66] C. Hauert. Fundamental clusters in spatial 2 2 games. Proc. R. Soc. Lond. B, 268: , [67] C. Hauert. Effects of space in 2 2 games. Int. J. Bifurc. Chaos, 12: , [68] C. Hauert. Cooperation, collectives formation and specialization. Adv. Complex Syst., 9: , [69] C. Hauert. Spatial effects in social dilemmas. J. Theor. Biol., 240: , [70] C. Hauert and M. Doebeli. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature, 428: , [71] C. Hauert, M. Holmes, and M. Doebeli. Evolutionary games and population dynamics: maintenance of cooperation in public goods games. Proc. R. Soc. Lond. B, 273: , [72] C. Hauert, F. Michor, M. A. Nowak, and M. Doebeli. Synergy and discounting of cooperation in social dilemmas. J. Theor. Biol., 239: , [73] C. Hauert, S. De Monte, J. Hofbauer, and K. Sigmund. Replicator dynamics for optional public good games. J. Theor. Biol., 218: , [74] C. Hauert, S. De Monte, J. Hofbauer, and K. Sigmund. Volunteering as red queen mechanism for cooperation in public goods games. Science, 296: , [75] C. Hauert and G. Szab o. Game theory and physics. Am. J. Phys., 73(5): , [76] C. Hauert, A. Traulsen, H. Brandt, M. A. Nowak, and K. Sigmund. Via freedom to coercion: the emergence of costly punishment. Science, 316: , [77] C. Hauert, A. Traulsen, H. De Silva nee Brandt, M. A. Nowak, and K. Sigmund. Public goods with punishment and abstaining in finite and infinite populations. Biol. Theor., 3(2): , [78] C. Hauert, J. Y. Wakano, and M. Doebeli. Ecological public goods games: Cooperation and bifurcation. Theor. Pop. Biol., 73: , [79] D. Helbing and W. Yu. The outbreak of cooperation among success-driven individuals under noisy conditions. Proc. Natl. Acad. Sci. U.S.A., 106: , [80] J. Hofbauer and K. Sigmund. Evolutionary games and population dynamics. Cambridge Univ. Press, Cambridge, UK, [81] J. H. Holland. Hidden order: how adaptation builds complexity. Addison-Wesley, Reading, MA, [82] J. H. Holland. Emergence: from chaos to order. Addison-Wesley, Reading, MA, [83] L. A. Imhof, D. Fudenberg, and M. A. Nowak. Evolutionary cycles of cooperation and defection. Proc. Natl. Acad. Sci. U.S.A., 102: , [84] M. O. Jackson and A. Watts. On the formation of interaction networks in social coordination games. Games Econ. Behav., 41: , [85] V. A. A. Jansen and M. van Baalen. Altruism through beard chromodynamics. Nature, 440: , 2006.

12 [86] K. Jensen, J. Call, and M. Tomasello. Chimpanzees are rational maximizers in an ultimatum game. Science, 318: , [87] M. Kandori, G. J. Mailath, and R. Rob. Learning, mutation, and long run equilibria in games. Econometrica, 61:29 56, [88] B. Kerr, M. A. Riley, M. W. Feldman, and B. J. M. Bohannan. Local dispersal promotes biodiversity in a real-life game of rock-paper-scissors. Nature, 418: , [89] T. Killingback and M. Doebeli. Self-organized criticality in spatial evolutionary game theory. J. Theor. Biol., 191: , [90] P. Langer, M. A. Nowak, and C. Hauert. Spatial invasion of cooperation. J. Theor. Boil., 250: , [91] S. A. Levin, B. Grenfell, A. Hastings, and A. S. Perelson. Mathematical and computational challenges in population biology and ecosystems science. Science, 275: , [92] S. A. Levin and R. T. Paine. Disturbance, patch formation, and community structure. Proc. Natl. Acad. Sci. U.S.A., 71: , [93] E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433: , [94] R. C. MacLean and I. Gudelj. Resource competition and social conflict in experimental populations of yeast. Nature, 441: , [95] J. M. McNamara, Z. Barta, L. Fromhage, and A. I. Houston. The coevolution of choosiness and cooperation. Nature, 451: , [96] J. M. McNamara, Z. Barta, and A. I. Houston. Variation in behaviour promotes cooperation in the prisoner s dilemma game. Nature, 428: , [97] J. M. McNamara, C. E. Gasson, and A. I. Houston. Incorporating rules for responding into evolutionary games. Nature, 401: , [98] S. Milgram. The small world problem. Psychol. Today, 1(1):60 67, [99] M. Milinski. Tit for tat in sticklebacks and the evolution of cooperation. Nature, 325: , [100] M. Milinski, R. D. Sommerfeld, H.-J. Krambeck, F. A. Reed, and J. Marotzke. The collective risk social dilemma and the prevention of simulated dangerous climate change. Proc. Natl. Acad. Sci. U.S.A., 105: , [101] M. Nakamaru, H. Matsuda, and Y. Iwasa. The evolution of cooperation in a lattice-structured population. J. Theor. Boil., 184:65 81, [102] J. Nash. Equilibrium points in n -person games. Proc. Natl. Acad. Sci. U.S.A., 36:48 49, [103] M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45: , [104] G. Nicolis and I. Prigogine. Self-organization in non-equilibrium systems: from dissipative structures to order through fluctuations. John Wiley & Sons, Hoboken, NJ, [105] M. Nowak and K. Sigmund. Chaos and the evolution of cooperation. Proc. Natl. Acad. Sci. U.S.A., 90: , [106] M. A. Nowak. Evolutionary biology of language. Phil. Trans. R. Soc. Lond. B, 355: , [107] M. A. Nowak. Evolutionary dynamics: exploring the equations of life. Harvard University Press, Cambridge, MA, [108] M. A. Nowak. Five rules for the evolution of cooperation. Science, 314: , [109] M. A. Nowak, S. Bonhoeffer, and R. M. May. Spatial games and the maintenance of cooperation. Proc. Natl. Acad. Sci. U.S.A., 91: , [110] M. A. Nowak, N. L. Komarova, and P. Niyogi. Evolution of universal grammer. Science, 291: , [111] M. A. Nowak and R. M. May. Evolutionary games and spatial chaos. Nature, 359: , [112] M. A. Nowak and R. M. May. The spatial dilemmas of evolution. Int. J. Bifurc. Chaos, 3:35 78, [113] M. A. Nowak, A. Sasaki, C. Taylor, and D. Fudenberg. Emergence of cooperation and evolutionary stability in finite populations. Nature, 428: , [114] M. A. Nowak and K. Sigmund. Tit for tat in heterogeneous populations. Nature, 355: , [115] M. A. Nowak and K. Sigmund. A strategy of win-stay, lose-shift that outperforms tit-for-tat in the prisoner s dilemma game. Nature, 364:56 58, [116] M. A. Nowak and K. Sigmund. Evolution of indirect reciprocity by image scoring. Nature, 393: , [117] M. A. Nowak and K. Sigmund. Phage-lift for game theory. Nature, 398: , [118] M. A. Nowak and K. Sigmund. Evolutionary dynamics of biological games. Science, 303: , [119] M. A. Nowak and K. Sigmund. Evolution of indirect reciprocity. Nature, 437: , [120] H. Ohtsuki, C. Hauert, E. Lieberman, and M. A. Nowak. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 441: , [121] H. Ohtsuki, Y. Iwasa, and M. A. Nowak. Indirect reciprocity provides only a narrow margin of efficiency for costly punishment. Nature, 457:79 82, [122] H. Ohtsuki and M. A. Nowak. Evolutionary games on cycles. Proc. R. Soc. Lond. B, 273: , [123] H. Ohtsuki and M. A. Nowak. The replicator equation on graphs. J. Theor. Biol., 243:86 97, [124] H. Ohtsuki and M. A. Nowak. Evolutionary stability on graphs. J. Theor. Biol., 251: , [125] H. Ohtsuki, M. A. Nowak, and J. M. Pacheco. Breaking the symmetry between interaction and replacement in evolutionary dynamics on graphs. Phys. Rev. Lett., 98:108106, [126] R. Olfati-Saber, A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 95(1): , [127] J. M. Pacheco, A. Traulsen, and M. A. Nowak. Active linking in evolutionary games. J. Theor. Biol.,

13 243: , [128] J. M. Pacheco, A. Traulsen, and M. A. Nowak. Coevolution of strategy and structure in complex networks with dynamical linking. Phys. Rev. Lett., 97:258103, [129] K. M. Page, M. A. Nowak, and K. Sigmund. The spatial ultimatum game. Proc. R. Soc. Lond. B, 267: , [130] T. R. Palfrey and H. Rosenthal. Participation and the provision of discrete public goods: a strategic analysis. J. Public Econ., 24: , [131] E. Pennisi. On the origin of cooperation. Science, 325: , [132] M. Posch, A. Pichler, and K. Sigmund. The efficiency of adapting aspiration levels. Proc. R. Soc. Lond. B, 266: , [133] W. Poundstone. Prisoner d Dilemma. Doubleday, New York, [134] G. R. Price. Selection and covariance. Nature, 227: , [135] G. R. Price. Fisher s fundamental theorem made clear. Ann. Human Genetics, 36: , [136] I. Prigogine. The end of certainty. Free Press, New York, [137] D. C. Queller. To work or not to work. Nature, 444:42 43, [138] D. G. Rand, A. Dreber, T. Ellingsen, D. Fudenberg, and M. A. Nowak. Positive interactions promote public cooperation. Science, 325: , [139] T. Reichenbach, M. Mobilia, and E. Frey. Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games. Nature, 448: , [140] W. Ren, R. W. Beard, and E. Atkins. Information consensus in multivehicle cooperative control: collective group behavior through local interaction. IEEE Contr. Syst. Mag., 27(2):71 82, [141] C. W. Reynolds. Flocks, herds, and schools: a distributed behavioral model. Comput. Graph., 21(4):25 34, [142] R. L. Riolo, M. D. Cohen, and R. Axelrod. Evolution of cooperation without reciprocity. Nature, 414: , [143] G. Roberts and T. N. Sherratt. Development of cooperative relationships through increasing investment. Nature, 394: , [144] F. C. Santos and J. M. Pacheco. Scale-free networks provide a unifying framework for the emergence of cooperation. Phys. Rev. Lett., 95:098104, [145] F. C. Santos and J. M. Pacheco. A new route to the evolution of cooperation. J. Evol. Biol., 19: , [146] F. C. Santos, J. M. Pacheco, and T. Lenaerts. Cooperation prevails when individuals adjust their social ties. PLoS Comp. Biol., 2:e140, [147] F. C. Santos, J. M. Pacheco, and T. Lenaerts. Evolutionary dynamics of social dilemmas in structured heterogeneous populations. Proc. Natl. Acad. Sci. U.S.A., 103: , [148] F. C. Santos, J. F. Rodrigues, and J. M. Pacheco. Epidemic spreading and cooperation dynamics on homogeneous small-world networks. Phys. Rev. E, 72:056128, [149] F. C. Santos, J. F. Rodrigues, and J. M. Pacheco. Graph topology plays a determinant role in the evolution of cooperation. Proc. R. Soc. Lond. B, 273:51 55, [150] F. C. Santos, M. D. Santos, and J. M. Pacheco. Social diversity promotes the emergence of cooperation in public goods games. Nature, 454: , [151] I. Scheuring. Evolution of generous cooperative norms by cultural group selection. J. Theor. Biol., 257: , [152] S. Van Segbroeck, F. C. Santos, T. Lenaerts, and J. M. Pacheco. Reacting differently to adverse ties promotes cooperation in social networks. Phys. Rev. Lett., 102:058105, [153] S. Van Segbroeck, F. C. Santos, A. Nowe, J. M. Pacheco, and T. Lenaerts. The evolution of prompt reaction to adverse ties. BMC Evol. Biol., 8:287, [154] K. Sigmund. Games of life. Penguin Books, London, [155] K. Sigmund, C. Hauert, and M. A. Nowak. Reward and punishment. Proc. Natl. Acad. Sci. U.S.A., 98: , [156] K. Sigmund and M. A. Nowak. Evolutionary game theory. Curr. Biol., 9:R503 R505, [157] H. A. Simon. On a class of skew distribution functions. Biometrika, 42: , [158] B. Sinervo and J. Clobert. Morphs, dispersal behavior, genetic similarity, and the evolution of cooperation. Science, 300: , [159] B. Skyrms. The stag hunt and evolution of social structure. Cambridge University Press, Cambridge, UK, [160] B. Skyrms and R. Pemantle. A dynamic model of social network formation. Proc. Natl. Acad. Sci. U.S.A., 97: , [161] J. Maynard Smith. Evolution and the theory of games. Cambridge Univ. Press, Cambridge, UK, [162] J. Maynard Smith and G. R. Price. The logic of animal conflict. Nature, 246:15 18, [163] S. Smukalla, M. Caldara, N. Pochet, A. Beauvais, S. Guadagnini, C. Yan, M. D. Vinces, A. Jansen, M. C. Prevost, J. Latge, G. R. Fink, K. R. Foster, and K. J. Verstrepen. Flo1 is a variable green beard gene that drives biofilm-like cooperation in budding yeast. Cell, 135: , [164] E. Sober and D. S. Wilson. Unto others: the evolution and psychology of unselfish behavior. Harvard University Press, Cambridge, MA, [165] K. P. Spiekermann. Sort out your neighbourhood: Public good games on dynamic networks. Synthese, 168: , [166] S. H. Strogatz. Exploring complex networks. Nature, 410: , [167] S. H. Strogatz. Sync: the emerging science of spontaneous order. Hyperion, New York, [168] G. Szabo and G. Fath. Evolutionary games on graphs. Phys. Rep., 446:97 216,

14 [169] G. Szabo and C. Toke. Evolutionary prisoner s dilemma game on a square lattice. Phys. Rev. E, 58:69, [170] C. E. Tarnita, T. Antal, H. Ohtsuki, and M. A. Nowak. Evolutionary dynamics in set structured populations. Proc. Natl. Acad. Sci. U.S.A., 106: , [171] C. E. Tarnita, H. Ohtsuki, T. Antal, F. Fu, and M. A. Nowak. Strategy selection in structured populations. J. Theor. Biol., 259: , [172] C. Taylor, D. Fudenberg, A. Sasaki, and M. A. Nowak. Evolutionary game dynamics in finite populations. Bull. Math. Biol., 66: , [173] C. Taylor and M. A. Nowak. Transforming the dilemma. Evolution, 61: , [174] P. D. Taylor and T. Day. Stability in negotiation games and the emergence of cooperation. Proc. R. Soc. Lond. B, 271: , [175] P. D. Taylor, T. Day, and G. Wild. Evolution of cooperation in a finite homogeneous graph. Nature, 447: , [176] P. D. Taylor and L. Jonker. Game dynamics and evolutionary stable strategies. Math. Biosci., 40: , [177] R. Thom. Structural stability and morphogenesis: an outline of a general theory of models. Addison-Wesley, Reading, MA, [178] A. Traulsen, J. C. Claussen, and C. Hauert. Coevolutionary dynamics: from finite to infinite populations. Phys. Rev. Lett., 95:238701, [179] A. Traulsen, J. C. Claussen, and C. Hauert. Coevolutionary dynamics in large, but finite populations. Phys. Rev. E, 74:011901, [180] A. Traulsen, C. Hauert, H. De Silva, M. A. Nowak, and K. Sigmund. Exploration dynamics in evolutionary games. Proc. Natl. Acad. Sci. U.S.A., 106: , [181] A. Traulsen and M. A. Nowak. Evolution of cooperation by multilevel selection. Proc. Natl. Acad. Sci. U.S.A., 103: , [189] G. J. Velicer, L. Kroos, and R. E. Lenski. Developmental cheating in the social bacterium Myxococcus Xanthus. Nature, 404: , [190] T. Vicsek, A. Czirok, E. Ben-Jacob, I. Cohen, and O. Shochet. Novel type of phase transition in a system of self-driven particles. Phys. Rev. Lett., 75: , [191] T. L. Vincent and J. S. Brown. Evolutionary game theory, natural selection, and Darwinian dynamics. Cambridge University Press, Cambridge, UK, [192] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, [193] J. Y. Wakano, M. A. Nowak, and C. Hauert. Spatial dynamics of ecological public goods. Proc. Natl. Acad. Sci. U.S.A., 106: , [194] M. Mitchell Waldrop. Complexity: the emerging science at the edge of order and chaos. Simon & Schuster, New York, [195] D. J. Watts. Six degrees: the science of a connected age. W. W. Norton, New York, [196] D. J. Watts. A twenty-first century science. Nature, 445:489, [197] D. J.Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393: , [198] C.Wedekind and M. Milinski. Cooperation through image scoring in humans. Science, 288: , [199] J. Weibull. Evolutionary game theory. MIT Press, Cambridge, MA, [200] S. A. West, I. Pen, and A. S. Griffin. Cooperation and competition between relatives. Science, 296:72 75, [201] G. S. Wilkinson. Reciprocal food-sharing in the vampire bat. Nature, 308: , [202] D. S. Wilson. A theory of group selection. Proc. Natl. Acad. Sci. U.S.A., 72: , [203] D. S. Wilson. The group selection controversy: history and current status. Annu. Rev. Ecol. Syst., 14: , [182] A. Traulsen and M. A. Nowak. Chromodynamics of [204] E. O. Wilson. Sociobiology: the new synthesis. cooperation in finite populations. PLoS ONE, 2(3):e270, Harvard University Press, Cambridge, MA, [205] G. U. Yule. A mathematical theory of evolution, [183] A. Traulsen, M. A. Nowak, and J. M. Pacheco. based on the conclusions of Dr. J. C. Willis, F.R.S. Phil. Stochastic dynamics of invasion and fixation. Phys. Rev. E, Trans. R. Soc. Lond. Ser. B, 213:21 87, :011909, [206] M. Zimmermann and V. M. Eguiluz. Cooperation, social networks, and the emergence of leadership in a prisoner s dilemma with adaptive local interactions. Phys. Rev. E, 72:056118, [184] A. Traulsen, M. A. Nowak, and J. M. Pacheco. Stochastic payoff evaluation increases the temperature of selection. J. Theor. Biol., 244: , [185] A. Traulsen, J. M. Pacheco, and M. A. Nowak. Pairwise comparison and selection temperature in evolutionary game dynamics. J. Theor. Biol., 246: , [186] A. Traulsen, N. Shoresh, and M. A. Nowak. Analytical results for individual and group selection of any intensity. Bull. Math. Biol., 70: , [187] R. L. Trivers. The evolution of reciprocal altruism. Q. Rev. Biol., 46:35 57, [188] P. E. Turner and L. Chao. Prisoner s dilemma in an RNA virus. Nature, 398: , [207] M. G. Zimmermann, V. M. Eguiluz, and M. S. Miguel. Coevolution of dynamical states and interactions in dynamic networks. Phys. Rev. E, 69:065102(R), 2005