（计算机软件与理论专业论文）网络中的纳什均衡与调和比率.pdf

摘要 本文综述了博弈论在网络中的应用和调和比率的计算在第一章中，简 述了博弈论和纳什均衡的基本概念：第二章蛤出了调和比率的定义以及相应 的一些结果；第三章证明了两个特殊时延函数下调和比率的上界第四章讨 论了网络纳什均衡的其他方面 我们的工作集中在m m i 时延函数下的平行网络在第三章中，我们证 明了，当连接个数为m 时，调和比率的上界为m ；在第四章中，我们给出了 不公平性的一个下界 关键词：博弈论，纳什均衡，调和比率，不公平性 1 本研究受到田家自然科学基金第6 0 2 7 3 0 4 5 号，科学技术部基础研究重大项目前期研究专 项第2 0 0 l c c a 0 3 0 0 号和上海市科档发展基金第0 2 5 1 1 5 0 3 2 号资助 m a b s t r a c t 2 i nt h i st h e s i s w ep r e s e n tt h ea p p h c a t i o no fg 8 i n et h e o r yi nt h ei n t e r n e t a n dt h ec o m p u t a t i o no fe o - c a l l e dc o o r d i n a t i o nr a t i o t h et h e s i si so r g a n i z e d a sf o l l o w s ：i nc h a p t e r1 w eg i v et h eb a s i ck n o w l e d g eo fg a m et h e o r ya n d n a s he q u i l i b r i u m ；i nc h a p t e r2 w eg i v et h ed e f i n i t i o no fc o o r d i n a t i o nr a t i o a n ds e v e r a lc o r r e s p o n d i n gr e s u l t s ；i nc h a p t e r3 ，w ef o c u eo nt w os p e c i a ll a t e n c y f u n c t i o a n ds h o wt h eu p p e rb o u n do fc o o r d i n a t i o nr a t i o ；i nc h a p t e r4 ，w e d i s c u s so t h e ra s p e c t so fn a s he q u i l i b r i u mi nn e t w o r k o u rw o r kw o l l l df o c u so n p a r a l l e ll i n k sn e t w o r kw i t hm m il a t e n c yf u n c - t o n s i nc h a p t e r3 ，w ep r o $ t h a tw h e nt h en u m b e ro fl i n k si sm ，c o o r d i n a t i o n r a t i oi su p p e rb o u n d e db ym ：i nc h a p t e r4 ，w es h o wal o w e rb o u n do fu n f a i r - n 鹤8 k e y w o r d s ：g a m et h e o r y ，n a s he q u i l i b r i u m ，c o o r d i n a t i o nr a t i o ，u n f a i r n e s s 2 t h i sw o r ki ss u p p o r t e db yag r a n tf r o mt h em i n i s t r yo fs c i e n c ea n dt c c h n o l o g yr g r a n t 2 0 0 1 c c a 0 3 0 0 0 ) ，n a t i o n a ln a t u r a ls d e n c ef u n d ( g r a n t6 0 2 7 3 0 4 5 ) a n ds h a n g h a is c i e n c e a n dt e c h n o l o g yd e v e l o p m e n tf u n d ( g r a n t0 2 5 1 1 5 0 3 2 ) 引言 互联网中，有着成千上万的用户，他们为着各自的利益独立衲柞出行动 并在相互之间发生联系这些行为包括合作和竞争，而在广大用户群之上并 不存在任何管理机构这种状况与博弃论中的非合作博弈有很多的相似之 处 博弈论是一种行之有效的分析工具，它的应用范围非常广泛，包括经济 学，政治学，困际关系，公共选择，甚至犯罪学等等我们将在第一章给出 有关博弈论和纳什均衡的预备知识 根据著名的纳什定理，在非合作网络环境下存在蚋什均衡在肯定了网 络纳什均衡的存在之后，一系列的问题接踵而至在如前所述的由自私用户 构成的网络中，是否存在唯一的纳什均衡2 若存在，是纯策略还是混合策 略? 在网络环境下，纳什均衡的效率又如何? 与社会最优值相比，相差多 少? 也就是说互联网的无组织结构对网络的性能究竟有多大影响? 为回答这些问题，特别是后面几个有关纳什均衡效率的问题，e k o u t s o u - p i a s 和c p s p a d i m i t r i o u 在w o r s tc ee q u i l i b r i a 一文中提出了一个全新的概 念：调和比率它被定义为纳什均衡与社会最优值在某个性能标准下的比 值我们将在本文的第二章和第三章围绕这一概念进行详尽的论述 除了前面介绍的有关调和比率的内容外，网络纳什均衡的研究领域还包 括许多其它的方面我们将在第四章对其中的b r a s 现象以及最优流的不公 平性进行探讨 我们的工作集中在m m i 时延函数下的平行网络在第三章中，我们证 明了，当连接个数为m 时，调和比率的上界为m ；在第四章中，我们给出了 不公平性的一个下界 第一章 博弈论与纳什均衡 博弈论是数学的一个分支，作为一种行之有效的分析工具，它的应用范 围非常广泛，包括经济学，政治学，国际关系，公共选择，甚至犯罪学等 等但博弈论在经济学中的应用最成功；博弈论的许多成果也是借助于经济 学的例子来发展的，因此很多人把它看作是经济学的一个分支 自上世纪中叶，博弈论诞生以来，计算机专家们就发现它在计算机理论 研究领域里，有重要的作用本文主要就是对博弈论在网络中的一些应用进 行论述 在这一章中，我们先做一些最基本的工作，简要的解释一下有关博弈论 的初步知识。 1 1 博弈论的基本知识 1 1 1 概念和定义 “博弃论”，英文为g a m et h e o r y ，即游戏理论。游戏有一个共同的特 点，即策略在其中起着举足轻重的影响和作用尤其当游戏参与者的初始条 件完全平等时，策略选择就成了游戏结果的唯一决定因素同时，在游戏 中，参与者之间的决策行为是相互影响的也就是说，个人的策略选择不仅 依赖于他自身，也依赖于他人的选择；个人的最优选择是其他参与者选择的 函数因此，博弈论就是研究决策主体的行为直接相互作用时的决策以及这 种决策的均衡问题 现在我们给博弈下一个定义：博弈即一些参与者，面对一定的环境条 件，在一定的规则下，同时或先后，一次或多次，从各自允许选择的行为或 策略中进行选择并加以实施，并从中各自取得相应结果的过程 2 由上述定义可以看出，一个基本的博弈主要由四个方面构成：f 1 ) 博弈 的参与者。只要是独立决策，独立承担结果昀一方，无论其组织的大小， 均视为平等的参与者，并称其为一个博弈方。( 2 ) 各博弈方各自可选择的 策略集合。不同的博弈方拥有不同的策略集合；策略集合可以有限，也可 以无限。( 3 ) 博弈的次序。有时各博弈方同时做出决策，有时他们的决策 有先后之分；不同的次序决定了不同的博弈，即使博弈的其他方面完全一 样。( 4 ) 博弈方的得益。各博弈方的每一组决策对应一个结果，该结果的量 化数值即为得益。得益是博弈方决策的目标，总是越大越好规定一个博弈 必须规定得益得益客现存在，但各博弈方并不一定充分了解各方的得蓝情 况除此之外，博弈论还有一个基本概念，“均衡”。均衡是指所有博弈方 的最优策略或行动的组合上述概念中，博弈方、策略、次序、得益统称为 博弈规则；博弈分析的目的是使用博弈规则决定均衡 在本文中的博弃有一个前提，那就是它们都是建立在“个体行为理性” 基础之上的。所谓个体行为理性，是指个体的行为始终都是以实现自身的最 大得益为唯一目标博弈论就是对上述定义的各种各样博弈进行分析讨论的 理论 1 1 2 博弈论的历史背景 一般认为，博弈理论开始于1 9 4 4 年由v o nn e u m a n n 和m o r g e n s t e r n 合 作的t h et h e o r yo fg 8 m 黜a n de c o n o m i cb e h a v i o u r 到5 0 年代，合作博弈 发展到鼎盛期，包括纳什( n a s h ，1 9 5 0 ) 和s h a p l e y ( 1 9 5 3 ) 的“讨价还价”模 型，g i l l i e s 和s h a p l e y ( 1 9 5 3 ) 关于合作博弈中的“核( c o r e ) ”的概念，以及其 他一些人的贡献 5 0 年代可以说是博弈论的巨人出现的年代合作博弈论在5 0 # - 毹达到顶 峰，同时非合作博弈论也开始创立纳什在1 9 5 0 和1 9 5 1 年发表了两篇关于 非合作博弈的重要支章；t u c k e r 于1 9 5 0 年定义了“囚徒困境”( p r i s o n e r s d i l e m m a ) 他们两个人的著作基本上奠定了现代非合作博弈论的基石 到6 0 年代后又出现了一些重要人物。s e l t e n ( 1 9 6 5 ) 将纳什均衡的概念引 入7 动态分析，提出了“精炼纳什均衡”概念；h a x s a n y i ( 1 9 6 1 - 1 9 6 8 ) 更* 把不 完全信息引入博弈论的研究然后在8 0 年代出现了几个比较有影响的人物， 包括k r e p s 和w i l s o n ，他们在1 9 8 2 年合作发表了关于动态不完全信息博弈的 重要文章。还有k r e p s ，m i l g r o m ，r o b e r t s 和w i l s o n1 9 8 2 年关于信誉问题的非 常有名的“四人帮模型” 博弈论在经济学中的绝大多数应用模型都是在7 0 年代中期之后发展起来 的大体从8 0 年代开始，博弃论运渐成为主流经济学的一部分，甚至可以 说成为微观经济学的基础1 9 9 4 年三位长期致力于博弈论的理论和应用研 究、实践的学者n a s h ，h a r s a n y i ，和s e l t e n 共同获碍诺贝尔经济学奖，则更使 3 博弈论作为重要的经济学科分支的地位和作用得到了最具权威性的肯定。 1 1 3 博弈的分类 在所有的博弈论模型中，基本的实体是博弈方。一旦定义了博弈方集 合，我们便可以区分两类模型：一类是以单个博弈方的可能行动集合为基本 元素；另一类是以博弈方群的可能联合行动计划为基本元素。称前一类为非 合作博弈，后一类为合作博弈在本文中，我们只讨论前者。 还可以从另外两个角度对博弈加以划分。根据博弈方行动的先后顺序， 博弈可以划分为静态博弈和动态博弈。静态博弈是指在博弈中，各博弈方同 时行动；动态博弈是指博弈方行动有先后，且后行动者能够观察到先行动者 所选择的行动另一个角度是博弃方对有关其他博弈方的特征、策略空间及 得益的知识若每一个博弈方对其他博弈方的特征、策略空间及得益有准确 的知识，称其为完全信息；否则，就是不完全信息 将上述两个角度的划分结合起来，就可以得到四种不同类型的博弈：完 全信息静态博弈，完全信息动态博弃，不完金叶富息静态博弈，不完全叶言息动 态博弈它们分别对应四个均衡概念：纳什均衡，子博弈精炼纳什均衡，贝 叶斯纳什均衡及精炼贝叶斯纳特均衡表1 1 概括了上面所讲的四种及对应 的四个均衡概念，也大致反映了三位诺贝尔经济学奖得主在非合作博弈论中 的地位。 静态动态 完全信息静态博畀；充奎信恩动态博弈； 完全信息纳什均衡：子博弈精炼纳什均衡； n a s h ( 1 9 5 0 ，1 9 5 1 )s e l t e n ( 1 9 5 6 ) 不完金叶富息静态博弈；不完全信息动态博弄； 不完全信息贝叶斯纳什均衡：精炼贝叶斯纳什均衡； s a r s a n y i ( 1 9 6 7 - 1 9 6 8 ) s e l t e n ( 1 9 7 5 ) 在本文中，我们主要讨论完全信息静态博弈，同时对完全信息动态博弈 也将有所涉及 还有其他的一些划分方法。例如根据博弈方的个数，博弈可以分为单人 博弈，两人博弈奉多人博弈。本文主要考虑多人博弈此外，根据博弈中的 得益，可以分为零和博弈，常和博弈以及变和博弈零和指各博弈方得益之 和总为零；常和指各博弈方得益之和总为常数，变和指各博弈方得益之和不 定。本文主要考虑变和博弈 4 1 2 几个典型的博弈问题 1 2 1囚徒的困境 我们先来看博弈论中最为经典的一个模型：囚徒困境。囚徒困境讲的是 两个嫌疑犯作案后被警察抓住，分别被关在不同的屋子里审讯( 非合作) 。警 察告诉他们：如果两人都坦白，各判五年刑；若两人都抵赖，各判一年；如 果一人坦白，一人抵赖，则坦白者无罪开释，抵赖者判八年刑。 囚徒b 坦白抵赖 撼噩 袁1 2 表1 2 给出了囚徒困境的策略式表述。每一囚徒有两个策略：坦白和抵 赖表中每一格有两个数字，第一个对应囚徒a 的得巫；第二个砷应囚 徒b 的得益策略形式又称标准形式，是博弈的两种表述形式之一( 另外一 种是扩展形式) ，它特剐方便于静态博弈分析。 在这个例子中，纳什均衡就是( 坦白，坦白) 。不论对方如何选择，个 人最优选择是坦白这是一种纯策略纳什均衡虽然从得益上看，( 抵赖， 抵赖) 对双方而言更理想，但它不满足个人理性要求，因此不是纳什均衡。 由此可见，纳什均衡往往是低效的 囚徒困境在现实生活中具有相当的普遍性，在市场竞争，环境问题、公 共资源开发利用以至军备竞赛中屡见不鲜，它反映了个人理性与集体理性之 间的矛盾 1 2 2 猜硬币博弈 这是一个古老的博弈两人通过猜硬币的正反面赌输赢，其中一人用 手盖住一枚硬币，由另一人猜是正面朝上还是反面朝上若猜对，则猜者 赢1 元；否则，猜者输1 元 我们不能像分析囚徒困境那样给出一个纯策略纳什均衡在这一博弈 中，取胜的关键是不能让另一方猜到自己的策略而同时自己又要尽可能猜出 对方的策略在多次重复中，如果双方的决策方式都正确，则我们可求得平 均的双方得益 5 猜硬币方 正面反面 盖硬币方主耋盛 表1 3 与猜硬币博弈情况类似的还有诸如田忌赛马，石头剪子布博弈等等这 类博弈不可能有确定性的解，它们需要用下一节所讲的混合策略来解决 1 2 3 性别战 性别战说的是，一男一女约会，或者去看足球比赛，或者看芭蕾舞演 出男的偏好足球赛，女的偏好芭蕾舞，但他们都宁愿在一起而不愿分开。 下表给出了得益矩阵 女 足球芭蕾 男嚣霈 表1 4 这个博弈有两个纯策略纳什均衡：( 足球，足球) ，( 芭蕾，芭蕾) 。 事实上，这个博弈还有一个混合策略纳什均衡类似的例子还有斗鸡博弈、 商场消耗战博弈等等这些例子充分表明了纳什均衡的多重性。我们将在后 面对纳什均衡的多重性进行更深层次的讨论。 1 2 4 s t a c k e l b e r g 寡头竞争模型 现在介绍一个经典的动态博弈，s t a c k e l b e r g 寡头竞争模型。某一市场 有礼个企业销售完全相同的商品，因为市场容量有限，因此在一定的价格水 平上该市场只能销售有限数量的该种商品。也就是说，能够将商品全部销出 的“市场出清价聿铲是投放到该市场上的该种商品总量的函数，商品总量越 大，市场出清价格就越低我们再假设企业的产量决策是各自独立的，企业 之间既没有相互的协商，也都不受任何的限制。 6 在这一博弈中，企业的策略就是选择产量。如果我们假设产量是连续可 微的，那么每个企业的策略空间就是无穷的，这意味着我们不能用图表的形 式表达这一博弈的得益情况。 与静态博弈不同，企业的行动有先后其中一个企业( 称其为领头企 业，l e a d e r ) ，首先选择产量铂o ；其它企业( 称其为尾随企业，f o l l o w e r ) 观测到吼，然后选择自己的产量吼0 因此这是一个完美信息动态博弈。 这一博弈体现了一个有趣的现象，即拥有信息优势可能使参与人处于劣势。 对这一博弈进行分析，需要用到子博弈精炼纳什均衡的概念，它的实质 是逆向归纳法理论的扩展也就是说，我们先分析尾随企业的得益，确定它 的理性行为，然后再分析领头企业的策略选择我们将在第四章中对这一模 型做深入研究 1 3 纳什均衡 1 3 1基本表述 为给出纳什均衡的正式定义，也为了以后讨论的方便，我们引入几个概 念的表示法我们常用g 表示一个博弈；如g 有n 个博弈方，每个博弈方的全 部可选策略的集合我们称为策略空间，分别用贝，叉表示；s d 最表 示博弈方i 的第j 个策略，其中j 可取有限个值( 有限策略博弈) ，也可取无 限个值( 无穷策略博弃) ；博弈方 的得益记为讹，u 是各博弈方策略的多元 函数n 个博弈方的博弈g 常写成g = s l ，叉；姓l 一，姓。) 定义1 1 在薄莽g = 品，最；l ，u 。) 尹，如果策略鲤舍( s i ，s ：) t 尹经一簿疹积的震略期是对其余搏痒方的策略红舍s 毛= ( s ，s ：- l ，s 磐1 ， ，s ：) 的最佳对策，也印 u i ( s ：，s 一* 。- ) u t ( 8 巧，s ：i ) ，v 5 “曼，v i 剧稀( s i ，3 ：) 为g 的一个纳什均衡 我们也可以用另一种表述方式，s ：是下述最大化问题的解： s ；a t m a x s l j e “u i ( s i d ，s 二) ， 从纳什均衡的定义可以看出，各博弈方都不愿单独改变策略的策略组合 就是纳什均衡在纳什均衡点，任何一方都不可能通过改变自己的策略来改 进自身的得益从博弈方的角度来看，纳什均衡时自己选择的策略即是最优 策略；尽管从系统角度来看，纳什均衡往往是低效的。 7 纳什均衡有纯策略和混合策略之分。如果博弈方在每一个给定的信息情 况下只选择一种特定的行动，称其为纯策略；反之，如果博弈方在给定信息 情况下以某种概率分别随机地选择不同的行动，称其为混合策略。在一些博 弈，如1 2 1 小节所讲的囚徒困境中，存在纯策略纳什均衡( 坦白，坦白) ： 但在其他一些博弈中，如1 2 2 小节所讲述的猜硬币就不存在纯策略纳什均 衡，但这一类博弈存在混合策略纳什均衡。我们将在下一小节中详细讲述混 合策略。 1 3 2混合策略 我们先给出混合策略的定义 定义1 2 在博并g = s l ，岛；u 1 ，u 。) 尹，烀彝庇的策略空问为 & = s 1 1 ，s 址) ，剧博劳虎以概率分希瓠= ( p i - ，p 塘) 飚祝迸择算介 可进策略襻力一个“混合策略”，算尹j 0 胁1 ，s t e p 玎= 1 ，忱 j = l 我们用仇= 仇慨，p i ) 表示博弈方 在混合策略慨，p i ) 下的期望效用函 数，它可以定义为：z ，：譬t 厶一t 炙) 地o i ，p t ) = e ( 功( 即) ) u t ( s ) ( 1 1 ) s si = 1 有了公式1 1 ，我们就可以将纳什均衡的概念扩大到包括混合策略的情 况 定义1 3 在搏并g = s l ，& ；札l ，u 。) 尹，稚_ ：；! 邑夸策略纽卸= ( 硝，碥) 是一个纳仟苟衡，当宫旖足： 饥妨，p 毛) 让( p i ，p ) ，v n ，v i 在猜硬币博弈中，盖硬币方以1 2 的相同概率随机选择出正面还是出反面 和猜硬币方以1 2 的相同概率随机选择猜正面还是猜反面就是一个混合策略 的纳什均衡这样的纳什均衡虽然不能明确告诉我们一次博弈中双方的具体 选择和博弈的确定结果，但却告诉了我们他们决策的具体方式，以及两博弈 方的期望得益： ；1 - 1 - 互1 i i ( 一1 ) + 荟1 i 1 1 + 互1 ；( 一1 ) = 0 8 即多次独立重复该博弈的结果应为不输不赢，则显然是这个零和博弃双方都 能接受的结果。 同样，在性别战中，当男的以2 3 的概率选择足球赛，1 3 的概率选择芭 蕾舞；女的以1 3 的概率选择足球赛，2 3 的概率选择芭蕾舞时，就构成了一 个混合襞略纳什均衡 1 4 纳什均衡的存在性与多重性 1 4 1 存在性 我们现在面临一个问题，即在允许采用混合策略的情况下，是否每个博 弈都有纳什均衡结论是不一定但纳什( 1 9 5 0 ) 证明，任何有限博弈都存 在至少一个纳什均衡。 定理1 1r 射仲均衡的存在栏定理：纳升，1 9 5 0 j 在一个有h 介搏瘁方的 孛弄g = s l ，一，文；u l ，u 。 尹，如果n 是有限的，且最都是有限桌，剧 访缚雾至少存在一介纳计动觎但可能包含混拿策略 但现实生活中使用的模型一般都是无限博弈，即博弈方有无穷个纯策 略所幸的是，每个博弈方有有限个纯策略只是纳什均衡存在的充分条件， 而不是必要条件但是，当博弈方有无穷多个纯策略时，纳什均衡的存在性 要求效用函数在纯鬣略上是连续的；否则，纳什均衡就可能不存在。 定理1 2f 纳仟均衡的存在拦定理2 ：g l i c k s b e r g ，j 9 船) 在一含辄个焯瘁方 的博弄g = s l ，& ；钍i ，钍。) 尹，妇果s ：是砍氏空闽上一个非空的、 用的，有界的凸集，且放用函数地( s ) 是连樊的，帮幺莓婷并存在一介混舍策 略纳什均衡 1 4 2多重性 在某种意义上，比存在性问题更复杂的是一个博弈可能有多个均衡。我 们已经看到，性别战有三个蚋什均衡，其中包括两个纯策略和一个混合策略 纳什均衡事实上，许多博弈都存在多个纳什均衡，有些博弈甚至有无穷多 个纳什均衡。 举个例子，分蛋糕博弈。考虑两个人分一块蛋糕，每个人独立的提出自 己要求的份额设岳l 为第一个人要求的份额，0 2 为第二个人要求的份额，如 果正l + 0 2 1 ，每个人得到自己要求的份额；否则，谁也得不到什么在这 一博弈中，任何满足o l + 霉2 = 1 的( 0 1 ，2 2 ) 都是纳什均衡，因而这个博弈有无 穷多个纳什均衡。 9 如前所述，博弈分析的目的是预测博弈方的理性行为方式。纳什均衡是 博弈方如何博弈的一致性预测：如果所有博弈方预测一个特定的纳什均衡将 出现，那么，理性行为将保证没有人会选择非纳什均衡的策略，这个纳什均 衡就会实际出现当一个博弈有多个纳什均衡时，要所有参与人预测同一个 纳什均衡会出现是非常困难的。不同的博弈方可能会预测不同的纳什均衡， 这将导致出现非纳什均衡例如，在性别战中，如果男的预期( 足球，足 球) ，而女的预测( 芭蕾，芭蕾) ，实际出现的就将是( 足球，芭蕾) 。 应该强调的是，是因为博弈方在预测上犯了错误，而不是因为博弈方预 测这个非纳什均衡结果全出现。在性别战中，若男的预期自己选择足球时， 非纳什均衡( 足球，芭蕾) 会出现，那么他就会选择芭蕾舞，结果就是纳什 均衡( 芭蕾，芭蕾) 。正是在这个意义上，我们说只有纳什均衡是一致性预 测，任何非纳什均衡都不可能成为一致性预期 不幸的是，当一个博弈有多个纳什均衡时，博弈论并没有一个一般的理 论证明纳什均衡结果一定会出现。因此，在后面的章节中，我们会重点关注 一些特定环境下纳什均衡的唯一性定理 1 5小结 本章介绍了博弈论的历史背景，基本定义和一些经典博弈。同时对博弃 论中最重要的概念，纳什均衡的定义，存在性和多重性以及其他相关内容作 了详尽的论述本章内容主要参考张维迎的博弈论与信息经济学 2 8 】和 谢识予的r 经济博弈论f 2 7 若想对博弈论有更深一步的了解，还可以参 考m m a r t i n ，a r u b i n s t e i n 的ao o u r e e 讯g a m et h e o r yf 1 8 】和g o w e n 的 g a m et h e o r y 【1 9 1 。 1 0 第二章 调和比率 博弈论作为分析理性行为的理论在上世纪d a v o n n e w m a n n 和m o r g e n s t e r n 创立之后，计算机学家就发现它可以在计算理论中起重要作用。下界的证明 往往可以看成是算法设计者及其对手之间的博弈 2 6 】；两人博弈则在有限模 型理论中被视为重要的复杂性示例和工具( e h r e n f e u e h t ，f r a i s s d ) 。 纳什均衡的计算本身即被认为是一个富有挑战性的课题。n k f i r d a h a v ， d m o n d e r e r ，和m t e n n e n h o l t z 8 1 证明，社会福利的最优化问题是n p 难的。 p a p a d i m i t r i o u 提出，在两人有限博弈中，计算纳什均衡的复杂度在p 和n p 之 间 1 6 ，17 他甚至认为在确定p 问题的边界中，纳什均衡的计算是最重要的 问题此外，如果我们从均衡的角度分析拥塞控制，那么它实质上就是一 个合作博弈f 7 ，1 2 1 ：而在分布式计算的研究领域里，博弈论也起着重要的作 用f 6 1 正式提出博弈论有可能成为计算机理论研究中里程碑式的工具的是p a p a - d i m i t r i o u 的a l g o r i t h m 8 ，g a m e 镕，a n dt h e n t e m e 卜文他在文中提到，随着 互联网在计算机理论研究申成为主要的模型和对象，鉴于它庞大、无序的特 性，博弈论将成为对网络进行分析和计算的重要工具博弈论和算法思想的 结合代表了计算机理论发展的新方向f 1 2 1 这一趋势源于互联网与其它的计算机系统之间巨大的差异在互联网 中，有看成千上万的用户，他们为着各自的利益独立的作出行动并在相互之 间发生联系这些行为包括合作和竞争，而在广大用户群之上并不存在任何 管理机构。这种状况与博弈论中的非合作博弃有很多的相似之处既然如 此，那么根据纳什定理，在网络模型下就存在纳什均衡9 ，1 4 ，1 5 1 。在肯定了 网络纳什均衡的存在之后，一系列的问题接踵而至在如前所述的由自私用 户构成的网络中，是否存在唯一的纳什均衡? 若存在，是纯策略还是混合策 略? 在网络环境下，纳什均衡的效率又如何? 与社会最优值相比，相差多 少? 也就是说互联网的无组织结构对网络的性能究竟有多大影响? 为回答这些问题，特别是后面几个有关纳什均衡效率的问题，e k o u t s o u p i a s 和c p a p a d i m i t r i o u 在w o r s te a s ee q u i l i b r i a 【1 6 一文中提出了一个全新 的概念：调和比率。它被定义为纳什均衡与社会最优值在某个性能标准下的 比值我们将在本文的剩余章节围绕这一概念进行详尽的讨论。 2 1 调和比率的定义 如前所述，互联网中的用户都是自私的，他们的决策行为都是自发并且 是独立的；另一方面，对于用户们的种种行为，互联网又缺乏有效的管理。 这种非合作的无组织状态导致整个网络呈现出一种纳什均衡。对网络中纳 什均衡( 以后简称网络纳什均衡) 的研究早在l - 幽5 5 0 年代1 ，2 5 1 就已开 始。b e c h m a n 【l 】注意到了网络通信中的非合作状况，并发现纳什均衡流在 本质上是其相关的凸规划的最优解。d a f e r m o s 和s p a r r o wf 3 1 可能是最早对纳 什均衡的性能进行有效计算的计算机专家在他们之后，许多人做了大量的 工作，给出了一系列改进的方法 然而，众所周知，纳什均衡以它的低效性而著称【3 】在很多场合下，纳 什均衡的性质比最优解差很多；有时这种差距甚至是趋于无穷的( 我们在后 面就会给出一个这样的例子) 低效性在很大程度上限制了对纳什均衡的研 究，这促使计算机学家们从另外的角度来看待纳什均衡的计算问题。 k o u t s o u p i a s 和p a p a d i m i t r i o u 的w o r s tc a s ee q u i l i b r i a 1 6 1 一文，在网络 纳什均衡的研究上，是具有里程碑意义的。在该文中，他们提出了衡量纳什 均衡优劣的一个全新而又重要的概念：调和比率调和比率衡量了纳什均衡 与社会最优值之间的差距，它被定义为最坏情形纳什均衡与社会最优值之间 的比率 调和比率的概念提出之后，对它的研究主要在两个模型之下进行。我们 将先简述这两个模型，然后再给出调和比率的确切定义在本章，我们主要 考虑静态博弈，在2 3 5 节中对动态博弈也进行了讨论。 2 1 1 模型1 ( 用户集合有限) 我们先给出k o u t s o u p i a s 和p a p a d i m i t r i o u 所用的模型，即最简单的但 也是最县理论价值的平行网络模型网络由一个公共源节点和目标节点 以及一些平行连接构成，并且连接的时延函数为线性形式记连接集合 为c = 1 ，m ) 。由于只考虑线性时延函数，记连接2 的速度为功不失一 般性，设口1 。记用户集合为z = 1 ，礼) ，每个用户i 都有一个通 信需求一，t z 1 2 给定上述定义，这个问题实质上就可以看成是m 个连接，扎个独立任务且 每个任务i 的长度为一的一个调度问题。对每个用户而言，他的纯策略空间 是 1 ，m ，而混合策略则是该集合上的一个概率分布。令( f 1 3 一，i 。) 是一组纯策略，那么定义用户i 的代价函数如下： j i ( f 1 i 一，k ) = 一 k = i ， 在这一情形下，求解社会最优值类似于一个装箱问题( 将重量分别 为r 1 ，p 的东西装入m 个大小相同的箱子里) ，因此它是一个n p 难的 问题。 在这一模型中，主要考虑混合策略。 2 1 2 模型2 ( 用户集合无限) 现在，我们考虑另外一种模型：用户集合无限，并且每个用户只控制总 需求量中很小的一部分。事实上，这种情形更符合互联网的实际状况在这 一假设下，总通信需求在网络各条路径上的分配就可以看成是一网络流，它 满足任意两个节点之间的总流量等于谊两点之间的总需求 在这一非合作环境下的纳什均衡，就对应于在给定两个节点之间的所有 路径都具有相同时延的网络流这是因为若流不满足这一性质，那么有些用 户就可以通过改变自己的策略，选择一些负栽较小的路径，从而改善自己的 总时延。我们先给出前述“流”的确切定义 定义2 1 彦町j 宏是一含函敷，：p _ 冗+ ，这里的p 是路径集合对任意一 个连擒，及给建的兢，定义，i = p l e ，p 。当p e p ，p = r 对，称流，为 旷行浣 有了流的定义，以后我们称纳什均衡对应的流为纳什均衡流；而称社会 最优值对应的流为最优流 和上一节类似，定义时延函数为乃( 矗) = e e p t , ( f 0 同样，要求丑连 续，非降代价函数为： 彤) = 耳( 厶) 厶 p p 对上式作适当变形并对路径中所有的边求和，可以得到： j ( ，) = e 丑( ，1 ) ，l j c 1 3 我们注意到，尽管在经典博弈论中，经常采用的是混合策略，包括将要 讲9 的p a p d i m i t r i o u ，o r d a 等人的工作；但由于在这一模型中，每个用户只控 制总需求量中很小的一部分，因此混合襞略与纯策略完全等价。以后，当考 虑模型2 时，我们只需研究纯策略纳什均衡。 2 1 3 调和比率的最初定义 在这里，我们只给出k o u t s o u p i a s 乖, p a p a d i m i t r i o u 对调和比率的最初定 义即采用的是模型1 ，并且考虑混合策略；模型2 下调和比率的定义我们 将在对纳什映射的讨论之后给出。 假设用户i 以p 的概率选择连接f ，定义连接2 上的期望通信量为： 尬= p 扩 t 对用户i 而言，当他选择连接埘，他的代价为 毋= r + p t r t = 蚴+ ( 1 一p ( 2 1 ) t i i 纳什均衡的性质使用户不愿改变自己的策略，因此，用户e 只会考虑那些 能最小化j ：! ；的连接我们定义刃的最小值为： ，2 珥n j 同时，定义9 = u ：p o 2 用户 的支持集更一般的，令研为指示变 量，当p i o 时，它的值为1 。 现在，我们固定所有的鼋，就可以求得所有用户在纳什均衡下的策略。 p = ( 蚴+ 一一) r 满足限制条件： 屿= s t + 一一 v f c s t ( 尬+ 一一) = 一，v i z 显然，若由上述式子求得的所有p ：都在( o ，1 】之间，那么先前固定的研就 定义了一个纳什均衡由研的不确定挂，纳什均衡的数量应该是n 和m 萌指 数 1 4 给定一个纳什均衡，它的最坏期望值为 忙y s 忙i i 。p j , r 器 三一)f n = 1t = l：i = f ( 2 2 ) 我们称之为社会代价。调争比率就是社会代价与社会最优值之间的比率： c r = m a x c o s t o p t( 2 3 ) ( 2 3 ) 对所有均衡取最大值。 从上述讨论，以及( 2 3 ) 的形式中可以看出，调和比率的最初定义还是相 当繁琐的。这实际上也制约了对它的进一步研究在后面的章节中，我们将 会对调和比率的形式进行大幅度的简化。 2 2 唯一性和纳什映射 在上一节的末尾，我们提到调和比率的定义过于复杂，以至于影响了对 它的计算事实上，这种复杂性在很大程度上是由纳什均衡的多重性所造成 的这不禁引发了我们的思考，如果能证明网络纳什均衡的唯一性，或者给 出唯一性成立的条件，那么调和比率的研究工作不就大太的简化了吗? 本节 我们将对唯一性进行阐述，并由此将调争比率的形式加以筒化。 2 2 1 模型1 有很多计算机学家，特别是a o r d a ，r r o m 和n s h i m k i n 在这一方面做 了大量的工作。他们在c o m p e t i t i v er o u t i n gi nm u t t i u s e rc o m m u n i c a t i o nr i o t - w o r k s 1 3 】一文中从多个角度探讨了这一问题 a o r d a 和他的同事们考虑了与( 2 1 1 ) 节相同的模型。不失一般性， 设n r 。定义斤为用户i 分配到连接址：的需求部分的期望值。，f 0 ( 非负限制) 并且满足：l c 矗= 一( 需求限制) 对连接f ，记，f 为该连 接上的总流量，五= 讵z 露。 在这里，用户i 的策略记为一= ( 矗，矗) 。所有用户的策略组合记 为s = ( s 1 ，s ”) 当一个策略组合满足所有的非负限制和需求限制时， 称该策略组合为可行；记所有可行策略组合的集合为s 。每个连接都有一 个时延函数，记为丑( 五) ，丑( ，i ) 连续可微，非降且是凸的。对每个用户i ， 记刀( 疗，) 一疗互) ，j t 在靠上连续可微，并且是凸的现在我们可以定 义用户油代价函数如下： j 2 ( s ) = ：坷( ，? ， )( 2 , 4 ) l e 1 5 。 i i s0c 因为刃在，上连续可微，我们给出它的偏导数 脚= 筹缸z + 互 其中，可= 器。 一个可行的策略组合5 = ( 1 ，酽) ，当满足下述条件时 j i ( ) = j i ( 矿，i 一) = m i n ( 一，j 一) 矿 ( 2 5 ) ( 2 6 ) 我们称它为一个纳什均衡点。 事实上，在( 2 6 ) 中定义的最小化问题，等价于k u h n t u c k e r 条件：对每 一个i z ，存在一个l a g r a n g e 系数，该系数对任意的连接? c 成立， ， 0 _ 研( ，1 ) = ”( 2 7 ) ，f = 0 _ g t ( ，i ) ”( 2 8 ) a o r d a 给出了下面的定理，证明了在平行网络中，纳什均衡的唯一性。 定理2 1 f 1 3 1 在平行网络中。如暴所有用户的代价函数都如前邃定义那 么纳什均衡存在茅且唯一。 在定理的证明中，主要用到了k u h n - n c k e r 条件。 在给出了有关唯一性的证明之后，a o r d a 还发现了纳什均衡的一些性 质。这些性质对后面章节的内容有很大的帮助，故我们引用在下。 定理2 2h 3 1 在平行网络中若所有用户的代价函数都如前速定义。那么 对任意的两个用户t 和j ，若一一，则有鞋| 。v l c 。此外t 若一 和 那么等式成i 当且仅当f = f i = 0 上述定理表明，若所有用户的代价函数都连续可微，且是凸的，那么在 用户对连接的使用上呈现出一种单调性：需求更高的用户对每个连接的使用 更多从定理2 2 ，可以直接得到下面的推论： 推论2 1 p s i 对任意的两个用户i 和 。若一= 一则成立鞋= 馥1 v l c 。 显然，若所有的用户需求都相同，即一三r ，z ，那么对任意的f c 和i z ，戍| j ；= t h 。 另一个有关m m i 时延函数的重要定理，我们将在下一章给出m m 1 时延函数的定义后再引入 今后，若不加以特别说明，在我们的模型里，所考虑的时延函数都满足 连续可微，非降这两个性质。 1 6 2 2 2 模型2 前面说过，在模型2 中，我们只需考虑纯策略纳什均衡。r o u g h g a r d e n 2 1 给出了纳什均衡流的性质。 乱理2 1i 2 1 棼一令流量 为纳钟均衡漉，当且仅当对任意的吼。现，p 。 若厶。 0 帮么耳。( ，) 耳。( ，) 。 上述引理说明，当流量，为纳什均衡流时，所有分配到正流量的路径时延都 是相等的，我们将这个值记为l ( f ) r o u g h g a r d e n1 2 1 也考察了最优流的性质。在一个网络中，寻找最小总对 延实质上是一个非线i 生规划( n l p ) ： m i n l e c t i ( 五) 8 t ： 已e p 厶= r ，l = p l e p ，p 厶0 ， v l z v p p 我们令以( ，) ；p 一( 朋，运用k a r l l s h k u h n t u e k e r , , 定j e 【l 7 及上述凸 规划( n l p ) ，可以得到： 引理2 2 ，2 j ，一个漉量，为最优流，当且仅当对任意的p 1 ，p 2 - p ，若，p 。 0 ，币么( ，) 墨，( ，) 上述引理说明，当流量，为最优流时，所有分配到正流量的路径的，值都是 相等的，我们将这个值记为f ( ，+ ) 从引理2 1 和2 2 中，我们可以发现纳什均衡流与最优流有着惊人的相 似之处这一点最早为b e c h m a n 【1 】所注意，他将最优流解释为时延函数 为j m ) 形式时的纳什均衡流事实上，最优流与纳什均衡流的区别在于， 前者衡量的是每条连接所承受的总时延；而后者只是自私的衡量每条连接的 时延 b e e h m a n 对两者的相似进行了深层次的研究，他运用凸规划( n l p ) 的 方法证明了纳什均衡流的存在性以及在代价意义下的唯一性 乱理2 3 i i 一个网络若它的对延函数连续| 莽降。那么对任意一个 需求r 存在一个纳骨均衡流。此外，若| ，f 都是纳什均衡流，1 f 么j ( f 、= j ( f ) 2 2 3纳什映射 上两个小节的讨论，在很大程度上解决了纳什均衡的唯一性问题一旦 我们认可了在菜些模型下纳什均衡的唯一性，纳什均衡就和最优值一样，是 被完全定义的这引发了我们对纳什映射的思考。 纳什映射这一概念，最早由y k o r i l i s l o 提出。他根据a o r d a 1 3 用到 的模型以及相应的唯一性证明，指出在平行网络中，若固定总需求量r ，任 意一个容量配置对应于一个唯一的纳什均衡。纳什映射彤如：c - - ，可 以用( c ) 表述相应容量配置下的纳什均衡 现在我们固定容量，即认为连接v i i 容量c j 不变，那么由引理2 3 ， 可以得到，给定一个需求r ，实际上就确定了一个纳什均衡在这一情形 下，纳什映射形如 厂：冗- + ，。同样，我们可以用( r ) 表述相应需求下的 纳什均衡。 在本文中，给定n ( r ) ，我们主要考虑的是在这一纳什均衡下，网络 的总代价借用f r i e d m a n 5 】中的符号，我们定义纳什均衡流的代价函数 为y ( r ) ，最优流的代价m 数为o p t ( r ) 。定义r ( r ) = z 篙为调和函数。我 们将在本文的剩余部分使用这些符号 2 3 上界和下界 自从k o u t s o u p i 8 s 和p a p a d i m i t r i o u 给出调和比率的概念