均衡存在性课件.ppt

《均衡存在性课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、博弈论导论AnIntroductiontoGameTheory中国科学技术大学·管理学院杜　少　甫Nash均衡的存在性ExistenceofNashEquilibrium知识准备反应函数(response/reactionfunction)：即最佳反应映射(Thebestresponsemapping)，在某个博弈中，用于反映一个局中人对其他局中人策略所作出的反应关系的函数。通常在连续情况下，通过一阶条件得到。紧致集(CompactSet)：一个欧氏空间(EuclideanSpace)Rn的子集被称

2、为紧致的，当且仅当此子集有界(bounded)且封闭(closed)。有界闭集实数集R(一维欧氏空间)中，任一闭区间如[0,1]是紧致集；而任一开区间如(0,1)、[0,1)是非紧致集（notclosed）；整数集Z不是紧致集（notbounded）平面集R2(二维欧氏空间)中的圆，立体集R3(三维欧氏空间)中的球。注：作为特例，Ø被视为紧致集。数学中与凸性(convexity)相关的几个概念凸集(convexset)：集合S被称为凸集，当且仅当(iif)对于∀a,b∈S和∀λ∈[0,1]，均有λa

3、+(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(

4、.)是拟凸的　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)注：有时为了避免混淆，凸/凹函数分别被称为下/上凸函数。MS/OR领域（包括GT）中，数学中的“凸”和“

5、拟凸”习惯上常被称作“凹(concave)”和“拟凹(quasi-concave)”。在阅读文献过程中，要根据上下文理解真正内涵在运筹优化中，函数凸凹性对优化求解很重要。本课程尽量采用数学意义上的说法。对于二次可微函数而言，判断凸性最直接的办法是一元情况：求二阶导数下凸；上凸n元情况：求海赛(Hessian)矩阵，即由所有二次偏导构成的n×n对称阵。Hessian矩阵：正定下凸；负定上凸。(n个顺序主子式)拟凹(凸)全局最大(小)值存在，未必唯一；严格拟凹(凸)全局最大(小)值存在且唯一。

6、扩展知识点：Hessian矩阵vsJacobian矩阵n×mn×n矩阵维度类似一元函数的导数在给定点处得到对可微函数的最优线性估计(切线)。类似于一元函数二阶导数判断多元函数凸性在大规模优化问题中有重要应用(Newton型方法，如求解无约束非线性问题的BFGS算法)作用每一行反映了一个实函数对每个自变量的导数，行向量是梯度的转置。f(x)的梯度为梯度的Jacobian矩阵即为Hessian矩阵说明元素形式一阶偏导(first-orderpartialderivatives)二阶偏导(second-or

7、derpartialderivatives)元素构成f:Rn→Rm(m个实函数)f:Rn→R(一个实函数)针对的函数类型雅可比(Jacobian)矩阵海赛(Hessian)矩阵不动点定理(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]映射，应用此

8、定理可断定必存在不动点；求解x=x2，得到两个不动点x=0和1；若x∈(0,1)，则没有不动点；若x∈[0,1)或(0,1]，则有一个不动点；但因定义域和值域不是紧致集，此定理不适用于对这种情况下的不动点存在性判定；任何闭区间内的函数f(x)=x+1无不动点。由于定义域和值域不同，因此此定理也不适用于此。Brouwer不动点定理提供了不动点存在的充分非必要条件(sufficientbutunnecessary)在不动点定理所述条件下，函数y=x与y=f(