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

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

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

3、e U, f (x) f (% ) +，則稱f在x0 上半連續(xù)。該條件也可以用上極限等價(jià)地表述：lim sup f (x) 進(jìn)一步地，若任意i,七具有二階導(dǎo)，對(duì)于所有的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：對(duì)于一個(gè)PGs，如果(1)策略組合S是緊的、凸的；(2)P是在S上連續(xù)可微函數(shù)， 且對(duì)S是嚴(yán)格凹的，則納什均衡唯一。定理 2.2.2(51：如果最佳響應(yīng)函數(shù)是標(biāo)準(zhǔn)的，則存在唯一納什均衡。定義3 (標(biāo)準(zhǔn)函數(shù))r (c)是標(biāo)準(zhǔn)函數(shù)，應(yīng)滿足：正：r (c) 0 ；單調(diào)性：if c c then r(c) r(c)； 可擴(kuò)展性：for all R 1, Rr(c) r(pc)。定義4 (最佳響應(yīng)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)定義一個(gè)策略組合

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 )也就是不可能在不損害任何人的前提下，使某一些人的效用得到提高。一個(gè)重要結(jié)論：對(duì)于每一個(gè)使得和效用最大(max X u (s)的策略組合s，都是帕累托最優(yōu)。iie KUtility possibility set圖3-2帕累托最優(yōu)示意圖參考文獻(xiàn)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