2.-Nash均衡存在性

OriginatedbyDsoft博弈论导论AnIntroductiontoGameTheory中国科学技术大学·管理学院杜少甫SchoolofManagement,USTC—2—Nash均衡的存在性ExistenceofNashEquilibrium知识准备反应函数(response/reactionfunction)：即最佳反应映射(Thebestresponsemapping)，在某个博弈中，用于反映一个局中人对其他局中人策略所作出的反应关系的函数。通常在连续情况下，通过一阶条件得到。紧致集(CompactSet)：一个欧氏空间(EuclideanSpace)Rn的子集被称为紧致的，当且仅当此子集有界(bounded)且封闭(closed)。有界闭集–实数集R(一维欧氏空间)中，任一闭区间如[0,1]是紧致集；而任一开区间如(0,1)、[0,1)是非紧致集（notclosed）；整数集Z不是紧致集（notbounded）–平面集R2(二维欧氏空间)中的圆，立体集R3(三维欧氏空间)中的球。–注：作为特例，Ø被视为紧致集。SchoolofManagement,USTC—3—数学中与凸性(convexity)相关的几个概念凸集(convexset)：集合S被称为凸集，当且仅当(iif)对于∀a,b∈S和∀λ∈[0,1]，均有λa+(1-λ)b∈S。S内任两点的直线段仍在S内凸集是连通的。一维实空间内的区间；二维欧氏空间中每个角都小于180°的多边形等。两凸集的交集必为凸集，而并集未必。凸函数(convexfunction)：实值函数f(.)是凸的iif函数f(.)的定义域C为凸集且∀a,b∈C和∀λ∈[0,1]，均有f(λa+(1-λ)b)≤λf(a)+(1-λ)f(b)函数曲线的上境图(曲线以上部分)是个凸集。改为则为严格凸，改成≥即为凹/上凸函数。拟凸函数(quasi-convexfunction)：实值函数f(.)是拟凸的iif函数f(.)的定义域C为凸集且∀a,b∈C和∀λ∈[0,1]，均有f(λa+(1-λ)b)≤max{f(a),f(b)}改为则为严格拟凸，改为≥即为拟凹函数参见课程ftp下的参考资料[4]Sababf(b)f(a)λa+(1-λ)bf(λa+(1-λ)b)λf(a)+(1-λ)f(b)abf(b)f(a)λa+(1-λ)bf(λa+(1-λ)b)λf(a)+(1-λ)f(b)SchoolofManagement,USTC—4—注：有时为了避免混淆，凸/凹函数分别被称为下/上凸函数。MS/OR领域（包括GT）中，数学中的“凸”和“拟凸”习惯上常被称作“凹(concave)”和“拟凹(quasi-concave)”。在阅读文献过程中，要根据上下文理解真正内涵在运筹优化中，函数凸凹性对优化求解很重要。本课程尽量采用数学意义上的说法。对于二次可微函数而言，判断凸性最直接的办法是一元情况：求二阶导数下凸；上凸n元情况：求海赛(Hessian)矩阵，即由所有二次偏导构成的n×n对称阵。Hessian矩阵：正定下凸；负定上凸。(n个顺序主子式)()0fx()0fx11121(),,,1,,nijijnnnaafxHaijnxxaa•拟凹(凸)全局最大(小)值存在，未必唯一；•严格拟凹(凸)全局最大(小)值存在且唯一。SchoolofManagement,USTC—5—扩展知识点：Hessian矩阵vsJacobian矩阵n×mn×n矩阵维度类似一元函数的导数在给定点处得到对可微函数的最优线性估计(切线)。类似于一元函数二阶导数判断多元函数凸性在大规模优化问题中有重要应用(Newton型方法，如求解无约束非线性问题的BFGS算法)作用每一行反映了一个实函数对每个自变量的导数，行向量是梯度的转置。f(x)的梯度为梯度的Jacobian矩阵即为Hessian矩阵说明元素形式一阶偏导(first-orderpartialderivatives)二阶偏导(second-orderpartialderivatives)元素构成f:Rn→Rm(m个实函数)f:Rn→R(一个实函数)针对的函数类型雅可比(Jacobian)矩阵海赛(Hessian)矩阵2(),,1,,ijfxijnxx(),1,,;1,,ijfxinjmx12()()(),,,Tnfxfxfxfxxx12()()(),,,TiiiimfxfxfxfxxxSchoolofManagement,USTC—6—不动点定理(FixedPointTheorems)Brouwer不动点定理：设C是Rn中的非空紧凸子集，函数f:C→C连续，则必存在x∈C，使x=f(x)。该点称为不动点(fixedpoint)。即：Rn中非空紧凸子集到自己的映射必有不动点。例如：–单值映射f(x)=x2,x∈[0,1]，显然f是[0,1]→[0,1]映射，应用此定理可断定必存在不动点；求解x=x2，得到两个不动点x=0和1；–若x∈(0,1)，则没有不动点；若x∈[0,1)或(0,1]，则有一个不动点；但因定义域和值域不是紧致集，此定理不适用于对这种情况下的不动点存在性判定；–任何闭区间内的函数f(x)=x+1无不动点。由于定义域和值域不同，因此此定理也不适用于此。Brouwer不动点定理提供了不动点存在的充分非必要条件(sufficientbutunnecessary)在不动点定理所述条件下，函数y=x与y=f(x)必有交点。SchoolofManagement,USTC—7—集值映射(Set-valuedmap/function)：又称多值映射(Multi-valuedmap/function)，是指函数值是个集合，即一个输入对应一个或多个输出。模糊的：ambiguous,misnomer即：从集合X到集合Y的集值映射定义域为X，值域是由Y的所有非空子集所构成的集合(集合的集合)集合S的所有子集的集合为{s|s⊆S}，显然包括Ø。设n=|S|，考虑{s|s⊆S}中元素个数(即S的子集数)：S的任意个元素所构成的集合均是S的子集，那么由k个元素构成的子集共有个。而即S元素个数与S的子集数之间是2|S|关系，因此通常定义符号2S≡{s|s⊆S}。注：此表述源自有限集合，对无限/连续集合也适用。例：不动点定理(FixedPointTheorems)单值映射vs集值映射单值映射(Single-valuedmap/function)：即传统的映射/函数，即函数值是单一数值，只要自变量值确定，则函数值也就随之唯一确定。明确的：well-defined,unambiguous,0,,knCkn012nnnnnCCC:2/,{1,2,3},{,,,}YfXXYabcd2,{},{},{},{},{,},{,},,{,,,}(1){};(2){};(3){,}YabcdabacabcdfafdfbcSchoolofManagement,USTC—8—不动点定理(FixedPointTheorems)集值函数有闭图(ClosedGraph)：若集合{(x,y)|y∈f(x)}是X×Y上的闭子集，则称集值函数f:X→2Y有闭图。例：[0,1]区间上的集值函数f(x)=[1-x/2,1-x/4]，其覆盖区域是封闭有界的。有闭图2/3,4/5x角谷不动点定理角谷静夫对Brouwer不动点定理的单值映射集值映射一般性扩展Kakutani,S.(1941).AgeneralizationofBrouwer’sfixedpointtheorem.DukeMathematicalJournal8(3):457–459.S为欧氏空间Rn中的非空紧凸子集，f:S→2S是S上的集值映射，且有闭图，对任意x∈S，f(x)均是非空凸集。那么必存在x*∈S，使得x*∈f(x*)。x*被称为不动点。注：例：[0,1]区间上的集值函数f(x)=[1-x/2,1-x/4]，其不动点须满足即区间[2/3,4/5]内的任一点均为不动点。1/21/4xxxSchoolofManagement,USTC—9—Nash均衡的存在性ExistenceofNashEquilibrium例：在两方策略式博弈G={S1,S2;u1,u2}中策略空间均是紧致集，但支付函数不连续。每个局中人的支付函数对己方策略都是严格凹/上凸的最优反应存在且唯一(Existence&Uniqueness)。局中人1的一阶条件局中人1的反应函数局中人2的一阶条件局中人2的反应函数12112221212112122122121[0,10];,;(2),4;(,)();(,)(2),4.SSsSsSsssussssusssss112121(,)2()0usssss1122()sRss11221112,4;()2,4;sssRsssSchoolofManagement,USTC—10—Nash均衡的存在性ExistenceofNashEquilibrium从上述反应函数可看出：每个局中人对于对方的任何策略均存在唯一的最优反应策略。然而：–两反应函数不相交不可自动实施(self-enforcing)无纯策略Nash均衡。–可从下图看出：假设从局中人的任一策略s10开始1s2s1122()sRss4102211()2sRss2211()2sRss01sSchoolofManagement,USTC—11—Nash均衡的存在性ExistenceofNashEquilibrium定理1.1(Debreu,1952;Glicksberg,1952;Fan,1952)在n人策略式博弈中，若每个局中人的纯策略空间Si是欧氏空间上的一个非空紧凸集(nonemptyconvexcompactset)；支付函数ui(s)连续且对si拟凹，则此博弈必存在一个纯策略NE。(sufficientbutunnecessary)Si:非空、凸、有界、封闭ui(s):连续、拟凹证明：运用拟凹的性质易于证明。思考：若将“拟凹”改为“严格拟凹”，那么定理可如何表述？SchoolofManagement,USTC—12—定理1.2：在有限策略式博弈G={S1,…,Sn;u1,…,un}，混合策略组合p*为NE的充要条件是：对所有局中人i，其每一个纯策略si有证明：见参考资料[5]定理1.3:在任一混合策略组合中，对局中人i的混合策略，必然存在，使证明见参考资料[6]1212(,,,)nnPPPpppp1(,,)iiiimippPp{1,,}ijm0and(,)()ijiijiipEsEpp(,)()iiiiEsEppSchoolofManagement,USTC—13—Nash均衡的存在性ExistenceofNashEquilibrium定理1.4(Nash,1950)有限非合作博弈必有Nash均衡——纯策略NE或混合策略NE即著名的“有限博弈Nash均衡存在性定理”，简称“Nash定理”证明：主要证明思想是应用角谷不动点定理。见参考资料[7]定理1.5(Glicksberg,1952)在n人策略式博弈中，若每个局中人的纯策略空间Si是欧氏空间上的一个非空紧凸集；支付函数ui(s)连续，则此博弈必存在一个NE(纯策略或混合策略NE)证明方法类似于Nash定理，也是应用不动点定理。vs.Nash定理：允许是某种无限博弈vs.定理1.1定理1.1提供了纯策略NE存在的一个充分条件，但要求支付函数拟凹。拟凹性在很多情况下并不能满足，此定理将条件进一步放宽，但并不保证一定是纯策略NE。SchoolofManagement,USTC—1