《博弈論：原理、模型與教程》第04章 Nash均衡解的特性 第02節(jié) Nash均衡的存在性

#例子2Cournot寡頭博弈模型假設(shè)每個(gè)寡頭企業(yè)具有相同的不變單位成本c，即c(q)二c?qiii需求函數(shù)為線性形式P=a-(q+q)，所以12兀(q,q)=q(a一q一q一c)iijiij此時(shí)，最優(yōu)化的一階條件為&_/、_nTOC\o"1-5"\h\z—i=a—(q+q)—q—c=0dq121匕兀1_/、_n—2=a—(q+q)—q—c=0dqi22企業(yè)的最優(yōu)反應(yīng)函數(shù)為

q=R(q)=(a—q—c)11222q=R(q)=(a一q一c)22121聯(lián)立求解上式，可得企業(yè)的Nash均衡產(chǎn)量為q*=q*=3(a—c)企業(yè)的Nash均衡利潤(rùn)分別為兀*=兀*=1(a—c)21295-1)5-2)在上述簡(jiǎn)單假設(shè)下，兩個(gè)企業(yè)的最優(yōu)反應(yīng)函數(shù)5-1)5-2)圖5-1Cournot模型的Nash均衡線的交點(diǎn)即為Nash圖5-1Cournot模型的Nash均衡第二部分實(shí)施Nash定理的證明已經(jīng)知道，在考慮混合戰(zhàn)略的情況下，一個(gè)完全信息靜態(tài)博弈“通常”都存在納什均衡。這一認(rèn)識(shí)最早由納什(Nash,1950,1951)進(jìn)行了證明，稱為納什定理。定理2.1納什定理如果完全信息靜態(tài)博弈G=《,ul是有限的,即參與人是有限的，S包含的純策略也是有限的，那么一定存在至少一個(gè)(純策略或混合策略)納什均衡。所謂“通?！敝傅木褪遣┺牡挠邢扌?。到目前為止,我們分析的博弈都滿足這兩個(gè)條件。參與人有限——通常為兩個(gè)人。S也是有限的——要么存在若干個(gè)純策略,例如猜幣游戲；要么雖然純策略由無(wú)窮多，但卻是有界閉集2例如古諾模型中的戰(zhàn)略集S=[0,a]，所以前i面分析的靜態(tài)博弈都存在納什均衡。對(duì)納什定理的證明分三個(gè)部分來(lái)完成第一步，介紹不動(dòng)點(diǎn)定理；第二步，說(shuō)明納什均衡就是不動(dòng)點(diǎn)；2在數(shù)學(xué)中，有界閉集必然意味著是有限的，即它不是無(wú)限的，或者說(shuō)拒斥了無(wú)限情。

第三步，完成證明。第一步，不動(dòng)點(diǎn)定理。圖2-29中的方框?yàn)檎叫?。bd為45°線，它實(shí)際上等價(jià)于函數(shù)y=f(x)=x。BD線上的每一點(diǎn)都滿足f(x)=x,把滿足f(x)=x的x稱為不動(dòng)點(diǎn)。BD線所代表的函數(shù)自變量x取值為［0,1］，稱為定義域，而因變量y的取值為［0,1］,稱為值域。定義域和值域都為［0,1］的函數(shù)f(x)，又可寫作f:［0,1］T［0,1］，讀作從［0,1］到［0,1］的映射?，F(xiàn)在做一個(gè)小游戲：拿一支筆，從AB線出發(fā)任意畫一條曲線，記住可以任意畫，但必須連續(xù)畫不能斷裂，至到CD線結(jié)束。這時(shí)發(fā)現(xiàn)無(wú)論如何畫，這條曲線一定會(huì)和BD相交，這個(gè)交點(diǎn)就是不動(dòng)點(diǎn)因?yàn)槿我猱嫷那€等價(jià)于一個(gè)函數(shù)g(x)，沒(méi)有斷裂意味著它是連續(xù)的，與BD線相交意味著g*(X*)，所以交點(diǎn)為不動(dòng)點(diǎn)。所有任意畫的曲線都有如下的性質(zhì)：定義域［0,1］是非空的、有界的、閉的、凸集合，簡(jiǎn)稱非空凸緊集。有界閉集即為緊集。函數(shù)f(x)是連續(xù)的，并且是自身對(duì)自身的映射。上面考慮的只是一元函數(shù)，對(duì)于n元函數(shù)是不是如果滿足上述性質(zhì)就存在不動(dòng)點(diǎn)？布勞爾(Brower)定理肯定地回答了這一點(diǎn)。定理2.2—布勞爾(Brower)不動(dòng)點(diǎn)定理。假設(shè)auRn是一個(gè)非空凸緊集合，并且f:ATA是一個(gè)連續(xù)函數(shù)；那么f(?)必有一個(gè)不動(dòng)點(diǎn);即，存在一個(gè)xeA使得x=f(x)o這里R為實(shí)數(shù)，Rn為實(shí)數(shù)的n重笛卡爾積，x為n維向量。在前面的例子中n二1,A二［0,1］o在實(shí)際運(yùn)用中，我們常常遇到的不是函數(shù)而是對(duì)應(yīng)的情況，例如猜幣游戲這個(gè)博弈存在的是最優(yōu)反應(yīng)對(duì)應(yīng)，而不是函數(shù)，這就有了對(duì)布勞爾不動(dòng)點(diǎn)定理的推廣定理2.3—角谷(Kakutani)不動(dòng)點(diǎn)定理。假設(shè)aurn是非空凸緊集，并且f:ATA是上半連續(xù)對(duì)應(yīng)，并且對(duì)于每一個(gè)xeA，集合f(x)uA是非空凸集，那么f(?)必有一個(gè)不動(dòng)點(diǎn)。即，存在一個(gè)xeA使得xef(x)o角谷不動(dòng)點(diǎn)定理與布勞爾不動(dòng)點(diǎn)定理的區(qū)別在于①映射f為對(duì)應(yīng)而不是函數(shù)，所以f(x)為一個(gè)集合(一個(gè)點(diǎn)也能組成集合，所以函數(shù)是對(duì)應(yīng)的特例)。②映射f是上半連續(xù)的。一個(gè)對(duì)應(yīng)只有既是上半連續(xù)又是下半連續(xù)才能稱為連續(xù)，因而上半連續(xù)比連續(xù)的要求要弱。關(guān)于對(duì)應(yīng)的上半連續(xù)，就是指如果存在一個(gè)序列xl,x2,…,xn收斂于x并且y1ef(x1),y2ef(x2),…,ynef(xn)收斂于y，那么一定有yef(x)(如果f(x)只有唯一值，那么e就變?yōu)镴即對(duì)應(yīng)包含著它的極限點(diǎn)在圖2-30(a)中，當(dāng)xta,即從a的左邊向其收斂時(shí)，f(x)TA但我們看到A電f(a)，即對(duì)應(yīng)f(x)并不包含極限點(diǎn)A，所以它不是上半連續(xù)的。在圖2-30(b)中，對(duì)應(yīng)f(x)包含它的每一個(gè)序列的極限點(diǎn)，特別是Aef(a)，因而它滿足上半連續(xù)，但它不是連續(xù)的。例如，猜幣游戲中每個(gè)參與人的最優(yōu)反應(yīng)對(duì)應(yīng)就是上半連續(xù)的。對(duì)于函數(shù)而言，上半連續(xù)就等同于連續(xù)。y打^(xL.y打^(xL.oAiOabxy”U(xL.JaIJ|.Oabx(a)非上半連續(xù)(a)非上半連續(xù)(b)上半連續(xù)2-30對(duì)應(yīng)的上半連續(xù)第二步，納什均衡是不動(dòng)點(diǎn)。根據(jù)納什均衡的定義，在給定其他參與人策略的情況下，參與人i選擇一個(gè)策略以使其收益最大化，并且對(duì)每一個(gè)參與人都如此，即納什均衡是一個(gè)使每一個(gè)參與人收益最大的策略組合針對(duì)其他參與人不同的策略，參與人i都有一個(gè)最優(yōu)策略與之相對(duì)應(yīng)，用數(shù)學(xué)來(lái)表示就是最優(yōu)反應(yīng)函數(shù)或?qū)?yīng)。如果參與人i的最優(yōu)反應(yīng)函數(shù)(對(duì)應(yīng))定義為B(p，…,p,p，…,p)=p,其中i=1,…,n,那么n個(gè)參與人的最優(yōu)反i1i-1i+1ni應(yīng)函數(shù)（對(duì)應(yīng)）就構(gòu)成了一個(gè)方程，將其定義為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:），即納什均衡是一個(gè)不動(dòng)點(diǎn)。例如，古1n1ni12諾模型中的最優(yōu)反應(yīng)函數(shù)共同構(gòu)成了一個(gè)方程組r（q，q），i二1,2，這i12個(gè)方程的解既是不動(dòng)點(diǎn)，也是納什均衡。第三步，完成證明。現(xiàn)在要完成的是證明：①最優(yōu)反應(yīng)對(duì)應(yīng)B的定義域?yàn)槎煌咕oi集；②B為上半連續(xù)的對(duì)應(yīng)。i由于R是B（I二1,2,…,n）的方程組，B滿足這兩個(gè)條件，總的策略ii方程R必然滿足這兩個(gè)條件，而根據(jù)不動(dòng)點(diǎn)定理，我們知道存在著不動(dòng)點(diǎn)（p：，…，p：），使得R（p：，…，p：）=（p：，…，p：）（1）定義域?yàn)榉强胀咕o集。所謂有界集合就是任意畫一個(gè)圓（圓的半徑可以任意大，但不能無(wú)窮大）可以把它包下。所謂閉集就是包含

邊界的集合。有界閉集即為緊致集合，簡(jiǎn)稱緊集。所謂凸集就是在集合內(nèi)任意找兩點(diǎn)，連接兩點(diǎn)的直線一定位于集合中。圖2-31中的直線和三角平面顯然是有界的，同時(shí)也是閉的，即它們是緊集。同時(shí)它們也是凸集。而圖2-32中的環(huán)是非空緊集，但卻不是凸集。如果博弈有n個(gè)人參與人，參與人i有k個(gè)純策略，那么策略方程R的定義域?yàn)椋?,1］kXn，它表示［0,1］的kXn重笛卡爾積，例如函數(shù)f（X,y）,x,yGA那么函數(shù)的定義域就為Aixi，即x,y都從集合A中取值。由于混合策略的取值為［0,1］,顯然［0,1］為非空凸緊集，所以［0,1］kxn也是非空凸緊集。在古諾模型中，它的定義域雖然與上面講的有所不同，即純策略有無(wú)窮多個(gè)，但策略q（產(chǎn)量）的取值為［0,a］（或［0,+型，它同樣是非空凸集。這表明納什均衡真正需要的并不是“有限的”要求，而是策略空間必須為緊致集合。如果一個(gè)參與人有兩個(gè)純策略x和y那么所有混合策略集合（策略空間）就是滿足x+y二1,x和y都大于等于零的直線。如果有三個(gè)純策略x,y,z，那么所有的混合策略集合（策略空間）就是一個(gè)滿足x+y+z二1,x,y,z都大于等于零的一個(gè)三角平面。如果2-31所示。（2）最優(yōu)反應(yīng)對(duì)應(yīng)是上半連續(xù)的。根據(jù)前面的介紹，我們已經(jīng)知道混合策略空間是非空凸緊集，并且預(yù)期收益函數(shù)是混合策略的線性函數(shù)，因而它是連續(xù)的和凹的（因?yàn)槠脼槔硇?，這就保證了根據(jù)最大化預(yù)期收益函數(shù)得到的最優(yōu)反應(yīng)對(duì)應(yīng)必然是上半連續(xù)和非空凸集，這在數(shù)學(xué)上被稱為最大化定理。綜上所述,最優(yōu)反應(yīng)方程R（p,,p）滿足不動(dòng)點(diǎn)定理的兩個(gè)條件:1n策略空間為非空凸緊集，最優(yōu)反應(yīng)對(duì)應(yīng)為上半連續(xù)并且是非空凸集。因而存在著不動(dòng)點(diǎn)，而不動(dòng)點(diǎn)就是納什均衡。知識(shí)擴(kuò)展》一、集值映射及其半連續(xù)性這里限于在歐氏空間中展開討論，當(dāng)然，我們也說(shuō)成拓?fù)淇臻g，但在這里的上下文，讀者可以將拓?fù)淇臻g直接理解為歐氏空間。設(shè)X是一個(gè)拓?fù)淇臻g，X的所有子集的全體記作2X。即2x={G:GuX}.注意，0e2x,Xe2x定義9.1.1設(shè)X和Y是兩個(gè)拓?fù)淇臻g。若對(duì)任一xeX,確定Y的一個(gè)子集(己作)F(x)與之對(duì)應(yīng)。這樣得到的對(duì)應(yīng)F:Xt2y稱作一個(gè)點(diǎn)對(duì)集映射(point-to-setmapping)或一個(gè)集值映射(set-valuedmapping)。相應(yīng)地，以往對(duì)每個(gè)xeX確定一個(gè)f(x)eY的映射f:XtY稱為單值映射(single-valuedmapping)如同單值映射的情形，我們引進(jìn)集值映射的圖像的概念。

定義9.1.2設(shè)F:XT2y是一個(gè)集值映射。稱XxY的子集工F(x)={(x,y)eXxY:xeX,yeF(x)}xeX為F的圖像(graph)表現(xiàn)下面我們建立集值映射的半連續(xù)性和連續(xù)性的概念定義9.1.3設(shè)F:設(shè)F:XT2y是一個(gè)集映射，xoeX9若對(duì)Y的與F(xo)之交館的每個(gè)開集G,館的每個(gè)開集G,若對(duì)Y的包含F(xiàn)(xo)的每個(gè)開集g，存在X中包含xo的一個(gè)開集存在x中包含xo的一個(gè)開集U(x0)使得xeU(xo)蘊(yùn)涵F(x)GH0.就說(shuō)F在xo是下半連續(xù)的(lowersemicontinuous)。U(xO)使得xeU(xo)蘊(yùn)涵F(x)uG,就說(shuō)F在xo是上半連續(xù)的(uppersemicontinuous)。若F在xO既是下半連續(xù)的又是上半連續(xù)的，就說(shuō)F在xo是連續(xù)的(continuous)集值映射的兩種半連續(xù)性和連續(xù)性,都是單值映射的通常的連續(xù)性概念的推廣。事實(shí)上，如果把單值映射看作在定義域的每點(diǎn)取值域的一個(gè)單點(diǎn)集的集值映射，則作為集值映射的下半連續(xù)性、上半連續(xù)性和連續(xù)性，都與作為單值映射的通常的連續(xù)性吻合。對(duì)于集值映射，下半連續(xù)性和上半連續(xù)性是不同的。請(qǐng)看下面的例子。例9.1.1設(shè)X=Y=I是實(shí)數(shù)軸上的一個(gè)閉區(qū)間，集值映射F:Xt2y由圖9.1給出。容易驗(yàn)證，在任一點(diǎn)x主x0，連續(xù)性是不成問(wèn)題的。即在任一點(diǎn)x主X0，F(xiàn)既是下半連續(xù)的又是上半連續(xù)的。但在x0&X，F(xiàn)是下半連續(xù)的而不是上半連續(xù)的。例9.1.2仍取X=Y=I為閉區(qū)間，集值映射G:Xt2y由圖9.2

給出。容易驗(yàn)證，在任一點(diǎn)x主x0,連續(xù)性是不成問(wèn)題的,但在x=x0G是上半連續(xù)的卻不是下半連續(xù)的。定義9.1.4若F:Xt2y在X的每個(gè)點(diǎn)都是下半連續(xù)的，就說(shuō)F在X是下半連續(xù)的。若F:Xt2y在X的每個(gè)點(diǎn)都是上半連續(xù)的■就說(shuō)F在X是上半連續(xù)的。若F:Xt2y在X的每個(gè)點(diǎn)都是連續(xù)的■就說(shuō)F在X是連續(xù)的。為了下面討論的方便，我們引入集值映射的逆象的概念。

定義9.1.5設(shè)定義9.1.5設(shè)F:Xt2y是一個(gè)集映射,B是Y的一個(gè)子集。稱F一i(B)二{xgX:F(x)HB工0}u為B的下逆象，或B的相交逆；稱F-1(B)={xgX:F(x)HBuB}u為B的上逆象，或B的包含逆基于上述定義，馬上可以證明下面的定理?！径ɡ?.1.1】F:Xt2y是下半連續(xù)的充要條件是“開集的相交逆為開集”,

即若G是Y的開集，則F-1(G)是X的開集。F:Xt2y是卜半連續(xù)l的充要條件是"開集的包含逆為開集”JP若G是Y的開集測(cè)F-1(G)u是X的開集。利用這個(gè)定理，易知例9.1.1的F:Xt2y是下半連續(xù)的，因?yàn)殚_集的相交逆都是開集，但F不是上半連續(xù)的，因?yàn)殚_集的包含逆不都是開集。同樣,對(duì)于例9.1.2的G:Xt2y，因?yàn)殚_集的包含逆都是開集，所以G是上半連續(xù)的，但開集的相交逆不都是開集，所以不是下半連續(xù)的。面是一個(gè)更為方便的上半連續(xù)性判別法。為行文方便，歐氏空間的子空間也稱為歐氏空間。注意在歐氏空間中，子集作為子空間的緊致性與有界閉性等價(jià)。定理9.1.2】設(shè)X和Y是歐氏空間.并且Y緊致.集值映射F:Xt2y使得對(duì)每個(gè)xgX,F(x)是Y的緊致子集。那么，F(xiàn):Xt2y為上半連續(xù)的充要條件是:F的XF(x)={(x,y)gXxY:xgX,ygF(x)xgX是XxY中的一個(gè)閉子集。根據(jù)這個(gè)定理，僅僅因?yàn)槔?.1.1中的映射的圖像表現(xiàn)的閉性在x=x0處遭到破壞，我們馬上知道F不是上半連續(xù)的。但例9?1?2中的集值映射G的圖像表現(xiàn)是XxY=IxI中的閉集■即知G是上半連續(xù)的。二、Kakutani不動(dòng)點(diǎn)定理我們主要關(guān)心有強(qiáng)烈應(yīng)用背景的歐氏空間凸子集到其非空緊致凸子集族的集值映射。設(shè)X為歐氏空間的凸集，我們約定，記X的非空緊致凸子集族為P(X)。當(dāng)然，P(X)e2X定義1設(shè)X是歐氏空間的凸集，F(xiàn):XTP(X)是集值映射。如果xeX使得xeF(x)，就說(shuō)xeX是集值映射F:XTP(X)的一個(gè)不動(dòng)點(diǎn)為區(qū)別起見(jiàn)，常常把由x=f(x)定義的不動(dòng)點(diǎn)稱為Brouwer不動(dòng)點(diǎn)，而把由xeF(x)定義的不動(dòng)點(diǎn)稱為Kakutani不動(dòng)點(diǎn)。后者是前者在集值映射情形的推廣。Brouwer不動(dòng)點(diǎn)定理說(shuō)，閉胞腔的連續(xù)自映射必有不動(dòng)點(diǎn)。而Kakutani不動(dòng)點(diǎn)定理說(shuō)，緊凸集的上半連續(xù)的集值自映射必有不動(dòng)點(diǎn)。三、Nash定理的一般證明(重點(diǎn)，講！我們首先在博弈的一般表示G={S，…,S;u，…,u}之下將1n1nNash均衡的概念加以推廣，使之包含混合策略的情形。設(shè)G={S，…,S；u，…,u}為一個(gè)有n個(gè)參與人的博1n1n弈，S={s,…,s}，每個(gè)seS為第i個(gè)參與人的一個(gè)純策略。STOC\o"1-5"\h\zii1iKiikii上的一個(gè)概率分布P二(P，…,P)為第i個(gè)參與人的一個(gè)混合策略ii1iKi這里,0<P<1,k=1,…,K，并且p+???+p=1ikii1iKi這時(shí),v(p,…,p)=迓??迓p…pu(s,…,s)i1n1knk1knkk=1k=11n1n1n為這n個(gè)博弈的參與人分別采用混合策略p,…,p時(shí)，第i個(gè)參與人1n所得到的期望支付。為符號(hào)方便,我們?nèi)缜坝沺=(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設(shè)博弈G={S，…,S;u,…,u},S={s,…,s}，第i個(gè)參與人1n1nii1iKi的混合策略為p=(p，…,p),v(p,…,p)為第i個(gè)參與人的期望ii1iKi1ni支付。n個(gè)參與人的一組混合策略p?(p*，…,pj稱為博弈g的一1n個(gè)Nash均衡，如果對(duì)任意的參與人i及參與人i的任意混合策略pi有v(p*,p*)>v(p,p*)ii-iii-i下面我們就證明Nash定理【定理1】設(shè)博弈G={S，…,S;u,…,u}，這里n為有限正整數(shù)，每個(gè)S為1n1ni有限集，則博弈G至少存在一個(gè)Nash均衡注意，這個(gè)均衡既可能是純策略均衡，也可能是混合策略均衡。證明(0)對(duì)于任意的S二{s，…,s}，記其概率空間為ii1iKiA=Ak廠1={pGRk.:p,…，p>0,pHFp=1}iii1iKi1iK..每個(gè)pGA為第i個(gè)參與人的一個(gè)混合策略。顯然A是一個(gè)前面講過(guò)...的K-1維標(biāo)準(zhǔn)單純形.對(duì)以下單純形的笛卡爾積，如前引進(jìn)簡(jiǎn)便記法:A=Ax…xA1nA=Ax…xAxAx…xA-.1.-1.F1n⑴記第i個(gè)參與人的最佳反應(yīng)對(duì)應(yīng)為：f:AtP(A)，這里P(A).-...表示A的所有非空緊致凸子集的集合。對(duì)任意pgA,f(p)顯然是i-i-ii-iA的非空閉子集，所以是A的非空緊致子集。因?yàn)槠谕Ц妒羌儾遡i略支付函數(shù)的線性組合(事實(shí)上還是凸組合)，所以f(p)是A的凸TOC\o"1-5"\h\zi-ii子集?？梢?jiàn)，對(duì)任意pgA,f(p)是A的非空緊致凸子集。這時(shí)，-i-ii-iipGf(p)表示除第i個(gè)參與人之外的其余n-1個(gè)參與人采用策略pii-i-i時(shí),第i個(gè)參與人的一個(gè)最佳混合策略。定義總的最優(yōu)反應(yīng)對(duì)應(yīng)映射為F:At2a,F(p)=(f(p)，…,f(p))1-1n-n這里2A表示A的所有子集的集合。⑵如果F:At2a有Kakutani不動(dòng)點(diǎn)p飛F(pJ,即有P飛f(P*),…,P*$f(P*)，則P*憐顯然就是該博弈的一個(gè)Nash均11-1nn-n衡。利用K