納什均衡和帕累托最優(yōu)的相關定理

1、認知無線網(wǎng)絡行為分析與網(wǎng)絡效能研究V1.0.0 (2011- 04-26)973項目；認知無線網(wǎng)絡的全局性能優(yōu)化；納什均衡及帕累托最優(yōu)的相關定理；簡介本文檔主要分兩大部分： 第一部分，主要是納什均衡的存在性與唯一性證明定理。第二部分，帕累托最優(yōu)的相關定理。納什均衡納什均衡定義 行動組合s* = (s , s ,., s )是納什均衡，則對于任意參與者i e K，有： 12ku (s ,s *) u (s,s *) for all sf e S i i - ii i - ii i簡言之，就是給定其他參與者策略的情況下，每個參與者選擇使自己效用最大化的策略。所有參與者的策略構(gòu)成的組合即為納什均衡。

2、2.1存在性定理定理21112：對所有的i e K，策略空間S (i = 1,2,., K)是歐式空間中一個非空的、緊的凸集;效用函數(shù)u (s)是連續(xù)的且對s是擬凹的。說明：在數(shù)學中，歐幾里得空間Rn的子集S是緊的，如果它是閉合的并且是有界的。(注:若不是在歐式空間中，閉合且有界的集合不一定是緊集。)如果一個集合所有的極限點都是這個集合中的點，那么這個集合是閉集。S是凸集是指，對滿足05 s ， u (s) 一 u (s , s )是不減的。i iii i i則稱G為超模博弈。說明： 上半連續(xù)：設X為拓撲空間， e X，而f : X t R為實值函數(shù)。若對每個 0都存在x0的開鄰域U使得Vx

3、e U, f (x) f (% ) +，則稱f在x0 上半連續(xù)。該條件也可以用上極限等價地表述：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上連續(xù)可微函數(shù)， 且對S是嚴格凹的，則納什均衡唯一。定理 2.2.2(51：如果最佳響應函數(shù)是標準的，則存在唯一納什均衡。定義3 (標準函數(shù))r (c)是標準函數(shù)，應滿足：正：r (c) 0 ；單調(diào)性：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帕累托最優(yōu)帕累托最優(yōu)定義一個策略組合

5、sPO = (s , s ,., s )稱為帕累托最優(yōu)，如果不存在其他 12k策略組合s，使得for all i e K, u (s) u (sPO )for som e i e K, u (s) u (sPO )也就是不可能在不損害任何人的前提下，使某一些人的效用得到提高。一個重要結(jié)論：對于每一個使得和效用最大(max X u (s)的策略組合s，都是帕累托最優(yōu)。iie KUtility possibility set圖3-2帕累托最優(yōu)示意圖參考文獻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