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

1、认知无线网络行为分析与网络效能研究V1.0.0 (2011- 04-26)973项目；认知无线网络的全局性能优化；纳什均衡及帕累托最优的相关定理；简介本文档主要分两大部分： 第一部分，主要是纳什均衡的存在性与唯一性证明定理。第二部分，帕累托最优的相关定理。纳什均衡纳什均衡定义 行动组合s* = (s , s ,., s )是纳什均衡，则对于任意参与者i e K，有： 12ku (s ,s *) u (s,s *) for all sf e S i i - ii i - ii i简言之，就是给定其他参与者策略的情况下，每个参与者选择使自己效用最大化的策略。所有参与者的策略构成的组合即为纳什均衡。

2、2.1存在性定理定理21112：对所有的i e K，策略空间S (i = 1,2,., K)是欧式空间中一个非空的、紧的凸集;效用函数u (s)是连续的且对s是拟凹的。说明：在数学中，欧几里得空间Rn的子集S是紧的，如果它是闭合的并且是有界的。(注:若不是在欧式空间中，闭合且有界的集合不一定是紧集。)如果一个集合所有的极限点都是这个集合中的点，那么这个集合是闭集。S是凸集是指，对满足05 s ， u (s) 一 u (s , s )是不减的。i iii i i则称G为超模博弈。说明： 上半连续：设X为拓扑空间， e X，而f : X t R为实值函数。若对每个 0都存在x0的开邻域U使得Vx

3、e U, f (x) f (% ) +，则称f在x0 上半连续。该条件也可以用上极限等价地表述：lim sup f (x) 进一步地，若任意i,七具有二阶导，对于所有的i e K，满足(1)，则该博弈称为 超模博弈(Supermodular games)。82 ul 0, V i 尹 j e K(1)8 s 8 s i j同理，满足(2)式，称为次模博弈(Submodular games)。(2)d2 ul 0 =i i - i i i - iP (a , a ) 一 P (b , a ) 0，i -i则定义为次序位势博弈 Ordinal potential games。2.2唯一性定理定理

4、2.2.1(41：对于一个PGs，如果(1)策略组合S是紧的、凸的；(2)P是在S上连续可微函数， 且对S是严格凹的，则纳什均衡唯一。定理 2.2.2(51：如果最佳响应函数是标准的，则存在唯一纳什均衡。定义3 (标准函数)r (c)是标准函数，应满足：正：r (c) 0 ；单调性：if c c then r(c) r(c)； 可扩展性：for all R 1, Rr(c) r(pc)。定义4 (最佳响应Best Response)B (a ) = a e A : u (a , a ) u (a , a ), Va e Ai ii i i i ii i ii帕累托最优帕累托最优定义一个策略组合

5、sPO = (s , s ,., s )称为帕累托最优，如果不存在其他 12k策略组合s，使得for all i e K, u (s) u (sPO )for som e i e K, u (s) u (sPO )也就是不可能在不损害任何人的前提下，使某一些人的效用得到提高。一个重要结论：对于每一个使得和效用最大(max X u (s)的策略组合s，都是帕累托最优。iie KUtility possibility set图3-2帕累托最优示意图参考文献C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, “Efficient power cont

6、rol via pricing in wireless data networks,” IEEE Transactionson Communications, vol. 50, pp. 291-303, February 2002.D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.D. Topkis, “Equilibrium points in non-zero sum n-person submodular games,” SIAM J.Control Optim., vol. 17, no. 6

7、, pp. 773-787, 1979.G. Scutari, S. Barbarossa, and D. P. Palomar, “Potential games: A framework for vector power control problems with coupled constraints,” in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Processing, Toulouse, France, May 2006, vol. 4, pp. 241-244.R. D. Yates, “A framework for uplink power control in cellular rad