文档介绍：上海交通大学
博士学位论文
复杂网络上的演化博弈与机制设计研究
姓名:荣智海
申请学位级别:博士
专业:控制理论与控制工程
指导教师:汪小帆;李翔
20080901
复杂网络上的演化博弈与机制设计研究摘要上海交通大学博士学位论文复杂网络理论是近年来复杂系统科学研究中最活跃的分支之一。大量实证性研究表明,许多真实网络热缫蛱赝蛭⒌缌ν⑸锿⑸缁岷献网等等哂行矶嘞嗨频慕峁固匦裕缧∈澜绾或薇甓忍匦浴4送猓煌型的无标度网络常常表现明显的度相关性:社会合作网络中的中心节点倾向于相互连接,表现同配度混合模式:而技术网络和生物网络中的中心节点倾向于选择小度节点作为邻居,呈现异配度混合模式。这些网络结构特性对于运行其上的动力学行为有着重要影响。关系。而机制设计殖莆D娌┺睦砺关注于设计合理的协议,引导个体的自私行为使系统的全局目标达得最优。机制设计近期被应用于网络路由协议设计中,可以把超付作为一种结构特性研究。度相关特性对网络演化博弈行为的作用,以及小世界网络和无标度网络中的超付特性,主要内容和研究成果如下:从个体动态组织角度,本文首先研究了小世界网络中的合作行为。研究表明在节点具有相同度的随机正则网络中,对于囚徒困境博弈,交换边概率的增加促进了网络中合作行为的涌现,这是由于个体通过结成大的合作簇有效抵御背叛者的入侵所致:然而对于雪堆博奔,由于合作者很难形成大的合作簇,所以当损益比超过一定阈值后随机正则网络中的合作频率低于均匀混合状态的均衡频率。而对于猄疛澜缤缒P停ü婊亓剖筗网络的度分布变得异质,网络中的合作水平得到了有效提升。研究竞争个体之间的合作涌现机制一直是经济、生物乃至信息领域学者关心的问题,博弈理论为此提供了一个理论框架。网络演化博弈把个体看作节点,个体之间的联系通过网络的边描述,研究网络结构与策略演化之间的相互作用本文重点探讨复杂网络上的演化博弈和超付特性,包括小世界、无标度和
上海交通大学博士学位论文基于一个扩展的雪堆博弈,本文进一步研究了可调度异质性的无标度网络上的合作行为。研究表明越异质的无标度网络具有越高的合作水平。这是由于具有大度的中心节点在稳定状态坚持合作策略,随着异质性的提高,中心节点可以带动更多的邻居成为合作者,促使了无标度网络中稳定策略个体的涌现。本文还研究了度相关性对网络博弈行为的影响。研究发现不论对于囚徒困境博弈还是雪堆博弈,由于同配网络的中心节点倾向于相互相连,减弱了合作中心节点之间的相持能力,使背叛者容易入侵中心节点;然而在异配网络中,中心节点之间沟通的减弱使它们更容易坚持初始策略不变,所以合作行为不容通过研究小世界网络中的超付特性,本文发现小世界网络中的平均超付高于最近邻网络和完全随机网络,这是由于小世界网络中的长程边拥有过高的超付。因此,通过在原始长程边附近移入新的长程边,可以有效减小长最后,本文研究了可调度异质性的无标度网络中的节点超付分布。研究表明节点超付与度之间呈现幂律关系,随着异质性的增加,。在度指数小于奈薇甓韧缰薪诘愠兜姆植家彩敲萋傻摹Mü呀诘闶杖的超付除以它传递数据包的数目,可以得到传递每个数据包的平均收益。仿真表明异质网络的中心节点的每包平均收益高于小度节点的收益,而随着网络变得均质,大度与小度节点之间的每包平均收益的差异是减小的。关键词:演化博弈,机制设计,小世界网络,无标度网络,度混合模式易在异配网络中湮灭。程边的超付。Ⅱ
上海交通大学博士学位论文,.,琾琣琤,甀—,琤,瑂獁瓸,猣:·瑆琤.,甇,—痓瑆獁,猣
.甌,上海交通大学博士学位论文,,.甒甅猄琣痙獁,痜瑃瑆,.’·【—,瓾
.瑆上海交通大学博士学位论文甒,篹獁猟、斩,—琩..甌猣甇畇,
上海交通大学学位论文原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名:日期:珂菽辍月
日期懈年谌学位论文作者签名:荣留诲学位论文版权使用授权书上海交通大学不保密瓯本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口,在年解密后适用本授权书。本学位论文属于朐谝陨戏娇蚰诖颉”指导教师签名:日期:畂寄辏聑
第一章绪论引言的“随机网络中标度的涌现’’一文中指出许多网络系统具有无标度特性——它们上海交通大学博士学位