《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性

#例子2Cournot寡头博弈模型假设每个寡头企业具有相同的不变单位成本c，即c(q)二c•qiii需求函数为线性形式P=a-(q+q)，所以12兀(q,q)=q(a一q一q一c)iijiij此时，最优化的一阶条件为&_/、_nTOC\o"1-5"\h\z—i=a—(q+q)—q—c=0dq121匕兀1_/、_n—2=a—(q+q)—q—c=0dqi22企业的最优反应函数为

q=R(q)=(a—q—c)11222q=R(q)=(a一q一c)22121联立求解上式，可得企业的Nash均衡产量为q*=q*=3(a—c)企业的Nash均衡利润分别为兀*=兀*=1(a—c)21295-1)5-2)在上述简单假设下，两个企业的最优反应函数5-1)5-2)图5-1Cournot模型的Nash均衡线的交点即为Nash图5-1Cournot模型的Nash均衡第二部分实施Nash定理的证明已经知道，在考虑混合战略的情况下，一个完全信息静态博弈“通常”都存在纳什均衡。这一认识最早由纳什(Nash,1950,1951)进行了证明，称为纳什定理。定理2.1纳什定理如果完全信息静态博弈G=《,ul是有限的,即参与人是有限的，S包含的纯策略也是有限的，那么一定存在至少一个(纯策略或混合策略)纳什均衡。所谓“通常”指的就是博弈的有限性。到目前为止,我们分析的博弈都满足这两个条件。参与人有限——通常为两个人。S也是有限的——要么存在若干个纯策略,例如猜币游戏；要么虽然纯策略由无穷多，但却是有界闭集2例如古诺模型中的战略集S=[0,a]，所以前i面分析的静态博弈都存在纳什均衡。对纳什定理的证明分三个部分来完成第一步，介绍不动点定理；第二步，说明纳什均衡就是不动点；2在数学中，有界闭集必然意味着是有限的，即它不是无限的，或者说拒斥了无限情。

第三步，完成证明。第一步，不动点定理。图2-29中的方框为正方形。bd为45°线，它实际上等价于函数y=f(x)=x。BD线上的每一点都满足f(x)=x,把满足f(x)=x的x称为不动点。BD线所代表的函数自变量x取值为［0,1］，称为定义域，而因变量y的取值为［0,1］,称为值域。定义域和值域都为［0,1］的函数f(x)，又可写作f:［0,1］T［0,1］，读作从［0,1］到［0,1］的映射。现在做一个小游戏：拿一支笔，从AB线出发任意画一条曲线，记住可以任意画，但必须连续画不能断裂，至到CD线结束。这时发现无论如何画，这条曲线一定会和BD相交，这个交点就是不动点因为任意画的曲线等价于一个函数g(x)，没有断裂意味着它是连续的，与BD线相交意味着g*(X*)，所以交点为不动点。所有任意画的曲线都有如下的性质：定义域［0,1］是非空的、有界的、闭的、凸集合，简称非空凸紧集。有界闭集即为紧集。函数f(x)是连续的，并且是自身对自身的映射。上面考虑的只是一元函数，对于n元函数是不是如果满足上述性质就存在不动点？布劳尔(Brower)定理肯定地回答了这一点。定理2.2—布劳尔(Brower)不动点定理。假设auRn是一个非空凸紧集合，并且f:ATA是一个连续函数；那么f(•)必有一个不动点;即，存在一个xeA使得x=f(x)o这里R为实数，Rn为实数的n重笛卡尔积，x为n维向量。在前面的例子中n二1,A二［0,1］o在实际运用中，我们常常遇到的不是函数而是对应的情况，例如猜币游戏这个博弈存在的是最优反应对应，而不是函数，这就有了对布劳尔不动点定理的推广定理2.3—角谷(Kakutani)不动点定理。假设aurn是非空凸紧集，并且f:ATA是上半连续对应，并且对于每一个xeA，集合f(x)uA是非空凸集，那么f(•)必有一个不动点。即，存在一个xeA使得xef(x)o角谷不动点定理与布劳尔不动点定理的区别在于①映射f为对应而不是函数，所以f(x)为一个集合(一个点也能组成集合，所以函数是对应的特例)。②映射f是上半连续的。一个对应只有既是上半连续又是下半连续才能称为连续，因而上半连续比连续的要求要弱。关于对应的上半连续，就是指如果存在一个序列xl,x2,…,xn收敛于x并且y1ef(x1),y2ef(x2),…,ynef(xn)收敛于y，那么一定有yef(x)(如果f(x)只有唯一值，那么e就变为J即对应包含着它的极限点在图2-30(a)中，当xta,即从a的左边向其收敛时，f(x)TA但我们看到A电f(a)，即对应f(x)并不包含极限点A，所以它不是上半连续的。在图2-30(b)中，对应f(x)包含它的每一个序列的极限点，特别是Aef(a)，因而它满足上半连续，但它不是连续的。例如，猜币游戏中每个参与人的最优反应对应就是上半连续的。对于函数而言，上半连续就等同于连续。y打^(xL.y打^(xL.oAiOabxy”U(xL.JaIJ|.Oabx(a)非上半连续(a)非上半连续(b)上半连续2-30对应的上半连续第二步，纳什均衡是不动点。根据纳什均衡的定义，在给定其他参与人策略的情况下，参与人i选择一个策略以使其收益最大化，并且对每一个参与人都如此，即纳什均衡是一个使每一个参与人收益最大的策略组合针对其他参与人不同的策略，参与人i都有一个最优策略与之相对应，用数学来表示就是最优反应函数或对应。如果参与人i的最优反应函数(对应)定义为B(p，…,p,p，…,p)=p,其中i=1,…,n,那么n个参与人的最优反i1i-1i+1ni应函数（对应）就构成了一个方程，将其定义为R（p，…,p），即1nB1（P2，…,Pn）=P1）…,…,P）=PiTOC\o"1-5"\h\zR（p，…，p）=<1i~1.1+1ni1n:B（p，…，p）=pn1n-1n如果（p:，…，p）是纳什均衡，它一定满足1nR（p:，…，p:）=（p:，…，p:），即纳什均衡是一个不动点。例如，古1n1ni12诺模型中的最优反应函数共同构成了一个方程组r（q，q），i二1,2，这i12个方程的解既是不动点，也是纳什均衡。第三步，完成证明。现在要完成的是证明：①最优反应对应B的定义域为耳腔凸紧i集；②B为上半连续的对应。i由于R是B（I二1,2,…,n）的方程组，B满足这两个条件，总的策略ii方程R必然满足这两个条件，而根据不动点定理，我们知道存在着不动点（p：，…，p：），使得R（p：，…，p：）=（p：，…，p：）（1）定义域为非空凸紧集。所谓有界集合就是任意画一个圆（圆的半径可以任意大，但不能无穷大）可以把它包下。所谓闭集就是包含

边界的集合。有界闭集即为紧致集合，简称紧集。所谓凸集就是在集合内任意找两点，连接两点的直线一定位于集合中。图2-31中的直线和三角平面显然是有界的，同时也是闭的，即它们是紧集。同时它们也是凸集。而图2-32中的环是非空紧集，但却不是凸集。如果博弈有n个人参与人，参与人i有k个纯策略，那么策略方程R的定义域为［0,1］kXn，它表示［0,1］的kXn重笛卡尔积，例如函数f（X,y）,x,yGA那么函数的定义域就为Aixi，即x,y都从集合A中取值。由于混合策略的取值为［0,1］,显然［0,1］为非空凸紧集，所以［0,1］kxn也是非空凸紧集。在古诺模型中，它的定义域虽然与上面讲的有所不同，即纯策略有无穷多个，但策略q（产量）的取值为［0,a］（或［0,+型，它同样是非空凸集。这表明纳什均衡真正需要的并不是“有限的”要求，而是策略空间必须为紧致集合。如果一个参与人有两个纯策略x和y那么所有混合策略集合（策略空间）就是满足x+y二1,x和y都大于等于零的直线。如果有三个纯策略x,y,z，那么所有的混合策略集合（策略空间）就是一个满足x+y+z二1,x,y,z都大于等于零的一个三角平面。如果2-31所示。（2）最优反应对应是上半连续的。根据前面的介绍，我们已经知道混合策略空间是非空凸紧集，并且预期收益函数是混合策略的线性函数，因而它是连续的和凹的（因为偏好为理性，这就保证了根据最大化预期收益函数得到的最优反应对应必然是上半连续和非空凸集，这在数学上被称为最大化定理。综上所述,最优反应方程R（p,,p）满足不动点定理的两个条件:1n策略空间为非空凸紧集，最优反应对应为上半连续并且是非空凸集。因而存在着不动点，而不动点就是纳什均衡。知识扩展》一、集值映射及其半连续性这里限于在欧氏空间中展开讨论，当然，我们也说成拓扑空间，但在这里的上下文，读者可以将拓扑空间直接理解为欧氏空间。设X是一个拓扑空间，X的所有子集的全体记作2X。即2x={G:GuX}.注意，0e2x,Xe2x定义9.1.1设X和Y是两个拓扑空间。若对任一xeX,确定Y的一个子集(己作)F(x)与之对应。这样得到的对应F:Xt2y称作一个点对集映射(point-to-setmapping)或一个集值映射(set-valuedmapping)。相应地，以往对每个xeX确定一个f(x)eY的映射f:XtY称为单值映射(single-valuedmapping)如同单值映射的情形，我们引进集值映射的图像的概念。

定义9.1.2设F:XT2y是一个集值映射。称XxY的子集工F(x)={(x,y)eXxY:xeX,yeF(x)}xeX为F的图像(graph)表现下面我们建立集值映射的半连续性和连续性的概念定义9.1.3设F:设F:XT2y是一个集映射，xoeX9若对Y的与F(xo)之交馆的每个开集G,馆的每个开集G,若对Y的包含F(xo)的每个开集g，存在X中包含xo的一个开集存在x中包含xo的一个开集U(x0)使得xeU(xo)蕴涵F(x)GH0.就说F在xo是下半连续的(lowersemicontinuous)。U(xO)使得xeU(xo)蕴涵F(x)uG,就说F在xo是上半连续的(uppersemicontinuous)。若F在xO既是下半连续的又是上半连续的，就说F在xo是连续的(continuous)集值映射的两种半连续性和连续性,都是单值映射的通常的连续性概念的推广。事实上，如果把单值映射看作在定义域的每点取值域的一个单点集的集值映射，则作为集值映射的下半连续性、上半连续性和连续性，都与作为单值映射的通常的连续性吻合。对于集值映射，下半连续性和上半连续性是不同的。请看下面的例子。例9.1.1设X=Y=I是实数轴上的一个闭区间，集值映射F:Xt2y由图9.1给出。容易验证，在任一点x主x0，连续性是不成问题的。即在任一点x主X0，F既是下半连续的又是上半连续的。但在x0&X，F是下半连续的而不是上半连续的。例9.1.2仍取X=Y=I为闭区间，集值映射G:Xt2y由图9.2

给出。容易验证，在任一点x主x0,连续性是不成问题的,但在x=x0G是上半连续的却不是下半连续的。定义9.1.4若F:Xt2y在X的每个点都是下半连续的，就说F在X是下半连续的。若F:Xt2y在X的每个点都是上半连续的■就说F在X是上半连续的。若F:Xt2y在X的每个点都是连续的■就说F在X是连续的。为了下面讨论的方便，我们引入集值映射的逆象的概念。

定义9.1.5设定义9.1.5设F:Xt2y是一个集映射,B是Y的一个子集。称F一i(B)二{xgX:F(x)HB工0}u为B的下逆象，或B的相交逆；称F-1(B)={xgX:F(x)HBuB}u为B的上逆象，或B的包含逆基于上述定义，马上可以证明下面的定理。【定理9.1.1】F:Xt2y是下半连续的充要条件是“开集的相交逆为开集”,

即若G是Y的开集，则F-1(G)是X的开集。F:Xt2y是卜半连续l的充要条件是"开集的包含逆为开集”JP若G是Y的开集测F-1(G)u是X的开集。利用这个定理，易知例9.1.1的F:Xt2y是下半连续的，因为开集的相交逆都是开集，但F不是上半连续的，因为开集的包含逆不都是开集。同样,对于例9.1.2的G:Xt2y，因为开集的包含逆都是开集，所以G是上半连续的，但开集的相交逆不都是开集，所以不是下半连续的。面是一个更为方便的上半连续性判别法。为行文方便，欧氏空间的子空间也称为欧氏空间。注意在欧氏空间中，子集作为子空间的紧致性与有界闭性等价。定理9.1.2】设X和Y是欧氏空间.并且Y紧致.集值映射F:Xt2y使得对每个xgX,F(x)是Y的紧致子集。那么，F:Xt2y为上半连续的充要条件是:F的XF(x)={(x,y)gXxY:xgX,ygF(x)xgX是XxY中的一个闭子集。根据这个定理，仅仅因为例9.1.1中的映射的图像表现的闭性在x=x0处遭到破坏，我们马上知道F不是上半连续的。但例9・1・2中的集值映射G的图像表现是XxY=IxI中的闭集■即知G是上半连续的。二、Kakutani不动点定理我们主要关心有强烈应用背景的欧氏空间凸子集到其非空紧致凸子集族的集值映射。设X为欧氏空间的凸集，我们约定，记X的非空紧致凸子集族为P(X)。当然，P(X)e2X定义1设X是欧氏空间的凸集，F:XTP(X)是集值映射。如果xeX使得xeF(x)，就说xeX是集值映射F:XTP(X)的一个不动点为区别起见，常常把由x=f(x)定义的不动点称为Brouwer不动点，而把由xeF(x)定义的不动点称为Kakutani不动点。后者是前者在集值映射情形的推广。Brouwer不动点定理说，闭胞腔的连续自映射必有不动点。而Kakutani不动点定理说，紧凸集的上半连续的集值自映射必有不动点。三、Nash定理的一般证明(重点，讲！我们首先在博弈的一般表示G={S，…,S;u，…,u}之下将1n1nNash均衡的概念加以推广，使之包含混合策略的情形。设G={S，…,S；u，…,u}为一个有n个参与人的博1n1n弈，S={s,…,s}，每个seS为第i个参与人的一个纯策略。STOC\o"1-5"\h\zii1iKiikii上的一个概率分布P二(P，…,P)为第i个参与人的一个混合策略ii1iKi这里,0<P<1,k=1,…,K，并且p+•••+p=1ikii1iKi这时,v(p,…,p)=迓••迓p…pu(s,…,s)i1n1knk1knkk=1k=11n1n1n为这n个博弈的参与人分别采用混合策略p,…,p时，第i个参与人1n所得到的期望支付。为符号方便,我们如前记p=(p,…,p,p,…,p)TOC\o"1-5"\h\z-I1i-1i+1n(p,p)=(p,…,p,p,p,…,p)i-i1i-1ii+1n定义1设博弈G={S，…,S;u,…,u},S={s,…,s}，第i个参与人1n1nii1iKi的混合策略为p=(p，…,p),v(p,…,p)为第i个参与人的期望ii1iKi1ni支付。n个参与人的一组混合策略p〜(p*，…,pj称为博弈g的一1n个Nash均衡，如果对任意的参与人i及参与人i的任意混合策略pi有v(p*,p*)>v(p,p*)ii-iii-i下面我们就证明Nash定理【定理1】设博弈G={S，…,S;u,…,u}，这里n为有限正整数，每个S为1n1ni有限集，则博弈G至少存在一个Nash均衡注意，这个均衡既可能是纯策略均衡，也可能是混合策略均衡。证明(0)对于任意的S二{s，…,s}，记其概率空间为ii1iKiA=Ak厂1={pGRk.:p,…，p>0,pHFp=1}iii1iKi1iK..每个pGA为第i个参与人的一个混合策略。显然A是一个前面讲过...的K-1维标准单纯形.对以下单纯形的笛卡尔积，如前引进简便记法:A=Ax…xA1nA=Ax…xAxAx…xA-.1.-1.F1n⑴记第i个参与人的最佳反应对应为：f:AtP(A)，这里P(A).-...表示A的所有非空紧致凸子集的集合。对任意pgA,f(p)显然是i-i-ii-iA的非空闭子集，所以是A的非空紧致子集。因为期望支付是纯策ii略支付函数的线性组合(事实上还是凸组合)，所以f(p)是A的凸TOC\o"1-5"\h\zi-ii子集。可见，对任意pgA,f(p)是A的非空紧致凸子集。这时，-i-ii-iipGf(p)表示除第i个参与人之外的其余n-1个参与人采用策略pii-i-i时,第i个参与人的一个最佳混合策略。定义总的最优反应对应映射为F:At2a,F(p)=(f(p)，…,f(p))1-1n-n这里2A表示A的所有子集的集合。⑵如果F:At2a有Kakutani不动点p飞F(pJ,即有P飞f(P*),…,P*$f(P*)，则P*怜显然就是该博弈的一个Nash均11-1nn-n衡。利用K