博弈论与信息经济学纳什均衡存在性

1、博弈论与信息经济学第2章 完全但不完美信息静态博弈-3纳什均衡的存在性1四个均衡概念的关系 占优战略均衡(DSE)、重复剔除的占优均衡(IEDE)、纯战略纳什均衡(PNE)和混合战略纳什均衡(MNE)，每个均衡概念依次是前一个均衡概念的扩展，或者说，前一个均衡概念是后一个均衡概念的特例。如果将存在某个适当定义的均衡的所有博弈称为一个集合，那么，存在前一个均衡的集合依次为存在后一个均衡的集合的子集 23纳什均衡的存在性 是不是所有的博弈都存在纳什均衡呢? 不一定。但是，纳什(Nash，1950)证明，任何有限博弈都存在至少一个纳什均衡。纳什均衡的存在性定理-I (Nash，I950)：每一个有限

2、博弈至少存在一个纳什均衡(纯战略的或混合战略的)。 这里，有限博弈指的是有有限个参与人且每个参与人有有限个纯战略的博弈。4均衡与不动点在经济学中，说明一个方程系统存在均衡解的方法是将问题变成寻找一个适当构造的某种集合ARN到其自身(A)的函数或对应的不动点。纳什均衡存在性定理的证明要用到Kakutani不动点定理(fixed point theorem)。Kakutani不动点定理是关于映射的Brouwer不动点定理在对应上的扩展。一个向量x是映射f(.)的Brouwer不动点，如果x=f(x)；或者是对应f(.)的Kakutani不动点，如果x f(x)。即，向量映射或对应到自身，并且保持固

3、定。5函数与对应函数或映射是集合上点与点之间的联系规则，对应(correspondence)是集合上点与子集之间的联系规则。简单地说，给定X上的一个点x，如果f(x)给出唯一的一个点yY，f(x)称为从X到Y的函数；如果f(x)给出一个点集Y(x)Y，f(x)称为从X到Y的对应。函数或映射是对应的特例，即Y(x)只包含唯一点的情况，而函数也可以看作是映射的特例，因为映射允许集合的元素是非实数。6反应函数与反应对应在库诺特模型中，给定企业j的产量qj，企业i的最优产量qi是唯一的，我们称qi = Ri(qj)为企业i的反应函数。在两人混合战略均衡中，给定参与人j的（均衡）混合战略j，参与人i可能

4、有无穷多个最优混合战略i，我们称i = ri(j)为i的反应对应。7Brouwer不动点定理假定f(x)是定义在点集X上的函数。如果f(x)是自身对自身的映射(即f: X X)， f(x)是连续的，X是非空的、紧的（有界的和闭的）、凸集合，那么，至少存在一个x*X，使得f(x*) = x*， x*称为不动点。 函数的连续性及集合的闭性(有界且包括边界)、有界性(有极限点)和凸性是保证不动点存在的充分条件，而不是必要条件。即使这些条件都不满足，不动点也可能存在。8RRx1x2x1x2x1x2R闭区间开区间半开区间闭集合开集合9平行阴影集合A是开的（相对于X），虚边线上的点不属于A，开圆盘x在A中

5、。平行阴影集合A是闭的（相对于X），因为集合A的补集XA是开的，开圆盘x在XA中，实线上的点属于A。10凸集凸集合：集合ARN是凸的，如果 x + (1- )x A，其中， x，x A，并且 0，1。也就是说，如果RN中的一个集合A是凸的，那么，如果它含有两个向量x和x，就包含连接这两个向量的整个线段(这两个向量的凸组合或加权平均)。11凸集合非凸集元素的全可见性与部分不可见性xxxx12f:0,1 0,1是连续函数，X=0,1是闭的、有界的、凸的，Brouwer不动点定理的条件均满足, x*是一个不动点。X = x: 0 xx0，x1x1不是凸的，因为(x0，x1) X，没有不动点。Brou

6、wer不动点定理：一维实数空间上的连续函数/映射：图像与45线相交13X = 0，)不是有界的，没有不动点。X= 0，1)不包含点1，因而不是闭的，没有不动点。Brouwer不动点定理：一维实数空间上的连续函数/映射：图像与45线相交14f(x)在点x0是不连续的，没有不动点。f(x)在点x0不连续，X是非闭的(不包括x = 1的点)，但有两个不动点存在。 Brouwer不动点定理：一维实数空间上的连续函数/映射：图像与45线相交15从0，1到其自身的连续函数有一个不动点连续性假设是不可缺少的，不连续函数可能没有不动点Brouwer不动点定理：一维实数空间上的连续函数/映射：图像与45线相交1

7、6映射f: AA有三个不动点Brouwer不动点定理：一维实数空间上的连续函数/映射：图像与45线相交17Kakutani不动点定理假定f(x): XX是定义在点集X上的对应，如果X是非空的、闭的、有界的和凸的，f(x)对于所有的xX是非空的、凸的，且上半连续(upper semi-continuous)，那么，至少存在一个x*X，使得x*f(x*)，称为不动点。对应的上半连续性等价于Brouwer不动点定理中函数的连续性。18函数的连续性连续的三个要素：有定义、有极限、极限值等于函数值，缺一不可。19函数的连续性20对应的连续性给定XRN和YRK，对应f：XY的图像(graph)是像集合(x

8、, y)XY：yf(x)。给定XRN和闭集YRK，如果对于任意两个序列xm xX和ymy，且对于每一m, xmX及ymf(xm)，有yf(x)，则对应f：XY有一个闭图。闭图的概念就是通常意义上的闭性（相对于XY）应用于集合(x, y)XY：yf(x)。21对应的上半连续性给定XRN和闭集YRK，对应f：XY是上半连续的，如果它有闭图，且X中任意紧集的像是有界的。这意味着，在上半连续对应下，紧集的像实际上是紧的（有界且闭的）。对应的上半连续要求，对于所有的x0X和包含f(x0)的开集V，存在一个x0的邻域U，使得对于所有的xU，有f(x)V。m维的欧几里德几何空间Em的子集N叫作点pEm的一个

9、邻域，如果对于某个实数r0，以p为中心，以r为半径的闭圆盘包含在N内。22对应(函数)有闭图，但不是上半连续的，a1/2的邻域的像不是闭的(无界)。上半连续对应23对应的下半连续性给定ARN和紧集YRK，对应f：AY是下半连续的，如果对于每一个序列xm xA，并且对于所有的m有xmA，以及对于每一个yf(x)，我们可以找到序列ymy，和一个正整数M，使得对于mM, 有ymf(xm)。有开图的任何对应f：AY都是下半连续的（相对于AY）。24下半连续，但没有闭图，所以不是上半连续的；下半连续只与集合的“内爆/聚爆”相一致。25上半连续，但没有开图，因而非下半连续；上半连续只与集合的“爆炸/裂爆”

10、相一致。26下半连续，但非上半连续上半连续，但非下半连续27连续对应：既上半连续，又下半连续1/228f(.)是凸的，不动点存在对应的凸性假设是不可缺少的；f(.)不是凸的，不动点不存在29上半连续但非凸的对应30上半连续但非凸的对应31上半连续且凸的对应32应用Kakutani不动点定理证明纳什均衡的存在性假定有n个参与人，每个参与人有有限个纯战略。我们定义，=(1, , i, , n)为n个参与人的混合战略组合，其中ii是第i个参与人的混合战略；=ni为混合战略组合的集合或空间(即)。我们用ri()代表i的反应对应，定义为给定其他参与人的混合战略-i时i的一个或多个最优战略i*。数学上讲，

11、ri()将每一个战略组合对应到i的战略空间i上的一个最优子集(虽然ri只依赖于-i而不依赖于i，我们用ri()而不用ri(-i)，是因为要应用不动点定理）。33应用Kakutani不动点定理证明纳什均衡的存在性定义对应r：为ri的笛卡尔积，也就是，给定一个混合战略组合，各参与人i的每个最优战略i*ri()，组成空间中的若干个元素=(1*, , i*, , n*)构成的集合，如此，将n个参与人的反应对应ri转换为到自身的对应r：。如果存在一个不动点* = (1*, , i*, ., n*)，使得*r(*)，由于对所有的i, i*ri(*)，这个不动点就是纳什均衡。因此，只要说明对应r：满足Kak

12、utani不动点定理的条件，就可以证明纳什均衡存在。 34Kakutani不动点定理假定f(x): XX是定义在点集X上的对应，如果X是非空的、闭的、有界的和凸的，f(x)对于所有的xX是非空的、凸的，且上半连续(upper semi-continuous)，那么，至少存在一个x*X，使得x*f(x*)，称为不动点。对应的上半连续性等价于Brouwer不动点定理中函数的连续性。35=0=1=0=11236应用Kakutani不动点定理证明纳什均衡的存在性首先，因为每一个i都是一个概率空间，因而是(J - 1)维的单纯形(这里J是第i个参与人的纯战略数量)，这意味着i(从而)是闭的、有界的、凸的

13、和非空的。设a1, , ak是Rn中的一组线性无关的点，在1+ k=1以及10，, k 0时，一切点x= 1a1+ kak的集合，称为k-1维单纯形，记为（a1, , ak）。k=2时的1维单纯形就是线段；k=3时的2维单纯形就是三角形；k=4时的3维单纯形就是三棱锥，各有K个顶点。37应用Kakutani不动点定理证明纳什均衡的存在性其次，因为期望效用是混合概率的线性函数，因而是连续的和拟凹的(quasi-concave)，ri()从而r()是非空的(有界闭集上的连续函数一定有最大值)。拟凹函数：定义在凸集合ARN上的函数f：AR是拟凹的，如果其上面的轮廓集合x A: f(x) t是凸集合，

14、即，如果对于任意的t R，x, x A和 0，1，f(x) t和f(x) t意味着f(x + (1- )x) t。38严格拟凹函数的轮廓集合39不严格的拟凹函数的轮廓集合40函数f(.)是拟凹的，当只当对于所有的x, x A和 0, 1，f(x + (1- )x) Min(f(x), f(x)。因此，凹函数必为拟凹的，但拟凹函数不一定为凹函数。例如，一个自变量的任意递增函数是拟凹的。所以，凹性是比拟凹性更强的性质。xyf(x)g(x)t(x)41一个自变量的严格凹函数连接函数f(.)图像上任意两点的直线完全在图像之下；函数f：AR的图像是集合(x, y) AR: y=f(x)42不严格的凹函数

15、连接两点x和x的直线在图像上。434445连续性和紧性假设对于使函数最大化的自变量值的存在性的必要性在非紧定义域上的连续函数没有最大化自变量值在紧定义域上的非连续函数没有最大化自变量值46应用Kakutani不动点定理证明纳什均衡的存在性进一步，期望效用函数的线性意味着，如果r()，r(), 那么 + (1 - ) r()，(0, 1)，即如果i和i是对应于-i的最优选择，那么它们的加权平均也是对应于-i的最优选择，因此，ri() 从而r()是凸的。47应用Kakutani不动点定理证明纳什均衡的存在性最后，我们要证明，r()是上半连续的，即: 如果一个序列(m,m)(,)，mr(m)，那么r

16、()，从而，由于r是ri的笛卡尔积，对所有的i，iri(-i)。假定不是这样，即存在一个序列(m,m) (,)，mr(m)，但r()，那么，由于r是ri的笛卡尔积，对某些i，iri(-i)。这样的话，存在一个0和一个i使得i(i,-i)i(i,-i)+3。48应用Kakutani不动点定理证明纳什均衡的存在性因为i是连续的和拟凹的，(m,m)(,)，如果m足够大，我们有i(i,m-i) i(i,-i)i(i,-i)+2 i(mi,m-i)+因此，i严格优于mi (给定m-i)，即mi ri(m)，与假设矛盾。因此，我们证明r()是上半连续的。因为Kakutani不动点定理的条件是满足的，所以，

17、r: 有一个不动点* = (1*，.，i*, .，n*)，使得*r(*)，且对所有的i, i*ri(*)，这个不动点就是纳什均衡。49无限博弈纳什均衡的存在性经济学家使用的模型一般都是无限博弈，即参与人有无穷多个不可数的纯战略。在上述存在性定理中，每个参与人有有限个纯战略只是纳什均衡存在的充分条件，而不是必要条件。在库诺特模型中，每个参与人有无穷多个纯战略，但纳什均衡是存在的。当参与人有无穷多个纯战略时，纳什均衡的存在性要求支付函数在纯战略上是连续的。如果支付函数不连续，均衡就可能不存在。 50纳什均衡的存在性定理II纳什均衡的存在性定理II(Debreu，1952；Ghksberg，1952

18、；Fan，l952)：在n人战略式博弈中，如果每个参与人的纯战略空间Si是欧氏空间上一个非空的、闭的、有界的凸集，支付函数ui(s)是连续的且对si是拟凹的，那么，存在一个纯战略纳什均衡。上述存在性定理的证明类似纳什定理的证明。支付函数的连续性意味着反应对应是非空的和上半连续的；支付函数对参与人自己的战略的拟凹性意味着反应对应是凸的。这样，不动点定理的条件是满足的。51欧氏空间n维欧氏空间记为En。欧几里德几何空间：具有无限性和均匀性的广延，与世界的真实空间是同一的。52定理I与定理II的关系纳什定理可以看作是上述定理的特例。尽管当纯战略的数量有限时，纯战略空间是非凸的，支付函数是非连续的，但

19、混合战略空间作为一个单纯形是欧氏空间上闭的、有界的非空凸子集，期望支付函数是连续的、拟凹的。当纯战略空间本身是欧氏空间上一个非空的、闭的、有界的凸集且支付函数在纯战略空间上是连续的、拟凹的时，就没有必要引入混合战略了。 53应用Kakutani不动点定理证明纳什均衡的存在性定理II假定有n个参与人，每个参与人有无限个纯战略。我们定义，s=(s1, , si, , sn)为n个参与人的战略组合，其中siSi是第i个参与人的战略；S=nSi为战略组合的集合或空间(即sS)。我们用ri(s-i)代表i的反应对应，定义为给定其他参与人的战略s-i时i的一个或多个最优战略si*。数学上讲，ri(s-i)

20、将每一个战略组合s-i对应到i的战略空间i上的一个最优子集。54应用Kakutani不动点定理证明纳什均衡的存在性定理II定义对应r：SS为ri的笛卡尔积，也就是，对于每一个参与人i，给定的其他参与人的战略s-i与i的每一个最优战略si*组成S空间中的若干个元素s=(s1, , si*, , sn)构成的集合，如此，就将n个参与人的反应对应ri转换为S到自身的对应r：SS。如果存在一个不动点s* = (s1*, , si*, ., sn*)S，使得s*r(s*)，由于对所有的i, si*ri(s*)，这个不动点就是纳什均衡。因此，只要说明对应r：SS满足Kakutani不动点定理的条件，就可以

21、证明纳什均衡存在。55连续性条件的重要性假定有两个参与人，每个参与人的战略空间都是0到1之间的实数，即S1 = S2 = 0，1。假定支付函数分别为u1(s1,s2) = -(s1 s2)2u2(s1,s2) = -(s1 s2 1/3)2, s1 1/3 -(s1 s2 + 1/3)2, s1 1/3这里，每个参与人的支付函数对自己的战略是严格凹的，但u2在s1 = 1/3点不连续。56连续性条件的重要性参与人的反应函数分别是:r1(s2) = s2r2(s1) = s1 1/3, s1 1/3 = s1 + 1/3, s1 1/3即参与人2的反应函数在点s1 = 1/3不连续。两条反应曲线

22、不相交，纳什均衡不存在，如图1.8所示。5758支付函数的拟凹性支付函数的拟凹性是一个很严格的条件，这个条件在许多情况下是不满足的。比如说，在库诺特模型中，利润函数的拟凹性要求逆需求函数和成本函数满足一些特殊的条件(如逆需求函数是凹的，成本函数是凸的)。当支付函数不满足拟凹性条件时，纯战略均衡可能不存在。当然，即使拟凹条件(和定理的其他条件)不满足，纯战略均衡也可能存在，因为这些条件是充分条件而非必要条件。 59纳什均衡的存在性定理III当支付函数在纯战略空间上是连续的但不一定拟凹时，引入混合战略可以保证纳什均衡的存在。 纳什均衡的存在性定理III(Glicksberg，1952): 在n人战

23、略式博弈中，如果每个参与人的纯战略空间Si是欧氏空间上一个非空的、闭的、有界的凸集，支付函数ui(s)是连续的，那么，存在一个混合战略纳什均衡。 定理的证明仍然是应用不动点定理于反应对应。这里，引入混合战略的目的是使反应对应满足凸性条件。 60伯川博弈参与人企业1和企业2。博弈规则企业1和企业2同时选择产品的价格p1,p20, )，尽可能多地销售自己的产品。支付函数两企业的产品同质(完全替代)，边际生产成本相同且不变c。总需求函数为线性Q(p)=ap。企业1和企业2的支付函数是：61支付函数1= (a-p1)(p1-c)，如果p1p22= 0，如果p1p262均衡与结果唯一的纳什均衡是: p1

24、 = p2 = p = c均衡结果是q1 = q2 = (a-c)/2， 1= 2= 0证明：把可能的战略组合分为四类， p1 c 或 p2 p2 c 或 p2 p1 c。在这两种情况下，价格较高的企业可以转向一个低于对手的价格，使其利润从零增加到某个正值；63证明p1 = p2 c。在这种情况下，一个企业可以转向一个低于对手的价格，其利润将增加，因为，虽然单位销售的利润有所下降，但销售量从市场需求的一半变为占领整个市场；p1 p2 = c 或 p2 p1 = c。在这种情况下，价格为c的企业可以提高其价格并低于另一企业的价格，其利润从零变为正值。64证明纳什均衡的一般方法分解战略组合空间，一部分一部分地证明会出现偏离。伯川悖论：在产品同质的情况下，虽然只有两个企业，双寡头利润并不增加。65产品有差异时的价格竞争如果两个企业的产品不完全相同，企业1的需求函数为q1 = a p1 + p2，企业2的需求函数是q2 = a