（控制理论与控制工程专业论文）复杂网络上的演化博弈与机制设计研究.pdf

上海交通大学博士学位论文 复杂网络上的演化博弈与机制设计研究 摘要 复杂网络理论是近年来复杂系统科学研究中最活跃的分支之一。大量实证 性研究表明，许多真实网络( 比如因特网，万维网、电力网、生物网、社会合作 网等等) 具有许多相似的结构特性，如小世界和( 或) 无标度特性。此外，不同类 型的无标度网络常常表现明显的度相关性：社会合作网络中的中心节点倾向于 相互连接，表现同配度混合模式：而技术网络和生物网络中的中心节点倾向于 选择小度节点作为邻居，呈现异配度混合模式。这些网络结构特性对于运行其 上的动力学行为有着重要影响。 研究竞争个体之间的合作涌现机制一直是经济、生物乃至信息领域学者关 心的问题，博弈理论为此提供了一个理论框架。网络演化博弈把个体看作节点， 个体之间的联系通过网络的边描述，研究网络结构与策略演化之间的相互作用 关系。而机制设计( 又称为逆博弈理论) 关注于设计合理的协议，引导个体的自 私行为使系统的全局目标达得最优。机制设计近期被应用于网络路由协议设计 中，可以把超付作为一种结构特性研究。 本文重点探讨复杂网络上的演化博弈和超付特性，包括小世界、无标度和 度相关特性对网络演化博弈行为的作用，以及小世界网络和无标度网络中的超 付特性，主要内容和研究成果如下： 从个体动态组织角度，本文首先研究了小世界网络中的合作行为。研究表 明在节点具有相同度的随机正则网络中，对于囚徒困境博弈，交换边概率的增 加促进了网络中合作行为的涌现，这是由于个体通过结成大的合作簇有效抵御 背叛者的入侵所致：然而对于雪堆博奔，由于合作者很难形成大的合作簇，所 以当损益比超过一定阈值后随机正则网络中的合作频率低于均匀混合状态的均 衡频率。而对于w a t t s s t r o g a t z ( w s ) j x 世界网络模型，通过随机重连机制使w s 网络的度分布变得异质，网络中的合作水平得到了有效提升。 上海交通大学博士学位论文 基于一个扩展的雪堆博弈，本文进一步研究了可调度异质性的无标度网络 上的合作行为。研究表明越异质的无标度网络具有越高的合作水平。这是由于 具有大度的中心节点在稳定状态坚持合作策略，随着异质性的提高，中心节点 可以带动更多的邻居成为合作者，促使了无标度网络中稳定策略个体的涌现。 本文还研究了度相关性对网络博弈行为的影响。研究发现不论对于囚徒困 境博弈还是雪堆博弈，由于同配网络的中心节点倾向于相互相连，减弱了合作 中心节点之间的相持能力，使背叛者容易入侵中心节点；然而在异配网络中， 中心节点之间沟通的减弱使它们更容易坚持初始策略不变，所以合作行为不容 易在异配网络中湮灭。 通过研究小世界网络中的超付特性，本文发现w s 小世界网络中的平均超 付高于最近邻网络和完全随机网络，这是由于w s 小世界网络中的长程边拥有 过高的超付。因此，通过在原始长程边附近移入新的长程边，可以有效减小长 程边的超付。 最后，本文研究了可调度异质性的无标度网络中的节点超付分布。研究表 明节点超付与度之间呈现幂律关系，随着异质性的增加，超付度指数是减小的。 在度指数小于3 的无标度网络中节点超付的分布也是幂律的。通过把节点收取 的超付除以它传递数据包的数目，可以得到传递每个数据包的平均收益。仿真 表明异质网络的中心节点的每包平均收益高于小度节点的收益，而随着网络变 得均质，大度与小度节点之间的每包平均收益的差异是减小的。 关键词：演化博弈，机制设计，小世界网络，无标度网络，度混合模式 上海交通大学博士学位论文 t h es t u d yo fe v o l u t i o n a r yg a m ea n d m e c h a n i s md e s i g no nc o m p l e xn e t w o r k s a b s t r a c t c o m p l e xn e t w o r k st h e o r yi so n eo ft h em o s ta c t i v eb r a j l c h e si nt h ef i e l do f c o m p l e xs y s t e ms c i e n c e i ti sw i d e l yr e c o g n i z e dt h a tm a n yr e a l w o r l dn e t w o r k s ， s u c ha si n t e r n e t ，t h ew o r l dw i d ew e b ，p o w e rg r i d s ，b i o l o g i c a ln e t w o r k s ，s o c i a l c o l l a b o r a t i o nn e t w o r k s ，a n de t c ，s h a r em a n ys i m i l a rs t r u c t u r a lf e a t u r e si n c l u d i n gt h e s m a l l w o r l da n d ( o r ) s c a l e - f r e ep h e n o m e n a b e s i d e s ，v a r i o u ss c a l e f r e en e t w o r k s e x h i b i td e g r e ec o r r e l a t i o n s ：s o c i a lc o l l a b o r a t i o nn e t w o r k su s u a l l y d i s p l a y t h e a s s o r t a t i v ed e g r e e m i x i n gp a t t e r n ，w h e r eh u b st e n dt oi n t e r c o n n e c tw i t he a c ho t h e r w h i l ei nt h et e c h n o l o g i c a la n db i o l o g i c a ln e t w o r k s ，h u b sa r ew i l l i n gt os e l e c tt h o s e n e i g h b o r sh a v i n gs m a l l e rd e g r e e s ，b yw h i c ht h en e t w o r k sa r ed i s a s s o r t a t i v e l ym i x e d t h e s es t r u c t u r a lf e a t u r e sp l a yc r u c i a lr o l e so nt h ed y n a m i c a lb e h a v i o r s i n v e s t i g a t i n gt h ee m e r g i n gm e c h a n i s m s o fc o o p e r a t i o ne m e r g i n ga m o n g c o m p e t i t i v ei n d i v i d u a l sh o l d sav e r yl o n gh i s t o r yw i t hs t r o n gi n t e r e s ta st h eh o tt o p i c i nt h ef i e l d so fe c o n o m i c s ，b i o l o g ya n di n f o r m a t i o ns c i e n c e ，a n dt h eg a m et h e o r y p r o v i d e sat h e o r e t i c a lf r a m e w o r kf o ri t t h en e t w o r k e de v o l u t i o n a r yg a m et h e o r y f o c u s e so nt h ei n t e r a c t i o nb e t w e e nt h en e t w o r ks t r u c t u r e sa n dt h ee v o l u t i o no f s t r a t e g i e s ，w h e r et h ei n d i v i d u a l sa r el o c a t e do nv e r t i c e sa n dt h ei n t e r a c t i o na m o n g i n d i v i d u a l sa r ed e s c r i b e db ye d g e so ft h en e t w o r k o nt h eo t h e rh a n d ，t h em e c h a n i s m d e s i g n ，t h es o c a l l e di n v e r s eg a m et h e o r y ，a i m sa td e s i g n i n gp r o t o c o l st oi n d u c e t h e s es e l f i s hi n d i v i d u a l s b e h a v i o r st oa c h i e v et h e o p t i m i z a t i o no ft h e w h o l e s y s t e m a t i co b j e c t r e c e n t l y ，t h em e c h a n i s md e s i g nw a sa p p l i e dt od e s i g nt h er o u t i n g p r o t o c o la n dt h eo v e r p a y m e na sas t r u c t u r a lp r o p e r t yw a ss t u d i e d i nt h i sp a p e r ，w ei n v e s t i g a t et h er o l e so ft h es m a l l w o r l d ，s c a l e f r e ea n dd e g r e e 1 1 1 上海交通大学博士学位论文 c o r r e l a t i o nf e a t u r e so nt h en e t w o r k e de v o l u t i o n a r yg a m e s ，a n ds t u d yt h es t r u c t u r a l p r o p e r t yo fo v e r p a y m e n ti nn e t w o r k sw i t hs m a l l w o r l da n ds c a l e f r e ep r o p e r t i e s t h e m a i nc o n t e n ta n dc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： f r o mt h ev i e w p o i n to ft h ei n d i v i d u a l s d y n a m i c a lo r g a n i z a t i o n ，w e f i r s t i n v e s t i g a t et h ec o o p e r a t i v eb e h a v i o r so ns m a l l w o r l dn e t w o r k s w eo b s e r v et h a t ，f o r ar a n d o mr e g u l a rg r a p hw h e r ea l lv e r t i c e sh a v et h es a l t l en u m b e ro fn e i g h b o r s ，t h e i n c r e a s eo ft h es w a p p i n ge d g ep r o b a b i l i t i e sp r o m o t e st h ee m e r g e n c eo fc o o p e r a t i v e b e h a v i o r si nt h ep r i s o n e r sd e l i m m ag a m e ，m a i n l yd u et ot h ef a c tt h a tt h ei n d i v i d u a l s p r o t e c tt h e m s e l v e sf r o mt h ei n v a s i o no fd e f e c t o r sb yc o m p o s i n gl a r g e rc l u s t e r sa tt h e s t e a d ys t a t e w h i l ef o rt h es n o w d r i f tg a m e ，s i n c et h ec o o p e r a t o r sa r ed i f f i c u l tt of o r m l a r g ec l u s t e r s ，t h ec o o p e r a t o r s f r e q u e n c i e so fr a n d o mr e g u l a rg r a p h sa r el e s st h a nt h e e q u i l i b r i u mf r e q u e n c yi nw e l lm i x e dp o p u l a t i o n sw h e nt h ec o s t - t o b e n e f i tr a t i oi s l a r g e rt h a nt h et h r e s h o l dv a l u e m o r e o v e r , s i n c et h em e c h a n i s mo fr e w r i n ge d g e s m a k e st h ew a t t s s t r o g a t z ( w s ) s m a l l - w o r l dn e t w o r k sb e c o m eh e t e r o g e n e o u s ，t h e c o o p e r a t i v eb e h a v i o r sa r ee n h a n c e d w ef u r t h e rs t u d yt h ec o o p e r a t i v eb e h a v i o r so nt h en e t w o r k sw i t hd i f f e r e n t d e g r e eh e t e r o g e n e i t i e so na ne x t e n d e ds n o w d r i f tg a m em o d e l o u rf i n d i n g ss h o w t h a tt h ec o o p e r a t i v eb e h a v i o r sa r ep r o m o t e dr a p i d l yw h e nt h en e t w o r kb e c o m e sm o r e h e t e r o g e n e o u s ，b e c a u s et h eh u b sw h i c h h a v eh i 【g hd e g r e e sa r ef o u n dt oh o l do nt h e i r c o o p e r a t i o ns t r a t e g ya tt h es t e a d ys t a t e ，a n di n f l u e n c em o r en e i g h b o r st ob e c o m e c o o p e r a t o r s t h e r e f o r e ，t h eh e t e r o g e n e i t yp r o m o t e st h ee m e r g e n c eo fi n d i v i d u a l s w i t hs t e a d ys t r a t e g i e s f u r t h e r m o r e ，w ei n v e s t i g a t eh o wt h ed e g r e e m i x i n gp a t t e r n a f f e c t st h e e m e r g e n c eo fc o o p e r a t i o n i nt h en e t w o r k e dg a m e o u rs t u d ys h o w st h a tn o to n l yf o r t h ep r i s o n e r sd i l e m m ag a m e ，b u ta l s of o rt h es n o w d r i f tg a m e ，w h e nan e t w o r k b e c o m e sa s s o r t a t i v em i x i n gb yd e g r e e ，t h eh u b st e n dt oi n t e r c o n n e c te a c ho t h e r c l o s e l y , d e s t r o y i n gt h es u s t a i n a b i l i t ya m o n gc o o p e r a t o r sa n dp r o m o t i n gt h ei n v a s i o n o fd e f e c t o r s h o w e v e r , i nd i s a s s o r t a t i v en e t w o r k s ，t h ea b s e n c eo fc l o s ec o n n e c t i o n s a m o n gh u b sp r o t e c t st h ec o o p e r a t i v eh u b st oh o l do nt h e i r i n i t i a ls t r a t e g i e sf r o m e x t i n c t i o n i v 上海交通大学博士学位论文 w i t he x t e n s i v ei n v e s t i g a t i o n so ft h eo v e r p a y m e n to ns m a l l w o r l dn e t w o r k s w e f i n dt h a tt h ea v e r a g eo v e r p a y m e n to fw ss m a l l w o r l dn e t w o r k si sl a r g e rt h a nt h o s e o fn e a r e s tn e i g h b o rn e t w o r k sa n dc o m p l e t e l yr a n d o mg r a p h s t h i si sb e c a u s et h o s e s h o r t c u t si nw ss m a l l w o r l dn e t w o r k so b t a i nv e r yh i g ho v e r p a y m e n t s t h e r e f o r e ，w e p r o p o s ea n e wm e t h o db yr e w i r i n gs o m en e w e d g e sb e s i d et h o s eo r i g i n a ls h o r t c u t s ， t h r o u g hw h i c ht h eo v e r p a y m e n t so fs h o r t c u t sa r er e s t r a i n e de f f i c i e n t l y f i n a l l y , w es t u d yt h ed i s t r i b u t i o no fv e r t e xo v e r p a y m e n t si ns c a l e - f r e en e t w o r k s w i t hd i f f e r e n td e g r e ee x p o n e n t s w ef i n dt h er e l a t i o nb e t w e e nd e g r e ea n d o v e r p a y m e n ti sap o w e r - l a wf o r m ，a n dt h eo v e r p a y m e n t d e g r e ee x p o n e n td e c r e a s ea s t h en e t w o r kb e c o m e sm o r eh e t e r o g e n e o u s t h eo v e r p a y m e n td i s t r i b u t i o ni sa l s oi na p o w e r - l a wf o r mf o rt h es c a l e f r e en e t w o r k sw h o s ed e g r e ee x p o n e n t sa r el e s st h a n3 t h eb o n u sp e rp a c k e to fav e r t e xi so b t a i n e dt h r o u g hd i v i d i n gt h eo v e r p a y m e n to f t h i sv e r t e xb yi t sc a r r i e dt r a f f i c o u ri n v e s t i g a t i o n s h o w st h a tav e r t e xw i t hl a r g e r d e g r e ew i l lc h a r g em o r et h a nt h a t 、斩t hs m a l l e rd e g r e ef o rt r a n s m i t t i n gp e rp a c k e ti n h e t e r o g e n e o u sn e t w o r k s ，a n dt h ed i f f e r e n c eb e t w e e nt h o s ev e r t i c e sw i t hd i f f e r e n t d e g r e e sb e c o m e sm i n o rw h e nt h en e t w o r kb e c o m e sh o m o g e n e o u s k e yw o r d s ：e v o l u t i o n a r yg a m e ，m e c h a n i s md e s i g n , s m a l l w o r l d n e t w o r k ， s c a l e - f l e en e t w o r k ，d e g r e e - m i x i n gp a a e m v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 学位论文作者签名： 日期：u 寸孑年7 月z7 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密瓯 ( 请在以上方框内打“4 ”) 学位论文作者签名：荣留诲 指导教师签名： 日期：2 oo 占年，月z 7 日 日期懈年 融日 上海交通大学博士学位论文 1 1 引言 第一章绪论 从生物的神经系统到蛋白质交互作用网络，从i n t e m e t 到电力网络，从航空 网到铁路交通网，从科研合作关系网络到世界金融贸易网，这些复杂系统都可以 用由节点和边构成的网络语言来描述【1 5 】。有趣的是，这些来自不同领域的刚络 竟有着非常相似的性质。1 9 9 8 年w a t t s 和s t r o g a t s 在发表于n a t u r e ) ) 上的“小 世界网络的集体动力学”一文中发现真实网络系统具有较短平均路径长度和局 部高聚类的小世界现象 6 】，一年之后b a r a b d s i 和a l b e r t 在发表于( ( s c i e n c e ) ) 上 的“随机网络中标度的涌现一文中指出许多网络系统具有无标度特性它们 的度分布都表现幂律形式【7 】。这两篇开创性的文章激发了人们探索网络奥秘的 热情，此后，复杂网络理论逐步建立起来：人们通过实证性研究揭示了许多网络 特性，建立了各种有趣的网络模型，分析了不同的网络动力学行为及其控制方法。 探索网络是为了更好地理解缤纷世界背后的运行机理，比如地球上的生物为 什么会呈现多样性? 为什么城市公路越修越宽，却仍无法缓解交通拥堵? 在风雪 和地震来临之际，为什么国人会紧密地团结起来，共度难关? 为什么次贷危机会 产生如此广泛的多米诺骨牌效应使金融巨头相继倒闭? 为了探究这些现象背后的 内在原因，我们必须理解复杂网络系统与网络行为之间丰富而又微妙的联系。 博弈论( g a m et h e o r y ) 为解释自私个体的交互行为提供了强有力的理论框架。 自从数学家v o nn e u m a n n 和经济学家m o r g e n s t e m 的合著博弈论与经济行为 问世以来 8 ，人们开始按照博弈方法来分析经济竞争、军事冲突及物种演化等 种种问题，尤其是生物学家s m i t h 将博弈论引入生物进化领域 9 】，利用博弈观点 理解个体合作行为和种群的进化，揭示底层自私个体之间的竞争和现实生活中广 泛存在的合作行为之间看似矛盾实则统一的内在动因。如果将个体看作节点，个 体之间的联系看作边，那么种群的组织形式可以用网络来描述。人们越来越关注 不同的网络结构与自私个体行为之间的相互作用。 利用博弈论分析网络上用户的自私行为也引起了信息科学研究者的关注 【1 0 】。研究表明个体如果自私地选择它们的行为，会使系统处于低效的状态。因 第1 页 上海交通大学博士学位论文 此，需要引入合适的措施来调控自私用户的行为，优化系统的性能。这一问题在 博弈论领域被称为机制设计问题。近期学者将机制设计思想引入网络研究【11 】， 考虑如何设计合理的路由协议优化网络性能。因此，网络博弈论不但在理论研究， 而且在实践应用方面均被广泛关注。 下面将综述复杂网络上的演化博弈和机制设计方面研究的最新进展。 1 2 经典博弈理论概述 博弈论，又称为对策论，研究的是理性个体交互作用下的行为和结果。它作 为应用数学的一个分支，广泛应用于生物【9 】、经济【1 2 】、政治 1 3 】、信息 1 4 】等 许多学科。博弈论研究的模型一般至少包含两个个体( i n d i v i d u a l ) ，也称为参与者 ( p l a y e r ) ；它们可以在多个策略( s t r a t e g y ) 间进行选择；任何个体的行为都会影响到 其他个体，每个个体都能够从与其他个体的互动中获得一定的收益( p a y o f f ) ；博 弈论研究个体理性的策略选择，即在他人选择既定的情况下，如何使自己利益最 大化的最优反应。博弈论中个体理i 生( r a t i o n a l i t y ) 的假设基础来源于古典经济学， 因为理性行为比非理性行为更容易预测 1 5 】。博弈论中最核心的概念是纳什均衡 ( n a s he q u i l i b r i u m ，n e ) ，它是指自私个体在相互作用过程中达到的一种均衡状态， 这种状态下没有个体可以通过单方面改变自己的策略而增加收益。纳什( n a s h ) 因 为证明了它的存在性而获得1 9 9 4 年经济学诺贝尔奖【1 6 】。在博弈理论研究中， 通常使用一些生动有趣的博弈模型来隐喻个体之间的冲突竞争，以下介绍两个著 名的博弈模型。 囚徒困境问题( p r i s o n e r sd i l e m m a ，p d ) ：两个小偷合伙作案，被捕后被隔离 审讯。如果双方都拒绝坦白同伴的罪行，两人将会被轻判1 年徒刑；为此，警方 设计了一个机制：如果一方坦白罪行，另一方拒不认罪，则前者将无罪释放，而 后者将被重判5 年徒刑；如果双方都坦白罪行，那么双方都会被判刑3 年。在这 种情况下，自私的个体会如何做出抉择? 可以发现，对于每个自私的个体来说， 如果对手选择合作拒绝认罪，则你的最优反应是坦白背叛对方：而如果 对手选择认罪，背叛对手的收益也要高于坚持合作的收益，由此可见，不论对手 采取哪种策略，选择背叛策略都是最佳的。因此，理性的个体最终会处于相互背 叛的状态显然此时的收益低于两人同时选择合作时的收益，在这种情况下理 第2 页 上海交通大学博士学位论文 性个体将面临两难的困境。这个例子来自于普林斯顿大学数学系教授塔克( t u c k e r ) 为心理学家讲解博弈论时的案例，由于囚徒困境模型可以很好地用于解释现实生 活中的环境污染、交通拥塞等问题，因而影响深远。通常，确定性地选择合作 ( c o o p e r a t i o n ，c ) 或者背叛( d e f e c t i o n , d ) 的方式称为纯策略( p u r es t r a t e g y ) ，囚徒困境 中( c ，c ) 是一个纯策略纳什均衡。 雪堆博弈( s n o w d r i f tg a m e ，s g ) ：在一个风雪交加的夜晚，两人开车相向而行， 被一个雪堆所阻。假设铲除这个雪堆使道路通畅需要的代价为c ，如果道路通畅 则带给每个人的好处为b ，b c 。如果两人一齐动手铲雪，他们的收益为b c 2 ： 如果只有一人铲雪，虽然两个人都可以回家，但是背叛者逃避了劳动，它的收益 为b ，而合作者的收益为6 一c ；如果两人都选择不合作，两人都无法及时回家， 他们的收益都为0 。那么，理性个体的最优选择是什么? 对于雪堆博弈来说，如 果对手选择背叛策略一呆在车中，那么另一方的最佳策略是下车铲雪按时 回家的合作收益b c 高于呆在车中的背叛收益0 。所以，在雪堆博弈中，个体的 最佳策略取决于对手：如果对手选择合作，个体的最佳策略是背叛；反之若对手 是背叛者，个体最好采取合作策略。因此，不同于囚徒困境博弈，雪堆博弈中存 在两个纯纳什均衡：( c ，d ) 和( d ，c ) 。在这种存在多个纳什均衡的情况下，个体 如何抉择是一个难题。谢林( s h e l l i n g ) 提出可以根据线索( 如历史信息) 进行选择均 衡，比如一个个体非常熟悉对手的脾气，知道对手很懒，那么他的最好选择下车 铲雪，通常这种根据线索找到的均衡也称为谢林点( s h e l l i n gp o i n t ) j 1 7 。然而，如 果两个个体没有线索可以利用，在不确定对手选择的情况下，个体也可以以概率 1 一，选择铲雪，以概率，选择呆存车中，= c ( 2 b c ) 称为双方合作时的损益比 ( c o s t t o b e n e f i t ) ，此时对对手来说选择合作或者背叛的期望收益是相同的这 样对手无法通过改变策略来提高自己的收益。通常将这种以一定概率分布在策略 中随机选择的方式称为混合策略( m i x e ds t r a t e g y ) ，雪堆博弈中存在一个混合纳什 均衡。与冈徒困境问题相比，合作者更容易在雪堆博弈中存在。 经典博弈理论在个体完全理。眭( p e r f e c t l yr a t i o n a l i t y ) 的假设下，集中研究博弈 的均衡问题，它们对自私个体是如何识别并到达均衡的传统解释是：自私个体基 于共同知识( c o m m o nk n o w l e d g e ) ，可以通过分析与自省得出正确结果 1 8 】。这个 解释显然存在许多问题：现实复杂环境中，即使再聪明的人也会犯错误，人们的 理性是有局限的；在生物的成长与漫长的进化过程中，个体无法清晰了解环境， 第3 页 上海交通大学博士学位论文 它们只有通过不断地试错来适应环境，均衡状态不是一蹴而就的；当博弈存在多 个均衡时，个体如何选择适合的均衡又如何收敛于它，便成为了一个难题。因此， 生物学家将生物进化论中的自然选择和遗传变异机制引入博弈论中，提出了演化 博弈理论，力图解释上述经典博弈论无法解答的问题。 1 3 演化博弈理论研究进展 在复杂环境中个体没有足够的能力去选择最佳策略以最大化他们的收益，此 时个体通常会根据它掌握的局部信息采取启发式的方法，做出令其满意的决策。 个体的这种选择过程表明它是有限理性的( b o u n d e dr a t i o n a l i t y ) 。演化博弈理论 ( e v o l u t i o n a r yg a m et h e o r y ) 着重研究有限理性的个体如何随着时间的推移在不断 的重复博弈过程中通过自适应地学习，优化收益。这一方面有助于“精炼”经典 博弈中存在的多个均衡通过个体长期寻优得到的演化稳定策略( e v o l u t i o n a r y s t a b l es t r a t e g y ，e s s ) 对随机扰动是稳定的；另一方面，在博弈演化过程中展现 出丰富的动力学行为特性，也为理解现实生活中合作的涌现和有限系统资源的合 理分配提供了一种有力的工具。 演化博弈理论考虑博弈发生在一个种群( p o p u l a t i o n ) q b ，个体之间按照某种方 式相互接触，其中最简单的接触方式是均匀混合( w e l l m i x e d ) ，通常它有两种处 理方式：一种是假设每个个体与种群中的其他所有个体进行博弈这时种群处 于全局耦合状态；另一种是假设每个个体与种群中随机选中的若干个个体进行博 弈。这些个体的理性是有限的，它们在不断的重复博弈过程中，学习优胜者的策 略，剔除无效策略。演化博弈理论将经典博弈论中的收益对应于进化论中的适应 度( f i t n e s s ) ，适应度越高的策略随着时间演化更有可能被保留下来，而适应度差 的策略会逐渐被淘汰，这是自然选择( n a t u r a ls e l e c t i o n ) 思想在博弈论中的自然推 广。最终，某种策略在种群中会达到一个均衡状态，此时任意少量的变异策略的 个体无法入侵整个种群，长期来看整个种群没有发生改变，这种策略称为演化稳 定策略，它最初由s m i t h 和p r i c e 在研究动物之间争夺食物等有限资源时提出【1 9 】， 演化稳定策略是纳什均衡的一个子集。过去研究演化稳定策略时假设种群的规模 是无限的，最近，n o w a k 等研究了种群规模有限的情况下的演化博弈动力学【2 0 】。 以下，主要介绍当每对个体采取两策略博弈时，种群策略演化稳定的各种情况。 第4 页 上海交通大学博士学位论文 ，p 1 a ，y e r 2 ， cd 蚓 叩；) 图1 1 两人两策略博弈的收益矩阵 f i g 1 1p a y o f fm a t r i xo f2 x 2g a m e 首先，对两人两策略博弈( 2 x 2g a m e ) 模型进行标准化。假设个体只有两种 策略可供选择：合作策略介体通过付出一定代价使对手获益；背叛策略一 不付出任何代价却可以从合作者处获益。如图1 1 所示，双方都选择合作时的收 益为r ，即“对双方合作的奖励( r e w a r df o rm u t u a lc o o p e r a t i o n ) ”；如果一方合作 而另一方背叛，则背叛者会获得“对背叛的诱惑( t e m p t a t i o nt od e f e c t ) ”t ，而合 作者则得到“给傻瓜的报酬( s u c k e r sp a y o f f ) s ；“双方都背叛的惩罚( p 嘶s i u n e m f o rm u t u a ld e f e c t i o n ) ”为尸。为了简化参数，通常设定尺= 1 ，尸= 0 ，丁和s 是两 个可变参数。考虑在均匀混合种群中，每对个体按照图1 1 收益矩阵进行博弈， 假设采用合作策略的个体比例为x ，选择成为背叛者的比例为y ，则种群中合作 背叛者的收益分别为： - r p c = ：r 强x + + 聊s y 。( 1 - 1 ) 【弓= 强+ 砂 7 t a y l o r 和j o n k e r 首先利用模仿者动态( r e p l i c a t o rd y n a m i c s ) 描述演化过程中策略的 动态变化 2 1 1 ：种群中某个策略比例的变化速度既与采用这个策略的个体比例成 正比，也与其收益成正比： ：2 x 足一矽。 ( 1 2 ) 【y = y ( 易一矽) 其中矽= 磁+ 坞是种群的平均收益。因此，演化博弈过程中，个体的适应度与 采用各种策略的个体比例密切相关。根据公式( 1 1 ) 和( 1 2 ) 并结合x + y = 1 ，可以 得到合作者的模仿者动态方程： x = x ( 1 - x ) ( r - s - t + p ) x + s - p 】， ( 1 - 3 ) 显然，这个非线性微分方程与收益矩阵的参数密切相关，根据动力学的不同特征 可以按以下四种情况分别进行讨论： 第5 页 上海交通大学博士学位论文 ( 1 ) 背叛占主导情况( dd o m i n a t ec ) ：在t r p s 情况下，采取背叛策略的个 体收益优于合作者的收益，根据图1 2 ( a ) 显示的相平面图可知x = 0 是稳定的 平衡点，因此稳定状态所有个体都会采取背叛策略，合作者会在种群中消亡。 囚徒困境问题属于这一参数范围，因此( d ，d ) 也是冈徒困境问题的一个演化 稳定策略。进一步，囚徒困境问题通常要求丁+ s 2 r ，以保证重复博弈时双 方合作的收益不低于交替采取合作背叛策略时个体的收益。设定r = 1 ，尸= 0 时，图1 3 中r l ，s r s p 时，与情况( 1 ) 相比，将s 与尸互 换，这样个体的最优反应是采取对手相反的策略，合作与背叛策略呈现共生 状态。随着种群演化，根据图1 2 ( b ) 可知个体采取合作策略的比例会趋近于 妒= ( p s ) ( r s 一丁+ p ) ，它是情况( 2 ) 的演化稳定策略。同样，在t + ss2 r 情况下，双方都合作时的收益优于合作背叛策略交替出现的情况，因此，合 作背叛共生区域对应图1 3 中0 s p s ，图1 2 ( c ) 表明参与者的最优策略是与对手一致：同时选 择合作或者背叛策略。猎鹿博弈( s t a g h u n t i n gg a m e ，s h ) 是体现这种情况的一 个生动例子 2 3 - 两个猎人共同打猎，同时发现一头鹿和两只兔子，他们必 须齐心合力才能把鹿抓到，然后他们可以平分这头鹿，每人收益为5 ，这样 兔子就抓不到了；每个猎人也可以毫不费力地抓到一只兔子，获利3 ，然而 鹿就会跑掉；如果一个猎人抓兔子而另一个去抓鹿，则前者( 背叛者) 将收获 一只兔子而后者( 合作者) 将一无所获。两个人的决策必须在瞬间做出，无法 充分沟通。这样，两个人的最佳策略是齐心合力抓鹿( c ，c ) ，次优策略是各 自抓兔子( d ，d ) ，这两种情况是猎鹿博弈的两个纯纳什均衡。同时，猎鹿博 弈也存在一个混合纳什均衡：每个猎人以概率矿= ( p s ) ( r s t + p ) = 3 5 去抓鹿，以2 5 的概率去抓兔子，此时对手选择猎鹿或者兔子的期望收益相 同。然而，通过图i 2 ( c ) 可以发现，x = 0 和x = 1 是猎鹿博弈的两个演化稳定 第6 页 上海交通犬学博士学位论文 策略；，点是不稳定的，少量变异策略会使种群趋向于x = 0 或者1 。由此可 见，演化稳定策略只是纳什均衡的一个子集，而且情况3 稳态的收敛结果与 初态“0 ) 的取值有关。图1 3 所示s 0 t i 所围成的矩形属于双稳态区域。 性别大战( b a t t l eo f t h es e x e s ) 和协调博弈( c o o r d i n a t i o ng a m e ) 也属于双稳态型博 弃【2 2 】，这种情况主要被社会领域学者研究。 ( 4 ) 合作占主导情况( c d o m l n a t e d ) ：当在t r 且p 0 ，t 1 时属于网徒困境情况。他们假定个体采用简单的最 优规则进行策略演化：每个个体在一轮博弈结束后，在下一轮中它会采取邻居( 包 含本身) 中收益最高个体本轮的策略，这是一个确定性的策略。他们发现与种群 均匀混合情况下合作行为湮灭不同，