纳什均衡和帕累托最优的相关定理

认知无线网络行为分析与网络效能研究V1.0.0(2011-04-26)973项目；认知无线网络的全局性能优化；纳什均衡及帕累托最优的相关定理；简介本文档主要分两大部分：>第一部分，主要是纳什均衡的存在性与唯一性证明定理。>第二部分，帕累托最优的相关定理。纳什均衡纳什均衡定义行动组合s*=(s,s,...,s)是纳什均衡，则对于任意参与者ieK，有：12ku(s,s*)>u(s',s*)forallsfeSii-iii-iii简言之，就是给定其他参与者策略的情况下，每个参与者选择使自己效用最大化的策略。所有参与者的策略构成的组合即为纳什均衡。2.1存在性定理定理2・1・1[1][2]：对所有的ieK，策略空间S^(i=1,2,...,K)是欧式空间中一个非空的、紧的凸集;效用函数u(s)是连续的且对s^是拟凹的。说明：在数学中，欧几里得空间Rn的子集S是紧的，如果它是闭合的并且是有界的。(注:若不是在欧式空间中，闭合且有界的集合不一定是紧集。)如果一个集合所有的极限点都是这个集合中的点，那么这个集合是闭集。S是凸集是指，对满足05<1的人，只要XeS,犬S，那么就有人X+(1-人)yeS。简单而言，就是S中的任何两点之间的直线段都属于S。图2-1左图为凸集，右图为非凸集定理2.1.2[3]：如果一个博弈G是S-模博弈(S-modulargames,SMG),则至少存在一个纯纳什均衡。定义1(S-模博弈S-modulargames,SMG)一个博弈G,如果满足：VieK，S是欧式空间中的一个紧集；u在s上是上半连续；VieK,Vs>s'，u(s)一u(s,s')是不减的。—i—iiii—i则称G为超模博弈。说明：>上半连续：设X为拓扑空间，％eX，而f:XtR为实值函数。若对每个£>0都存在x0的开邻域U使得VxeU,f(x)<f(%)+£，则称f在x0上半连续。该条件也可以用上极限等价地表述：limsupf(x)<f(xo)xtx0图2-2上半连续函数的例子(蓝点表f(xo))图2-3下半连续函数的例子(蓝点表f(x0))>进一步地，若任意i,七具有二阶导，对于所有的ieK，满足(1)，则该博弈称为超模博弈(Supermodulargames)。82ul>0,Vi尹jeK(1)8s8sij

同理，满足(2)式，称为次模博弈(Submodulargames)。(2)d2ul<0,Vi尹jeKdsdsij(2)超模博弈和次模博弈统称为S-模博弈S-modulargames(SMG)。定理2.1.3E41：如果一个有有限个参与者的博弈是位势博弈(Potentialgames,PGs)，且策略集合是紧的，效用函数是连续的，则至少存在一个纯纳什均衡。定义2(严格位势博弈ExactPotentialgames，EPGs)如果存在一个函数P:A—R，满足VieK，有u(a,a)一u(b,a)=P(a,s)一P(b,a)ii-iii-ii-ii-i如果uke{uj处处二次可微时，一个博弈是EPGs的充分条件是62u(a)。2u(a)I=j6a6a6a6aijji类似地，满足u(a,a)一u(b,a)>类似地，满足u(a,a)一u(b,a)>0=ii-iii-iP(a,a)一P(b,a)>0，i-i则定义为次序2.2唯一性定理定理2.2.1(41：对于一个PGs，如果(1)策略组合S是紧的、凸的；(2)P是在S上连续可微函数，且对S是严格凹的，则纳什均衡唯一。定理2.2.2(51：如果最佳响应函数是标准的，则存在唯一纳什均衡。定义3(标准函数)r(c)是标准函数，应满足：正：r(c)>0；单调性：ifc>c'thenr(c)>r(c')；可扩展性：forallR>1,Rr(c)>r(pc)。定义4(最佳响应BestResponse)B(a)={aeA:u(a,a)>u(a',a),Va'eA}i—iiiii—iii—ii帕累托最优帕累托最优定义一个策略组合sPO=(s,s,...,s)称为帕累托最优，如果不存在其他12k策略组合s，，使得forallieK,u(s')>u(sPO)forsomeieK,u(s')>u(sPO)也就是不可能在不损害任何人的前提下，使某一些人的效用得到提高。一个重要结论：对于每一个使得和效用最大(maxXu(s))的策略组合s，都是帕累托最优。iieKUtilitypossibilityset图3-2帕累托最优示意图参考文献C.U.Saraydar,N.B.Mandayam,andD.J.Goodman,“Efficientpowercontrolviapricinginwirelessdatanetworks,”IEEETransactionsonCommunications,vol.50,pp.291-303,February2002.D.FudenbergandJ.Tirole,GameTheory.Cambridge,MA:MITPress,1991.D.Topkis,“Equilibriumpointsinnon-zerosumn-personsubmodulargames,”SIAMJ.ControlOptim.,vol.17,no.6,pp.773-787,1979.G.Scutari,S.Barbarossa,andD.P.Palomar,“Potentialgames:Aframeworkforvectorpowercontrolproblemswithcoupledconstraints,”inProc.IEEEInt.Conf.Acoustics,SpeechandSignalProcessing,Toulouse,France,May2006,vol.4,pp.241-244.R.D.Yates,“Aframeworkforuplin