复杂网络下动态拓扑囚徒困境博弈研究(攻略)

复杂网络下动态拓扑囚徒困境博弈研究(攻略) 华 中 科 技 大 学 硕 士 学 位 论 文 I 摘 要 20 世纪末，复杂网络取得了高速的发展，复杂网络广泛应用于经济学、生物科 学、信息科学等各个领域。而在博弈论中引入复杂网络，为研究群体中个体之间的 行为建立了一个极好的框架。复杂网络上的博弈主要围绕两个方面:网络拓扑结构 和策略选择机制展开研究。 本文针对经典的囚徒困境博弈，分别从网络拓扑结构以及博弈个体的策略选择 机制出发，对复杂网络上的囚徒困境博弈进行了介绍。 首先介绍了复杂网络上的博弈的两个基础理论:复杂网络和博弈论。针对复杂 网络介绍了复杂网络理论的发展、描述网络特性的网络参数和复杂网络模型。而对 博弈论则介绍了博弈理论发展、Nash 均衡、囚徒困境博弈以及演化博弈。 然后介绍了囚徒困境博弈下的两种不同策略选择机制:基于模仿学习和基于记 忆的自我学习机制。并在复杂网络上提出了一种新的动态拓扑囚徒困境博弈算法， 该算法使网络在博弈过程中拓扑结构也在不断变化，实现了网络拓扑和博弈动力学 的共演化。并用Matlab 进行仿真，采用动态拓扑博弈算法时，发现如下结果:网络 节点度的最大值变小，且度最大值随着背叛诱惑值增大而减小;大于网络平均度的 节点数增多;在采用基于记忆自我学习机制时，度数为1 的节点的合作比趋向于0， 度大于1 的节点的合作比趋向于1;在采用基于模仿学习机制时，与静态拓扑的囚徒 困境博弈相比，动态拓扑囚徒困境博弈算法网络的合作水平较高。 最后对全文作了总结，并对以后的工作进行了展望。 关键词:复杂网络; 博弈论; 复杂网络上的博弈; 敉嚼Ь巢?? 动态拓扑 华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract In the 20th century, complex network have made a rapid development. The complex networks are widely used in many different fields, such as economics, biological sciences, information science and so on. By introducing complex network to game theory, a perfect frame on which we can study the behavior of individuals on networks is established. The research of the game on complex networks has two main points: network topology and the learning mechanism of individual on complex networks. Based on the above two points: network topology and the learning mechanism of individual on complex networks. This paper introduced the Prisoner?s Dilemma Game (PDG) on complex networks. First we introduced two basic theories of the game on complex networks: complex networks and game theory. To complex networks, we review the development of complex networks, some network parameters and some typical network structures. And we also studied something about game theory, including the development of game theory, Nash Equilibrium, Prisoner?s Dilemma Game (PDG), and Evolutionary Game. Then two different learning mechanisms of individual on complex networks: the learning mechanism of imitating the strategy of neighbors and the learning mechanism based on historical memory. A Prisoner?s Dilemma Game (PDG) Model based on Dynamic topology (PDG-DT) was proposed, in this model the network topology is changed while the game is going on, so the network topology and the strategy of individuals have a co-evolutionary. Matlab software are used to simulate. When we do simulation under the PDG-DT model, we found the result as follows. The maximum degree of network nodes is smaller than that of initial network nodes, and as the value of temptation become higher the maximum get lower; the number of nodes whose degree is larger than average degree of network nodes become greater; when the network uses the learning mechanism based on historical memory, the cooperation level of nodes whose degree equals 1 trend to be 0, and the cooperation level of nodes whose degree is greater than 1 approach to be 1; when the network uses the learning mechanism of imitating the strategy of neighbors, compare to Prisoner?s Dilemma Game (PDG) Model based on Static 华 中 科 技 大 学 硕 士 学 位 论 文 III topology (PDG-ST), the network under the PDG-DT model can get a higher level of cooperation. At last, the entire work is reviewed and outlook of this thesis is made. Keywords: Complex networks; Game theory; The Game on Complex Networks; Prisoner?s Dilemma Game; Dynamic topology ? 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名: 日期: 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密?，在______年解密后适用本授权数。 本论文属于 不保密?。 (请在以上方框内打“?”) 学位论文作者签名: 指导教师签名: 日期: 年 月 日 日期: 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪 论 1.1 研究背景与意义 随着科技的发展，人们对事物的认识不断加深，我们不再局限于管中窥豹式的 对单个物体进行研究，而是着眼于整体对各种单体所组成的复杂系统进行探索和发 现，由此诞生了一门新兴的学科——复杂性科学。复杂性科学可运用于各种不同的 科学领域，复杂性科学为各领域内的问题提供科学的解决方法，正如著名科学家霍 金所说:“下一个世纪将是复杂性科学的世纪 [1] 。” 复杂系统可以通过网络来描述。网络中的节点代表系统中不同的个体，网络节 点间的边表示系统中个体之间的某种联系和制约。所以复杂性科学中的一个重要组 成部分就是复杂网络。复杂网络可以描述现实世界中的各种系统，包括生物学的地 球生态系统、医学的人体神经系统、经济学中的商业经济系统、计算机科学的Internet 网络系统、电力网络系统以及交通运输系统等等。统计这些系统的网络特性， 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 其共同点和差异，建立起相应的复杂网络模型，将带来现实意义。例如研究电力网 络系统中输电线路的拓扑结构，可以提高电力网络的鲁棒性;研究交通运输网络的 拓扑结构可以提高道路的利用率和降低交通系统的堵塞率;研究计算机网络的拓扑 结构可以提高网络带宽利用率和减小网络拥塞率等等。 20 世纪末复杂网络研究取得了两个重大的发现:一是Watts 和Strongatz 提出的 小世界现象 [2] ，二是Barabasi 和Albert 提出网络的无标度特性 [3] 。这两个发现很好地 揭示了现实网络的两大特性，为复杂网络学科的发展作出了巨大的贡献。在了解现 实网络的这两种特性后，能够比较自己所建立的网络模型是否符合现实网络这两种 特性。 博弈论也称对策论，它首先广泛应用于经济学当中。1944 年匈牙利数学家冯?诺 依曼和经济学家摩根斯坦共著的《博弈论与经济行为》标志着经典博弈论的诞生 [4] 。 之后约翰?福布斯?纳什在 1951 年提出的纳什均衡理论将博弈论的发展向前迈进 了一大步。随着人们对博弈论的研究，人们开始对网络中个体间的博弈进行研 华 中 科 技 大 学 硕 士 学 位 论 文 2 究，从而复杂网络被引入到博弈论之中。复杂网络为群体中复杂的博弈关系研 究提供了一个很好的框架。人们对复杂网络博弈的研究主要包括:合作行为在 复杂网络中涌现的原因分析，合作水平与复杂网络特征的关系，复杂网络上网 络合作行为的特点，提高复杂网络中合作水平的方法等等。目前，对复杂网路 上博弈的研究已经取得了许多成果，人们将这些研究成果广泛应用在经济、生 物、计算机领域。 在一个网络群体中，在个体都是自私的情况下如何保证群体中的合作水平， 这是具有现实意义的问题。例如对生物种群的合作行为的研究，对商业领域中 企业之间的合作竞争行为等等。影响合作行为有两个因素:一是网络拓扑结构 [5~7] ，二是网络中博弈个体的策略学习机制 [8~9] 。本文提出了复杂网络上的动态拓 扑囚徒困境博弈，该算法实现了网络拓扑和博弈策略的共演化，通过将该博弈 算法和静态拓扑下的博弈进行比较，讨论了网络拓扑和学习策略对合作行为的 涌现、合作行为的特征、合作水平等方面的影响。 1.2 国内外研究现状 对于复杂网络的研究主要分为三个部分:1) 现实网络结构和行为特征的数据分 析;2) 复杂网络建模;3) 复杂网络上的动力学问题 [17] 。本文研究的主要内容为复杂 网络下的囚徒困境博弈，其相关知识包括复杂网络建模以及复杂网络上的博弈动力 学。下面我们对相关知识的研究现状作简单的总结。 现实世界中存在大量的网络系统，人们为了更方便的对网络系统进行研究，就 针对现实网络系统的统计特性建立各种网络模型。最初，科学家们利用规则网络来 代表一些简单的真实网络系统，二维方格网络是典型的规则网络。20 世纪50 年代末， 匈牙利数学家Erd?s 和Rényi 突破传统图论，提出了一种完全随机的网络模型(ER 模 型) [18] 。ER 模型中，网络节点之间按照概率 p 随机连接，当 ER 模型中的网络节点 数N 很大时，其度分布函数P(k)服从Poisson 分布，且网络直径l 随着连接概率p 的 增大而减小。当时人们认为ER 模型是反映现实网络的最佳网络模型，直到20 世纪 末，随着计算机网络的迅猛发展，人们通过对计算机网络的统计分析，发现原有的 华 中 科 技 大 学 硕 士 学 位 论 文 3 网络模型并不能反映Internet 网络特性。此时复杂网络的研究出现了两个重大的研究 成果:第一个是Watts 和Strongatz 于1998 年在Nature 杂志上共同发表的《Collective Dynamics of „Small-World? Networks》，文中发现了真实网络中存在小世界特性，即小 平均路径长度和大聚集系数，并由此建立了小世界网络模型 [2] 。第二个是 1999 年 Barabasi 和Albert 指出许多现实网络的度分布呈幂律分布，也称网络的无标度特性， 并建立了无标度网络模型 [3] ，该模型生成的主要机制是生长和优先连接。之后人们在 这些基本的网络模型上进行一系列的拓展。针对WS 小世界模型，Newman 和Watts 随后又提出了一种NW小世界模型，NW小世界模型不同点是采取了“随机化加边” 而不是WS 小世界模型的“随机化重连”的策略 [19] 。在对Internet 网研究中Li 和Chen 发现计算机终端分布在不同的域中，然后与本域之外的节点相连的，即计算机终端 在某个域中进行优先连接，根据这个发现提出了局域世界网络模型 [20] ，该模型表现 了现实网络中网络整体由不同的局域世界组成。针对 BA 网络模型，人们随后也提 出了许多改进模型。Krapivsky、Redner 以及 Leyvraz 改变了 BA 网络模型中线性的 优先连接概率，采取非线性的优先连接概率，采取这种生成算法生成的网络度分布 没有无标度特性 [21] 。Dorogvtsev、Mendes 和Samukhin 通过对现实社会网络的研究发 现每个人的的魅力不一样，就像某些人交际能力比较强，更容易与其他成为朋友。 根据社会网络中的这一特点，引入了节点的吸引度概念，节点的吸引度越大，该节 点就越容易被选中进行连接，调整吸引度的值之后这种模型下的网络度分布呈幂律 指数为 2~3 的幂律分布 [22] 。在进行论文写作的过程中，我们常会引用当前时间较近 的文献，而时间较久远的论文被引用的次数较少。根据上述现象 Dorogovtsev 和 Mendes 提出了一种考虑时间的DM幂律老化模型 [23] ，该模型中节点与新节点相连的 概率p 和节点的度与节点年龄的乘积 ( ) D i α τ ? 成正比关系。Bianconi 和Barabasi 提出 了适应度模型 [24] ，即重新连接时除了考虑节点度之外，还添加了节点适应度因素。 周涛、汪秉宏与中国科学技术大学严钢合作提出了随机阿波罗网络模型 [25~26] ，该模 型由于其简单性和优美性，一提出就受到了广泛的关注，不仅是物理学家，很多数 学家也研究了该绲母呶榭觯?a id="sogousnap0_17">拓扑等价类，并计算了此网络的平均距离，度度 关联强度，谱密度等特征。文章中提出的证明演化网络具有小世界效应的数学方法 华 中 科 技 大 学 硕 士 学 位 论 文 4 与近似求解簇系数的解析方法得到了广泛的应用，例如复旦大学章忠志利用类似的 方法研究了高维的确定性和随机阿波罗网络 [25~26] ，并提出名为演化阿波罗网络的新 模型 [27] 。随着人们对网络模型研究的深入，我们研究的网络的边不再只是简单地代 表节点间连接关系，每条边被赋予了权重，例如计算机网络中的带宽和交通网中的 运输能力等。所以除了上述对无权网络模型的研究外，人们开始对权重网络模型进 行研究，2004 年Barrat、Barthelemy 和Vespignani 共同提出了演化权重网络模型—— BBV 模型 [28] 。随着对真实网络认识的不断加深，复杂网络建模的研究将取得更多的 成果。 在复杂网络的第三个研究方向(复杂网络上的动力学问题)中一个重要的部分 就是复杂网络上的博弈，在复杂网络上的每一轮演化博弈中，个体与所有的邻居进 行一次博弈，根据自身与邻居的策略获得一个收益，总计获得一个累积收益。个体 下一轮按照一定的策略演化规则，根据自身与邻居的累积收益更新自己的策略。 Nowak 等人运用斑图对二维方格网络上的囚徒困境博弈进行了研究，发现二维方格 网络中的合作节点聚集成簇，在斑图中出现较大块的合作斑点抵御背叛策略 [29~30] 。 Doebeli 等人擞冒咄级远礁裢缟系难?巡?慕醒芯浚?纸醒?巡?氖? 合作节点也聚集成簇，但斑图中的合作簇较小，同时还发现空间结构的合作水平比 全混合结构的合作水平要低，抑制了合作水平 [31] 。Wang Wenxu 等人对复杂网络下基 于记忆策略选择机制的雪堆博弈进行了研究 [32] ，发现随着损益比的增加网络的合作 水平下降，而记忆长度对合作水平的影响是变化的，当记忆长度小于某个值 L 时， 记忆长度的增加有助于合作水平的提高，当记忆长度大于某个值 L 时，记忆长度的 增加对合作水平的影响很小，甚至会降低合作水平。Kim 等人对小世界网络模型的 囚徒困境博弈进行了研究 [33] ，他们发现小世界网络中的长程连接(Long-range connection)容易导致合作的突然崩溃，即网络中的合作节点快速地消失，而且合作 节点的恢复时间与稳定状态下合作节点的度相关，与长程连接的数量无关。Santos 对同质和异质小世界网络模型的囚徒困境博弈进行了研究 [34~36] ，对比同质和异质小 世界网络下的合作水平发现网络的异质性有利于提高合作比。Li Wei 等人提出了网 络拓扑和博弈动力学的共演化机制，即网络拓扑随着博弈过程变化，这里的共演化 华 中 科 技 大 学 硕 士 学 位 论 文 5 机制是在每轮博弈之后，更新节点的边。作者对这种机制下网络拓扑演化后的网络 特性进行了统计和分析，发现网络具有无标度(Scale-free)、宽标度(Broad-scale) 以及单标度(Single-scale)的特性。复杂网络上博弈论的研究越来越多地应用在生 物学、经济学、社会学等多个领域，对现实社会具有重大的意义。 1.3 论文内容和组织结构 本文主要对复杂网络上的囚徒困境博弈进行了研究，目前复杂网络上的博弈有 两个主要研究方向:一是网络拓扑结构对网络博弈动力学的影响 [5~7] ;二是网络中博 弈个体策略选择机制对博弈演化的影响 [11~13] 。本文基于这两点对复杂网络上的囚徒 困境博进行了讨论，文章由五部分组成，其组织结构如下: 第一章介绍了复杂网络上博弈的研究背景与意义，国内外在复杂网络上博弈的 研究成果，本文的工作内容和文章的组织结构。 第二章介绍了复杂网络上的博弈的两个 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 :复杂网络和博弈论。对于复杂 网络，重点介绍了用来描述复杂网络的网络参数和网络模型。复杂网络的网络参数 主要有度分布、平均路径长度和网络聚集系数。复杂网络的网络模型包括规则网络、 随机网络、小世界网络以及无标度网络。针对博弈论，主要介绍了Nash 均衡，囚徒 困境博弈和演化博弈。 第三章对复杂网络上的囚徒困境博弈进行了讨论，重点研究了复杂网络博弈的 两个内容:1、网络拓扑结构;2、网络节点的策略选择机制。针对网络拓扑结构我 们对规则网络和无标度网络进行研究，而针对策略选择机制我们对基于模仿学习 [8~13] 和基于记忆的自我学习 [14~16] 两种机制进行讨论。最后在复杂网络上提出了一种新的 动态拓扑囚徒困境博弈。 第四章对上一章所提及的复杂网络上的静态拓扑和动态拓扑囚徒困境博弈算法 进行了仿真。针对动态拓扑囚徒困境博弈算法下的度分布以及不同背叛诱惑值 T 的 合作比 c ρ 进行了统计和分析，并将其与静态拓扑博弈算法的合作水平 c ρ 进行对比和 分析。最后论证了动态拓扑下的合作水平会高于静态拓扑下的合作水平。 第五章对本文的工作进行了总结，并对复杂网络上的博弈研究进行了展望。 华 中 科 技 大 学 硕 士 学 位 论 文 6 2 复杂网络与博弈论 2.1 复杂网络 2.1.1 复杂网络概述 在我们周围存在许许多多网络系统，计算机网络、人际关系网络、神经系统网 络、交通网络、电力传输网络等等。对这些形形色色的网络系统进行研究将给我们 带来很大的启发和帮助。研究传染病在人群或牲畜中的传播网络，可以控制和减少 传染病的流行;研究电力传输网络的网络结构可以降低电力故障对全网带来的损失 提高电力系统的稳定性;研究交通运输网络的拓扑可以制定更好的交通路线带来更 高效的交通运输。社会领域、经济领域以及政治领域中的问题都需要运用复杂网络 的知识来解答。 对网络的研究源于由著名的七桥问题——在哥尼斯堡有一条河把城市分为 4 块 陆地，而 4 块陆地由 7 座桥相连接。问能否从任意一块陆地出发，只走过每一座桥 各一次，然后回到出发点, 如图2-1 所示。 图2-1 七桥问题 此后科学家运用数学的图论和统计学知识对网络进行研究，分析其网络拓扑结 构和网络上的传播动力学。一开始的网络研究只是针对规则网络，例如二维空间的 方格网络。到了 20 世纪 50 年代科学家们开始认识到网络节点间边的随机性，由此 提出了节点之间随机相连的随机网络。到20 世纪末复杂网络的研究取得了两个巨 大 的成果，第一个是1998 年，在Nature 杂志上刊登的由Watts 和Strongatz 共同发表的 《Collective Dynamics of „Small-World? Networks》，文中引入了著名的小世界网络模 型(Small-World) [2] ;第二个是1999 年在Science 上发表，由Barabasi 和Albert 共著 华 中 科 技 大 学 硕 士 学 位 论 文 7 的《Emergence of Scaling in Random Networks》，这篇文章阐述了许多复杂网络的度 分布呈幂律分布，并且建立了无标度网络模型(Scale-Free) [3] ;这两种网络模型展现 了现实复杂网络中的两种特性 [37] :1)小世界特性，即有很小的最短路径长度平均值 和很大的聚集系数;2)无标度特性，即度分布呈幂律分布。 2.1.2 复杂网络网络参数 把网络系统抽象成一种简单的模型——网络由相互连接的多个节点组成，每个 节点代表网络中的实体，节点间的边表示两个节点相关联。不同的网络拥有不一样 的统计特性，所以我们用3 个网络参数来对网络进行描述。 1) 度和度分布 节点的度就是指该节点与其他节点相连的边数。节点的度是描述网络局部特性 的基本参数。而度分布函数P(k)体现的是整个网络宏观的统计特性。 2) 平均路径长度 在一个节点数为N 的网络中，节点i 到节点j 的最短路径，即经过最少边到达节 点 j 为 ( , ) l i j ，则该节点 i 的最小路径为 min 1 1 ( ) ( , ) N j l i l i j N = = ? 。对于无向网来说 ( , ) ( , ) l i j l j i = ，在此我们讨论无向网，该网络的平均路径长度为 min 1 1 ( ) N i l l i N = = ? 。 平均最短路径 l 描述了节点之间的平均距离，同时也反映了网络的尺寸，故也称 为网络直径。 3) 聚集系数 聚集系数描述网络中节点之间相互连接的紧密程度。具体来说，若第i 个节点的 度为 i k ，那么由只与节点i 相连那些节点构成的子网(不包括节点i)的节点数为 i k ， 该子网的总边数为 ( ) E i ， i k 个节点构成的全通图的总边数为 ( 1) 2 i i k k ? ，那么该节点 i 的聚集系数为 2 ( ) ( ) ( 1) i i E i C i k k = ? ，而该网络的聚集系数为 1 1 ( ) N i C C i N = = ? 。 华 中 科 技 大 学 硕 士 学 位 论 文 8 2.1.3 复杂网络模型 1.规则网络 规则网络的节点之间按照确定的方法相互连接，常见的规则网络的所有节点度 均匀分布，例如图2-2 的二维方格网络。 图2-2 二维方格网络 规则网络的特征:平均路径较小，聚集系数较大。 2.随机网络 随机网络模型(ER 模型) [18] 的建立过程为:一个网络的节点数为N，任意一对节 点以概率p 相连接，最后生成网络的总边数为n。 若p = 1，网络的总边数为 ( 1) 2 N N ? ;若p = 0，网络总边数为0;若 (0,1) p? ， 网络总边数为 ( 1) 2 pN N n ? = 。 当网络节点数 N 很大时，随机网络的度分布函数 P(k)服从 Poisson 分布，即 ( ) (1 ) k k N k N P k C p p ? = ? 。针对连接概率p 的变化，如果p 较小，存在大量孤立节点， 网络的直径l = ?;p 增大，l 减小;p = 1，则l = 1。 随机网络随p 的变化如图2-3 所示。 华 中 科 技 大 学 硕 士 学 位 论 文 9 图2-3 连接概率p=0.1、0.3、0.8，节点数N=10 的随机网络 随机网络的特征:平均路径小、聚集系数小。 3.小世界网络 以上两种网络模型都不能很好的拟合现实的网络系统，现实的网络系统通常具 有高聚合和短平均路径长度两种特性。著名的“六度分离”理论很好地说明了现实 网络这两种特性，即每个人最多通过6 个人可以认识世界上任何人。 1998 年 Watts 和 Strongatz 提出的小世界网络模型再现了这两种特性 [2] 。小世界 模型的建立分为两步: 初始化:小世界网络中共有 N 个节点，且均匀分布在一个圆的圆周上。每 个节点与k 个节点相连，即每个节点的度为k; 随机化:网络中的每个节点以p 的概率重连，即断开原来相连的节点与其他 未与之相连的节点建立连接。不能出现重复连接和自我连接。 对重连概率 (0,1) p? ，小世界网络的变化如图2-4 所示。小世界的网络参数变化 如下: 1) 平均路径长度 当 2 p Nk ? ，即保证网络中会出现一条重连边情况下，系统的平均路径开始下降。 2) 聚集系数 令p = 0 时，聚集系数为C(0)，当p 在0~1 之间变化时C 在C(0)附近变化。 3) 度分布 当p = 0，此时是规则网络，度分布P(k)是中心点位于K=k 的δ 函数。 华 中 科 技 大 学 硕 士 学 位 论 文 10 当p = 1，此时是随机网络，度分布P(k)为Poisson 分布，P(k)在K=k 时有最大 值。 随机性增加 规则 随机 小世界 p=0 p=1 图2-4 小世界网络的变化 小世界网络的特性:平均路径长度小、聚集系数大。 4.无标度网络 在对计算机网络的研究中，人们发现该网络的节点度分布呈现幂律分布。根据 这个发现1999 年，Barabasi 和Albert 提出了无标度网络模型(BA 网络模型) [3] 。无 标度网络就是指节点度分布为幂律分布—— ( ) P k k γ ? ? ，其网络拓扑结构如图2-5 所 示。 BA 网络模型的构造算法如下: 1) 首先初始化一个节点数为n 0 的首尾相连的环形连接; 2) 每次引入一个新的节点 i，新加入的节点与原网络 m 个节点相连，节点 i 与 原网络中节点j 的连接概率为 ( , ) j j k p i j k = Σ 。该步骤重复N- n 0 次后，生成一个节点数 为N 的BA 网络。 华 中 科 技 大 学 硕 士 学 位 论 文 11 图2-5 无标度网络拓扑结构 在现实的网络演化中，生长和优先连接是决定演化的两个基本因素。无标度网 络构造过程中引入了这两个因素，在生长的过程中，网络节点的度越大，被连接的 概率越大，这样节点的度会出现马太效应 [38] ，即多的越多，少得越少。所以在一个 无标度网络中通常会存在少数度很大的超级节点。根据无标度网络的度分布特点， 对无标度网络的鲁棒性和脆弱性进行讨论。若发生随机节点故障，无标度网络具有 极高的鲁棒性;如果针对度较大的节点进行蓄意攻击，则无标度网络具有高度的脆 弱性。 无标度网络的特性:平均路径长度小、聚集系数小、节点的度分布呈幂律分布。 2.2 博弈论 2.2.1 博弈论概述 博弈论(Theory Game)也称为对策论，对博弈论通行的定义是:研究决策主体 的行为发生直接相互作用时候的决策以及这种决策的均衡问题。 博弈思想自古就存在，田忌赛马就是一个运用博弈论在竞技中获胜的事例。最 初的博弈思想仅仅停留在军事、商业、游戏竞赛等各个领域中具体案例的经验上， 并没有形成一套系统的博弈理论。1944 年，匈牙利数学家冯?诺依曼和经济学家摩根 斯坦共著的《博弈论与经济行为》标志着现代博弈论理论体系的诞生 [4] 。该著作 华 中 科 技 大 学 硕 士 学 位 论 文 12 在经济领域中对博弈理论进行了研究，并把原来的 2 方博弈推广到 n 方博弈。 随后，1950~1951 年约翰?福布斯?纳什利用不动点定理证明了均衡点的存在，即 在两人或者多人博弈情况下，对于每个个体改变博弈策略无法获得更大的收益， 这就称为纳什均衡 [39] 。随着更多的学者参与到博弈论研究之中，博弈论日趋完 善。 博弈论广泛存在于人们的社会生活和科学研究中，它无处不在。例如棋局对弈、 战争决策、网络资源的分配与控制、商业合作、生物演化的研究等等，当你根据局 势做出判断和决策时，都将运用到博弈理论。 任何一个博弈必须包括3 个要素 [40] 。 参与者(player):在博弈中可以获得利益或者损失，并且拥有决策权的主体。参 与者的集合用I 来表示，I = {1, 2, 3, …, n }。 博弈的策略空间(strategy space):参与博弈的主体可以选择的策略集合。对于 参与者i，他的策略集用S i 表示，例如他的策略有三种x, y, z，则S i = {x, y, z}。 收益函数(payoff):根据博弈结果，参与者的收益和损失。收益函数用u(s 1 , s 2 , …, s n )表示。 定义2.1 [40] 博弈表达的基本式由参与者集合I、策略空间S 和收益函数u 三个要 素组成，即G = {I, S, u}，其中I = {1, 2, 3, …, n }，S = {S 1 , S 2 , …, S n }，u = {u 1 , u 2 , …, u n }。收益函数u i :S?R，它表示第i 位参与者在不同策略组合下所得到的收益。也 可将博弈表示的基本式写作G = { S 1 , S 2 , …, S n ; u 1 , u 2 , …, u n }。 对于一场博弈来说，双方所了解的信息决定了博弈的过程。所以根据信息了解 的程度我们把博弈分为完全信息博弈和非完全信息博弈。在博弈中博弈参与者根据 自己所掌握信息进行策略的选择，如果参与者都了解所有该博弈的相关信息，则称 这样的博弈为完全信息博弈。若参与者对相关信息并不能全部获得，或是参与者保 留了自己的信息，则称这样的博弈为非完全信息博弈。由上给出有关非完全信息 博 弈和完全信息博弈的定义: 定义 2.2 [40] 如果所有参与者在给定任意策略组合下，每一个参与者的收益都是 确定的(包括期望值)，那么就是完全信息博弈。 华 中 科 技 大 学 硕 士 学 位 论 文 13 定义 2.3 40] [ 如果至少有一个参与者的收益是不确定的(不确定是指参与者主观 认为收益具有多种可能性)，那么就是非完全信息博弈。 棋经有云:宁失一子，不失一先。棋类游戏中先后手会对棋局最后的胜负有一 定的影响，在博弈中顺序也是一个重要的因素。根据博弈参与者作出决策的时间顺 序把博弈分为静态博弈和动态博弈。静态博弈是指博弈参与者同时做出策略选择， 或者不同时进行决策但是决策之前并不知道其他参与者所选的策略。动态博弈是指 在时间上博弈参与者有先后顺序地做出策略选择。 根据上面的两点，可以得到四类博弈:非完全信息动态博弈、非完全信息静态 博弈、完全信息动态博弈、完全信息静态博弈 [41] 。 博弈中一个最重要的概念就是均衡，均衡就是博弈达到稳定的一种状态，即此 时博弈参与者无法通过调整自己的策略来提高自己的收益。而以上 4 类博弈分别对 应 4 种均衡，非完全信息动态博弈对应精炼贝叶斯纳什均衡，非完全信息静态博弈 对应于贝叶斯纳什均衡，完全信息动态博弈对应于子博弈完美纳什均衡，完全信息 静态博弈对应于纳什均衡，如表2-1 所示。 表2-1 四类博弈 静态 动态 完全信息 完全信息静态博弈 纳什均衡 完全信息动态博弈 子博弈完美纳什均衡 非完全信息 非完全信息静态博弈 贝叶斯纳什均衡 非完全信息动态博弈 精炼贝叶斯纳什均衡 2.2.2 Nash 均衡 1950 年，纳什在他的博士论文《非合作博弈》中提出了著名的纳什均衡理论， 该理论为现代博弈理论和经济理论奠定了基础，纳什也因该理论对经济学领域的 突 出贡献而荣膺1994 年诺贝尔经济学奖。 在博弈过程中，每个博弈参与者都是完全理性的，即以最大化自身收益为目标， 而每个博弈参与者的收益不仅仅取决于自身的策略，还与博弈对方的策略有关。 当 华 中 科 技 大 学 硕 士 学 位 论 文 14 每个博弈参与者采取的策略组成的集合为s=(s 1 , s 2 ,…, s n )时，每个博弈参与者都不能 通过改变自己的策略来提高自身收益，那么称这种情况为纳什均衡。下面给出纳 什 均衡的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 定义。 定义2.5 [41] 在博弈G={I, S, u}中，对于所有的博弈参与者所选的策略组合中， 如果存在一个策略组合s * =(s 1 * , s 2 * ,…, s n * )，使得对某一个节点i 可选的所有策略s i 以 下不等式都成立: u(s i * , s -i * )?u(s i , s -i * ) (2.1) 那么策略组合s * =(s 1 * , s 2 * ,…, s n * )就是博弈G 的一个纳什均衡。 并不是所有的博弈都存在纳什均衡，纳什定理给出了纳什均衡存在的充分条件。 定理2.1 [40] 纳什定理 如果完全信息静态博弈G={I, S, u}是有限的，即参与者是 有限的，S 包含的纯策略也是有限的，那么一定存在纳什均衡。 纳什定理只是纳什均衡存在的充分条件，所以不符合上述条件的博弈也可能存 在纳什均衡。并且在一个博弈中有可能存在多个纳什均衡点。 2.2.3 囚徒困境博弈 囚徒困境博弈是完全信息博弈中最著名的一个例子 [41] ，囚徒困境的情景如下: 两名犯罪嫌疑人 A 和 B，涉嫌闯入民宅行窃被警察逮捕。警察将两名嫌疑人分别关 在两个不同的房间进行审问，A 和B 面对审问有两种策略:1.坦白(相关术语为“背 叛”)，2.抵赖(相关术语为“合作”)。此时会出现以下三种状况: 双方都坦白，则本着坦白从宽的原则，两人都被判刑8 年; 有一方坦白，另外一方选择抵赖，则坦白者戴罪立功被释放，而抵赖一方则被 加罚2 年，判刑10 年; 双方都抵赖，则因证据不足，双方只因私闯民宅而判2 年。 将以上的囚徒困境博弈用博弈的基本式表示为以下的形式。 根据以上的描述，此次博弈的收益矩阵如下: 1) 参与者:囚徒1 和2，I = {1, 2}; 2) 策略空间:囚徒1 策略空间S 1 等于囚徒2 的策略空间S 2 ，S 1 = S 2 =,坦白， 华 中 科 技 大 学 硕 士 学 位 论 文 15 抵赖,; 3) 收益函数:囚徒1 收益函数u 1 ，囚徒2 的收益函数u 2 ，收益矩阵如图2-6 所 示。 图2-6 囚徒困境博弈 假设每个博弈的参与者都以自己的利益最大为出发点，就以上的情景对罪犯 A 的策略进行分析，若对方B 选择抵赖，A 选择抵赖会被判刑2 年，而A 选择坦白可 以获得释放，所以A 选择坦白;若对方B 选择坦白，A 选择抵赖的话会获得10 年的 判刑，而选择也坦白则会获得8 年的较轻的刑罚，所以A 也会选择坦白。综上所述， 在得知无论 B 选择哪种策略，A 都会选择坦白，这种两人都选择坦白的情况，就是 纳什均衡。而对于整体而言，两人都选择抵赖，才是帕雷托最优。所以仅从个人的 理性出发得到的策略对于整体而言并不是最好的，纳什均衡与帕雷托最优是相互矛 盾的。 根据以上描述给出通用的囚徒困境的模型，博弈中两个人同时进行决策，选择 两种策略合作或者欺骗中的一种与对方进行博弈。对于这两种策略每个人所获得的 收益用式(2.1)所示的矩阵标识。若双方都选择合作(Cooperation, C)，两人所得的收 益为 R;双方都选择背叛(Defection，D)，两人所得的收益为 P;若一方选择合作 (Cooperation, C)另一方选择欺骗(Defection，D)，则合作方获得的收益为S，欺 骗方获得的收益为T。并且以上的收益满足条件:T > R > P > S，2R > T + S。囚徒困 境博弈中各个参数如表2-2 所示。囚徒困境广泛适用于现实世界中的各种现象，在政 治军事、商业竞争、以及生物的群体行为中都可以找到符合囚徒困境的例子。 华 中 科 技 大 学 硕 士 学 位 论 文 16 C D C R S A D T P ? ? = ? ? ? ? (2.1) 表2-2 囚徒困境博弈的参数说明 符号 英文 中文(非术语) 解释