复杂网络及其上的演化博弈简介 关剑月 1 1, 刘旭升 (1. 物理科学与技术学院计算物理与复杂系统研究所, 甘肃兰州 730000) 摘要 : 本文主要向本科生同学简要介绍复杂系统及复杂网络的一些基本概念, 并概述复杂网络 上演化博弈的研究背景及研究进展情况 旨在为本科生了解该交叉学科方向提供一个窗口 关键词 : 复杂系统 ; 复杂网络 ; 演化博弈 复杂系统是指具有复杂相互作用的大量单元组成的宏观系统 真实世界的许多复杂系统可以通过复杂网络来进行描述 [1-7], 因而复杂网络成为研究复杂系统结构和动力学性质的一个非常重要的工具 那么, 什么是网络呢? 简单的说, 网络可以看作是由节点按照某种方式连接在一起而构成的系统, 其中, 节点代表物理实体, 节点间连接则表示物理实体之间的关系或作用 比如, 在食物链网络中, 节点表示物种, 节点间连接表示物种之间的捕食关系 ( 图 1 ) [3] ; 在科学家合作网中, 科学家用网络中的节点表示, 他们之间的合作关系用节点之间的连接来描述 ( 图 2) [6], 等 图论上, 一个具体的网络可以抽象为一个由点集和边集组成的图 ( 图 3) 从统计物理的角度来看, 网络是包含了大量个体以及个体之间相互作用的系统, 是描述系统现象及其内部关系的图 图 1. 食物链网 : 节点表示物种, 节点间连线表示物种之间的捕食 - 被捕食关系 基金项目 : 本论文为教师特邀评述 通讯作者 : 关剑月 (1981-), 女, 河北省邯郸市人, 兰州大学计算物理与复杂系统研究所副教授 联系方式 :E-mail: guanjy@lzu.edu.cn,tel.: 13919136416 5
图 2. 科学家合作网 : 节点表示科学家, 节点间连线表示他们之间的合作关系 图 3. 由 8 个节点和 12 条边构成的网络图 在复杂网络的研究过程中, 人们发现网络的结构对系统的动力学行为有着重要的作用, 那么如何来描述网络结构呢? 网络结构主要通过三个基本的几何参量来刻画 : 度分布 平均路径长度和成团系数, 下面分别介绍这三个参量的含义 度与度分布 : 节点的度定义为与该节点相连的其他节点的数目 节点度是网络研究中最基本的量 网络中所有节点的度的平均值称为网络的平均度 网络中节点的度分布 P(k) 表示从网络中随机选出一个节点, 该节点的度为 k 的概率 平均路径长度 : 在无向 无权网络中, 两个节点 i,j 之间的路径长度 ( 距离 )d ij 定义为连接这两个节点的最短路径上的边数 网络中任意两个节点之间的距离最大值称为网络的直径, 记为 D 对网络中所有的节点对之间的最短路径长度进行平均, 即可得到整个网络的平均最短路径长度 L 网络的平均路径长度也称为网络的特征路径长度 研究发现, 许多实际的网络尽管节点数目很多, 而网络的平均路径长度却小的惊人 对于固定节点平均度的网络, 如果其平均路径长度至多与网络规模的对数成正比, 则称该网络具有小世界效应 6
成团系数 : 在你的朋友关系网络中, 你的两个朋友很可能彼此也是朋友, 这种属性称为网络的成团性质 网络中的一个集团是指由一系列的点组成的一个集合, 其中任意一个节点和该集团中的其他点都连通 成团系数就是用来描述网络的集团化程度的参量, 即网络中连接在一起的集团各自的近邻中有多少是共同的邻居 网络的成团系数定义为与网络中的任意一点相连的点也相互连接的概率 假定一节点 i 有 k i 个最近邻, 那么这些最近邻中最多可存在 k i (k i -1)/2 条连接, 用 E i 表示这些最近邻的点之间的实际连接数, 则节点 i 的成团系数定义为实际连接数 E i 与总的可能的边数 k i (k i -1)/2 的比值 对网络中的所有节点的成团系数取平均值, 就得到了整个网络的成团系数 现实世界中, 合作是一种普遍存在的现象, 不论是动物世界还是人类社会 ( 图 4) 然而自私的个体之间为什么能够合作? 合作存在的机制是什么? 近些年的研究发现, 演化博弈理论可以给出很好的解释 [8,9] 那么让我们首先来了解一些有关博弈论的基本概念和研究背景 图 4. 左边是人们通过合作来共同捕猎 ; 右图是动物之间的合作 1944 年, 匈牙利数学家 von Neumann 和 Morgenstern 的著作 博弈理论和经济行为 的问世, 标志着博弈论的诞生 博弈论最重要的任务之一是为如何解决社会两难问题提供一种指导方针和解释在没有中心调控下, 通过个体之间的微观相互作用仍有可能自发产生一种更有效而切合实际的集体合作 博弈, 又叫策略博弈, 它是基于微观个体相互作用的模型 只要个体之间存在矛盾 竞争与合作, 则其微观动力学演化机制均可以通过博弈模型来描述 那么, 什么是博弈呢? 实际上我们通常玩的五子棋 象棋 剪刀 - 石头 - 布都是博弈, 一个常规的博弈 ( 具有完整信息的静态博弈 ) 通常由三部分组成 : 参与博弈的个体 ( 至少有两个 ); 每个博弈个体可以选择的策略集合 ; 博弈个体通过采取某种策略与其它个体进行博弈后获取的收益 [8] 1950 年, 美国数学家纳什提出了博弈论中的一个重要概念 纳什均衡 (Nash equilibrium), 这是博弈理论发展中的一个重要的里程碑 虽然经典博弈论证实了纳什均衡的存在, 但到目前为止还没有证实实际博弈中的策略学习动力学遵从经典博弈论所描述的静态图像 博弈个体的更加符合实际的策略学习动力学则由演化博弈论给出 Smith 和 Price 于 1973 年发表创造性论文 动物冲突的逻辑 [10], 首次提出演化稳定策略的概念, 该文章的出版标志着演化博弈理论的正式诞生 演化博弈理论与传统博弈理论不同, 演化博弈理论并不要求参与人是完全理性的, 也不要求完全信息的条件 演化博弈论把博弈理论和动态演化过程结合起来, 在方法论上, 它不同于博弈论将重点放在静态均衡和比较静态均衡上, 强调的是一种动态的均衡 演化博弈论是我们关注的焦点, 目前, 演化博弈论已经发展成为一门应用科学, 在许多领域中有着广泛的应用, 如经济学 社会学 政治学和演化生物学等 7
下面介绍一种最典型也是应用最多的博弈模型 -- 囚徒困境博弈 [11-14] 1950 年, 由就职于兰德公司的梅里尔 弗勒德和梅尔文 德雷希尔拟定出相关困境的理论, 后来由顾问艾伯特 塔克以囚徒方式阐述, 并命名为 囚徒困境 经典的囚徒困境如下 ( 图 5): 警方逮捕甲 乙两名嫌疑犯, 但没有足够证据指控二人有罪 于是警方分开囚禁该两名嫌疑犯, 分别对二人进行审问, 并向双方提供以下相同的选择 : 若甲方指控乙方, 即作证检控对方 ( 即 背叛 对方 ), 而乙方保持沉默 ( 认罪 ), 那么甲方将即时获释, 沉默者 ( 乙方 ) 将判监 10 年 ; 若二人都保持沉默 ( 合作 ), 则二人均判监半年 ; 若二人都互相检举 ( 互相 背叛 ), 则二人均判监 2 年 用如下表格表示收益矩阵 : 表 1. 囚徒困境博弈的收益表示 甲沉默 ( 合作 ) 甲指控 ( 背叛 ) 乙沉默 ( 合作 ) 二人同服刑半年 甲即时获释 ; 乙服刑 10 年 乙指控 ( 背叛 ) 甲服刑 10 年 ; 乙即时获释 二人同服刑 2 年 从表 1 中不难看出, 若甲采取 背叛 策略, 此时乙采取 合作 策略获取的收益 判监 10 年 低于采取 背叛 策略获取的收益 判监 2 年 若甲采取 合作 策略, 乙采取 合作 策略获取的收益 判监半年 低于采取 背叛 策略获取的收益 即时获释 因此, 在囚徒困境博弈中个体的最佳策略是 背叛, 即 背叛 相对于 合作 为优势策略 然而, 从总体收益来看, 若两人都 合作, 两人被判年数之和为 1; 若一人 背叛, 一人 合作, 两人被判年数之和为 10; 若两人都 背叛, 两人被判年数之和为 4 由此可以看出两个个体均采用优势策略并不能得出全局最佳收益的结果 这就是 困境 的由来 图 5. 囚徒困境博弈 为了解决以上困境或社会两难问题, 需要考虑更加符合现实的因素和机制 在对演化博弈的研究中, 五种有利于合作的机制被提出, 分别是 : 亲缘选择 直接互惠 间接互惠 空间或网络互惠 群体选择 [15] 与其他四种机制不同的是, 在没有任何策略复杂性的情况下, 空间结构会导致合作行为的涌现, 该机制的提出引起学术界的广范关注 近年来, 人们对复杂网络上的演化博弈做了大量研究, 提出了很多理论来解释合作的产生和演化 [8,16-21] 目前, 复杂网络上的演化博弈依然在蓬勃发展, 新的研究成果不断涌现, 不断深化我们对合作现象内在机制的认识 当然, 现在还有很多重要的问题需要解决 比如, 目前为止, 复杂网络上的演化博弈仍然没有一套系统的数学描述, 这就致使我们很多时候对观察到的现象还停留在定性的认识上 ; 真实复杂系统结构是动态变化的, 个体之间的相互作用会影响其在空间中的 8
分布模式, 同时复杂系统的结构也会影响个体间的博弈动力学, 那么两者之间是如何相互影 响 协同演化的呢? 等等 这些问题仍需要人们进行不断的探索! 年轻的我们在努力, 更年 轻更有活力的你们是否也有兴趣加入进来, 和我们一起寻找答案呢? 参考文献 [1] D.J. Watts and S.H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393 (1998) 440. [2] A.-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science 286 (1999) 509. [3] S.H. Strogatz. Exploring complex networks. Nature 410 (2001) 268. [4] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002) 47. [5] S.N. Dorogovtsev and J.F.F. Mendes, Evolution of networks. Adv. Phys. 51 (2002) 1079. [6] M.E.J. Newman, The structure and function of complex networks. SIAM Review 45 (2003) 167. [7] S. Boccaletti, V. Latora, Y. Moreno, et al. Complex networks: Structure and dynamics. Physics Reports 424 (2006) 175. [8] G. Szabó and G. Fáth, Evolutionary games on graphs. Phys. Rep. 446 (2007) 97. [9] J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge: Cambridge University Press, 1998. [10] J.M. Smith and G.R. Price. The logic of animal conflict. Nature 246 (1973) 15. [11] G. Szabó and C. Töke. Evolutionary prisoner's dilemma game on a square lattice. Phys. Rev. E 58 (1998) 69. [12] G. Abramson and M. Kuperman. Social games in a social network. Phys. Rev. E 63 (2001) 030901(R). [13] F.C. Santos and J.M. Pacheco. Scale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation. Phys. Rev. Lett. 95 (2005) 098104. [14] J. Vukov, G. Szabó, and A. Szolnoki. Evolutionary prisoner's dilemma game on Newman -Watts networks. Phys. Rev E 77 (2008) 026109. [15] M.A. Nowak. Five Rules for the Evolution. Science 314 (2006) 1560. [16] H. Ohtsuki, C. Hauert. E. Lieberman, et al. A simple rule for the evolution of cooperation on graphs and social networks. Nature 441(2006) 502. [17] M.H. Vainstein and J.J. Arenzon. Disordered environments in spatial games. Phys. Rev. E 64 (2001) 051905. [18] M. Tomochi and M. Kono. Spatial prisoner's dilemma games with dynamic payoff matrices. Phys. Rev. E 65 (2002) 026112. [19] Z.-X.Wu, X.-J Xu, Y. Chen, et al. Spatial prisoner's dilemma game with volunteering in Newman-Watts small-world networks. Phys. Rev. E 71 (2005) 037103. [20] J.Y. Guan, Z.X. Wu, Z.G. Huang, et al. Promotion of cooperation induced by nonlinear attractive effect in spatial Prisoner's Dilemma game. Europhys. Lett. 76 (2006) 1214. [21] X.S. Liu, J.Y. Guan, Z. X. Wu. Effects of limited interactions between individuals on cooperation in spatial evolutionary prisoner's dilemma game. Chaos, Solitons & Fractals 56 (2013) 106 112. 9