下载文档原格式
复杂网络演化博弈理论研究综述一、本文概述Overview of this article随着信息技术的飞速发展，复杂网络作为一种描述现实世界中各种复杂系统的有效工具，已经引起了广泛关注。
而在复杂网络中，演化博弈理论则为我们提供了一种深入理解和分析网络动态行为的重要视角。
本文旨在全面综述复杂网络演化博弈理论的研究现状和发展趋势，以期能为相关领域的学者和研究人员提供有益的参考和启示。
With the rapid development of information technology, complex networks have attracted widespread attention as an effective tool for describing various complex systems in the real world. In complex networks, evolutionary game theory provides us with an important perspective to deeply understand and analyze the dynamic behavior of networks. This article aims to comprehensively review the research status and development trends of complex network evolutionary game theory, in order to provide useful reference and inspiration for scholars and researchers in related fields.本文首先回顾了复杂网络和演化博弈理论的基本概念和研究背景，阐述了两者结合的必要性和重要性。
接着，文章从网络结构、博弈规则、动态演化等多个方面对复杂网络演化博弈理论进行了深入的分析和讨论。
第３期２０２１年５月阅江学刊ＹｕｅｊｉａｎｇＡｃａｄｅｍｉｃＪｏｕｒｎａｌＮｏ．３Ｍａｙ２０２１㊃经济观察㊃复杂网络上的演化博弈及其学习机制与演化动态综述王先甲摘要：博弈论是在完全理性假设下研究多人相互作用的选择理论，演化博弈是在有限理性假设下研究群体在相互作用过程中基于个体学习与选择的群体特征演化动态理论，网络上的演化博弈是研究结构化群体的演化博弈理论㊂本文回顾了基于完全理性的博弈论，在对有限理性新的理解的基础上介绍了演化博弈理论的发展历程，着重论述了复杂网络理论与演化博弈理论交叉衍生的复杂网络上的演化博弈的研究现状与发展趋势，特别分析和总结了演化博弈中最基本㊁最核心的个体学习机制与群体演化动态特征，由此揭示演化博弈中从个体微观行为到群体宏观特征的演化机理㊂关键词：博弈论；演化博弈；复杂网络；复杂网络上的演化博弈；学习机制；演化动态中图分类号：Ｆ２２４．３２㊀㊀文献标识码：Ａ㊀㊀文章分类号：１６７４⁃７０８９（２０２１）０３⁃００７０⁃１５基金项目：国家自然科学基金项目 复杂网络上演化博弈合作形成机理与控制策略 （７１８７１１７１）；国家自然科学基金重点项目 学习机制下群体博弈行为演化与管理实验 （７２０３１００９）作者简介：王先甲，博士，武汉大学经济与管理学院教授㊁博士生导师㊂㊀㊀一㊁引㊀言微观经济学主要研究完全理性假设基础上的个体选择㊂古典经济学把消费者问题和生产者问题分别看成独立的个体优化选择问题，消费者与生产者之间通过无形的市场相互联系㊂直到１９５９年，Ｄｅｂｒｅｕ在著作中建立一般均衡理论，①把消费者与生产者纳入一个经济系统内，通过他们的相互作用确定市场均衡㊂这种思想和分析框架与Ｎａｓｈ建立博弈论的思想与框架几乎完全一致㊂这种看起来十分完美的一般均衡理论至少存在两个弱点：一是仍然以完全理性为前提假设；二是无法展示市场均衡的形成过程，因为它本质上是消费者和生产者同时决策形成的㊂虽然存在这些弱点，却产生了一大进步，那就是经济０７①ＤｅｂｒｅｕＧ，ＴｈｅｏｒｙｏｆＶａｌｕｅ，ＮｅｗＨａｖｅｎ：ＹａｌｅＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９５９．. All Rights Reserved.王先甲：复杂网络上的演化博弈及其学习机制与演化动态综述学界从此不太排斥用博弈论研究多个个体间的相互作用了㊂然而，多个个体相互作用通常是一个过程，并且每个个体无法预期作用过程的未来，这使得基于完全理性的决策失去了基础，因为对未来的不可知性使决策者不知道怎样进行理性选择㊂因此，多个个体在相互作用过程中对未来预期未知时如何选择就成为需要研究的重要问题㊂演化博弈为开展这类问题的研究提供了分析工具㊂演化博弈在有限理性假设下探讨群体在相互作用过程中的个体行为选择规则及群体行为演化㊂也就是说，在群体相互作用过程中个体是按某种规则进行选择而不是按完全理性假设来选择㊂既然群体博弈是一个过程，那么个体的行为选择也可能是一个过程，个体会在这个过程中不断学习以便选择对自己更有利的行为㊂因此，个体选择行为时所依据的规则本质上就是通过某种学习机制确定的㊂每个个体选择自己的行为后形成群体整体的状态（也称系统状态），群体状态刻画了群体在相互作用过程中不同时刻的特征，不同时刻状态间的关系一般称为状态转移（也称为演化动态，有时也将演化动态理解为状态转移过程的极限）㊂当组成群体的个体间具有某种特殊联系时，该群体被称为结构化群体㊂因为网络是描述结构化群体的基本工具，且结构关系会发生各种复杂的变化，所以在研究结构化群体的相互作用过程时，复杂网络上的演化博弈就成为观注的重点㊂本文试图对复杂网络上的演化博弈等相关问题的研究状况与发展趋势进行简要的回顾与总结㊂㊀㊀二、博弈论发展历程回顾博弈论是研究理性决策者之间竞争与合作关系的数学方法，其分析范围较广，几乎包括社会科学领域所有的基本问题㊂①实际上，竞争与合作行为一直伴随着人类的发展㊂一般认为最早涉及人类博弈行为的著作是２０００多年以前中国春秋时期的‘孙子兵法“，②记录战争艺术的著作‘三国演义“也是研究博弈行为的智慧结晶㊂但这些相对零星的研究成果只是展现了人类博弈行为的某个侧面，尚未从科学意义上对人类博弈行为进行定量分析㊂最早采用定量方法分析人类博弈行为的研究发生在经济学领域，Ｃｏｕｒｎｏｔ㊁Ｂｅｒｔｒａｎｄ㊁Ｅｄｇｅｗｏｒｔｈ分别探讨了寡头产量竞争㊁寡头价格竞争和垄断竞争㊂③经典儿童文学名著‘爱丽丝漫游仙境“的作者Ｄｏｄｇｓｏｎ（后来更名为ＬｅｗｉｓＣａｒｒｏｌｌ）也是一位数学家，他用零和博弈研究政治问题㊂④这些工作成功地在人类特定领域的博弈行为研究中引入了定量方法，但是还不能算是正式的博弈论研究工作㊂Ｚｅｒｍｅｌｏ开启了博弈论的第一个正式的研究工作，⑤他除了建立集合论公理体系框架之外，还首次用博弈论研究了国际象棋㊂博弈论研１７①②③④⑤ＭｙｅｒｓｏｎＲ，ＧａｍｅＴｈｅｏｒｙ：ＡｎａｌｙｓｉｓｏｆＣｏｎｆｌｉｃｔ，Ｃａｍｂｒｉｄｇｅ：ＨａｒｖａｒｄＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９９１．ＳｕｎＴ，ＴｈｅＡｒｔｏｆＷａｒ，ＴｒａｎｓｌａｔｅｄｂｙＣｌｅａｒｙＴ，Ｂｏｓｔｏｎ＆Ｌｏｎｄｏｎ：Ｓｈａｍｂａｌａ，１９８８．ＣｏｕｒｎｏｔＡ，ＲｅｃｈｅｒｃｈｅｓｓｕｒｌｅｓＰｒｉｎｃｉｐｅｓＭａｔｈéｍａｔｉｑｕｅｓｄｅｌａｔｈéｏｒｉｅｄｅｓＲｉｃｈｅｓｓｅｓ，Ｐａｒｉｓ：Ｈａｃｈｅｔｔｅ，１８３８．ＢｅｒｔｒａｎｄＪ，Ｔｈéｏｒｉｅｍａｔｈéｍａｔｉｑｕｅｄｅｌａｒｉｃｈｅｓｓｅｓｏｃｉａｌｅ ，ＪｏｕｒｎａｌｄｅｓＳａｖａｎｔｓ，ｖｏｌ．６８（１８８３），ｐｐ．４９９－５０８．ＥｄｇｅｗｏｒｔｈＦ， Ｌａｔｅｏｒｉａｐｕｒａｄｅｌｍｏｎｏｐｏｌｉ ，ＧｉｏｒｎａｌｅｄｅｇｌｉＥｃｏｎｏｍｉｓｔｉ，ｖｏｌ．４０（１８９７），ｐｐ．１３－３１．ＢｌａｃｋＤ， Ｌｅｗｉｓｃａｒｒｏｌｌａｎｄｔｈｅｔｈｅｏｒｙｏｆｇａｍｅｓ ，ＡｍｅｒｉｃａｎＥｃｏｎｏｍｉｃＲｅｖｉｅｗ，ｖｏｌ．５９，ｎｏ．２（２００１），ｐｐ．２０６－２１０．ＤｏｄｇｓｏｎＣＬ，ＴｈｅＰｒｉｎｃｉｐｌｅｓｏｆＰａｒｌｉａｍｅｎｔａｒｙＲｅｐｒｅｓｅｎｔａｔｉｏｎ，Ｌｏｎｄｏｎ：Ｈａｒｒｉｓｏｎ，１８８４．ＺｅｒｍｅｌｏＥ， Üｂｅｒｅｉｎｅａｎｗｅｎｄｕｎｇｄｅｒｍｅｎｇｅｎｌｅｈｒｅａｕｆｄｉｅｔｈｅｏｒｉｅｄｅｓｓｃｈａｃｈｓｐｉｅｌｓ ，ＩｎＨｏｂｓｏｎＥＷ，ＬｏｖｅＡＥＨ，ｅｄｓ．，ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＦｉｆｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｇｒｅｓｓｏｆＭａｔｈｅｍａｔｉｃｉａｎｓ，ｖｏｌ．ＩＩ，Ｃａｍｂｒｉｄｇｅ：ＣａｍｂｒｉｄｇｅＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９１３，ｐｐ．５０１－５０４．. All Rights Reserved.阅江学刊：２０２１年第３期究的第一个里程碑式的工作应该是由ＶｏｎＮｅｕｍａｎｎ完成的，他于１９２８年比较完整地给出了零和博弈模型及其解的概念，①后来的主要研究者实际上都受到这一工作的启发㊂ＶｏｎＮｅｕｍａｎｎ和Ｍｏｒｇｅｎｓｔｅｒｎ建立了决策理论的公理体系㊁零和博弈与非零和博弈的分析框架，并将其运用于经济学研究，但是他们的理论局限于矩阵博弈㊂博弈论更一般的模型和解的概念及其分析框架是由Ｎａｓｈ建立的，他对多人相互作用关系给出了更一般的描述并提出了Ｎａｓｈ均衡解概念㊂Ｎａｓｈ的研究工作和思想在很大程度上受到ＶｏｎＮｅｕｍａｎｎ的影响，但在适应范围和分析框架方面又有本质的拓展，使博弈论最终成为研究多人相互作用行为的一般工具㊂Ｎａｓｈ在２０世纪５０年代发表的关于博弈论的几篇著名论文奠定了非合作博弈的理论基础㊂②然而，由于Ｎａｓｈ的研究工作以完全信息为基础，具有极强的数学理论性且不能处理经济学中几乎无处不在的不确定性信息问题，所以最初并未被经济学界所接受㊂Ｈａｒｓａｎｙｉ于１９７７年在著作中建立了一套解释和描述多人相互作用中的不完全信息理论，③提出了ＢａｙｓｉａｎＮａｓｈ均衡解概念和不完全信息非合作博弈论㊂但是Ｎａｓｈ和Ｈａｒｓａｎｙｉ的研究只能处理静态的非合作博弈，即博弈各方只能同时进行一次行为选择，不能处理多人相互作用过程的动态博弈问题㊂Ｓｅｌｔｅｎ㊁Ｋｒｅｐｓ㊁Ｗｉｌｓｏｎ建立了多阶段动态非合作博弈理论，④提出了子博弈完美Ｎａｓｈ均衡概念和 颤抖手 精炼均衡概念㊂由于在非合作博弈研究中的杰出工作，Ｎａｓｈ㊁Ｈａｒｓａｎｙｉ和Ｓｅｌｔｅｎ三人在１９９４年被授予诺贝尔经济学奖㊂Ｔｕｃｋｅｒ于１９５０年发现囚徒困境现象，⑤为非合作博弈的研究提供了典型原型，也揭示了博弈论与决策理论的重要区别，决策理论研究单人在理性假设下的决策行为，决策主体寻求的是能使自身偏好最优的行为选择，而在Ｎａｓｈ的博弈论框架下理性人的行为出现了一种由囚徒困境所表征的特点，即个体理性与集体理性的冲突㊂实际上，囚徒困境现象在实践中广泛存在，Ｃｏｕｒｎｏｔ的数量竞争模型也是囚徒困境㊂这种十分简单的博弈模型却导致博弈出现了几个不同的发展方向，其中一个是合作博弈㊂虽然ＶｏｎＮｅｕｍａｎｎ和Ｍｏｒｇｅｎｓｔｅｒｎ建立了合作博弈的基本框架，但是合作博弈的研究在２０世纪５０年代中期到６０年代中后期才有了较快的发展，这一时期经济学界正在怀疑Ｎａｓｈ提出的非合作博弈，因为它不能处理不完全信息而产生了可应用性问题㊂合作博弈按效用的可转移性可以分为效用可转移型和效用不可转移型，Ａｕｍａｎｎ较早研究了效用不可转移合作博弈，⑥随后关２７①②③④⑤⑥ＶｏｎＮｅｕｍａｎｎＪ， Ｚｕｒｔｈｅｏｒｉｅｄｅｒｇｅｓｅｌｌｓｃｈａｆｔｓｓｐｉｅｌｅ ，ＭａｔｈｅｍａｔｉｓｃｈｅＡｎｎａｌｅｎ，ｖｏｌ．１００，ｎｏ．１（１９２８），ｐｐ．２９５－３２０．ＶｏｎＮｅｕｍａｎｎＪ，ＭｏｒｇｅｎｓｔｅｒｎＯ，ＴｈｅｏｒｙｏｆＧａｍｅｓａｎｄＥｃｏｎｏｍｉｃＢｅｈａｖｉｏｒ，Ｐｒｉｎｃｅｔｏｎ：ＰｒｉｎｃｅｔｏｎＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９４４．ＮａｓｈＪＦ，Ｂａｒｇａｉｎｉｎｇｐｒｏｂｌｅｍ ，Ｅｃｏｎｏｍｅｔｒｉｃａ，ｖｏｌ．１８，ｎｏ．２（１９５０），ｐｐ．１５５－１６２．ＮａｓｈＪＦ， Ｎｏｎ－ｃｏｏｐｅｒａｔｉｖｅｇａｍｅｓ ，ＡｎｎａｌｓｏｆＭａｔｈｅｍａｔｉｃｓ，ｖｏｌ．５４，ｎｏ．２（１９５１），ｐｐ．２８６－２９５．ＮａｓｈＪＦ， Ｔｗｏ－ｐｅｒｓｏｎｃｏｏｐｅｒａｔｉｖｅｇａｍｅｓ ，Ｅｃｏｎｏｍｅｔｒｉｃａ，ｖｏｌ．２１，ｎｏ．１（１９５３），ｐｐ．１２８－１４０．ＨａｒｓａｎｙｉＪＣ，ＲａｔｉｏｎａｌＢｅｈａｖｉｏｒａｎｄＢａｒｇａｉｎｉｎｇＥｑｕｉｌｉｂｒｉｕｍｉｎＧａｍｅｓａｎｄＳｏｃｉａｌＳｉｔｕａｔｉｏｎｓ，Ｃａｍｂｒｉｄｇｅ：ＣａｍｂｒｉｄｇｅＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９７７．ＳｅｌｔｅｎＲ， Ｒｅｅｘａｍｉｎａｔｉｏｎｏｆｔｈｅｐｅｒｆｅｃｔｎｅｓｓｃｏｎｃｅｐｔｆｏｒｅｑｕｉｌｉｂｒｉｕｍｐｏｉｎｔｓｉｎｅｘｔｅｎｓｉｖｅｇａｍｅ ，ＩｎｔｅｒｎａｔｉｏｎａｌＧａｍｅＴｈｅｏｒｙ，ｖｏｌ．４，ｎｏ．１（１９７５），ｐｐ．２５－５５．ＫｒｅｐｓＤ，ＷｉｌｓｏｎＲ， Ｓｅｑｕｅｎｔｉａｌｅｑｕｉｌｉｂｒｉｕｍ ，Ｅｃｏｎｏｍｉｅｔｒｉｃａ，ｖｏｌ．５０，ｎｏ．４（１９８２），ｐｐ．８６３－８９４．ＴｕｃｋｅｒＡＷ，ＡＴｗｏ－ｐｅｒｓｏｎＤｉｌｅｍｍａ，Ｕｎｐｕｂｌｉｓｈｅｄｎｏｔｅｓ，ＳｔａｎｆｏｒｄＵｎｉｖｅｒｓｉｔｙ，１９５０．ＡｕｍａｎｎＲＪ， Ｔｈｅｃｏｒｅｏｆａｃｏｏｐｅｒａｔｉｖｅｇａｍｅｗｉｔｈｏｕｔｓｉｄｅｐａｙｍｅｎｔ ，ＴｒａｎｓａｃｔｉｏｎｓｏｆｔｈｅＡｍｅｒｉｃａｎＭａｔｈｅｍａｔｉｃａｌＳｏｃｉｅｔｙ，ｖｏｌ．９８，ｎｏ．３（１９６１），ｐｐ．５３９－５５２．. All Rights Reserved.王先甲：复杂网络上的演化博弈及其学习机制与演化动态综述于效用不可转移合作博弈的研究虽然并不多但依然沿用Ａｕｍａｎｎ的框架㊂自ＶｏｎＮｅｕｍａｎｎ和Ｍｏｒｇｅｎｓｔｅｒｎ构建效用可转移合作博弈的框架以来，合作博弈基于特征函数，主要研究联盟成员如何合理有效地分配收益㊂围绕合理有效地在联盟中分配收益问题建立解概念及公理体系是合作博弈理论发展的中心㊂１９５３年Ｇｉｌｌｉｅｓ引入了核（Ｃｏｒｅ）作为合作博弈解的概念，①这个解概念具有给出的分配方案对任何子结盟没有诱导性的特性，但它不是单值的而是集值的㊂在合作博弈中集值解概念为数不少，Ａｕｍａｎｎ和Ｍａｓｃｈｅｒ提出的合作博弈协商集解概念是集值的，②Ｐｅｌｅｇ的内核（Ｋｅｒｎｅｌ）解概念㊁Ｍａｓｃｈｌｅｒ的预核（Ｐｒｅｋｅｒｎｅｌ）解概念等都是集值解概念㊂③而Ｓｈａｐｌｅｙ在１９５３年提出了一个著名的单值解概念，④称为Ｓｈａｐｌｅｙ值，这个解概念可解释为每个个体得到的收益是其所有可能的边际贡献的平均值，并且Ｓｈａｐｌｅｙ用一组公理完全刻画了这个单值解概念㊂单值解概念还包括Ｓｃｈｍｅｉｄｌｅｒ的核仁（Ｎｕｃｌｅｏｌｕｓ）（它的表示形式虽然是集合，但由于采用字典序定义，实际上是一个单值解概念）㊁Ｔｉｊｓ的τ值和平均字典值解概念㊂⑤Ｐｅｌｅｇ和Ｓｕｄｈöｌｔｅｒ是合作博弈解概念公理化分析的集大成者㊂⑥在合作博弈研究中，Ｓｈａｐｌｅｙ的研究工作被认为是开创性的，被统称为关于稳定分配（匹配）与市场设计的研究，他与Ｒｏｔｈ一起获得２０１２年诺贝尔经济学奖㊂当前，博弈论几乎在所有涉及多智能体（包括人和生物）的领域得到了发展和应用㊂Ａｕｍａｎｎ和Ｈａｒｔ㊁Ｙｏｕｎｇ和Ｚａｍｉｒ出版了四本博弈论手册，⑦堪称博弈论全书，这套博弈论手册共分８０个专题对博弈论进行了较详细的论述㊂㊀㊀三、演化博弈论的发展历程回顾尽管在过去几十年里，博弈论得到了长足发展，但仍然存在一些缺陷㊂第一，经典博弈论（包括合作博弈与非合作博弈）假设参与人是完全理性的㊂在决策理论意义下，一个决策者是理性的是指他可以选择与自己偏好一致的最优决策（行为）㊂而在博弈论意义下，参与人是理性的是指参与人选择的策略（行为）在博弈中不被严格占优㊂这个定义是一种否定表示形式，它并未告诉人们直接选择什么㊂第二，以Ｎａｓｈ均衡为基础来定义解概念给出了多人相互关系中所有参与人共同的合理的理性预期，虽然它在本质上是所有３７①②③④⑤⑥⑦ＧｉｌｌｉｅｓＤ，ＳｏｍｅＴｈｅｏｒｅｍｓｏｎＮ－ｐｅｒｓｏｎＧａｍｅｓ，Ｐｒｉｎｃｅｔｏｎ：ＰｒｉｎｃｅｔｏｎＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９５３．ＡｕｍａｎｎＲＪ，ＭａｓｃｈｌｅｒＭ， Ｔｈｅｂａｒｇａｉｎｉｎｇｓｅｔｆｏｒｃｏｏｐｅｒａｔｉｖｅｇａｍｅ ，ＡｄｖａｎｃｅｓｉｎＧａｍｅＴｈｅｏｒｙ，ｖｏｌ．５２（１９６４），ｐｐ．４４３－４７６．ＰｅｌｅｇＢ，Ｖｏｒｏｂ ｅｖＮＮ，ＴóｔｈＬＦ， Ｏｎｔｈｅｋｅｒｎｅｌｏｆｃｏｍｓｔａｎｔ－ｓｕｍｓｉｍｐｌｅｇａｍｅｓｗｉｔｈｈｏｍｏｇｅｎｅｏｕｓｗｅｉｇｈｔｓ ，ＩｌｌｉｎｏｉｓＪｏｕｒｎａｌｏｆＭａｔｈｅｍａｔｉｃｓ，ｖｏｌ．１０（１９６６），ｐｐ．３９－４８．ＭａｓｃｈｌｅｒＭ，ＰｅｌｅｇＢ，ＳｈａｐｌｅｙＬＳ， Ｔｈｅｋｅｒｎｅｌａｎｄｂａｒｇａｉｎｉｎｇｓｅｔｆｏｒｃｏｎｖｅｘｇａｍｅｓ ，ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＧａｍｅＴｈｅｏｒｙ，ｖｏｌ．１，ｎｏ．１（１９７１），ｐｐ．７３－９３．ＳｈａｐｌｅｙＬＳ， Ａｖａｌｕｅｆｏｒｎ－ｐｅｒｓｏｎｇａｍｅｓ ，ＩｎＴｕｃｋｅｒＡＷ，ＫｕｈｎＨＷ，ｅｄｓ．，ＣｏｎｔｒｉｂｕｔｉｏｎｓｔｏｔｈｅＴｈｅｏｒｙｏｆＧａｍｅｓ，ｖｏｌ．ＩＩ，Ｐｒｉｎｃｅｔｏｎ：ＰｒｉｎｃｅｔｏｎＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，１９５３，ｐｐ．３０７－３１７．ＳｃｈｍｅｉｄｌｅｒＤ， Ｔｈｅｎｕｃｌｅｏｌｕｓｏｆａｃｈａｒａｃｔｅｒｉｓｔｉｃｆｕｎｃｔｉｏｎｇａｍｅ ，ＳｉａｍＪｏｕｒｎａｌｏｎＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｉｃｓ，ｖｏｌ．１７（１９６９），ｐｐ．１１６３－１１７０．ＴｉｊｓＳＨ， Ｂｏｕｎｄｓｆｏｒｔｈｅｃｏｒｅｏｆａｇａｍｅａｎｄｔｈｅτ－ｖａｌｕｅ ＩｎＭｏｅｓｃｈｌｉｎＯ，ＰａｌｌａｓｃｈｋｅＤ，ｅｄｓ．，ＧａｍｅＴｈｅｏｒｙａｎｄＭａｔｈｅｍａｔｉｃａｌＥｃｏｎｏｍｉｃｓ，Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ－Ｈｏｌｌａｎｄ，１９８１，ｐｐ．１２３－１３２．ＰｅｌｅｇＢ，ＳｕｄｈöｌｔｅｒＰ，ＩｎｔｒｏｄｕｃｔｉｏｎｔｏｔｈｅＴｈｅｏｒｙｏｆＣｏｏｐｅｒａｔｉｖｅＧａｍｅｓ，Ｂｏｓｔｏｎ：ＫｌｕｗｅｒＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒｓ，２００７．ＡｕｍａｎｎＲＪ，ＨａｒｔＳ，ＨａｎｄｂｏｏｋｏｆＧａｍｅＴｈｅｏｒｙｗｉｔｈＥｃｏｎｏｍｉｃＡｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌ．１，Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ－Ｈｏｌｌａｎｄ，１９９２．ＡｕｍａｎｎＲＪ，ＨａｒｔＳ，ＨａｎｄｂｏｏｋｏｆＧａｍｅＴｈｅｏｒｙｗｉｔｈＥｃｏｎｏｍｉｃＡｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌ．２，Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ－Ｈｏｌｌａｎｄ，１９９４．ＡｕｍａｎｎＲＪ，ＨａｒｔＳ，ＨａｎｄｂｏｏｋｏｆＧａｍｅＴｈｅｏｒｙｗｉｔｈＥｃｏｎｏｍｉｃＡｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌ．３，Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ－Ｈｏｌｌａｎｄ，２００２．ＹｏｕｎｇＨＰ，ＺａｍｉｒＳ，ＨａｎｄｂｏｏｋｏｆＧａｍｅＴｈｅｏｒｙｗｉｔｈＥｃｏｎｏｍｉｃＡｐｐｌｉｃａｔｉｏｎｓ，ｖｏｌ．４，Ａｍｓｔｅｒｄａｍ：Ｎｏｒｔｈ－Ｈｏｌｌａｎｄ，２０１５．. All Rights Reserved.阅江学刊：２０２１年第３期参与人的选择互为最优反应的结果，却无法给出这种基于最优反应的均衡的形成过程，也不能讨论均衡的稳定性㊂第三，多重均衡问题导致经常无法排除明显不合理的均衡，进而影响参与人做出最终选择㊂第四，对合作的理解存在分歧㊂合作博弈将合作理解为结盟，而非合作博弈把合作理解为参与人选择对他人有利的策略（行为）㊂第五，无法反映参与人的学习过程㊂演化博弈虽然源于生物学，但是之所以被列入博弈论的范畴，正是因为它在一定程度上回答了上述五个问题㊂㊀㊀（一）有限理性完全理性假设是经典博弈论和经典经济学理论的基石，也是它们遭受质疑的首要问题㊂与完全理性相对立的是有限理性㊂理性本质上是讨论人在决策时选择行为的依据或原则㊂亚当∙斯密最早在其著作‘国富论“中提出经济人概念，后来被约翰∙穆勒等人总结为经济人假设，经济人假设指出人总是做出使自己利益最大化的决策㊂ＶｏｎＮｅｕｍａｎｎ和Ｍｏｒｇｅｎｓｔｅｒｎ建立的经典决策理论中以完全理性假设作为决策者或博弈参与人的行为选择原则，这里的完全理性假设与经济人假设是一致的㊂美国经济学家Ａｒｒｏｗ很可能是最早提出有限理性概念的学者，①他认为，人的行为是有意识理性的，但这种理性又是有限的㊂Ｓｉｍｏｎ一直是有限理性概念的倡导者，②他认为，人类的认知能力在心理上存在临界极限，决策中的推理活动需要足够的能力来支撑，而人类只有有限能力，决策中需要大量的信息，而能获得的信息是有限的㊂因此，决策者并非总是可以实现其最优决策，即决策者的决策是在有限理性下的决策㊂自从Ｓｉｍｏｎ认为有限理性是建立决策理论的基石以来，③不少学者总结了对各种有限理性进行解释和描述的模型㊂④大多数学者认为，决策者在决策过程中可以通过不断学习提高有限的知识水平㊁有限的推理能力㊁有限的信息处理能力，从而使有限理性得到不断改善㊂Ｔｈａｌｅｒ获得２０１７年诺贝尔经济学奖的工作就是通过探索有限理性展示人格特质如何系统地影响个人决策与市场㊂⑤虽然关于有限理性的多项研究成果已经获得了几届诺贝尔经济学奖，但是人们仍然认为，对有限理性的理解仅限于局部的㊁定性的分析，决策论学者㊁博弈论学者㊁经济学学者并未形成共识㊂人们对有限理性与完全理性有如下理解：当决策者面对决策问题时，如果决策者对当前和未来的信息结构和偏好结构具有完全知识，他将按完全理性假设确定的决策规则选择行为，否则，他将按其他规则选择行为㊂根据有限知识㊁有限信息㊁有限推４７①②③④⑤ＡｒｒｏｗＫＪ， Ｒａｔｉｏｎａｌｃｈｏｉｃｅｆｕｎｃｔｉｏｎｓａｎｄｏｒｄｉｎｇｓ ，Ｅｃｏｎｏｍｉｃａ，ｖｏｌ．２６，ｎｏ．１０２（１９５９），ｐｐ．１２１－１２７．ＳｉｍｏｎＨＡ， Ａｂｅｈａｖｉｏｒａｌｍｏｄｅｌｏｆｒａｔｉｏｎａｌｃｈｏｉｃｅ ，ＱｕａｒｔｅｒｌｙＪｏｕｒｎａｌｏｆＥｃｏｎｏｍｉｃｓ，ｖｏｌ．６９，ｎｏ．１（１９５５），ｐｐ．９９－１１８．［美］赫伯特㊃西蒙：‘现代决策理论的基石“，杨砺㊁徐立译，北京：北京经济学院出版社，１９８９年，第１页㊂ＳｉｍｏｎＨＡ， Ｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙａｎｄｏｒｇａｎｉｚａｔｉｏｎａｌｌｅａｒｎｉｎｇ ，ＯｒｇａｎｉｚａｔｉｏｎＳｃｉｅｎｃｅ，ｖｏｌ．２，ｎｏ．１（１９９１），ｐｐ．１２５－１３４．ＳｅｌｔｅｎＲ，Ｆｅａｔｕｒｅｓｏｆｅｘｐｅｒｉｍｅｎｔａｌｌｙｏｂｓｅｒｖｅｄｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙ ，ＥｕｒｏｐｅａｎＥｃｏｎｏｍｉｃＲｅｖｉｅｗ，ｖｏｌ．４２，ｎｏ．３（１９９８），ｐｐ．４１３－４３６．ＡｒｔｈｕｒＷＢ， Ｄｅｓｉｇｎｉｎｇｅｃｏｎｏｍｉｃａｇｅｎｔｓｔｈａｔａｃｔｌｉｋｅｈｕｍａｎａｇｅｎｔｓ：Ａｂｅｈａｖｉｏｒａｌ－ａｐｐｒｏａｃｈｔｏｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙ ，ＡｍｅｒｉｃａｎＥｃｏｎｏｍｉｃＲｅｖｉｅｗ，ｖｏｌ．８１，ｎｏ．２（１９９１），ｐｐ．３５３－３５９．ＷａｌｌＫＤ， Ａｍｏｄｅｌｏｆｄｅｃｉｓｉｏｎ－ｍａｋｉｎｇｕｎｄｅｒｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙ ，ＪｏｕｒｎａｌｏｆＥｃｏｎｏｍｉｃＢｅｈａｖｉｏｒ＆Ｏｒｇａｎｉｚａｔｉｏｎ，ｖｏｌ．２０，ｎｏ．３（１９９３），ｐｐ．３３１－３５２．ＢｏａｒｄＲ，Ｐｏｌｙｎｏｍｉａｌｌｙｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙ ，ＪｏｕｒｎａｌｏｆＥｃｏｎｏｍｉｃＴｈｅｏｒｙ，ｖｏｌ．６３，ｎｏ．２（１９９４），ｐｐ．２４６－２７０．ＳａｍｕｅｌｓｏｎＬ，Ｂｏｕｎｄｅｄｒａｔｉｏｎａｌｉｔｙａｎｄｇａｍｅｔｈｅｏｒｙ ，ＱｕａｒｔｅｒｌｙＲｅｖｉｅｗｏｆＥｃｏｎｏｍｉｃｓａｎｄＦｉｎａｎｃｅ，ｖｏｌ．３６，ｎｏ．ｓ１（１９９６），ｐｐ．１７－３５．ＴｈａｌｅｒＲＨ，Ｍｉｓｂｅｈａｖｉｎｇ：ＴｈｅＭａｋｉｎｇｏｆＢｅｈａｖｉｏｒａｌＥｃｏｎｏｍｉｃｓ，ＮｅｗＹｏｒｋ：Ｗ．Ｗ．Ｎｏｒｔｏｎ＆Ｃｏ．，２０１５．. All Rights Reserved.王先甲：复杂网络上的演化博弈及其学习机制与演化动态综述理能力确定的规则做出行为选择，称为有限理性下的选择㊂本质上，有限理性出现的原因是决策者不能完全掌握信息结构和偏好结构㊂决策者在有限理性假设下做出行为选择所依据的规则应该有利于改善他的收益㊂这样就可以连续统一地解释完全理性假设和有限理性假设下的选择行为㊂决策者可以通过各种途径改善知识㊁信息和推理能力，从而改善有限理性，改善的标志是决策者的收益提高了㊂决策者面临决策问题将以改善收益为目的，不断增进对信息结构与偏好结构的理解，从而使理性的有限性得到改善，直到对信息结构和偏好结构完全掌握，就能够按照完全理性确定的规则选择行为了㊂引入学习的观点具有必然性，因为决策者会通过不断学习改善理性的有限性并适时调整策略㊂如果将这种通过不断学习更新有限理性并调整策略的特征置入群体相互关系中，那么群体成员通过随机配对进行反复博弈㊁学习㊁调整策略，最终会显示出个体（类型或策略）适应性㊂这种思路与达尔文自然选择思想形成的生物进化理论的分析框架几乎完全相同，人类与生物的很多行为（比如竞争与合作）具有相似性，二者的学习方式完全可能互相启示㊂于是，生物学家Ｍａｙｎａｒｄ和Ｐｒｉｃｅ借鉴了研究生物种群群体状态进化和稳定机制的方法来分析人类的行为，将生物进化理论的思想引入博弈论，提出了演化博弈思想和演化稳定均衡策略的概念㊂这种起源于生物进化理论的博弈分析方法就被称为演化博弈论㊂㊀㊀（二）演化博弈论的发展历程回顾实际上，演化博弈思想最早应该源于Ｆｉｓｈｅｒ在１９３０年开展的研究工作，①但遗憾的是他没有给出演化博弈的形式化表示与分析框架㊂Ｍａｙｎａｒｄ和Ｐｒｉｃｅ首先提出了源于生物学的演化博弈，并给出其形式化表示，②后经Ｔａｙｌｏｒ㊁Ｊｏｎｋｅｒ㊁Ｓｅｌｔｅｎ发展而成㊂③演化博弈将生物学中的演化概念用于解释生物或人的选择行为是有限理性假设下基于规则的选择过程，并将群体博弈描述成一个过程，在动态系统稳定与博弈论的Ｎａｓｈ均衡之间建立起联系，使得展现Ｎａｓｈ均衡的实现过程成为可能㊂Ｗｅｉｂｕｌｌ对１９９５年之前的演化博弈论研究进展进行了系统的总结㊂④作为研究生物认识的方法，演化博弈关注个体的行为表现特征而非生物组织内在的基因特征㊂于是，演化博弈形成的基础被认为是生物特征学的三个基本原则，即个体异质性㊁适应性和自然选择㊂表现型由基因库的多样性保障，表现型的成功生存可以用适应性测量，自然选择决定了更适应的表现型比更不适应的表现型在下一代繁殖中有更多的数量㊂变异（突变）是由偶然因素引起的，多数突变者因表现型行为不适应环境而被淘汰，少数突变者将因新的表现型更适应环境而生存㊂Ｍａｙｎａｒｄ和Ｐｒｉｃｅ提出了演化博弈解的概念，⑤即演化稳定均衡（策略）㊂演化稳定策略有如下性质：对己方而言，对手以小概率５７①②③④⑤ＦｉｓｈｅｒＲＡ，ＴｈｅＧｅｎｅｔｉｃａｌＴｈｅｏｒｙｏｆＮａｔｕｒａｌＳｅｌｅｃｔｉｏｎ，Ｏｘｆｏｒｄ：ＣｌａｒｅｎｄｏｎＰｒｅｓｓ，１９３０．ＭａｙｎａｒｄＳＪ，ＰｒｉｃｅＧＲ， Ｔｈｅｌｏｇｉｃｏｆａｎｉｍａｌｃｏｎｆｌｉｃｔ ，Ｎａｔｕｒｅ，ｖｏｌ．２４６，ｎｏ．５４２７（１９７３），ｐｐ．１５－１８．ＴａｙｌｏｒＰＤ，ＪｏｎｋｅｒＬＢ， Ｅｖｏｌｕｔｉｏｎａｒｙｓｔａｂｌｅｓｔｒａｔｅｇｉｅｓａｎｄｇａｍｅｄｙｎａｍｉｃｓ ，ＭａｔｈｅｍａｔｉｃａｌＢｉｏｓｃｉｅｎｃｅｓ，ｖｏｌ．４０，ｎｏ．１（１９７８），ｐｐ．１４５－１５６．ＳｅｌｔｅｎＲ， Ｅｖｏｌｕｔｉｏｎａｒｙｓｔａｂｉｌｉｔｙｉｎｅｘｔｅｎｓｉｖｅｔｗｏ－ｐｅｒｓｏｎｇａｍｅｓ ，ＭａｔｈｅｍａｔｉｃａｌＳｏｃｉａｌＳｃｉｅｎｃｅｓ，ｖｏｌ．５，ｎｏ．３（１９８３），ｐｐ．２６９－３６３．ＷｅｉｂｕｌｌＪＷ，ＥｖｏｌｕｔｉｏｎａｒｙＧａｍｅＴｈｅｏｒｙ，Ｃａｍｂｒｉｄｇｅ：ＴｈｅＭＩＴＰｒｅｓｓ，１９９５．ＭａｙｎａｒｄＳＪ，ＰｒｉｃｅＧＲ， Ｔｈｅｌｏｇｉｃｏｆａｎｉｍａｌｃｏｎｆｌｉｃｔ ，Ｎａｔｕｒｅ，ｖｏｌ．２４６，ｎｏ．５４２７（１９７３），ｐｐ．１５－１８．. All Rights Reserved.阅江学刊：２０２１年第３期选择变异策略时，演化稳定策略严格占优于变异策略㊂从传统的博弈论观点来理解就是：对己方而言，如果对手在演化稳定策略和变异策略之间随机选择并以很小的概率选择该变异策略时，演化稳定策略严格占优于变异策略㊂从生物学观点来理解就是：如果演化稳定策略种群被变异策略种群中的一小部分入侵，演化稳定策略种群在抵御该小变异种群过程中比变异种群有更强大的生存能力，表明演化稳定策略种群在抵御变异策略种群时具有稳定性㊂演化稳定策略还可以解释为：对己方而言，演化稳定策略对抗任何变异策略得到的收益严格大于该变异策略得到的收益㊂根据演化稳定策略的定义，可以证明演化稳定策略也是Ｎａｓｈ均衡策略㊂由于Ｎａｓｈ均衡策略是互为最优反应策略，所以也可以认为演化稳定策略是对任意策略的严格意义下的最优反应策略㊂由于可以将演化稳定策略理解成Ｎａｓｈ均衡策略的一种精炼，所以它成为解决多重Ｎａｓｈ均衡的一种方法㊂演化动态将演化稳定策略与生物演化（进化）巧妙地联系起来，演化动态描述了演化过程中个体改变策略的规则，包括演化系统结构㊁个体特征㊁策略的更新规则㊂它反映了基于适应性和学习性选择进化的本质㊂从数学上讲，演化动态是系统历史在当前时刻的动态映射㊂在复制（演化）动态关系下，可以证明渐近稳定点与演化稳定策略是等价的㊂①这样就把有限理性下某种演化动态的演化稳定策略与完全理性下的Ｎａｓｈ均衡策略有机联系了起来㊂基于这一思想，Ｍａｙｎａｒｄ建立了演化博弈的分析框架，②可以说是演化博弈的奠基之作㊂演化动态是演化博弈的核心概念，演化动态可分成确定性演化动态和随机性演化动态，一般来讲，对任何确定性演化动态都可以构造相应的随机演化动态㊂㊀㊀四、复杂网络上的演化博弈发展现状与发展趋势㊀㊀（一）复杂网络理论复杂网络理论是用网络工具研究由多个基本单元通过复杂相互作用构成的复杂系统的方法㊂主要研究不同网络拓扑模型及其统计特性㊁复杂网络形成机制㊁复杂网络上的动力学行为规律㊂由于现实中存在大量的复杂相互作用关系，复杂网络被认为是对大量真实复杂相互作用关系系统在结构关系上的拓扑抽象㊂复杂网络以网络为描述工具，于是，网络理论自然成为研究复杂网络的基础㊂网络理论起源于图论，③图论源于数学家Ｅｕｌｅｒ在１７３６年访问加里宁格勒时发现的七座桥散步问题㊂图论是研究图的各种性质的学问㊂图是由节点的集合和连接节点的边的集合构成的二元组，节点代表个体，边代表个体之间的相互作用关系㊂网络是被赋予某种特定意义的图㊂网络理论是研究具有特定意义的有限个体相互作用关系的工具㊂最简单的复杂网络是规则网络，主要包括格网络㊁全局耦合网络和最邻近耦合网络㊂④６７①②③④ＰｅｔｅｒｓＨ，ＧａｍｅＴｈｅｏｒｙ：ＡＭｕｌｔｉ－ｌｅｖｅｌｅｄＡｐｐｒｏａｃｈ，Ｂｅｒｌｉｎ：ＳｐｒｉｎｇｅｒＶｅｒｌａｇ，２００８．ＭａｙｎａｒｄＳＪ，ＥｖｏｌｕｔｉｏｎａｎｄｔｈｅＴｈｅｏｒｙｏｆＧａｍｅｓ，Ｃａｍｂｒｉｄｇｅ：ＣａｍｂｒｉｄｇｅＵｎｉｖｅｒｓｉｔｙ，１９８２．段志生：‘图论与复杂网络“，‘力学进展“，２００８年第６期，第７０２－７１２页㊂ＰｅｒｃＭ，ＪｏｒｄａｎＪＪ，ＲａｎｄＤＧ，ｅｔａｌ， Ｓｔａｔｉｓｔｉｃａｌｐｈｙｓｉｃｓｏｆｈｕｍａｎｃｏｏｐｅｒａｔｉｏｎ ，ＰｈｙｓｉｃｓＲｅｐｏｒｔｓ，ｖｏｌ．６８７（２０１７），ｐｐ．１－５１．. All Rights Reserved.王先甲：复杂网络上的演化博弈及其学习机制与演化动态综述复杂网络的复杂性主要利用结构复杂性来刻画，比如高聚类系数㊁短路径长度的小世界现象及度分布呈现幂律特征的无标度特性等，典型的复杂网络主要有随机网络㊁ＷＳ小世界网络和ＢＡ无标度网络等㊂Ｅｒｄｏｓ等提出了随机网络（也称ＥＲ随机图）的概念㊂①ＥＲ随机网络模型假设网络中有Ｎ个节点，将任意两个节点以概率ｐ进行连接，可以生成一个由Ｎ个节点构成的平均度为ｐ（Ｎ－１）的网络，该网络的节点度满足泊松分布㊂Ｅｒｄｏｓ等建立了随机网络理论并开创了基于图论的复杂网络理论的系统性研究㊂②Ｍｉｌｇｒａｍ发现了小世界现象，③由他的社会调查以及 小世界实验 可以推断地球上任意两个人之间的平均度为６（称为６度分离），表明任意两个社会成员之间总是可以通过一条相对较短的路径实现相互连接㊂Ｗａｔｔｓ和Ｓｔｒｏｇａｔｚ发现了这种小世界现象的结构特征，④并提出了ＷＳ小世界网络（简称ＷＳ模型）㊂这种网络有一种看上去很复杂但遵循一定规则的结构，即对于节点数给定（Ｎ）的最邻近耦合网络，把网络中任一条边以概率ｐ断开并重新连接到另一个随机挑选的节点上，但是不允许出现重复或自连接的情况，此时概率ｐ与网络结构有如下关系：当ｐ＝０时，该网络仍然为最邻近耦合网络；当ｐ＝１时，该网络变为特殊ＥＲ随机网络；当０＜ｐ＜１时，随着ｐ的增大，节点度之间的异质性随之增大，同时网络中可能会出现孤立簇㊂这种现象与随机重新连接性可能会破坏网络的连通性有关㊂为了保证网络连通性，Ｎｅｗｍａｎ和Ｗａｔｔｓ对ＷＳ小世界网络模型进行了修改，⑤提出了ＮＷ小世界网络（简称ＮＷ模型）㊂在ＮＷ模型中，从一个最邻近的环形网格中以概率ｐ随机选取一对节点建立新连接，要求任何两个节点间最多只存在一条边㊂这种用随机添加新边取代ＷＳ模型中随机重新连接的方法有效地保证了网络连通性㊂ＮＷ小世界网络与ＷＳ小世界网络的基本特征是具有较大的簇系数和较小的最短平均距离，因此统称为小世界网络㊂Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ发现了一种具有特殊度分布特性的网络结构，⑥即极少数节点的度较大而大量节点的度较小，提出用ＢＡ无标度网络来刻画这种特性㊂ＢＡ无标度网络的生成规则为：从一个有ｍ０个初始节点的全局连通网络开始，每次增加一个新节点，从已有节点中随机选择ｍ（ｍɤｍ０）个节点与之连接，新节点与已有节点的相连概率与已有节点的度成正比，网络生成过程中不允许重复连接㊂这种ＢＡ无标度网络的主要特征是节点度满足幂率分布且幂率函数具备标度不变性㊂ＢＡ无标度网络可以用来描述不断增长和择优开放的现实世界㊂ＢＡ无标度网络和小世界网络一起揭示了现实世界形形色色的复杂网络具有普遍的㊁非平凡的结构特性㊂７７①②③④⑤⑥ＥｒｄｏｓＰ，ＲéｎｙｉＡ， Ｏｎｒａｎｄｏｍｇｒａｐｈｓ ，ＰｕｂｌｉｃａｔｉｏｎｅｓＭａｔｈｅｍａｔｉｃａｅ，ｖｏｌ．６，ｎｏ．４（１９５９），ｐｐ．２９０－２９７．ＥｒｄｏｓＰ，ＲéｎｙｉＡ， Ｏｎｔｈｅｅｖｏｌｕｔｉｏｎｏｆｒａｎｄｏｍｇｒａｐｈｓ ，ＰｕｂｌｉｃａｔｉｏｎｓｏｆｔｈｅＭａｔｈｅｍａｔｉｃａｌＩｎｓｔｉｔｕｔｅｏｆｔｈｅＨｕｎｇａｒｉａｎＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ，ｖｏｌ．５，ｎｏ．１（１９６０），ｐｐ．１７－６１．ＭｉｌｇｒａｍＳ， Ｔｈｅｓｍａｌｌｗｏｒｌｄｐｒｏｂｌｅｍ ，ＰｓｙｃｈｏｌｏｇｙＴｏｄａｙ，ｖｏｌ．２，ｎｏ．１（１９６７），ｐｐ．１８５－１９５．ＷａｔｔｓＤＪ，ＳｔｒｏｇａｔｚＳＨ， Ｃｏｌｌｅｃｔｉｖｅｄｙｎａｍｉｃｓｏｆ ｓｍａｌｌ－ｗｏｒｌｄ ｎｅｔｗｏｒｋｓ ，Ｎａｔｕｒｅ，ｖｏｌ．３９３，ｎｏ．６６８４（１９９８），ｐｐ．４４０－４４２．ＮｅｗｍａｎＭＥ，ＷａｔｔｓＤＪ， Ｓｃａｌｉｎｇａｎｄｐｅｒｃｏｌａｔｉｏｎｉｎｔｈｅｓｍａｌｌ－ｗｏｒｌｄｎｅｔｗｏｒｋｍｏｄｅｌ ，ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，ｖｏｌ．６０，ｎｏ．６（１９９９），ｐｐ．７３３２－７３４２．ＢａｒａｂａｓｉＡＬ，ＡｌｂｅｒｔＲ， Ｅｍｅｒｇｅｎｃｅｏｆｓｃａｌｉｎｇｉｎｒａｎｄｏｍｎｅｔｗｏｒｋｓ ，Ｓｃｉｅｎｃｅ，ｖｏｌ．２８６，ｎｏ．５４３９（１９９９），ｐｐ．５０９－５１２．. All Rights Reserved.。
复杂网络上演化博弈动力学研究综述作者：湛文涛纪庆群来源：《计算机光盘软件与应用》2012年第22期摘要：博弈论是研究个体之间相互作用的，演化博弈论能够很好地解释现实中的网络，因而博弈演化理论的研究越来越来得到关注。
本文对常见的复杂网络博弈理论做了介绍，然后我们探讨了这一领域的研究趋势。
关键词：网络结构；囚徒困境；合作行为中图分类号：TP3 文献标识码：A 文章编号：1007-9599 （2012） 22-0000-02博弈论（Game theory）主要是研究个体在相互作用过程中如何获得最大利益的理论，是对合作与竞争关系的一种反映。
一般而言，一个博弈通常由以下几个组成部分：a参与博弈的个体至少两个b.博弈个体可以从策略集中选取自己的博弈策略c.博弈结束后博弈个体可以得到得收益d.博弈个体进行策略更新的目的是为了达到最大收益。
经典博弈论认为博弈个体是非常理性的，博弈目的都是追求自己的最大收益，而且也知道其它博弈个体也是完全理性的；而演化博弈论以种群为研究对象，认为博弈个体是有限理性的，博弈个体的策略可能因变异而改变。
演化博弈论的特征与实际网络较为符合，使得复杂网络上的博弈演化研究得到越来约多学者的参与和研究，在这里主要综述一下复杂网络上的网络结构是如何对博弈产生影响的。
1 复杂网络中的经典网络模型当策略更新规则相同时，网络结构不一样，对博弈的影响也不一样。
在这里先介绍一下对演化博弈有影响的网络：规则网络、小世界网络和无标度网络。
1.1 规则网络：网络中节点间按某种规则连接的网络称之为规则网络。
规则网络中每个节点的边数都是一样的有，即有相同的邻居数或者度（一般用K来表示节点的度），规则网络节点之间聚成团的趋势比较大并且节点间平均最短路径比较大。
1.2 小世界网络：节点间平均路径长度比较短而聚集系数比较大是小世界网络的重要特征。
小世界网络分为两种，一种是WS小世界网络，在规则网络上进行随机化重连得到的；另一种是NW小世界网络，在规则网络上随机化加边得到的。
演化博弈理论与应用研究综述2009年04月13日星期一 13:38摘要：本文分别对国内外关于演化博弈论的研究做了总结并指出其存在的问题，主要讨论演化博弈论的理论渊源、发展情况及存在的挑战与演化博弈论在应用研究现状及发展展望。
关键词：博弈论；演化博弈论；演化稳定策略；演化均衡；进化稳定策略Research on Evolutionary Game Theory and Application: a ReviewWANG Wen-bin，DA Qing-li, CHEN Wei-da(School of Economics and Management Southeast University, Nanjing,210096)Abstract: This paper studies the theory and application of revolutionary game theory at home and abroad. Specifically, we discussed the headstream of revolutionary game theory, its development and challenges. Finally, we show the expectation of the future research direction of the field.Keywords: game theory; revolutionary game theory; evolutionary stable strategy; evolutionary equilibrium; evolutionary stable strategy演化博弈论是在博弈论的基础上发展起来的一种理论。
传统的博弈论强调参与者必须是理性的，而且博弈的整个过程中不允许犯错误，每个决策阶段都保持理性。
这种严格理性的要求限制了博弈论的应用。
演化博弈python【演化博弈python】是什么？演化博弈是一种研究自然选择和个体间互动如何影响演化过程的方法论。
它结合了生物学、经济学和数学等多个学科，通过建立数学模型来解释和预测不同个体的生存和繁殖策略。
Python 是一种广泛使用的编程语言，具有易学易用的特点，并且在科学计算和数据分析领域广泛应用。
因此，【演化博弈python】可以理解为使用Python编程语言进行演化博弈研究和模拟的过程。
一、演化博弈的基础概念在进行【演化博弈python】之前，我们首先需要了解一些基础概念。
1. 演化：指的是在一定环境下适应性更好的个体相对于适应性较差的个体更容易存活和繁殖的过程。
演化博弈的目的就是研究不同个体间的互动如何影响演化过程。
2. 博弈：指的是多个参与者在特定规则下进行的决策和行动。
参与者可以是生物个体、经济主体或者其他个体单位。
3. 策略：指参与者在面对博弈时所选择的行动方式。
策略可以是固定的、随机的或者基于某种规则的。
二、如何进行演化博弈python的建模进行【演化博弈python】的关键是建立合适的模型来描述参与者之间的互动和策略选择。
下面将介绍一种常用的模型——囚徒困境模型。
囚徒困境模型是演化博弈中常用的模型之一，它描述了两个参与者之间的合作和背叛行为。
1. 建立参与者类使用Python进行模拟时，首先需要建立参与者类。
参与者类可以包括参与者的属性和方法。
属性可以包括参与者的策略选择、得分和演化程度等。
2. 确定博弈规则在囚徒困境模型中，博弈规则可以根据合作和背叛的行为来定义。
可以规定参与者通过选择合作得到较小的效益，选择背叛得到较大的效益。
同时，为了增加模型的随机性，可以设置一定概率让参与者选择不遵循规则。
3. 进行演化博弈模拟在模拟过程中，可以随机生成一定数量的参与者，让他们进行多轮博弈，并根据博弈结果来更新参与者的策略和得分等属性。
可以设置多次模拟和迭代，以观察不同参与者之间的演化过程。
Overview of Evolutionary Games and Their Learning Mechanisms and Evolutionary Dynamics on
Complex Networks
作者： 王先甲[1]
作者机构： [1]武汉大学经济与管理学院
出版物刊名： 阅江学刊
页码： 70-84页
年卷期： 2021年 第3期
主题词： 博弈论;演化博弈;复杂网络;复杂网络上的演化博弈;学习机制;演化动态
摘要：博弈论是在完全理性假设下研究多人相互作用的选择理论,演化博弈是在有限理性假
设下研究群体在相互作用过程中基于个体学习与选择的群体特征演化动态理论,网络上的演化博
弈是研究结构化群体的演化博弈理论.本文回顾了基于完全理性的博弈论,在对有限理性新的理解的基础上介绍了演化博弈理论的发展历程,着重论述了复杂网络理论与演化博弈理论交叉衍生的
复杂网络上的演化博弈的研究现状与发展趋势,特别分析和总结了演化博弈中最基本、最核心的
个体学习机制与群体演化动态特征,由此揭示演化博弈中从个体微观行为到群体宏观特征的演化
机理.。
第2卷第2期 智 能 系 统 学 报 Vol.2№.22007年4月 CAA I Transactions on Intelligent Systems Apr.2007复杂网络上的演化博弈王 龙,伏 锋,陈小杰,王 靖,李卓政,谢广明,楚天广(北京大学工学院,北京100871)摘 要:主要介绍了近年来复杂网络上的演化博弈研究现状和研究方向.复杂网络理论的发展为描述博弈关系提供了系统且方便的框架,网络上的节点表示博弈个体,边代表与其邻居的博弈关系.介绍了经典演化博弈论中的演化稳定策略概念和复制动力学方程,以及二者的相互联系.介绍了混合均匀有限人口中随机演化动力学问题,并给出了与确定复制方程的相互转化关系.介绍了小世界、无标度等复杂网络上演化博弈的研究结论,给出了复杂网络上演化博弈论的未来发展方向.关键词:演化博弈论;复制动力学;演化稳定策略;复杂网络;有限人口;合作中图分类号:N949 文献标识码:A 文章编号:167324785(2007)022*******Evolutionary games on complex net w orksWAN G Long ,FU Feng ,C H EN Xiao 2jie ,WAN G Jing ,L I Zhuo 2zheng ,XIE Guang 2ming ,C HU Tian 2guang(College of Engineering ,Peking University ,Beijing 100871,China )Abstract :In t his survey ,recent develop ment s and f ut ure directions of evolutionary games on complex net 2works are p resented.The develop ment of complex network t heory provides a systematic and convenient f ramework for description of t he dynamical interactions of games.The vertices represent players ,while t he edges denote t he links between players in terms of game dynamical interaction.First ,some important concept s of evolutionarily stable strategy and replicator dynamics are int roduced ,and t he connection be 2tween t he evolutio narily stable st rategy and replicator dynamics is established.Then ,t he stochastic evolu 2tionary dynamics of finite well 2mixed pop ulatio ns and t heir relationship to t he deterministic replicator dy 2namics are presented.Some result s on fixed probability and time are also given.Furt hermore ,some recent result s of evolutionary games on complex networks such as small 2world and scale 2f ree networks are int ro 2duced.Finally ,unresolved open p roblems ,f ut ure research directions ,and possible application areas for evolutionary games on complex networks are pointed out.K eyw ords :evolutionary game ;replicator dynamics ;evolutionarily stable strategy ;complex networks ;fi 2nite pop ulations ;cooperation收稿日期:2006212218.基金项目:国家自然科学基金资助项目(60674050,60528007);973国家重点基础研究发展计划资助项目(2002CB312200);863国家高技术研究发展计划资助项目(2006AA04Z258);“十一五”规划资助项目(A2120061303). 博弈论是研究依据其他参与者的效用(utility )情况,理性参与者策略之间相互作用的一门科学[1].博弈论的要素有两点:参与博弈者的目标或利益相互冲突,且他们都是理性的.现代博弈论已成为一门横跨数学、生物、心理学、计算机科学、运筹学、经济、哲学、政治、军事战略等领域的交叉学科.公认的现代博弈论起源于数学家Von Neumann 和经济学家Morgenstern 的合著:博弈理论和经济行为[2].尽管当时这本著作中的博弈论的理论框架只适用于一些有限的特例,如只讨论了零和非合作博弈问题等,但它第一次用数学语言描述和解决了博弈问题.此后,经过许多学者的努力,特别是Nash 在非合作博弈理论中创造性地引入策略均衡的概念,博弈论日渐成为非常重要且有用的分析工具[3].近十多年来,诺贝尔经济学奖先后授予研究博弈论的科学家Nash、Selten、Harsanyi、Aumann、Schelling等人,说明博弈论越来越得到更多人的重视,博弈论的威力也得到越来越广泛的承认.1 博弈论和复杂网络所谓Nash均衡(Nash equilibrium)是指给定博弈中其他个体(player)的策略时,任何一个个体都不能单方面改变自己的策略来增加自己的收益(payoff)的情形.换言之,在Nash均衡中,相对其他个体,个体的所选策略已经是最佳的反应,此时Nash均衡成为一致解的概念.但是,作为博弈一致解的概念,在有些情况下Nash均衡并不是必要条件而是充分条件.因此,博弈论的后Nash均衡时代主要是针对博弈的假设和前提的重新修改和扩展.其中最主要的2个分支:动态博弈和非完全信息博弈.非完全信息(incomplete information)和非完美信息(imperfect information)的区别在于:前者表示博弈中的个体不精确地知道博弈收益的大小或其他博弈个体的类型(type);后者表示博弈过程的信息集合的元素个数超过一(即不知道博弈中其他个体的行动(actions)).通过Harsanyi转换(Harsanyi t ransformation),可将“非完全信息博弈”转换成“完全但非完美信息博弈”.在动态博弈中,个体决策的时间(即行动的先后次序)将对博弈结果起作用.田忌赛马就是动态博弈的例子之一.本文将介绍完全信息下非合作博弈的基本概念和演化博弈理论.演化博弈这一概念最初是由Maynard Smit h和Price 在研究对称人口博弈时提出的[4],他们成功地把博弈论应用到生物背景中去.其主要思想就是采用依赖于接触频率的适应度(frequency2dependent fit2 ness,对应于博弈论中的效用或收益)的策略更新方法.近些年,演化博弈论不仅在理论生物学中得到充分的发展,也在其他学科,如经济学、社会学、心理学等得到广泛的应用.近年来,由于复杂网络研究的兴起与发展,使得人们对各种现实网络的结构演化、复杂性有了比较清晰的认识.特别是1998年Cornell大学的Watt s 和其导师St rogatz在Nat ure杂志上撰文给出了小世界网络模型[5],复杂网络研究迅速引起了诸多领域中科研工作者的兴趣,特别是物理学界、生物学界,复杂网络理论得到了充分的探索和发展.1999年美国Not re Dame大学的Barabasi和其学生Al2 bert在Science杂志撰文指出[6],很多复杂网络的度分布近似服从幂率分布,也就是常说的无标度网络(scale2f ree networks),并给出了一个偏好连接(p referential attachment)的模型,简单探讨了这一现象的内在机制.自20世纪60年代以来,随着匈牙利数学家Erdos和Renyi的关于随机图论的论文的发表,人们对真实世界网络的认识停留在随机网络的认识水平上.Barabasi和Albert的发现,改变了以往人们对现实网络的认识,从而成为复杂网络研究的催化剂.很多有关复杂网络的重要性质、组织规律及其复杂网络上的动力学的研究论文相继发表,特别是无标度网络上传染病的阈值问题、复杂网络的层次性、结构性、自相似性等方面重要的结果[7-10].有关复杂网络研究的现状,读者可参考文献[11-15],这里不再赘述.复杂网络理论为描述博弈个体之间的博弈关系提供了方便的系统框架.网络上的节点表示博弈个体,边代表与其邻居的博弈关系.这样一来,就可以利用复杂网络拓扑关系,来研究一些复杂的博弈关系下的博弈.比如,以前的博弈理论中的混合均匀(well2mixed)假设就可以看成是在全连通图上进行的博弈.在空间二维格子(lattice)或一维格子(ring)上博弈即可转化为规则网络上的博弈.然而,真实世界的网络是异质的(heterogeneous),大部分节点的邻居数目存在差异,甚至成幂率分布.因此,研究接触网络(network of contact s)的异质性对其上的博弈动力学的影响是非常有意义的.在演化博弈研究中,一个重要的方向就是研究理性的博弈者之间如何涌现出合作行为.比如,在囚徒困境博弈(Prisoner’s Dilemma)中,每个纯策略的个体都有2种选择:合作(cooperation,C)与作弊(defection,D).D策略个体利用C策略个体,获得T收益,而C获得S.双方都合作获得R,都作弊获得P,其中T>R>P>S,2R>T+S.在单轮博弈情况下,无论对手采取何种策略,个体的最佳策略总是作弊(defect).然而,在双方都采取合作(cooperate)策略的情况下,二者总的收益才是最大的.这一现象说明了社会两难(social dilemma)问题的实质.当囚徒困境博弈在2个个体之间进行多次时,每个个体都可以根据上次博弈的结果选择进行下次博弈的策略(即迭代囚徒困境博弈)(iterated prisoner’s di2 lemma game).在20世纪70年代末的Axelrod锦标赛(Axelrod tournament)中,英国数学家、生物学家Rapoport提出的Tit2for2Tat(TF T)策略脱颖而出,打败了其他策略.所谓TF T是一个偏向合作的策略,第一步采取合作,然后重复其对手上一步的策略.但是TF T在有环境干扰时表现并不好,此时・2・智 能 系 统 学 报 第2卷Pavlov策略就能打败TF T.Pavlov策略是属于更一般的Win2Stay2Lo se2Shift(WSL S)策略类型. WSL S策略是指个体如果现在的策略获得的收益大于某个期望水平(aspiration level),那么下一步就保持这个策略不变,否则就切换到另外一个策略.在演化博弈中使用较多的另外一个范例是雪堆博弈(snowdrift game).假设合作的收益为b,成本为c(b>c),两个个体都选择合作则得到收益b-c/2,如果都作弊则收益为0.合作者遇到作弊者,则收益为b-c,作弊者则得到收益b.由于在雪堆博弈中,选择合作总比选择作弊要好,Nash均衡为混合策略(合作的频率为x3=(b-c)/(b-c/2).因此雪堆博弈被广泛地用于研究生物之间的合作行为.TF T策略和WSL S策略是建立合作和作弊策略基础上的宏策略(meta2st rategy).一般在博弈中只考虑最简单的策略(合作或作弊),如果囚徒困境博弈在相同的多个个体之间进行多次,其中个体可以通过记忆或学习、或者对作弊者进行惩罚,那么在合适的内在机制之下,合作行为将会涌现并逐渐占据优势.对合作机制的研究,特别是在复杂网络上的演化博弈背景中,是目前演化博弈研究的一个热点.2 演化稳定策略与复制动力学演化稳定策略(evolutio narily stable st rategy, ESS)相关概念最早由英国学者Maynard Smit h提出[16].策略I是ESS,必须满足条件:如果几乎所有的个体(pop ulation)都采取策略I,那么这些I策略的个体的适应度要比任何可能的变异策略要大.否则变异策略可以入侵种群并且I将不稳定.有了ESS的概念,就可以判断策略的稳定性.由于经典博弈中最重要的概念是收益矩阵(payoff mat rix)和收益,因此可以把经典博弈中的想法应用到ESS中来.假设生物的适应度跟收益成正比(或是收益的函数),或就等于收益,并且经典博弈中参与者理性(rationality)选择的策略就对应于ESS.与传统的Nash均衡相比,ESS这个概念要更加严格一些,因此可用于平衡点选择.因为所有的ESS必定是Nash均衡,但只有严格对称Nash均衡才是ESS.值得一提的是,这里的ESS是一个“静态”的概念,其假设只要求表现更好的策略具有更快的复制(增长)速率,并不涉及具体的博弈动力学.复制动力学(replicator dynamics)在1978年由Taylor和Jonker引进[17].其主要假设为给定的策略类型的单位复制率 ρiρi 正比于适应度之差:ρiρi=fit ness of type i-average fit ness.(1) 复制动力学是关于博弈动力学(策略更新)的连续确定性方程,从而可以赋予前面介绍的ESS这一静态的概念以动力学含义.复制方程在不动点附近的稳定性将对应于策略的稳定性(ESS).复制动力学与演化稳定性的关系可以总结如下[18-19]:1)ESS对应于吸引子;2)内部ESS对应于全局吸引子;3)对势博弈(potential game)而言,某个不动点是ESS当且仅当它是吸引子;4)对2×2矩阵博弈而言,某个不动点是ESS当且仅当它是吸引子.3 有限人口上的演化博弈动力学以往复制动力学及ESS的概念均假设人口为无限且混合均匀.但更实际一点,往往需要考虑人口非无限情形,此时演化动力学将受到有限人口因素的影响而满足随机动力学基本性质(Markov过程).2004年Nowak等人在Nat ure上发表文章指出在有限人口的情形下,采用依赖于频率的Moran过程(birt h2deat h process),经典的ESS的判据需要做修改,并提出了在弱选择下的“1/3规则”[20].假设种群由N个混合均匀的策略为A或B的个体组成,收益矩阵为A BA a bB c d假设有i个A策略的个体,那么策略A和B的适应度分别为f i=1-w+w[a(i-1)+b(N-i)]/[N-1],g i=1-w+w[ci+d(N-i-1)]/[N-1].(2) 这里适应度由个体原有的基线(baseline)1加上通过博弈获得的收益经过加权得到.w∈[0,1],表示自然选择的强度,即博弈收益对适应度贡献的大小.在每一时间步长,按照正比于适应度的概率选择一个个体进行复制,并替代一个随机选取的种群中个体.A类型的个体可能增加一个,减少一个或保持不变.因此Markov过程的转移矩阵为三对角矩阵(t ri2diagonal mat rix),矩阵元素为P i,i+1=if ii f i+(N-i)g iN-iN,P i,i-1=(N-i)g ii f i+(N-i)g iiN,(3)・3・第2期 王 龙,等:复杂网络上的演化博弈P i,i=1-P i,i+1-P i,i-1,其他元素为零.这个随机过程具有2个吸收态(ab2 sorbing state)i=0和i=N.如果种群达到这2个吸收态之一的话,系统将永远保持状态不变.以x i表示种群从i个A个体开始演化到i=N终态的概率,即固定概率(fixation p robability),那么有以下关于x i的递归方程(recursive equation)[20-22]:x i=P i,i+1x i+1+P i,i x i+P i,i-1x i-1,(4)边界条件为x0=0和x N=1.方程的解由Karlin和Taylor在1975年给出[23]:x i=1+∑i-1j=1∏jk=1g kf k1+∑N-1j=1∏jk=1g kf k,(5)考虑单个A个体能入侵并占据所有的B个体的概率:ρA=x1=11+∑N-1j=1∏jk=1g kf k,(6)对于中立博弈(neut ral game)来说,此时w=0,x1= 1/N.若ρA>1/N,那么自然选择偏向于A取代B.在有限人口N的情况下,B策略是ESS,记作ESS N,如果以下条件满足[20]:1)选择不利于A入侵B,这意味着B种群中的一个变异A具有较低的适应度;2)选择不利于A取代B,这意味着固定概率ρA<1/N.值得一提的是,不像在无限人口中2种策略有可能共存的情况,在有限人口中,某种策略最终会被固定下来(即最终不存在2种策略共存的情况),但达到固定的时间有可能很长,此时讨论固定概率就没有多少意义了.因此固定时间(fixation time)从另一个方面反映了自然选择如何影响种群进化的速度.一般讨论条件平均固定时间(conditional mean fixation time).在文献[22]、[24]中,发现系统从状态i=1演化到i=N,或从i=N-1到i=0的条件平均固定时间是相等的.进一步地,这一结果跟收益矩阵没有关系,即无论是在A对B是占优的情况下,还是在A和B都是对自己的最好反应等情况下,条件平均固定时间的均值和方差都是相等的.这是一个相当有趣的结果.文献[24]还发现,这一结果对于Wright2Fisher过程或同时有多个变异存在的情况并不成立.对于有限人口,演化动力学是一个随机过程,那么在人口N趋于无穷大的情况下,二者有没有联系呢?Traulsen等人发现[25],若采用标准的Moran 更新过程,在N→∞时,人口演化的随机动力学将对应于调整复制方程(adjusted replicator equation )或Maynard Smit h形式的复制方程.如果采用对比较(pair comparison)更新方式,在N→∞时,人口演化的随机动力学形式上将对应于标准复制方程.如果记x=i/N,以ρ(x,t)表示人口在t时刻处于x 状态的概率密度,那么ρ(x,t)满足Fokker2Planck 方程(FPE)[25-26]:dd xρ(x,t)=-dd x[a(x)ρ(x,t)]+12d2d x2[b2(x)ρ(x,t)].(7)式中:T+(x)=f ix f i+(1-x)g ix(1-x),T-(x)=g ix f i+(1-x)g ix(1-x),a(x)=T+(x)-T-(x),b(x)=(1/N)[T+(x)+T-(x)],使用Ito积分,式(7)FPE方程变成Langevin方程:x=a(x)+b(x)ξ,(8)式中:ξ为非相关高斯噪声.在N→∞时,b(x)→0,式(8)方程由随机微分方程变成了确定性的复制方程.文献[26]推广了Nowak的有限人口时弱选择下ESS N的充分条件:当N wν1时,“1/3规则”是有效的;对w固定且Nµ1时,传统的ESS判定条件成立.有限人口因素对人口策略演化的影响是当前研究的一个热点问题.更详细的内容可以参考文献[27-30].4 复杂网络上的演化博弈上面所讨论的混合均匀的有限人口中的博弈动力学,相当于在全连通图上的演化博弈问题.复杂网络或图为描述博弈关系提供了方便的框架:顶点表示博弈个体,边表示博弈关系.在每一时间步长,节点与其所有邻居进行博弈,累积博弈获得的收益,然后根据更新规则进行策略更新,如此这样重复迭代下去.近年来,复杂网络上演化博弈问题,尤其是对合作行为产生的机制的探索,引起了学术界广泛的注意和兴趣[31-33].尽管对合作行为提出了一些可行的机制,但合作行为的本质和真正内在机理,仍然是一个尚未解决的问题[34-35].复杂网络上的演化博弈研究主要可分为2种:一种是研究网络拓扑对合作的影响,主要是静态(static)网络的拓扑性质对合作水平的影响;另外一种是网络拓扑和博弈动力学的共演化(co2evolution),主要是自适应(adaptive)网・4・智 能 系 统 学 报 第2卷络上博弈动力学,即网络拓扑调整受博弈动力学影响.Nowak等人首先研究了空间二维格子上的囚徒困境博弈,即每个博弈个体跟邻近的4个或8个邻居进行博弈.在此基础上发现了美妙的空间混沌[36-37],并发现了对于囚徒困境博弈,博弈个体的空间分布会加强合作(spatial cooperation).但是, Hauert等人发现对于雪堆博弈,博弈个体的空间分布结构往往会削弱合作水平[38].Szabó等人利用平均场(mean2field)、对估计(pair2app roximation)等方法,系统地研究了二维平面各种规则格子上的演化博弈问题[39-41].由于社会网络具有小世界和无标度等特性,因此研究拓扑特性对合作的影响是十分有意义的.小世界网络上的空间纯策略博弈主要分为2类:一类是基于环的小世界网络;另一类是基于方格的小世界网络.Santo s等人研究了同质(homogeneo us)和异质(heterogeneous)的小世界网络上的演化博弈问题[42-44].异质小世界网络是由规则网络演化而来:由一个具有N个节点的环开始,环上每一个节点与两侧各有m条边相连.对每条边以概率p随机进行重连(自我连接和重边除外).重连以后,如果保持网络的平均度不变,此时的网络就为异质小世界网络;而同质小世界网络也是由规则网络演化而来:由一个具有N个节点、平均度为z的规则网络开始,其边数为E=N・z/2.以概率p进行交叉换边重连(同样避免重复连边).这样重连以后不改变节点的度的网络就为同质的小世界网络(此时每个节点的度相等,亦称之为规则随机图(regular random grap h).对于上述2种小世界网络,当概率p=0时,相应的网络为规则网络,而当概率p=1时,相应的网络为随机网络.Santo s等仿真了环型小世界网络上的“弱”囚徒困境的博弈情形.他们发现平衡态时异质小世界网络上的合作策略比例比同质小世界网络上的要大.在异质小世界网络上,当概率p不断增大时,平衡态时合作策略比例也不断增强[42,45].而在同质小世界网络上,对于囚徒困境博弈,存在一个临界作弊收益值b c,当b<b c时,随着概率p不断增大,对应平衡态时合作反而不断降低;当b>b c 时,随着概率p不断增大,对应平衡态时合作不断增强[42].Ren[46]等发现在均匀小世界网络上,同时也存在一个临界概率p c,当概率p<p c时,平衡态时合作水平不断增强;当概率p>p c时,平衡态时合作水平反而不断降低.这说明p c为最优概率值,能保证合作最强.大部分工作采取策略演化更新规则:w Sx←Sy=11+exp[(M x-M y)/T].(9)式中:w Sx←Sy表示节点x模仿邻居节点y策略的概率,M x、M y表示节点x、y的累积收益,T表示节点的理性程度.当T=0时,表示完全理性选择;当T→∞时,表示完全随机选择.适当的T也可以加强合作,即存在一个最优的能使博弈合作程度达到最强[46].Szabó等人也研究了方格小世界网络上的带有loner的囚徒困境博弈问题(即带有志愿者参加(volunteering participation)的囚徒困境博弈),发现重连概率大于一定的阈值时,相图会发生振荡[47].有趣的是,若分别用优先选择邻居和随机选择邻居的演化规则,在方格小世界上会发现优先选择邻居能促进合作[48-49].Tomassini等仿真研究了方格小世界网络上的鹰鸽博弈(hawk2dove game,数学上等价于前面所提到的雪堆博弈),发现平衡态的合作与演化规则、收益比(gain2to2cost)r以及重连概率p相关[50].Santo s和Pacheco等采用同步更新的策略模仿(st rategy imitation)更新方法对无标度网络上的空间纯策略博弈行为进行了较系统的研究[43,51-53],发现与规则网络、随机网络相比,无标度网络更有利于合作行为的产生.因此网络拓扑的异质性(度分布为幂率分布)是提升合作水平的一个重要因素.Ren等采用“优先学习”方法,即优先选择邻居来进行模仿演化,数值仿真显示平衡态时合作水平得到加强[54].类似于亲缘选择中的合作判据Hamilton规则[55],Oht suki等人发现在网络上合作行为产生的一个充分性判据:b/c>k,其中b、c分别为合作行为的收益和代价,k为网络的平均度[56].这一合作行为简单判定规则适用于二维格子、随机网络和无标度社会网络.考虑在网络上的入侵和固定动力学(dy2 namics of invasion and fixation),即一个变异A入侵种群B的固定概率,Antal等人发现在度不相关无标度网络上的一个变异的固定概率跟它发生的节点的度相关,且发现对投票模型(voter model),固定概率正比于度,对生灭(birt h2deat h)过程,固定概率反比于度[57].除了网络的异质性对合作行为有影响外,网络的平均度也是影响合作涌现的重要因素之一.文献[58]研究了随机图、小世界、无标度3种网络中平均度对合作水平的影响,发现对于每种网络均存在适当的平均度使得合作水平最优.另一方面,博弈动力学与网络拓扑共演化的问题也得到一些关注和研究.网络拓扑影响博弈结果,而博弈结果反过来作用于网络拓扑,调整网络拓扑・5・第2期 王 龙,等:复杂网络上的演化博弈(或社会关系),这种情形更符合实际.Zimmermann 等人认为个体可以依据博弈结果调整与邻居的边来实现合作者与合作者之间的联合,从而有利于合作行为的涌现和维持[59-60].Santo s等人考虑了网络拓扑调整与博弈演化之间的时间尺度的关系,并假设不满意博弈结果的节点以一定概率断开与邻居中作弊者的边,并随机重连到作弊者的邻居,发现存在时间尺度之比的临界值,一旦超过这个临界值,合作将会占上风[61].Pacheco等人考虑了简化的情形,提出了活跃连接(active linking)的假设,在一定条件下,自然选择将偏向于合作[62].目前文献中关于这方面的结果比较少,但这个问题又为大家所关注,因此这个问题将是今后研究的一个重点.5 演化囚徒困境博弈中的合作涌现真实社会的网络拓扑除了具有小世界、无标度等性质外,还具有社团结构(community st ruct ure)这一重要的性质.社团结构是指整个网络是由若干个“群(gro up)”或“团(cluster)”构成的.每个群内部的节点之间的连接相对比较紧密,但是各个群之间的连接却比较稀疏.因此,研究社团结构对合作水平的影响是很有意义的.笔者研究了具有社团结构的无标度网络上的囚徒困境博弈问题[63].不失囚徒困境博弈的一般特性,博弈矩阵M取为[36]M=10b0.(10)式中:1<b<2.采用文献[64]中具有社团结构的无标度网络模型,生成节点总数N=6000、具有3个相同大小群的社团结构的博弈关系网络.用二维向量表示个体的策略类型:合作(C)与作弊(D):C=1,D=1.个体x的收益为他跟所有邻居博弈一次的收益的总和:P x=∑y∈Ωxs T x Ms y,其中s x、s y表示节点的状态(策略),Ωx表示x的所有邻居.采用同步更新规则(synchronous up date rule),在每一时间步长,节点x从其邻居中随机选取节点y进行策略更新,若P y>P x,则以概率W sx ←xy=P y-P xbk>.(11)采用节点y所用的策略s y,其中k>为节点x和y的度中的较大值.初始时刻,合作者与作弊者等比例随机分布在网络顶点上.系统演化10000时间步长后,再取1000步时间步长上合作者比例的平均数,得到平衡态时合作者的比例.每个数据点对应于40次不同的网络实现和初始分布条件下合作者比例的平均值.图1显示了相同网络规模,但不同平均度m+n及不同社团内外连接数之比m/n时的合作频率对参数b的变化情况.可以发现,在具有社团结构无标度网络上,随着平均度m+n的增加,合作水平也相应地减小.同时,在保持平均度m+n不变,改变内外连接数之比m/n时,合作水平随着m/n减小而降低.另外,在没有外部连接时(对应于n=0),合作水平总是最优的.此时对应于3个Barabasi2Al2 bert(BA)无标度网络,而无标度网络是利于合作的涌现的[51],因此此时合作水平最高.随着外部连接数的增加、内部连接的较少,网络结构中的一些hub (网络中度较大的节点)并不直接相连,并且网络中回路(loop)减少了,这些因素影响了合作水平[63].图1 对应于不同m+n与m/n时合作频率对参数的变化情况Fig.1 Frequency of cooperators vs.b corresponding todifferent m+n and m/n文献[51-53]指出复杂网络的异质性是影响合作水平的重要因素.但复杂网络的异质程度大小会对合作水平产生什么影响呢?考虑了异质New2 man2Watt s小世界网络上的演化囚徒困境博弈问题[65].与Watt s2St rogatz小世界模型中断边重连机制不同[5],本文采用改进的Newman2Watt s小世界模型,即在低维规则环上添加m条长程边形成小世界网络.首先随机地从N个节点中选出N h个节点・6・智 能 系 统 学 报 第2卷。
