（控制理论与控制工程专业论文）网络博弈模型的分析与控制研究.pdf

上海交通大学博士学位论文 网络博弈模型的分析与控制研究 摘要 酒吧问题及少数者博弈( m g ) 是各种实际拥塞和协调问题的简化模型，它 们描述了网络、交通、经济、生态以及其它领域中，面对有限资源独立的参与者 之间的相互竞争行为。对这类拥塞博弈的深入研究有助于更好地理解各种实际的 拥塞现象，并进而提供有效的避免和控制拥塞的决策方案，从而使资源得到合理 的利用。雪堆博弈描述了生物和社会经济系统中参与者之间的利益冲突，揭示了 个体理性与群体理性的矛盾对立，被认为是博弈理论研究合作行为产生、维系和 演化的一个范例。 在基本的拥塞博弈和雪堆博弈模型中，参与者仅依据公共的信息系统，并凭 借自己的过去经验参与博弈，参与者之间没有直接的信息交流或相互作用。近年 来，复杂网络研究的兴起使得人们开始关注网络的结构特性与博弈系统的演化行 为之间的关系。复杂网络理论为博弈理论的竞争与合作的研究提供了新的思路和 方法。本文的主要研究内容也正是在拥塞博弈和雪堆博弈模型中考虑网络拓扑结 构的影响，并从复杂网络理论的角度对拥塞与合作系统进行分析和控制。 本文的主要内容和成果总结如下： 分析了酒吧问题的纯策略和混合策略的纳什均衡。首先从控制理论角度 提出了酒吧问题的分散p i 控制算法。根据信息结构的不同，p i 控制算法分为“完 全信息”算法和“部分信息”算法。“部分信息”结构使博弈结果收敛到了纯策 略纳什均衡，将其扩展到多酒吧模型后，同样使资源得到了有效的利用。然后借 鉴m t e m e t 拥塞控制思想提出了酒吧问题的分散a i a d ( a d d i t i v e i n c r e a s e a d d i t i v e d e c r e a s e ) 控制算法，并分别研究了酒吧的资源水平恒定的模型以及资源水平时 变的模型，发现a i a d 算法利用有限的信息也能够使系统有效跟踪资源容量的变 摘要 化，而且资源利用率比较高。 针对社会人群呈现出复杂网络结构特征的现象，将复杂网络拓扑结构引 入了演化少数者博弈( e m g ) 中，研究了星型网络、小世界网络和无标度网络 上的e m g 模型。不同参数配霞下的仿真结果显示系统的动态依赖于底层网络结 构。当收益函数对称时，星型网络上的稳态概率分布由基本e m g 模型中的自组 织分离变为了中庸人群的峰化，而小世界网络和无标度网络没有改变e m g 模型 的稳态概率分布，并且此时它们取得了最优的资源配置。小世界网络的重连概率 越小，系统的协调效果越好。无标度网络上参与者的成功率与他们的度存在正相 关，而且系统的性能与网络的聚类特性相关，网络的聚类系数越大，系统的性能 越好。 提出了随机k a u f f m a n 网络上的一种修正演化少数者博弈( m e m g ) 模 型，研究了网络的平均连接度对系统行为的影响。参与者通过自组织形成了两组 极端行为的相反人群。而且当网络的平均连接度等于2 时，整个系统取得了最佳 的合作效果。与相同参数设置下基本m g 和e m g 模型相比，整体性能有了显著 的提高。将这种网络连接模式扩展到多选择博弈模型中，同样增强了系统的协调 性。 针对现实生活中朋友关系网络的距离相关的特性，研究了基于距离的空 间小世界网络上的雪堆博弈模型，网络中两个节点的连接概率是它们之间网格距 离的幂律函数。与规则网络相比，距离无关的小世界网络促进了合作行为的演化。 然而在距离相关的小世界网络拓扑结构下，随着幂指数的增加，长程连接的减少 以及短程连接的增加在损益比比较大的时候阻碍了整体合作水平的提高。 关键词：复杂网络，酒吧问题，少数者博弈，雪堆博弈，随机k a u f f m a n 网络 上海交通大学博士学位论文 a n a l y s i sa n dc o n t r o lo fn e t w o r kg a m e m o d e l s a b s t r a c t t h eb a rp r o b l e ma n dm i n o r i t yg a m ea r es i m p l i f i e dm o d e l so fal o to fp r a c t i c a lc o n g e s t i o na n d c o o r d i n a t i o np r o b l e m s ，w h i c hd e s c r i b et h em u t u a lc o m p e t i t i o no fi n d e p e n d e n ta g e n t sf o rl i m i t e d r e s o u r c e si nn e t w o r k ，t r a f f i c ，e c o n o m y , e c o l o g ya sw e l la so t h e rf i e l d s ad e e p e ru n d e r s t a n d i n go f w h a tt r a n s p i r e so ft h i sc l a s so fc o n g e s t i o ng a m em a yh e l pu sd e v e l o pm e t h o d sf o ru n d e r s t a n d i n g h o wr e s o u r c e ss u b j e c tt oc o n g e s t i o nc a nb eb e t t e rm a n a g e d t h es n o w d r i f tg a m ed e s c r i b e st h e b e n e f i tc o n f l i c ta m o n ga g e n mi n b i o l o g i c a la n ds o c i o e c o n o m i cs y s t e m sa n d d i s c o v e r st h e c o n t r a d i c t i o nb e t w e e ni n d i v i d u a lr a t i o n a l i t ya n dc o m m u n i t yr a t i o n a l i t y , w h i c hh a sb e e nr e g a r d e d a sap a r a d i g m a t i cm o d e lf o rs t u d y i n gt h ee m e r g e n c e ，p e r s i s l e n c ea n de v o l u t i o no fc o o p e r a t i v e b e h a v i o rw i t hg a m et h e o r y t h e r ei sn oe x p l i c i tc o m m u n i c a t i o na n di n t e r a c t i o nb e t w e e ni n d i v i d u a l si nt h eb a s i cc o n g e s t i o n g a m ea n ds n o w d r i f tg a m em o d e b w h e r ea g e n bo n l ym a k eu s eo ft h eg l o b a li n f o r m a t i o na n dt h e i r o w np a s te x p e r i e n c e i nr e c e n ty e a r s ，t h er e s e a r c ho fc o m p l e xn e t w o r ka t t r a c t sm u c ha t t e n t i o nt o t h er e l a t i o n s h i pb e t w e e nt h es t r u c t u r ee f f e c to fc o m p l e xn e t w o r ka n dt h ee v o l u t i o n a r yb e h a v i o r so f g 舢es y s t e m c o m p l e xn e t w o r kt h e o r yp r o v i d e sn e wi d e a sa n dm e t h o d sf o rt h es t u d yo f c o m p e t i t i o na n dc o o p e r a t i o ni ng a m et h e o r y t h ef o c u so ft h i sd i s s e r t a t i o ni st oc o n s i d e rt h e i m p a c to fn e t w o r kt o p o l o g ys t r u c t u r eo nt h ec o n g e s t i o ng a m ea n ds n o w d r i f tg a m em o d e l s , a n a l y z e a n dc o n t r o lt h ec o n g e s t i o na n dc o o p e r a t i o ns y s t e mf r o mt h ev i e w p o i n to f c o m p l e xn e t w o r kt h e o r y t h em a i nc o n t e n ta n dc o n t r i b u t i o n so f t 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 ： w ea n a l y z et h ep u r es t r a t e g ya n dm i x e ds t r a t e g yn a s he q u i l i b r i ao ft h eb a rp r o b l e m f r o m ac o n t r o l - t h e o r e t i cp o i n to fv i e w , ad e c e n t r a l i z e dp ic o n t r o la l g o r i t h mi sp r o p o s e df o rt h e 1 1 1 a b s t r a c r b a r p r o b l e m a c c o r d i n g t ot h ei n f o r m a t i o ns t r u c t u r e ，t h ep ic o n t r o l a l g o r i t h m i s d i f f e r e n t i a t e da s f u l li n f o r m a t i o n ”a l g o r i t h ma n d “p a r t i a li n f o r m a t i o n ”a l g o r i t h m u n d e r t h e “p a r t i a li n f o r m a t i o n ”s t r u c t u r e ，t h ea l g o r i t h mc o n v e r g e st ot h ep u r es t r a t e g yn a s h e q u i l i b r i u m t h ee f f e c t i v eu t i l i z a t i o no fr e s o u r c eo c c u r sa l s of u rag e n e r a l i z a t i o no ft h e “p a r t i a li n f o r m a t i o n ”a l g o r i t h m t ot h em u l t i - b a rp r o b l e m i n s p i r e db yt h ei n t e m e t c o n g e s t i o nc o n t r o ls c h e m e ，ad e c e n t r a l i z e da i a d ( a d d i t i v ei n c r e a s ea d d i t i v ed e c r e a s e ) c o n t r o la l g o r i t h mi st h e np r o p o s e dt ot h eb a rp r o b l e m ，w h i c hi si n v e s t i g a t e di nt h em o d e l s w i t hf i x e dc a p a c i t yl e v e la n dv a r y i n gc a p a c i t yl e v e lr e s p e c t i v e l y w ef i n dt h a tt h ea i a d a l g o r i t h mw i t hl i m i t e di n f o r m a t i o nc a na l s om a k et h es y s t e mf o l l o wt h ec h a n g e so ft h e c a p a c i t yl e v e le f f e c t i v e l ya n da c h i e v ev e r yh i g hu t i l i z a t i o no f r e s o u r c e c o n s i d e r i n gt h ee m e r g e n c eo fc o m p l e xn e t w o r ks t r u c t u r ee f f e c ti nt h es o c i a lp o p u l a t i o n s ， w ei n t r o d u c et h ec o m p l e xn e t w o r kt o p o l o g ys t r u c t u r et ot h ee v o l u t i o n a r ym i n o r i t yg a m e ( e m g ) ，a n ds t u d yt h ee m g m o d e lo ns t a rn e t w o r k ，s m a l l - w o r l dn e t w o r ka n ds c a l e - f r e e n e t w o r k s i m u l a t i o nr e s u l t su n d e rv a r i o u sp a r a m e t e rs e t t i n g si n d i c a t et h a tt h ed y n a m i c so f t h es y s t e md e p e n d sc r u c i a l l yo nt h es t r u c t u r eo ft h eu n d e r l y i n gn e t w o r k w i t ht h e s y m m e t r i cp a y o f ff u n c t i o n ，t h es t e a d yp r o b a b i l i t yd i s t r i b u t i o no ft h em o d e lo n s t a r n e t w o r ki sc h a n g e df r o mt h es e l f - s e g r e g a t i o ni nt h eb a s i ce m gm o d e lt ot h ec l u s t e r i n g t o w a r d sc a u t i o u sp o p u l a t i o n s ，w h e r e a si ti sn o ta f f e c t e db ys m a l l - w o r l da n ds c a l e f r e e n e t w o r k sa n dt h e i rs y s t e ma t t a i n st h eo p t i m a lr e s o u r c ea l l o c a t i o na tt h i ss t a t e t h es m a l l e r f e w r i n gp r o b a b i l i t yo ft h es m a l l - w o r l dn e t w o r k , t h eb e t t e rc o o r d i n a t i o no ft h es y s t e m t h e r ee x i s t sap o s i t i v ec o r r e l a t i o nb e t w e e nt h es u c c e s sr o t e sa n dd e g r e e so ft h ea g e n t so n s c a l e f r e en e t w o r k i np a r t i c u l a r , t h ep e r f o r m a n c eo ft h es y s t e mi sc o r r e l a t e dt ot h e c l u s t e r i n gp r o p e r t yo ft h en e t w o r k , w h e r el a r g e rc l u s t e r i n gc o e f f i c i e n tl e a d st ob e t t e r p e r f o r m a n c e w ep r o p o s eam o d i f i e de v o l u t i o n a r ym i n o r i t yg a m e ( m e m g ) m o d e lo nr a n d o mk a u f f m a n n e t w o r lt h ep r o p e r t i e so fs u c has y s t e mf o rd i f f e r e n tn 坼姐c o n n e c t i v i t yo ft h en e t w o r k a g es t u d i e d t h ea g e n t st e n dt os e l f - s c g r e g a t ei n t oo p p o s i n gg r o u p sc h a r a c t e r i z e db y e x t r e m ea c t i o n s ，a n dc a l lc o o r d i n a t et h e i rb e h a v i o r so p t i m a l l yi nt h es y s t e mw i t ht h em e a n c o n n e c t i v i t ye q u a lt o2 t h ep e r f o r m a n c eo ft h es y s t e ma saw h o l ei si m p r o v e dg r e a t l y c o m p a r e dw i t ht h a to ft h eb a s i cm ga n de m gm o d e lu n d e rt h es a m es e t t i n g s e n h a n c e d i v 上海交通大学博士学位论文 c o o p e r a t i o no c c u l sa l s of o rag e n e r a l i z a t i o no ft h en e t w o r kc o n n e c t i v i t yp a t t e r nt ot h e m u l t i p i ec h o i c eg a m em o d e l s m o t i v a t e db yt h ed i s t a n c e - r e l a t e dp r o p e r t yo ft h er e a lf r i e n dn e t w o r k , as n o w d r i f tg a m e m o d e lo ns p a t i a ld i s t a n c e - d e p e n d e n ts m a l l - w o r l dn e t w o r ki sp r o p o s e d ，w h e r et w on o d e s a r ec o n n e c t e dw i t hp r o b a b i l i t yd e p e n d i n go nt h e i rl a t t i c ed i s l a n c ei nt h ep o w e r - l a wf o r m c o n t r o l l e db ya ne x p o n e n t i nt h ed i s t a n c e - i n d e p e n d e n tc a s e ，t h es m a l l - w o r l dc o n n e c t i v i t y p a t t e r nc o n t r i b u t e st o a ne n h a n c e m e n to fc o o p e r a t i o n c o m p a r e dw i t h t h a t i nr e g u l a r l a t t i c e s h o w e v e f w h e nt h ec o s t t o - b e n e f i tr a t i oi sl a r g e ，t h ee v o l u t i o no fc o o p e r a t i o n t e n d st ob ei n h i b i t e dw i t ht h ei n c r e m e n to ft h ee x p o n e n ti nt h es p a t i a ld i s t a n c e - d e p e n d e n t s m a l l - w o r l ds t m c t u r e ，w h e r et h e l o n g - d i s t a n c e c o n n e c t i o n sb e c o m e s p a r e a n d s h o r t - d i s t a n c ec o n n e c t i o n sb e c o m ed e n s e k e yw o r d s ：c o m p l e xn e t w o r k , b a rp r o b l e m ，m i n o r i t yg a m e ，s n o w d r i f t g a m e ，r a n d o m l ( a u f f m a nn e t w o r k v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导f ，独 立进i 行研究工作所取锝的成槊。除文r t ，已经注明引嗣的内容外，本论 文不包含任何其他个入或集体已经发表或撰写过的作晶成果。对本文 的研究做出重要贡献的个人和集体，均已在文z ：，以明确方式标明。本 人完全意识到本声明的法律结果l l j 本人承掇。 学位论文作者签名： 扬列挥 嘲嘲年紫匆翻 ，上海交通大学，上海父遗大孕 学位论文版权使用授权书 本学位论文作者完全、j ，鳃学校有关缫留、使用学位沦文的规定， 列意学校徕翻并陶因家：疗关部门或机构送交论：文的复印件和电予版， 允游淦文被套阕和借阅。本人授权一t 海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采删影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密暖，在一年解密后适用本授权书。 本学位论文属于， 不保密阢 ( 请在以e 方框内打“”) 学警誓掌慈悫魏掺i ： ：一、j 二：。二= 。：、奏： ”f 。_ ：。冀，。! “、。s - 鼻姆堪魑黧毫鬻j 釜1 蕊* 再 j 叠g j 霹期? 翻暖警i 镄叟；黪黪爹爹蛰 。指夥教翔签名： r 、一 ? | 一 、j 一 誉藤 鬻憋 ! = i 誉黪辫受追謦誊擎j 攀霉 上海交通大学博士学位论文 1 1 引言 第一章绪论 博弈论( g a m et h e o r y ) ，又称对策论，是使用数学模型研究冲突对抗条件下 最优决策问题的理论。博弈论作为一种分析方法被广泛应用于经济学、管理学、 政治学、军事学、生物学、统计学等不同的学科。博弈论的研究对象主要是人与 人之自j 的关系，特别是人与人之间行为的相互影响和相互作用，人与人之间利益 和冲突、竞争与合作。其中，拥塞博弈( c o n g e s t i o ng a m e ) 1 是现实社会中各 种拥塞问题的简化模型，它模拟了网络、交通、经济、生态以及其它领域中，面 对有限资源独立的参与者的相互竞争行为。在众多的拥塞博弈模型中，由a r t h u r 提出的酒吧问题( b a rp r o b l e m ) 2 以及由 c h a i l e t 和z h a n g 提出的少数者博弈 ( m i n o r i t yg a m e ) 3 ，4 已成为得到广泛研究的经典模型。而雪堆博弈( s n o w d r i f t g a m e ) 5 ( 又称为鹰一鸽博弈) 描述的是博弈论的永恒主题：冲突与合作，其 研究涵概了从生物系统到社会系统的多个领域。 从2 0 世纪末开始，复杂网络研究正渗透到从数理学到生命学和工程学等众 多不同的学科，对复杂网络的定量与定性特征的科学理解已成为网络时代科学研 究中一个极其重要的挑战性课题 6 ，7 。复杂网络作为一种非常有效的手段，可 用来描述人与人之间的社会关系、物种之间的捕食关系、计算机之间的网络连接 以及科研文章之间的引用关系等。近年来复杂网络研究的兴起使得人们开始关注 网络的结构特性与博弈行为之间的联系。我们可以将博弈中的个体( 博弈方，局 中人，参与者) 定义为网络中的节点( n o d e ) ，而将个体之间的相互作用( 例如亲 朋关系或信息交流) 定义为节点之间的连接( 1 i n k ) 。因此，复杂网络理论为博弈 理论的竞争与合作的研究提供了新的思路和方法。 本文提出并研究了一组具有代表性的网络结构演化博弈模型，分析了聚类性 第一章绪论 ( c l u s t e r i n g ) 、连接度分布( d e g r e ed i s t r i b u t i o n ) 、小世界( s m a l l w o r l d ) 以及无 标度( s c a l e f r e e ) 【8 一l o 】等复杂网络的基本结构特性对拥塞博弈和雪堆博弈的动 力学自适应演化行为的影响，揭示其基本现象和基本规律，从而寻求导致最优化 集体有效性的网络结构。下面介绍本文的基本概念及复杂网络上博弈问题的研究 进展。 1 2 酒吧问题 拥塞博弈的概念是r o s e m h a l 于1 9 7 3 年提出来的【1 1 。拥塞博弈分为对称博 弈和非对称博弈。对称博弈指的是选择同一个资源的参与者的收益相同。非对称 博弈指的是选择同一个资源的参与者的收益因人而异i l l 】，这类博弈大多用于描 述生态领域的问题 1 2 - 1 5 。拥塞博弈可以用来模拟现实生活中的多种实际问题， 例如模拟高峰时期的交通 1 6 1 、i n t e m e t 拥塞现象【1 7 】或者一群动物的觅食现象【1 8 】 等等。而酒吧问题是原始拥塞博弈的一种简化模型。 1 2 1 问题的提出 酒吧问题是美国著名经济学家a r t h u r 于1 9 9 4 年在美国经济评论上发表 的题为归纳推理和有界理性 2 1 一文中提出的，后来他在1 9 9 9 年的科学 杂志上发表的复杂性和经济学【1 9 】一文中阐述了这个博弈。a r t h u r 是斯坦福 大学的经济学系教授，同时也是美国著名的研究复杂性的圣菲( s a n t af e ) 研究 所的研究人员。他认为经济主体或参与者的行动是建立在归纳推理基础之上，而 不是传统经济学所认为的演绎推理的基础之上。酒吧问题就是为了说明这个想法 而提出来的。 e lf a r o l 是圣菲研究所所在地的一间酒吧，每周四晚上该酒吧都会有爱尔兰 音乐演奏。假设共有( = 1 0 0 ) 个人，各自独立决定周四晚上去酒吧欣赏音乐 还是留在家里看电视。由于酒吧的容量是有限的( 比如空间有限或者座位有限) ， 如果人数不超过c ( = 6 0 ) ，人们可以惬意地欣赏音乐；如果人数超过了c ，酒吧 2 上海交通大学博士学位论文 会变得嘈杂拥挤，人们无法悠闲地欣赏音乐，都会感到不愉快，此时留在家里比 去酒吧更舒服。每个参与者在决策之前首先预测当晚去酒吧的人数 2 0 ，2 1 ，如 果预测的结果不超过c ，他会去酒吧；否则留在家里。 酒吧问题与各种实际的拥塞问题具有多个共同点，比如多用户共同分享资源 ( 道路、网络服务器以及酒吧等) ；参与者在动态环境下相互作用，协调行为； 多数情况下参与者基于部分的、冲突的信息做出决策。因此对酒吧问题的深入研 究有助于更好地理解各种实际的拥塞现象，进而提供有效的避免和控制捌塞的决 策方案，以使资源得到合理充分的利用。而且酒吧问题被认为是复杂自适应系统 的范例 2 2 1 ，因此对它的研究也有助于更好地理解一些实际的复杂自适应系统， 如i n t e r n e t 、生态系统和金融市场【2 3 】等。 1 2 2 理性与预测性 由于每个参与者根据自己的利益进行独立的决策控制，因此酒吧问题是一个 重复的非合作博弈。非合作博弈理论最核心的内容是纳什均衡( n a s he q u i l i b r i u m ) 【2 4 。纳什均衡的概念是数学家n a s h 在其博士学位论文中最早提出来的，后经 整理成文发表出来，其定义如下： 给定一个策略组合盯( 纯策略或混合策略) 。如果对任意的参与者i 的任意 策略置e s , ( 墨是参与者f 的策略空间) ，都有 峨( 西，o - ；) 峨 ，盯二)( 1 - 1 ) 成立，那么盯称为一个纳什均衡。其中u 。表示参与者i 的收益，z 表示盯+ 中参 与者i 的策略，矿；表示除了参与者i 之外其他参与者的策略构成的策略组合。 但是对于酒吧问题，收敛于纳什均衡的两个充分条件理性和预测性不能 同时并存1 2 5 ，2 6 。理性是指人们会对自己的信念( b e l i e f ) 做出最佳反应。最佳 反应意味着采取的策略所带给参与者的收益，不小于其他任何策略能够带来的收 益。预测性是指信念与最后的结果一致。为了直观地理解，假设参与者预测酒吧 不拥塞的概率为p ，理性反应是当p 1 2 时去酒吧。如果参与者都能够准确地 3 第一章绪论 预测，那么预测结果应该与事实相符。但是这翟出现了矛盾：如果参与者预测酒 吧不拥塞的概率p c1 2 ，但实际上不拥塞的概率为1 ；如果参与者预测酒吧不拥 塞的概率p ，1 2 ，但实际上不拥塞的概率为0 。因此如果参与者是理性的并且采 用了预测性的学习算法，他们的信念不会收敛，博弈结果也不会趋于纳什均衡。 如果博弈结果收敛于纳什均衡，那么人们或者是非理性的或者没有采用预测性的 学习算法。这一结论不依赖于初始条件的选取【2 7 】。 如果把酒吧问题看作预测博弈 2 8 1 ，那么参与者的策略集合是0 到的一个 整数集合。每个人的收益等于自己的策略与酒吧人数之差的负绝对值，所以预测 越准确，收益越高。该预测博弈没有纯策略的纳什均衡。在混合策略纳什均衡中， 策略小于c 的参与者的平均人数恰好等于c 。分析表明酒吧平均人数的经验分布 收敛于预测博弈的一组相关均衡 2 9 1 ，而相关均衡又等价于混合策略的纳什均 衡。所以从仿真结果看到酒吧人数在c 附近上下波动，尽管初始条件是确定的， 结果看起来却好像是由随机过程产生的。 1 2 3 避免拥塞的学习算法 酒吧问题的参与者都是自私的，但是资源是有限的，每个人都希望去酒吧并 且希望去的人数不超过最优值。为了抑制和避免拥塞，使资源得到有效的利用， 近年来研究学者提出了一系列的自适应学习算法，如最小二乘法【3 0 3 2 、虚拟 博弈法【3 3 】以及无悔学习法【3 4 】等。 i最小二乘法 该算法假设参与者不需要预测酒吧的人数，而是通过自己的真实经历调整去 酒吧的概率。假设参与者f 最初去酒吧的概率为a 。令为控制参数，y ) 表示 k 时刻酒吧的人数，有 ) ， ) - 艺薯 ) ( 1 - 2 ) 4 上海交通大学博士学位论文 其中耻) 的值为1 的概率是n ) ，值为0 的概率是1 一只 ) 。基于信号处理中 的最小二乘算法【3 5 】，概率b ) 的演化规则如下： b ( 七4 - 1 ) 一只 ) 一一( y ( t ) 一c 地 )( 1 3 ) 当参与者应用上述算法调节自己的行为时，酒吧人数很快地趋近最优值c ， 而且波动很小。个参与者中有c 个人的概率最后接近于1 ，一c 个人的概率 接近于0 。 i i 虚拟博弈法 虚拟博弈法假设参与者基于自己去酒吧的次数计算两个事件的经验分布 拥 塞，不拥塞) 【3 3 】。令参与者f 的初始控制参数包( o ) 一0 ，q ( o ) = 0 ，演化规则如下： 啪岫叫：嬲y ( k ) ，= c 。a 删n d x 删i ( k ) = ： ( 1 - 4 ) - m 她鼢惦蒜： m s ， 其中) ，( 七) 表示女时刻酒吧的人数，薯 ) 1 ，o ) 表示七时刻参与者f 的选择，其中 “1 ”表示去酒吧，“0 ”表示留在家里。 因此，参与者i 在下一时刻去酒吧并且酒吧不拥挤的条件概率是 p f + 1 ) - 岛 + 1 ) c j + 1 ) 。假设参与者去酒吧而且酒吧不拥塞时的收益为+ 1 ， 拥塞时的收益为一1 ，留在家里的收益为0 ，其在k + 1 时刻的期望收益为： 。 + 功f 卜n 等+ 9 + 卜d o 一只 + 坳爹耄篓： c - 一回 其在k + 1 时刻采取的策略五0 + 1 ) 满足下面的条件： 毛 + 1 ) 8 f g j ! 豁e z ( 七+ 1 ) ) ( 1 。7 ) 利用虚拟博弈法得到的结果与最小二乘算法相似，去酒吧的人数接近于最优 值c ，其中一部分参与者的概率趋近于1 ，另一部分参与者的概率趋近于0 。 5 第一章绪论 i i i 无悔学习法 该算法的思想基于指数更新的机制【3 6 】。令( 七) 札0 ) 表示七时刻参与者j 的选择，其中“1 ”表示去酒吧，“0 ”表示留在家里。u 让) 表示参与者i 的策略 墨在t 时刻的累积收益，即 ) 一：。吩 o ) ) 策略薯在t + 1 时刻的权值定义 为： 似垆器 m s ， 厶罔o j “ 其中卢，0 为常数【3 4 】。参与者i 采取某个策略的概率与该策略的权值成正比。 当参与者利用无悔学习算法调节自己的行为时，结果显示酒吧人数在最优值 c 附近上下波动，但人数的平均值趋近于c ，因此参与者去酒吧的平均概率趋近 千c | n ， 1 3 少数者博弈 少数者博弈( m g ) 【3 】是酒吧问题的一个简化模型，其反映了社会经济活动中 众多千差万别的参与者对有限资源竞争的基本特征，思想是金融市场中的普遍原 则少数人获胜。例如，对于某一股票的买卖，如果买方人数多于卖方人数， 会导致股票价格的上扬，因而处在少数者的卖方的交易者是有利的。通过对少数 者博弈这一简单模型的研究，人们对类似的复杂适应系统的理解有了显著的进展 4 。3 7 ，并取得了大量的研究成果。本节重点介绍关于少数者博弈的主要研究进 展及与我们的研究工作相关的内容。 1 3 1 少数者博弈模型 少数者博弈模型假设共有n ( n 为奇数) 个参与者，在某一时刻他们各自 必须独立地选择a 组或b 组( 如表示去酒吧或留在家里) 。当所有参与者都做出 6 上海交通大学博士学位论文 选择后，人数少的那一组的人为获胜方，人数多的那一组的人为失败方。每个参 与者根据过去获胜方( 人数少的那个组) 记录的公共信息做出决定。假定记录仅 告知哪个组为获胜方，而不告知实际的获胜人数，则此信息可以用二进制序列表 示：当a 方为获胜方时用“1 ”表示，否则用“0 ”表示。而且假定参与者的记 忆容量有限并且相同，每人只能记住最近m 次的获胜方记录，并依据这一历史信 息做出下一轮选择哪个组的决定。对于给定的每一种历史，都可以有2 种不同选 择。每一种不同选择，构成参与者的一个策略。对于给定的记忆容量m ，共有2 用 种不同的历史，因而共有2 ，种不同的策略。表卜1 列出了研= 2 的所有策略。 在博弈开始的时候，每个人随机从含有全部策略的策略库中选取s 个策略 ( s z3 ，4 ，) ，允许重复。每一轮博弈结束后，获胜者的收益( 少数者) 加 一分，失败者( 多数者) 的收益减一分，这是一种最简单的记分规则。每个参与 者为了从手中的s 个策略中挑选最优策略，会给每个策略打分( 称为虚分) 。若 某个策略预测了正确的少数方( 不管该策略是否被选用) ，它的虚分加一分，反 之减一分。在每一轮决策时，参与者总是采用s 个策略中累积虚分最高的策略来 决定选那个组。 表1 - 1m 2 的所有策略 t a b l e1 - 1a l ls t r a t e g i e sw i t hm - 2 历史 策略l簧略2策略1 5簧略1 6 0 000ll 0 l00ll 1 00 、0 ll l l 0 l 01 1 3 2 少数者博弈的相变行为 虽然按照模型的定义，参与者都是独立的理性个体，每人只追求自己获取最 7 第一章绪论 大利益而不考虑他人。然而在某种程度上这些参与者能够通过策略的变更而显示 出对于整个社群的适应性，他们能够相互协调彼此合作而使整个社群达到资源优 化配置的最佳状态。 在给定和s 的条件下，随着m 的由小增大，可以发现参与者的协调性在不 断改变【3 8 】。选择a 组人数的标准偏差仃随m 的变化曲线见图卜l 。标准偏差口 定义为： 盯= i 耄( a ( t ) - a ) 2 ( 1 9 ) 其中一( f ) 表示a 组的人数，j 一亭：。爿( f ) 表示平均人数。随着埘的改变，仃不 是单调变化的，系统在小m 和大m 时的行为有很大不同，存在一个从有效相到 非有效相的转变。“有效”一词来源于有效市场理论 3 9 1 ，指的是市场有效时参 与者不能利用信息在市场上获利。当m 较小时，系统处于有效相，参与者的自适 应性差，导致了较大的盯；当m 较大时，系统处于非有效相，参与者可以协调自 己的行为，特别是当m 增加到用。( 2 2 一n x s ) 时，参与者之间呈现出最佳的 合作。然后随着m 的进一步增大，参与者之间的协调性减弱，直至m 很大 ( 2 x 2 ”n s ) 时，整个系统接近于随机选择博弈( r a n d o mc h o i c eg a m e ，r c g ) 的极限：每个人完全随机独立地选择自己的行动，而不依赖于任何获胜方历史的 观察和策略的选择。一个随机博弈的参与者可以简单地通过抛一枚硬币来决定自 己的行动，若硬币正面朝上，他就选择a 组，否则选择b 组。 有效相与非有效相的出现主要归因于周期2 动力学过程 4 0 ，4 1 与参与者之 问协调效应 4 2 的竞争。当m 较小时，周期2 动力学过程占主导地位，例如，当 某一历史信息第一次出现时，参与者的选择相当于随机做出的决定，使得少数方 的人数接近总人数的一半，而当该历史信息第二次出现时，群集行为出现了，很 多人选择该历史第一次出现时的获胜组，这样一来该历史第一次出现时的失败组 会变成获胜组，并且少数方的人数很少，导致了标准偏差很大，以后遇到相同历 史信息时，上述两种情况交替出现；而当m 较大时，嵌入的周期2 动力学不是很 明显，参与者之间的协调效应居于主导地位，使得标准偏差小于r c g 的极限值。 而且还证实在近似情况下，仅仅是变量矿的函数。 8 上海交通大学博士学位论文 图1 - 1 口与m 的关系曲线，其中n - 1 0 1 ，j 2 ( 见文献【3 8 1 ) f i g 1 - 1 oa sa f u n c t i o n o fmf o rn - 1 0 1a n ds 一2 ( s e e r e f e r e n c e 【3 8 ) l 3 3 历史信息的相关性 少数者博弈的参与者根据过去m 次的获胜方记录进行决策，这些历史记录是 人们所知道的唯一信息。文献 4 3 用随机生成的m 位的二进制序列代替真实的历 史信息( 即获胜方记录构成的历史) ，通过比较发现基于真实信息和基于虚假信 息的系统行为是相同的。因此，作者得出了历史信息不相关的结论，即少数者博 弈的基本特性不依赖于参与者对真实历史信息的记忆，关键在于大家享有的是一 组相同信息，而不管这些信息是真实的还是虚假的。 随后的研究展开了对少数者博弈模型中历史信息相关性的讨论。文献 4 4 研究的混合人群模型假设参与者的共享信息不相同，人群中有两种不同记忆容量 的参与者，其中从个人的记忆容量m 一3 ，n 6 个人的记忆容量m 一6 ，总人数 n - n 3 + n 6 。在真实历史信息下，这种混合的记忆结构可以使系统的平均成功 率在人群的某种组合( 以3