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

973-认知无线网络项目 认知无线网络行为分析与网络效能研究V1.0.0 (2011- 04-26)973项目；认知无线网络的全局性能优化；纳什均衡及帕累托最优的相关定理；1. 简介本文档主要分两大部分： 第一部分，主要是纳什均衡的存在性与唯一性证明定理。 第二部分，帕累托最优的相关定理。2. 纳什均衡 纳什均衡定义 行动组合是纳什均衡，则对于任意参与者，有： 简言之，就是给定其他参与者策略的情况下，每个参与者选择使自己效用最大化的策略。所有参与者的策略构成的组合即为纳什均衡。2.1 存在性定理定理2.1.1 C. U. Saraydar, N. B. Mandayam, and D. J. Goodman, “Efcient power control via pricing in wireless data networks,” IEEE Transactionson Communications, vol. 50, pp. 291303, February 2002. D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.：（1）对所有的，策略空间是欧式空间中一个非空的、紧的凸集；（2）效用函数是连续的且对是拟凹的。说明： 在数学中，欧几里得空间 的子集S是紧的，如果它是闭合的并且是有界的。（注：若不是在欧式空间中，闭合且有界的集合不一定是紧集。） 如果一个集合所有的极限点都是这个集合中的点，那么这个集合是闭集。 S是凸集是指，对满足的，只要，那么就有。简单而言，就是S中的任何两点之间的直线段都属于S。图 21左图为凸集，右图为非凸集定理2.1.2 D. Topkis, “Equilibrium points in non-zero sum n-person submodular games,” SIAM J.Control Optim., vol. 17, no. 6, pp. 773787, 1979.：如果一个博弈G是S-模博弈（S-modular games，SMG），则至少存在一个纯纳什均衡。定义1（S-模博弈S-modular games，SMG）一个博弈G，如果满足：（1） ，是欧式空间中的一个紧集；（2） 在s上是上半连续；（3） ，是不减的。则称G为超模博弈。说明： 上半连续：设 X 为拓扑空间， ，而为实值函数。若对每个都存在 x0 的开邻域 U 使得，则称 f 在 x0 上半连续。该条件也可以用上极限等价地表述：图 22上半连续函数的例子（蓝点表）图 23下半连续函数的例子（蓝点表） 进一步地，若任意具有二阶导，对于所有的，满足（1），则该博弈称为超模博弈（Supermodular games）。 (1)同理，满足（2）式，称为次模博弈（Submodular games）。 (2) 超模博弈和次模博弈统称为S-模博弈S-modular games（SMG）。定理2.1.3 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. 241244.：如果一个有有限个参与者的博弈是位势博弈（Potential games，PGs），且策略集合是紧的，效用函数是连续的，则至少存在一个纯纳什均衡。定义2（严格位势博弈Exact Potential games，EPGs）如果存在一个函数，满足,有如果处处二次可微时，一个博弈是EPGs的充分条件是类似地，满足，则定义为次序位势博弈Ordinal potential games。2.2 唯一性定理定理2.2.14：对于一个PGs，如果（1）策略组合是紧的、凸的；（2）P是在上连续可微函数，且对是严格凹的，则纳什均衡唯一。定理2.2.2 R. D. Yates, “A framework for uplink power control in cellular radio systems,” IEEE J. Select. Areas Commun., vol. 13, pp. 13411347, 1995.5. 更新纪录版本号修改日期修改人修改细节备注V1.0.011-11-22张双露初稿：如果最佳响应函数是标准的，则存在唯一纳什均衡。定义3（标准函数）是标准函数，应满足：（1）正：；（2）单调性：；（3）可扩展性：。定义4（最佳响应Best Response）3. 帕累托最优帕累托最优定义 一个策略组