（计算机应用技术专业论文）基于社会网络和博弈论的合作理论研究.pdf

摘要中国科学技术大学博士学位论文 摘要 本文工作将合作理论、博弈理论、复杂网络理论和人工免疫系统相结合，针 对目前人类合作研究的不足以及当代社会出现的最新博弈及合作利他行为，提出 了网络重复博弈模型，并在此模型框架内，研究博弈策略演化问题和网络结构演 化问题，对合作理论和方法、合作策略演化以及网络演化问题作出了创新性的研 究。 人类之间的合作和利他机制在维持社会稳定，促进社会进步方面具有重要作 用，有征据表明在原始部落和现代社会均存在高级形式的合作现象。人类合作利 他行为的范围和深度为所有其他动物所无法比拟，因此人类合作利他为何能够发 生并得以维持自然成为人类认识自身的一个重要课题。 目前研究表明，网络结构对合作的产生和维持具有一定影响，在合作者之间 形成的群体结构有助于抵制背叛者的入侵，从而对合作加以维持。本文重点研究 宏观网络结构与微观博弈的相互影响，包括静态网络结构对博弈策略的演化影 响，以及利用微观博弈结果调节社会网络结构。 本篇论文的主要工作和创新点有： l 、提出了网络重复博弈模型，该模型扩展了已有重复博弈模型，考虑社会 网络结构与微观博弈的相互影响，同时引入随机博弈的特征，体现了当代社会的 博弈新特征，从而对人类合作问题加以研究。该模型是目前工作未曾深入研究的， 丰富了合作理论和博弈理论，是本文的研究基础和主要贡献。 2 、针对本文提出的网络重复博弈模型，设计完成了完全网络下的博弈策略 计算机模拟竞赛。目的是测试人为设计的各种经典博弈策略( 如t i t f o r t a t 等) 在竞赛中的胜负情况，实验结果表明，在社会网络中即使人们之间不太会有长期 博弈，而较多采取o n e s h o t 博弈，背叛依然不是人们的首选策略。 3 、在网络重复博弈模型框架下，利用抗体浓度调节机制，提出了博弈策略 演化模型和具体算法。本文在三种静态复杂网络环境下对博弈策略的涌现加以研 究，分析了策略涌现的具体特征和影响因素，对策略演化趋势给出了定性分析。 在三种静态复杂网络l 辛的数值实验结果表明，在本文模型中，给定一定的环境约 第1 页 摘要 中国科学技术大学博士学位论文 束条件，合作及利他能够自发地演化出来并得以保持。这是本文的创新点之一。 4 、本文对网络重复博弈模型下博奔群体内部的复杂网络结构的形成和演化 加以研究，提出了网络与策略协同演化模型，扩展了偏好连接思想，主要研究微 观博弈对宏观网络结构的影响，对社会网络形成的原因从博弈角度给出了新的解 释，数值模拟结果表明本文模型能够生成满足符合真实特征的小世界网络。同时， 策略演化结果表明合作能够涌现和维持。本文的研究对社会网络的形成机制做出 了扩展和提高，指出个体之间的博弈策略及博弈结果可能是社会网络形成的重要 原因。 5 、本文以网络重复博弈模型创新性地将合作理论、博弈理论、复杂网络理 论和人一【_ ：免疫理论相结合，以博弈论为理论工具，以人工免疫机制为具体方法， 研究社会网络中的人类合作演化问题，成为社会学、经济学、物理学和计算机科 学的交叉研究。本文的研究在丰富合作理论和博弈理论的同时，扩展了人工免疫 系统的应用领域，这也是本文的创新点。 综上所述，首先，本文工作针对当前研究的不足，引入复杂网络理论和博弈 新特征，基于合作理论和博弈理论提出网络重复博弈模型研究人类合作问题，取 得较好成果，丰富和扩展了合作理论；其次，结合人工免疫理论，分析了该模型 的策略涌现机制，对合作问题给出自己的解答，同时扩展了人工免疫理论的应用 领域；最后，本文扩展了偏好连接思想，提出了网络和策略协同演化模型，研究 博弈策略对网络结构的形成机制，结果说明本文模型生成的网络结构符合真实网 络的统计特征，从而对复杂网络理论也是较好的补充和提高。本论文工作具有较 好的创新性，覆盖面广，对已有研究的不足之处做出了较好的研究，将带来更多 研究课题和进一步的成果。 第【i 负 a b s t r a c t中国科学技术大学博士学位论文 a b s t r a c t b a s e do nc o o p e r a t i o nt h e o r y ，g a m et h e o r y ，c o m p l e xn e t w o r kt h e o r ya n d a r t i f ic i a li m m u n es y s t e m ，t h i st h e s i sp r o p o s e san o v e li t e r a t e dg a m em o d e l o nn e t w o r k s ( i g n ) ，w h i c ha i m st om a k eu pt h ei n s u f f i c i e n c yo fh u m a n c o o p e r a t i o nr e s e a r c ha n dt os u i tt h en e wg a m ea n dc o o p e r a t i o nb e h a v i o r s i nm o d e r ns o c i e t y i nt h isf r a m e ，t h i st h e s i sc o n c e n t r a t e so nt h e e v o l u t i o no fs t r a t e g i e sa l o n gw i t he v o l u t i o no fn e t w o r ks t r u c t u r e sa n d o b t a i n si n n o v a r o t yp r o d u c t i o n t h em e c h a n i s m so fh u m a nc o o p e r a t i o na n da l t r u i s mc o n t r i b u t eg r e a t l y t om a i n t a i n i n gt h es t a b i l i z a t i o na n dp r o m o t i n gt h ep r o g r e s so fo u rs o c i e t y m a n ye v i d e n c e ss h o wt h a tc o o p e r a t i o nd o e se x i s tb o t hi nm o d e r ns o c i e t i e s a n dp r i r e a lt r i b e s ag r e a td i f f e r e n c eb e t w e e nh u m a nb e i n ga n do t h e r a n i m a l si st h a t ，t h er a n g ea n dd e p t ho fh u m a nc o o p e r a t i o ne x c e e dag r e a t l o tt h a na 1 1o t h e ra n i m a l s t h u s ，w h ya n dh o wh u m a nc o o p e r a t i o nc o u l da r i s e a n dm a i n t a i nb e c o m e sav e r yi m p o r t a n tr e s e a r c ht o p i cb yw h i c hh u m a nc a n u n d e r s t a n da n dc o m p r e h e n di t s e l fs i n c el o n gl o n ga g o c u r r e n tr e s e a r c hm a k e sc l e a rt h a ts o c i a ln e t w o r ks t r u c t u r e sa f f e c t t h ee m e r g e n c ea n dm a i n t a i n a n c eo fh u m a nc o o p e r a t i o ni nac e r t a i ne x t e n t a n dt h ec l u s t e r sc o n s i s t i n go fc o o p e r a t o r sh e l pt or e s i s tt h ei n t r u s i o n o fd e f e c t o r s t h er e s e a r c hc o n t e n to ft h ist h e s i sisi nt h ef r a m e w o r ko f r e c i p r o c a la l t r u i s ma n dc o n c e n t r a t eo n t h em u t u a li n f l u e n c eo fg a m e s t r a t e g i e sa n dn e t w o r k ss t r u c t u r e sw h i c hh a sd o n ei m p o r t a n te x t e n s i o na n d i m p r o v e m e n tt oc u r r e n tr e s e a r c hw o r k t h em a i nw o r ka n ds i g n i f i c a n c e so f t h i st h e s i si n c l u d e s ： ( 1 ) t h ei g ni sp r o p o s e dw h i c hi sa ni m p o r t a n te x t e n s i o na n d i m p r o v e m e n tf o rc u r r e n tw o r ka n dg a m em o d e l s t h i sg a m em o d e lc o n s i d e r s t h em u t u a li m p a c to fm a c r o s c o p i c a ls o c i a ln e t w o r ks t r u c t u r e sa n d m i c r o c o s m i cg a m e sa n dt h er a n d o m i c i t yi ng a m ei n t e r a c t i o n si np o p u l a t i o n s w h i c he m b o d yt h en e wp r o p e r t i e so fg a m i n gd u et ot h eq u i c kd e v e l o p m e n t 搪1 1 i 吡 中国科学技术大学博士学位论文 o ft h et e c h n o l o g ya n ds y s t e mo ft r a n s p o r t a t i o n ，i n f o r m a t i o na n dc o m p u t e r n e t w o r k s t h er e s e a r c hc o n t e n to ft h i sm o d e lh a sn o tb e e nf u l l yn o f i i c e d o rs t u d ie d w e “n is ht h et h e o r e t i c a lp r o o ft h a tt h ef o l kt h e o r e misa ls o t e n a b l ei nt h eg a m em o d e lp r o p o s e dw h i c he x p l a i n st h ep o s s i b i l i t yo fh u m a n c o o p e r a t i o nu n d e rt h i sg a m em o d e l t h i sm o d e le n r i c h e st h ec o o p e r a t i o n t h e o r ya n de v o l u t i o n a r yg a m et h e o r ya n db e c o m e st h ef o u n d a t i o na n dm a i n c o n t r i b u t i o no ft h i st h e s i s ( 2 ) b a s e do ni g n ，t h i st h e s i sd e s i g n sa n df i n i s h e st h ec o m p u t e r t o u r n a m e n ti nw e l l 一m i x e dp o p u l a t i o n sf o rg a m es t r a t e g i e st oo b t a i nt h e r e s u l to fv i c t o r yo rd e f e a to fm a n yc l a s s i c a lg a m es t r a t e g i e sp l a n n e db y r e s e a r c h e r s t h er e s u l to b t a i n e di sd i f f e r e n tw i t ho t h e rr e s e a r c h e r s a n dh a sb e e na n a l y z e da n dc o m p a r e dw i t ho t h e rr e s u l t s ( ： ) w ea r ea m o n gt h ef i r s tt oe x p l a i nt h es t r a t e g ye v o l u t i o no ns o t i a l n e t w o r k s i nt h ef r a m e w o r ko fi g n ，w ep r o p o s eag a m es t r a t e g i e s e v o l u t i o n a r ya l g e r i t h mu s i n ga n t i b o d yr e g u l a t i o nm e c h a n i s m o nt h r e e s t a t i cn e t w o r k s ( w e l lm i x e dp o p u l a t i o n ，s c a e - f r e en e t w o r k sa n ds m a l l w o r l dn e t w o r k s ) ，w ef i n dt h a tg a m es t r a t e g yw i t hc e r t a i np r o p e r t i e sw i l l a l le v o l v ea n de m e r g es p o n t a n e o u s i fa n dt h ee m e r g e n c ei sc l o s e l y c o r r e l a t e dw i t ht h ee n v i r o n m e n t a lf a c t o r s t h eq u a i t a t i v ea n a l y s i so f e v o l u t i o n a r yt r e n di sa l s op r e s e n t e d t h i si so n eo ft h ei n n o v a t i o np o i n t s o ft h i st h e s i s ( 4 ) t h ec o e v o h t i o nm o d e lo fg a m es t r a t e g ya n dn e t w o r ks t r u c t u r e i sp r o p o s e dw i t ht h ee x t e n s i o no f p r e f e r e c i a la t t a c h m e n tm e c h a n i s mt o s t u d yt h et h ei n f l u e n c eo fm i c r o c o s m i cg a m e s o nm a c r o c o s m i cn e t w o r k s t r u c t u r e t h u sag o o de x p l a i n a t i o nt os o c i a ln e t w o r kf o r m a t i o ni sp u t f o r w a r da n dt h en u m e r i c a lr e s u l t ss h o wt h a ts m a l l - w o r l dn e t w o r k sc a nb e e v o v e du s i n gt h em o d e lp r o p o s e d t h er e s e a r c hi m p r o v e st h ef o r m a t i o n t h e o r yo fs o c i a ln e t w o r k sa n di n d i c a t e st h a tg a m ei n t e r a c t i o n sb e t w e e n i n d i v i d u a l sm i g h tb et h ei m p o r t a n tr e a s o no rm e c h a n i s m 第l v 负 a b s t r a c t中国科学技术大学博士学位论文 ( 5 ) t h i st h e m sc o m b i n e st h ec o o p e r a t i o nt h e o r y ，g a m et h e o r y ，c o m p l e x n e t w o r k st h e o r ya n da r t i f i c i a li m m u n et h e o r yt op r o p o s et h ei g na n ds t u d y t h ee v o l u t i o no fs t r a t e g i e sa n dn e t w o r ks t r u c t u r e s t a k i n gt h eg a m et h e o r y a st h e o r e t i c a lt o o a n dt h ei m m u n em e c h a n i s ma sp r a c t i c a lm e t h o d s ，t h e h u m u nc o o p e r “i o njss tu d ic d7 i h i sr e s e a r c hc o n t r i b u t e sp r e f e r a b l yt o c o o p e r a t i o nt h e o r ya n dg a m et h e o r yw h i c hi sa l s ot h ei n n o v a t i o np o i n t i ns u m m a r y ，t h i st h e s i sc o n t r i b u t e si nt h r e ea s p e c t s ：f i r s t ，n o v e l m o d e li sp r o p o s e dt os o l v ep r o b l e m si n s p i r e db yt h eo b s e r v a t i o nt or e a l w o r l dp h e n o m e n ai ns o c i a ln e t w o r k s ，w h i c hi sp r o v e dt ob eag o o da n d e f f i c i e n tm o d e lt os t a n df o rp r a c t i c a lg a m e s t h i sw o r k e n r i c h e st h e c o o p e r a t i o nt h e o r ya n dg a m et h e o r y ；s e c o n d l y ，i te x p l o r e st h em e c h a n i s m o fc o o p e r a t i o ne m e r g e n c ea n dt h ei m p a c to fe n v i r o n m e n tu s i n ga r t if i c i a l i m m u n em e t h o d s ：a tl a s t ，t h ep r e f e r e c i a la t t a c h m e n ti d e ai se x t e n d e da n d t h ee v oju t i o na l g o r i t h mo fn e t w o r ks t r u c t u r ei sp r o p o s e dt os t u d yt h e n e t w o r kf o r m a t i or m e c h a n i s m c o m p u t e rs i m u f a t i o ns u s t a i o st h et h e o r y p r o p o s e da n ds m a l lw o r l dn e t w o r k sc a ne m e r g ef r o mi n i t i a l l yb l a n kn e t w o r k t h i st h e s i sisc r e a t i v ea n dc o v e r i n gt h em o s ta d v a n c e dt h e o r i e sa n dh a s b e e ni nt h ef r o n to ft h er e s e a r c ho nh u m a nc o o p e r a t i o n i tw i l lb r i n gn e w t o p i c sa n dg e tf u r t h e ri m p r o v e m e n t si n t h ef u t u r e 第v 页 盟_ l j l 型赴一 生旦丑坐垫盔走兰煎土堂丝迨童 第1 章绪论 生性残忍的动物总是受各种各样的本能和习性的引诱与驱使，我们 人类也概莫能外但事实是，人类按照一定的规则组织起来，谴责虚伪， 制止犯罪，维护公正，给人恩惠，与人为善。 一约瑟夫巳特勒 美德的本性，17 3 7 年 本篇论文研究分为两大部分，其一是将社会网络的影响和博弃新特征引入重 复博弈模型，提出网络重复搏弈模型，主要研究宏观网络结构和微观交互博弈的 相互影响；其二是针对模型给出理论分析，并借鉴人工免疫机制研究策略演化和 网络演化问题，采用基于主体的计算机模拟技术，完成了数值实验，对人类合作 问题给出研究和解答。 本章将首先介绍和人类合作研究密切相关的研究背景，基本概念，主要理论 和研究现状，通过分析当前研究的热点及存在问题，阐述本文的研究目标和思路， 介绍本文研究的主要贡献和创新之处。在本章最后，给出本论文的组织与章节安 排。 1 1 研究背景 众所周知，人类之间的合作在历史发展的不同阶段均具有重要作用，对人类 社会的发展具有直接影响，因此研究人类合作研究具有重大的理论意义和实践意 义。在人类漫长的进化历史中，最初的合作秩序通过自然选择建立，即自然选择 的压力迫使人类进化出有利于合作的偏好；随着人类生产能力的提高，自然施加 于人类的选择压力开始减轻，人类的生存能力逐渐提高，合作秩序不得不通过其 他手段来维护；现代社会的分工使人类合作的规模达到前所未有的程度，使得合 作秩序的维护必须依赖一个建立在民主基础上的现代司法制度。 人类学家、社会学家、经济学家、生理学家、心理学家和哲学家等通过不懈 努力，一直都在尝试从各种不同的学科角度对人类台作问题给出解释，提出相应 的理论和学说。目前人类合作研究主要有三种角度，即经济学角度、心理学角度 和生物学角度。从古典经济学、新古典经济学到新制度经济学，经济学研究的主 第1 页 釜! 童绪逵生国猎生擅丕盘堂丝堂鱼造皇 要任务是资源利用，收入分配和制度分析，这其中必然涉及到人类之间合作的研 究。近年来在经济学范畴内，基于博弈论的研究方法愈加受到重视，并已经得到 了许多有价值的研究成果。 人类社会和动物世界的不同集中体现于在人类大规模群体中实现了劳动分 工和遗传上无关的人类之间的合作。针对目前的三种利他类型( 亲缘利他、互惠 利他和纯粹利他) ，研究人员从不同角度进行了大量研究，提出了各种观点。关 于合作和利他的论文不断发表在主流科学杂志 p s ： ( 2 ) r s + t 。 2 针对图2 3 的具体实例通过重复严格优势的剔除过程可知，双方都将选择坦 白，即背叛，各自获得收益1 ，而不是对双方同时更有利的不坦白，即合作，各 自获得收益3 。可以看出，囚徒困境对经济人理性假说提出了重要挑战，因为在 个人完全理性的选择之下，在总体上却出现了无效率。 2 1 3 纳什均衡 如果博弈可以通过重复严格优势获得唯一解则最好，但是许多i 尊弈不能这样 进行求解。与之相反，纳什均衡解的概念具有在广泛类型的博弈中均存在的优点。 纳什均衡以美国普林斯顿大学的数学家和统计学家约翰纳什命名，在非合作博 弈论和经济分析里所应用的博弈论思想中，纳什均衡都处于核心地位。 定义1 1 混合策略组合盯是一种纳什均衡，如果对于所有局中人i 有 吩p l 盯：j u s ，盯：j ，s ，s ， 纯策略纳什均衡是满足同样条件的纯策略组合。如果一种纳什均衡中每个局 中人具有对对手策略的唯一最优反应，则称此纳什均衡为严格的 5 7 。 纳什均衡隐含着一个l j u 提假定，即局中人对博弈结构有充分了解，拥有完全 信息。在纯策略中，纳什均衡是指这样一种策略分布：假使其他局中人不变换其 策略，则任何一个局中人都不能通过单方面变换自己的策略来增加其效用。纳什 还证明，在一个有限局中人和行动的博弈中，至少总存在一个纳什均衡。这里的 纳什均衡策略必须包括混合策略，因为存在着没有纯策略均衡的博弈。 纳什均衡刻画了人们理性选择的结果：利益冲突达到一种稳态以至无人会单 方面加以改变。纳什均衡并未对这一结果做出福利上即总体上优与劣的判断，于 第1 8 页 噩2 重担羞理论塑趣垒 虫国型堂撞苤太堂熊堂焦诠童 是由于人们的不合作可能使得每个人都达不到可能的最大收益。囚徒困境就是明 显例证，其中唯一的纳什均衡是双方均背叛，因为在其它策略组合下均有一方能 因改变策略而获益，但是其帕累托最优是双方均不背叛。这表明，帕累托最优并 不一定能在纳什均衡点上实现。也即，在存在利益冲突的情况下，利己主义个人 雎陆选择的结果在总体 ：可能并不是最有效的。这就对经济学中的完全理性人假 设提出了重大挑战，市场经济会达到或者趋向帕累托最优这一结论在引入利益冲 突后有可能无法成立。个人利己的理性选择并不能保证人们的处境都得到改善。 就此而言，纳什均衡揭示了利己理性的弱点。在人人求得白利的同时，如何防止 对一切人均不利的结果出现，这已成为今天博弈论和经济学中研究的热点问题。 许多博弈具有多个纳什均衡，如图2 4 为“性别大战”博弈的收益矩阵： 妻子 f o o t b a ll 丈夫 b a l l e t b a l l e tf o o t b a l l 0 ，0 2 ，1 1 ， 2 0 ，o 图2 4 性别大战博弈的收益矩阵 在“性别大战”博弈中，丈夫和妻子要决定周末进行何种活动。丈夫喜欢看 足球比赛，妻子喜欢欣赏芭蕾。此博弈具有2 个纳什均衡，即两人都去看足球比 赛，或者都去看芭蕾表演。但是博弈结果到底应该是哪一个，纳什均衡概念并没 有给出明确的结果。 2 1 4 重复博弈和民间定理 重复博弈是目前人们了解得最为透彻的一类博弈，局中人每一期都面对同样 的策略博弈，而且局中人的全部收益是每阶段所得收益的加权平均。重复博弈可 以看成是对经济和政治科学中某些长期关系的一个很好的近似。重复选择之所以 能引入新的均衡博弈结果，是因为局中人的选择依赖于他们在之前阶段获得的信 息。 重复博弈分为无限期重复博弈和有限期重复博弈。对于有限期重复博弈，可 以用逆向归纳法来解，但此方法不能用于无限期模型。 第1 9 页 簋2 童担差堡迨蛰监垒 生国魁堂董盔盍堂堂堂焦迨塞 重复博弈的经典假设是每一期同一个固定集合中的局中人彼此博弈，对此稍 加改变，可得到重复博弈的几个变型，如包含长期和短期局中人的重复博弈，局 中人世代交替的博弈，r o s e n t h a l 和l a n d a u 完成的对手随机匹配的博弈 5 6 。 更一般的，r o s e n t h a l 说明除非贴现因子取临界值，囚徒困境唯一的马尔科夫均 衡就是所有的局中人都要在第一期背叛 5 8 ，5 9 。另一个重复博弈模型的变型假 定存在沟一多局中人，设为n 个。每个局中人博弈无限次，但是在每一期面对不同 的对手。更准确地晚，一个两人参加的阶段博弈，假定存在编号为l 和2 的两个 局中人群，各有n 人。每一期，每个局中人1 和一个局中人2 相匹配进行博弈。 匹配个特定局中人2 的概率是1 n ，且每阶段的匹配是独立的。此类模型可用 来解释为什么交易者会诚实行为，即便他们几乎不可能在将来再遇到彼此 6 0 ，6 1 。 无限重复博弈的“民间定理”( f o l kt h e o r e m ) 认为，如果局中人有足够的 耐心，那么任何可行的个人理性收益都能在均衡中得以实施。于是，如果局中人 极端有耐心的话，重复选择实质上允许任何收益都能成为均衡的博弈结果。该定 珲刈人类合作研究具有重要意义，该定理说明，虽然对囚徒困境博弈来说，背叛 是双方的理性选择和唯一的纳什均衡，但当该博弈重复进行时，就可能出现其他 的均衡结果，于是合作的可能性相应出现。 重复博弈的民间定理之所以称之为“民间定理”是因为重复博弈促进合作的 思想，早就有很多人提出，以致无法追溯到其原创者，于是早在被文字记录之前， 它就已经是口头相传的传统博弈论的一部分。 重复博弈引进了许多新的均衡点，其中有不少均衡点可以实现合作。民间 定理说明了行为规则的多样性：有无穷多种行为规则可以支持合作行为。在正常 的均衡状态中，可观察到的行为可以完全相同，即博弈双方相互合作。但其背后 的行为规则却可能大不相同。 2 1 5 演化博弈 演化博弈论( e v o l u t i o n a r yg a m et h e o r y ) 有两个理论来源，一个是演化理 论，另一个是博弈理论，而传统博弈论研究完全理性的人类互动行为。梅纳德史 密斯( m a y n a r ds m i t h ) 在1 9 7 3 年提出了著名的演化稳定策略( e s s ，e v o l u t i o n a r y 第2 0 页 簋2 重担羞堡造麴越叁 主国型堂越查盔堂撞堂焦迨童 s t a b l es t r a t e g y ) ，奠定了演化经济学的基础 1 4 。近年来演化博弈论最重要的 进展是随机稳定概念( s s ) ，这是杨( p y o u n g ) 和福斯特( f o s t e r ) 的贡献 6 2 。 演化稳定策略只能抵御初始的冲击，它保证这个策略比其他策略都占优。但若在 演化博弈过程中发生了冲击，则演化稳定策略就无能为力，它不能保证必然导向 预计的稳定点。随机稳定策略则可避免此种情况。只要保证每次转移矩阵不变， 不管中间发生了多少次冲击，整个博弈都能向均衡点收敛。随机稳定策略被广泛 运用r 制度分析中，因为制度变迁的过程正是一个不断冲击，不断相互作用的过 程。演化理论从生物进化论而来，而重复博弈就是学习的过程，这两种理论的融 合将是演化博弈论发展的方向。 博弈论作为一种有力的数学分析手段，在经济学和社会学中有着广泛的应用 前景。博弈、合作与经济制度紧密相联，诺斯认为对经济制度的研究实质上就是 对合作的机制的研究。近年来经济学的一系列突出成就和最新进展越来越集中地 表现出人们对经济行为主体认识的深化。作为洞察主体行为规律和分析经济现象 背后机制形成的认识工具，博弈论在研究变革社会的秩序演进与制度创新方面应 用潜力陋人。 在人类合作研究领域也出现了很多博弈模型，特别是重复博弈模型，但是这 些模型未能关注现代社会出现的新的博弈现象和特征，这些特征主要表现在社会 网络的影响，博弈规模，博弈匹配概率等方面，本文研究主要针对这些不足，在 博弈理论方面提出了网络重复博弈模型，能够更好的体现这些特征，从而研究这 些博弈的合作行为和规律。 2 2 复杂网络理论 近年来人类合作研究和复杂网络r 益紧密结合，由于复杂网络理论的引入， 人类合作研究出现了新的理论和方向。本文研究同样和复杂网络理论结合，因此 在本节将简要介绍复杂网络理论中和本文研究相关的重要知识。 自2 0 世纪9 0 年代以来，复杂网络研究方兴未艾，各种理论模型层出不穷。 关于网络的研究可以上溯到欧拉( e u l e r ) 对哥尼斯堡七桥问题的研究，之后图 论以及网络理论的研究在2 0 世纪成为自然科学的重要部分。社会科学同样对网 第2 1 丽 篓! 童担羞型迨扭地笪生国懿主蕉丕态芏监茎僮诠毫 络加以关注，其研究的典型问题包括社会网络的集中性( c e n t r a l i t y ) 和连通性 ( c o n n e c t i v i t y ) 。近年来网络研究的重大发展表现在研究重点由单个小网络的 分析转移到对大规模网络的统计特征，这一转变很大程度上依赖于计算机和通信 网络的迅速发展，使得收集和分析大规模网络数据成为可能。过去研究者常常研 究几十或几百个节点的网络，现在则是百万甚至数十亿个节点。这种转变也迫使 原先的解析方法加以改变，很多针对原来小网络的问题对于大规模网络已意义不 大。 2 2 1 基本概念 复杂网络理论和图论密切相关，其中的很多概念和方法都来自于图论，下面 先介绍网络的基本概念。 l ，节点( n o d e v e r t e x ) ：网络的基本单元。在不同网络中有其实际意义， 如在计算机网络中可表示路由器，在社会网络中代表个人，在铁路网络 中代表站点等。 2 ，边( e d g e l i n k ) ：连接两个节点的线段。在复杂网络中，边被视为节点 之间的联系或关系。 3 ，有i t 无向( d i r e c t e d u n d i r e c t e d ) ：如果边只向一方行进，则称该边为 有向边：如果允许双向行进，则称为无向边。如果所有边均为有向，则 称该网络为有向网络，否则称为无向网络。 4 ，度( d e g r e e ) ：连接到某个节点的边的数目称为该节点的度。对于有向图， 度分为出度( o u t d e g r e e ) 和入度( i n d e g r e e ) ，二者可能不等；对于 无向图，其出度和入度相同。 5 ，最短路径( s h o r t e s tp a t h ) ：指网络中任意两个节点之间的最短路径。 而网络中所有节点的最短路径的平均值则称为网络的最短路径。 6 ，尺度( d i a m e t e r ) ：指网络中任意两个节点之间的最长的最短路径的连接 数。也有研究者认为尺度指网络中的平均最长最短路径。 7 ，簇系数( c l u s t e rc o e f f i c i e n t ) ：对于某个节点，其簇系数定义为它所 有邻接点之间的实际连接数目与可能连接数目的比例。而网络的簇系数 则是所有节点的簇系数的平均值。形象化表述为，你的朋友的朋友之间 第2 2 暇 塑! 望翅筮型堡塑趣垒 主固磅堂熊盔厶生撼： ：生焦论塞 也有很大可能是朋友。 2 2 2 网络分类 复杂网络可以分为四种，社会网络，信, g n n ，技术网络和生物网络。在现 实世界中分别有很多实例，下面逐一介绍。 1 ，社会网络( s o c i a ln e t w o r k s ) ： 社会网络由人类社会中的人群集合作为节点集，他们之间的联系或交互 作为边而形成的网络，人与人之间的联系或交互多种多样，研究人员研究过 诸如友谊( f r i e n d s h i p ) 6 3 ，6 4 、商业关系( b u s i n e s sr e l a t i o n ) 6 5 ， 6 6 、联姻关系( i n t e r m a r r i a g e ) 6 7 、演员合作关系 6 8 ，6 9 ，7 0 ，7 1 ， 电话联系 7 2 ，7 3 、e m a i l 关系 7 4 。 社会网络中著名的“小世界”特征由m i i g r a i n 等完成 7 5 ，7 6 。“小世界” 特征指出，尽管现实世界很大，个体很多，但是，任意两个个体之间存在较 小的连通路径。该实验成为“六度分离”概念的源头。 2 ，信息网络( i n f o r m a t i o nn e t w o r k s ) 信息网络也称为“知识网络”，经典的例子是科学论文引用网络 7 7 。该 网络描述如下：学术论文总是引用前人的相关工作，这些引用就形成了网络， 其中，论文为节点，论文a 到b 若存在有向边，则表示a 引用了b 。于是， 引用网络的结构反映了存储在节点中的信息结构，这就是“信息网络”称呼 的由来。p r i c e 首先指出，引用网络的入度和出度均服从幂率分布( p o w e rl a w d e g r e ed i s t r i b u t i o n ) 7 8 ( 后面将详细介绍该分布) 。 另外一个重要的信息网络是w o r l dw i d ew e b 7 9 ，在该网络中，页面 ( p a g e ) 为节点，页面之间的超链接( h y p e r l i n k ) 为边。需要指出，w w w 和 i n t e r n e t 有区别，后者是大量计算机通过光纤或其他链接介质连通的物理网 络。w w w 的入度和出度同样都具有幂率分布。 3 ，技术网络( t e c h n o l o g i c a ln e t w o r k s ) 第2 3 页 苤2 童扭苤型监塑攫垒生园翌 坐茧盔盎堂擅：匕生焦丝塞 技术网络指，人类制造出的用于传输物品或资源的网络，如电力网、信 息网等。电力网格是技术网络的典型实例，在每个国家都有横贯全国或部分 地区的高压三相传输电网。w a t t s 和s t r a g a t z 8 0 ，8 1 以及a m a r a l 等 8 2 都对此做过研究。其他实例包括航空线路 8 2 、公路网 7 1 、电路网 8 3 ， 8 4 ，以及前面提及的i n t e r n e t 。 4 ，生物网络( b i o l o g i c a ln e t w o r k s ) 很多生物系统都能表示为网络，其中典型实例为代谢网络( m e t a b o l i c n e t w o r k s ) 8 5 ，8 6 。其他实例包括蛋白质网络( p r o t e i nn e t w o r k ) 8 7 ， 8 8 、基因调节网络( g e n er e g u l a t o r yn e t w o r k ) 8 9 和食物网络( f o o dw e b ) 9 0 ，9 1 。在食物网中，节点代表生态系统中的物种，若节点a 至节点b 有 一条有向边，则表示a 以b 为食。 2 2 3 统计特征 研究人员最早提出的网络模型也是最简单的模型，随机网络模型，这是因为 当时对真实世界中大规模网络的数据统计无法进行，于是推测现实网络服从随机 网络模型。但是近年来的研究结果显示并非如此，真实网络具有很多与规则网络 和随机网络不同的统计特征，其中最重要的就是小世界效应和无标度特性。下面 将简单介绍复杂网络的部分统计特征。 l ，平均最短路径 网络最短路径的概念已在前面介绍 算公式： 忙上”：z l 。j d , j 公式1 1 是广为使用的平均最短路径计 ( 公式2 1 ) f 为网络的平均最短路径，d i 为节点f 与节点j 之间的路径长度，如果i 与，之 间没有路径，若按无穷大计算，则z 也为无穷大。于是具体计算时此种情况就不 计入平均。如果网络含有n l 条边，则使用宽度优先搜索法( b f s ) 可以o ( m n ) 时 问复杂度计算得到。 第2 4 页 釜2 重扫羞堡论塑拯盘虫国叠 堂挂盔太生蝗坐焦迨塞 为了避免上述无路径问题，也有研究者提出下述计算公式： 2 面i i 可万善九。1 ( 公式2 2 ) 可容易看出，此公式避免了上述无穷大问题。 2 ，簇系数 簇系数是真实网络和随机网络模型不同的重要特征。簇系数的概念也已经在 前面描述，下面介绍簇系数的计算公式，该公式由w a t t s 和s t r o g a t z 给出 7 1 ： cnumbero f t r i a n g l e sc o n n e c t e dt ov e r t e xi ( 公式2 3 ) n u m b e ro ft r i p l e sc e n t e r e do nv e r t e xi c = 二f c n 。 e 称为节点的簇系数，c 称为网络的簇系数。在节点规模和边规模大致相 同时，真实网络中的簇系数比随机网络的要大