[所有分類]博弈論：原理、模型與教程第04章Nash均衡解的特性第02節(jié)Nash均衡的存在性

《[所有分類]博弈論：原理、模型與教程第04章Nash均衡解的特性第02節(jié)Nash均衡的存在性》由會(huì)員分享，可在線閱讀，更多相關(guān)《[所有分類]博弈論：原理、模型與教程第04章Nash均衡解的特性第02節(jié)Nash均衡的存在性（33頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、博弈論：原理、模型與教程 第一部分 完全信息靜態(tài)博弈第4章 Nash均衡解的特性4.2 Nash均衡解的存在性（已精細(xì)訂正！）=本節(jié)推薦參考文獻(xiàn)：（01）張石生.不動(dòng)點(diǎn)理論及應(yīng)用（M）. 重慶：重慶出版社，1984年8月第1版.（注：有趣的是，該書的責(zé)任編輯尹明善，就是后來從摩配起步創(chuàng)業(yè)成功的力帆老總）（02）張奠宙，顧鶴榮.不動(dòng)點(diǎn)定理（M）. 沈陽：遼寧教育出版社，1989年4月第1版.（03）王則軻，左再思，李志強(qiáng).經(jīng)濟(jì)學(xué)拓?fù)浞椒ǎ∕）. 北京：北京大學(xué)出版社，2002年1月第1版.=將Nash均衡作為博弈的解，會(huì)面臨這樣的問題：Nash均衡是否存在，或者說對(duì)于所關(guān)心的博弈問題，是否一定存

2、在一個(gè)Nash均衡？非常慶幸的是，我們能夠得到一個(gè)肯定的答案。下面將對(duì)本書所涉及的博弈論中一些經(jīng)典的存在性結(jié)論進(jìn)行介紹。定理4-1（Nash均衡的存在性定理1，1950） 每一個(gè)有限的戰(zhàn)略式博弈至少存在一個(gè)Nash均衡（包括純戰(zhàn)略和混合戰(zhàn)略Nash均衡）。定理4-1是博弈論中關(guān)于Nash均衡存在性的最基本定理。1950年，John Nash在文章Equilibrium points in n-person games 中首次提出Nash均衡的概念，并給出該存在性定理。無論怎樣強(qiáng)調(diào)該定理對(duì)于博弈論以后的發(fā)展的意義都不過分，因?yàn)镹ash均衡之后的博弈論的發(fā)展（尤其是非合作博弈論的發(fā)展）基本上都是以

3、該定理為基石的。定理4-1的條件簡(jiǎn)單，但得出的結(jié)論卻十分肯定。下面給出的定理的詳細(xì)證明。供有興趣的讀者參考。為證明該定理，先給出如下必要的基本概念。定義4-1 從集合到集合的一個(gè)規(guī)則，若滿足：,都中的一個(gè)集合與之對(duì)應(yīng)，則稱為由到的對(duì)應(yīng)，記為：。簡(jiǎn)單地說，對(duì)應(yīng)是函數(shù)概念的擴(kuò)展，函數(shù)將集合中的點(diǎn)映到中的點(diǎn)，而對(duì)應(yīng)將集合中的點(diǎn)映到中的子集。對(duì)應(yīng)：的圖像是指中的集合。對(duì)應(yīng)：為上半連續(xù)的，是指和中任意包含的開集，在中都存在的一個(gè)鄰域，只要，就有。顯然對(duì)應(yīng)的上半連續(xù)性為函數(shù)連續(xù)性概念的擴(kuò)展，對(duì)應(yīng)一個(gè)函數(shù)它的上半連續(xù)性就等于它的連續(xù)性。對(duì)應(yīng)：的圖像為閉圖，是指任意給定若就有。閉圖將閉集的概念推廣到集合的直積

4、中。若對(duì)應(yīng)的值域?yàn)榫o集，則有閉圖就意味著為上半連續(xù)的。有了這些基本概念，下面證明基本定理4-1.證明的基本思想是將Kakutani不動(dòng)點(diǎn)定理應(yīng)用于參與人的反應(yīng)對(duì)應(yīng)上。參與人的反應(yīng)對(duì)應(yīng) 為對(duì)手選擇時(shí)，將每一個(gè)戰(zhàn)略組合映射到的一個(gè)混合戰(zhàn)略集。給定對(duì)手選擇，給混合戰(zhàn)略集中的每個(gè)戰(zhàn)略最大化參與人的支付。這里雖然只依賴于，而不依賴于，仍將 寫作的對(duì)應(yīng)，因?yàn)樯院髸?huì)在戰(zhàn)略組合空間之中尋找一個(gè)不動(dòng)點(diǎn)。定義反應(yīng)對(duì)應(yīng)為的Cartesian直積，即，則的不動(dòng)點(diǎn)為滿足 的戰(zhàn)略組合，因此對(duì)每個(gè)參與人，所以的不動(dòng)點(diǎn)即為一個(gè)Nash均衡。因此，對(duì)定理4-1的證明轉(zhuǎn)化為證明參與人的反應(yīng)對(duì)應(yīng)具有不動(dòng)點(diǎn)。由Kakutani不動(dòng)點(diǎn)

5、定理，,存在不動(dòng)點(diǎn)的充分條件為：為有限維歐氏空間的緊的凸子集；非空；為凸；有閉圖。在這里，若成立，即為緊集，且成立，則對(duì)應(yīng)為上半連續(xù)的。下面分別證明這些條件滿足：首先，因?yàn)闉榫S數(shù)為的單純形，所以滿足。其次，因?yàn)槊恳粋€(gè)參與人的支付函數(shù)在自己的混合戰(zhàn)略上是線性的，因此也是連續(xù)的。連續(xù)函數(shù)在緊集上取得最大值，所以非空，滿足。再次，為了證明 ，采用反證法。若非凸，則存在及 ，且存在，使得，但對(duì)每一個(gè)，有 因此若，是相對(duì)于的最優(yōu)反應(yīng)，那么它們的加權(quán)平均也是。而這與非凸矛盾，所以凸。最后，仍用反證法證明 。假設(shè)不滿足，則存在序列但，所以存在,。因此存在和，使得。又因?yàn)闉檫B續(xù)的且，因此對(duì)足夠大的,有 所以對(duì)

6、于 嚴(yán)格優(yōu)于，這與矛盾。所以 滿足。至此，也就完成了有限博弈中Nash均衡的存在性的證明。在經(jīng)濟(jì)學(xué)和現(xiàn)實(shí)生活中也有很多無限博弈，即參與人的戰(zhàn)略有無限多個(gè)或參與人的戰(zhàn)略能在一個(gè)集合中連續(xù)取值，如廠商之間的價(jià)格或產(chǎn)量競(jìng)爭(zhēng)。對(duì)應(yīng)于這些情況有如下的存在性定理。定理4-2（Nash均衡的存在性定理2，Debru 1952,Glicksberg 1952,Fan 1952） 對(duì)于戰(zhàn)略式博弈,若為歐氏空間的非空緊凸子集，支付函數(shù)關(guān)于戰(zhàn)略組合連續(xù)，關(guān)于擬凹，則該博弈存在純戰(zhàn)略的Nash均衡。該定理的證明與Nash均衡的存在性定理4-1類似，支付函數(shù)關(guān)于所有參與人戰(zhàn)略組合的連續(xù)性意味著反應(yīng)對(duì)應(yīng)具有閉圖。另外，支

7、付函數(shù)關(guān)于自己戰(zhàn)略的擬凹性意味著反應(yīng)對(duì)應(yīng)為凸值的。同樣運(yùn)用Kakutani不動(dòng)點(diǎn)定理便可以證明該定理。注意：在上述定理中關(guān)于參與人戰(zhàn)略組合的連續(xù)性條件是非常重要的，它類似于有限博弈中期望支付關(guān)于混合戰(zhàn)略是連續(xù)的，因此Nash均衡的存在性定理4-1可以看作是該定理的特例。但同時(shí)在參與人的支付函數(shù)上該定理的條件較Nash均衡的存在性條件強(qiáng)，但正是因?yàn)檩^強(qiáng)的條件從而導(dǎo)致了較強(qiáng)的結(jié)果純戰(zhàn)略Nash均衡的存在性！在很多博弈中不存在純戰(zhàn)略的Nash均衡，但卻存在混合戰(zhàn)略 Nash均衡，因此將上述條件放松便得到相關(guān)條件下關(guān)于混合戰(zhàn)略的存在性結(jié)論。定理4-3(Nash均衡的存在性定理3，Glicksberg

8、1952) 對(duì)于戰(zhàn)略式博弈，若戰(zhàn)略空間為距離空間中的非空緊子集，支付函數(shù)關(guān)于戰(zhàn)略組合連續(xù)，則該博弈存在混合戰(zhàn)略的Nash均衡（將純戰(zhàn)略Nash均衡作為混合戰(zhàn)略Nash均衡的特例）。在上述關(guān)于Nash均衡的存在性定理4-2和定理4-3中，都要求參與人的支付關(guān)于所有參與人戰(zhàn)略組合的連續(xù)性，在經(jīng)濟(jì)學(xué)的一些理論或應(yīng)用中，非連續(xù)性或非擬凹的收益函數(shù)是很常見的。如果有不連續(xù)的收益，則一個(gè)緊的戰(zhàn)略空間就不再確保參與人對(duì)應(yīng)其對(duì)手戰(zhàn)略的最優(yōu)反應(yīng)一定存在。為了探尋此時(shí)均衡的存在性，Dasgupta進(jìn)一步對(duì)以上存在性條件進(jìn)行放松，得到如下存在性定理。定理4-4（Nash均衡的存在性定理4，Dasgupta和Mask

9、in 1986） 對(duì)于戰(zhàn)略式博弈 ，若對(duì)于所有的，為有限維歐氏空間的非空緊凸子集；關(guān)于擬凹，關(guān)于上半連續(xù)且 關(guān)于連續(xù)，則該博弈存在一個(gè)純戰(zhàn)略的Nash均衡。該定理的證明仍然與前述定理的證明類似，仍然采用Kakutani不動(dòng)點(diǎn)定理，其中收益函數(shù)關(guān)于自己戰(zhàn)略的擬凹性保證了反應(yīng)對(duì)應(yīng)的凸值性，的極大值關(guān)于的連續(xù)性及的上半連續(xù)性保證了反應(yīng)對(duì)應(yīng)具有閉圖，因此證明過程類似定理4-1，這里不再重復(fù)。在上述定理的基礎(chǔ)上，Dasgupta繼續(xù)對(duì)的連續(xù)性及擬凹性進(jìn)行放松，得到了當(dāng)支付函數(shù)只在戰(zhàn)略集的某個(gè)子集上不連續(xù)時(shí)，相關(guān)條件下混合戰(zhàn)略均衡的存在性。其思想是用有限分割去近似戰(zhàn)略空間，證明的方法仍然是用Kakutan

10、i不動(dòng)點(diǎn)定理。由于涉及一些較復(fù)雜的數(shù)學(xué)名詞的解釋，這里不再介紹，建議有興趣的讀者參閱相關(guān)文獻(xiàn)。至此為止，所列出的關(guān)于Nash均衡的存在性結(jié)論其證明思想都是Kakutani不動(dòng)點(diǎn)定理。從數(shù)學(xué)上看，以上一系列的存在性定理都是在不斷放松Kakutani不動(dòng)點(diǎn)定理成立的條件，而且都在試圖不斷放松對(duì)支付函數(shù)的要求以滿足Kakutani不動(dòng)點(diǎn)定理的條件。在反應(yīng)對(duì)應(yīng)具體凸性這一點(diǎn)上它們是相同的。當(dāng)反應(yīng)對(duì)應(yīng)的凸性不再滿足，而只是滿足一定的單調(diào)性（通常指單調(diào)增，有些情況下可以單調(diào)減）時(shí)，支付函數(shù)也只是滿足一定的單調(diào)性時(shí)，關(guān)于Nash均衡的存在性結(jié)論也已經(jīng)有所發(fā)展，這便是超模博弈理論。超模博弈理論為戰(zhàn)略空間只是滿

11、足一定的序結(jié)構(gòu)，支付函數(shù)只是滿足一定的單調(diào)性的博弈的Nash均衡存在性提供了一定的保證，不僅如此，它還保證了這種博弈有純戰(zhàn)略的Nash均衡。在戰(zhàn)略空間的一定序結(jié)構(gòu)下，該類博弈的Nash均衡的戰(zhàn)略集的上下界存在且與可理性化戰(zhàn)略集的上下界重合。在思想方法上由于反應(yīng)對(duì)應(yīng)的凸性假設(shè)不再必要，該類博弈的Nash均衡的存在性的理論基礎(chǔ)不再是Kakutani不動(dòng)點(diǎn)定理，而是Tarski不動(dòng)點(diǎn)定理。關(guān)于該類博弈的具體內(nèi)容有興趣的讀者請(qǐng)參閱Topkis的相關(guān)著作。實(shí)際講授=第一部分 回顧例子1 猜幣游戲一般地，用表示在給定參與人2的戰(zhàn)略的情況下，參與人1的最優(yōu)反應(yīng)。由式（3-4）可得= = （3-10）在式（3

12、-10）中，參與人1的期望收益在時(shí)隨遞增，在時(shí)隨遞減。因此當(dāng)時(shí)，參與人1的最優(yōu)反應(yīng)（即選擇正面）；當(dāng)時(shí)，參與人1的最優(yōu)反應(yīng)（即選擇反面）（參見圖3-7中的兩段水平虛線）。 1 （反面） （正面）（正面）1（反面）圖3-7 參與人的最優(yōu)反應(yīng)前面已經(jīng)提到，在時(shí)，參與人1選擇純戰(zhàn)略正面或反面是無差異的。而且從式（3-10）可以看到，參與人1的期望收益在時(shí)與無關(guān)，所有混合戰(zhàn)略對(duì)參與人1都是無差異的。也就是說，當(dāng)時(shí)，對(duì)于到之間的任何，混合戰(zhàn)略都是對(duì)的最優(yōu)反應(yīng)，即（參見圖3-7所示中間的豎線段）。綜上分析，可得參與人1最優(yōu)反應(yīng)為 （3-11）在式（3-11）中，當(dāng)時(shí)，可以為 中的任一值，從而使得有不止一個(gè)

13、值。因此，稱為參與人1的最優(yōu)反應(yīng)響應(yīng)（best correspondence），而不是最優(yōu)反應(yīng)函數(shù) 最優(yōu)反應(yīng)函數(shù)表示給定參與人2的一個(gè)戰(zhàn)略，參與人1僅有一個(gè)最優(yōu)戰(zhàn)略與之相對(duì)應(yīng)；而最優(yōu)反應(yīng)響應(yīng)則表示給定參與人2的一個(gè)戰(zhàn)略，參與人1不只有一個(gè)最優(yōu)戰(zhàn)略與之相對(duì)應(yīng)。參見第5章中關(guān)于Cournot模型的介紹。對(duì)稱地，可得參與人2的最優(yōu)反應(yīng)響應(yīng)。將參與人1與參與人2的最優(yōu)反應(yīng)響應(yīng)置于同一張平面，最優(yōu)反應(yīng)響應(yīng)曲線的交點(diǎn)，即是Nash均衡。（反面）11/21O（正面）（反面）正面圖 參與人1的最優(yōu)反應(yīng)對(duì)應(yīng) 1/21正面1/2背面 01正面圖 參與人2的最優(yōu)反應(yīng)對(duì)應(yīng)1/2納什均衡點(diǎn)（不動(dòng)點(diǎn)）1正面1/2背面 0

14、1正面圖 納什均衡點(diǎn)例子2 Cournot寡頭博弈模型假設(shè)每個(gè)寡頭企業(yè)具有相同的不變單位成本，即 ，需求函數(shù)為線性形式，所以此時(shí)，最優(yōu)化的一階條件為企業(yè)的最優(yōu)反應(yīng)函數(shù)為聯(lián)立求解上式，可得企業(yè)的Nash均衡產(chǎn)量為 （5-1）企業(yè)的Nash均衡利潤(rùn)分別為 （5-2） 在上述簡(jiǎn)單假設(shè)下，兩個(gè)企業(yè)的最優(yōu)反應(yīng)函數(shù)均為直線，兩條直線的交點(diǎn)即為Nash均衡，如圖5-1所示。（不動(dòng)點(diǎn)）圖5-1 Cournot 模型的Nash均衡第二部分 實(shí)施Nash定理的證明已經(jīng)知道，在考慮混合戰(zhàn)略的情況下，一個(gè)完全信息靜態(tài)博弈“通?！倍即嬖诩{什均衡。這一認(rèn)識(shí)最早由納什（Nash，1950，1951）進(jìn)行了證明，稱為納什定理

15、。定理2.1 納什定理 如果完全信息靜態(tài)博弈是有限的，即參與人是有限的，包含的純策略也是有限的，那么一定存在至少一個(gè)(純策略或混合策略)納什均衡。所謂“通?！敝傅木褪遣┺牡挠邢扌?。到目前為止，我們分析的博弈都滿足這兩個(gè)條件。參與人有限通常為兩個(gè)人。也是有限的要么存在若干個(gè)純策略，例如猜幣游戲；要么雖然純策略由無窮多，但卻是有界閉集 在數(shù)學(xué)中，有界閉集必然意味著是有限的，即它不是無限的，或者說拒斥了無限情。，例如古諾模型中的戰(zhàn)略集，所以前面分析的靜態(tài)博弈都存在納什均衡。對(duì)納什定理的證明分三個(gè)部分來完成：第一步，介紹不動(dòng)點(diǎn)定理；第二步，說明納什均衡就是不動(dòng)點(diǎn)；第三步，完成證明。第一步，不動(dòng)點(diǎn)定理。

16、先來看圖2-29。001ADC1B不動(dòng)點(diǎn)圖2-29 從區(qū)間0,1區(qū)間0,1連續(xù)函數(shù)具有不動(dòng)點(diǎn)圖2-29中的方框?yàn)檎叫?。?5線，它實(shí)際上等價(jià)于函數(shù)。線上的每一點(diǎn)都滿足，把滿足的稱為不動(dòng)點(diǎn)。線所代表的函數(shù)自變量取值為，稱為定義域，而因變量的取值為,稱為值域。定義域和值域都為的函數(shù)，又可寫作，讀作從到的映射?，F(xiàn)在做一個(gè)小游戲：拿一支筆，從線出發(fā)任意畫一條曲線，記住可以任意畫，但必須連續(xù)畫不能斷裂，至到線結(jié)束。這時(shí)發(fā)現(xiàn)無論如何畫，這條曲線一定會(huì)和相交，這個(gè)交點(diǎn)就是不動(dòng)點(diǎn)。因?yàn)槿我猱嫷那€等價(jià)于一個(gè)函數(shù)，沒有斷裂意味著它是連續(xù)的，與線相交意味著，所以交點(diǎn)為不動(dòng)點(diǎn)。所有任意畫的曲線都有如下的性質(zhì)：（1

17、）定義域是非空的、有界的、閉的、凸集合，簡(jiǎn)稱非空凸緊集。有界閉集即為緊集。(2)函數(shù)是連續(xù)的，并且是自身對(duì)自身的映射。上面考慮的只是一元函數(shù)，對(duì)于元函數(shù)是不是如果滿足上述性質(zhì)就存在不動(dòng)點(diǎn)？布勞爾（Brower）定理肯定地回答了這一點(diǎn)。定理2.2布勞爾（Brower）不動(dòng)點(diǎn)定理。 假設(shè)是一個(gè)非空凸緊集合，并且是一個(gè)連續(xù)函數(shù)；那么必有一個(gè)不動(dòng)點(diǎn)；即，存在一個(gè)使得。這里為實(shí)數(shù)，為實(shí)數(shù)的重笛卡爾積，為維向量。在前面的例子中。在實(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)

18、定理。 假設(shè)是非空凸緊集，并且是上半連續(xù)對(duì)應(yīng)，并且對(duì)于每一個(gè)，集合是非空凸集，那么必有一個(gè)不動(dòng)點(diǎn)。即，存在一個(gè)使得。角谷不動(dòng)點(diǎn)定理與布勞爾不動(dòng)點(diǎn)定理的區(qū)別在于：映射為對(duì)應(yīng)而不是函數(shù)，所以為一個(gè)集合(一個(gè)點(diǎn)也能組成集合，所以函數(shù)是對(duì)應(yīng)的特例)。映射是上半連續(xù)的。一個(gè)對(duì)應(yīng)只有既是上半連續(xù)又是下半連續(xù)才能稱為連續(xù)，因而上半連續(xù)比連續(xù)的要求要弱。關(guān)于對(duì)應(yīng)的上半連續(xù)，就是指如果存在一個(gè)序列收斂于并且收斂于，那么一定有（如果只有唯一值，那么就變?yōu)椋?，即?duì)應(yīng)包含著它的極限點(diǎn)。在圖2-30(a)中，當(dāng)，即從的左邊向其收斂時(shí)，但我們看到，即對(duì)應(yīng)并不包含極限點(diǎn)，所以它不是上半連續(xù)的。在圖2-30（b）中，對(duì)應(yīng)包含

19、它的每一個(gè)序列的極限點(diǎn)，特別是，因而它滿足上半連續(xù)，但它不是連續(xù)的。例如，猜幣游戲中每個(gè)參與人的最優(yōu)反應(yīng)對(duì)應(yīng)就是上半連續(xù)的。對(duì)于函數(shù)而言，上半連續(xù)就等同于連續(xù)。（a）非上半連續(xù) （b）上半連續(xù)圖2-30 對(duì)應(yīng)的上半連續(xù)第二步，納什均衡是不動(dòng)點(diǎn)。根據(jù)納什均衡的定義，在給定其他參與人策略的情況下，參與人選擇一個(gè)策略以使其收益最大化，并且對(duì)每一個(gè)參與人都如此，即納什均衡是一個(gè)使每一個(gè)參與人收益最大的策略組合。針對(duì)其他參與人不同的策略，參與人都有一個(gè)最優(yōu)策略與之相對(duì)應(yīng)，用數(shù)學(xué)來表示就是最優(yōu)反應(yīng)函數(shù)或?qū)?yīng)。如果參與人的最優(yōu)反應(yīng)函數(shù)（對(duì)應(yīng)）定義為那么個(gè)參與人的最優(yōu)反應(yīng)函數(shù)（對(duì)應(yīng)）就構(gòu)成了一個(gè)方程，將其定義

20、為，即如果是納什均衡，它一定滿足，即納什均衡是一個(gè)不動(dòng)點(diǎn)。例如，古諾模型中的最優(yōu)反應(yīng)函數(shù)共同構(gòu)成了一個(gè)方程組，這個(gè)方程的解既是不動(dòng)點(diǎn)，也是納什均衡。第三步，完成證明?，F(xiàn)在要完成的是證明：最優(yōu)反應(yīng)對(duì)應(yīng)的定義域?yàn)榉强胀咕o集；為上半連續(xù)的對(duì)應(yīng)。由于是的方程組，滿足這兩個(gè)條件，總的策略方程必然滿足這兩個(gè)條件，而根據(jù)不動(dòng)點(diǎn)定理，我們知道存在著不動(dòng)點(diǎn)，使得。（1）定義域?yàn)榉强胀咕o集。所謂有界集合就是任意畫一個(gè)圓（圓的半徑可以任意大，但不能無窮大）可以把它包下。所謂閉集就是包含邊界的集合。有界閉集即為緊致集合，簡(jiǎn)稱緊集。所謂凸集就是在集合內(nèi)任意找兩點(diǎn)，連接兩點(diǎn)的直線一定位于集合中。圖2-31中的直線和三角平

21、面顯然是有界的，同時(shí)也是閉的，即它們是緊集。同時(shí)它們也是凸集。而圖2-32中的環(huán)是非空緊集，但卻不是凸集。11BABA0圖2-31 非空凸緊集圖2-32 圓為凸集，環(huán)為非凸集如果博弈有個(gè)人參與人，參與人有個(gè)純策略，那么策略方程的定義域?yàn)?，它表示的重笛卡爾積，例如函數(shù)，那么函數(shù)的定義域就為，即都從集合中取值。由于混合策略的取值為，顯然為非空凸緊集，所以也是非空凸緊集。在古諾模型中，它的定義域雖然與上面講的有所不同，即純策略有無窮多個(gè)，但策略（產(chǎn)量）的取值為，它同樣是非空凸集。這表明納什均衡真正需要的并不是“有限的”要求，而是策略空間必須為緊致集合。如果一個(gè)參與人有兩個(gè)純策略，那么所有混合策略集合

22、（策略空間）就是滿足都大于等于零的直線。如果有三個(gè)純策略，那么所有的混合策略集合（策略空間）就是一個(gè)滿足都大于等于零的一個(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)方程滿足不動(dòng)點(diǎn)定理的兩個(gè)條件：策略空間為非空凸緊集，最優(yōu)反應(yīng)對(duì)應(yīng)為上半連續(xù)并且是非空凸集。因而存在著不動(dòng)點(diǎn)，而不動(dòng)點(diǎn)就是納什均衡。=知識(shí)擴(kuò)展一、集值映射及其半連續(xù)性

23、這里限于在歐氏空間中展開討論，當(dāng)然，我們也說成拓?fù)淇臻g，但在這里的上下文，讀者可以將拓?fù)淇臻g直接理解為歐氏空間。設(shè)是一個(gè)拓?fù)淇臻g，的所有子集的全體記作。即.注意, ,。定義9.1.1設(shè)和是兩個(gè)拓?fù)淇臻g。若對(duì)任一,確定的一個(gè)子集(己作)與之對(duì)應(yīng)。這樣得到的對(duì)應(yīng)稱作一個(gè)點(diǎn)對(duì)集映射(point-to-set mapping)或一個(gè)集值映射(set-valued mapping)。相應(yīng)地，以往對(duì)每個(gè)確定一個(gè)的映射,稱為單值映射(single-valued mapping)。如同單值映射的情形，我們引進(jìn)集值映射的圖像的概念。定義9.1.2設(shè)是一個(gè)集值映射。稱的子集為的圖像(graph)表現(xiàn)。下面我們建立

24、集值映射的半連續(xù)性和連續(xù)性的概念。定義9.1.3設(shè)是一個(gè)集值映射，。若對(duì)的與之交非空的每個(gè)開集，存在中包含的一個(gè)開集使得蘊(yùn)涵,就說在是下半連續(xù)的(lower semicontinuous)。若對(duì)的包含的每個(gè)開集，存在中包含的一個(gè)開集使得蘊(yùn)涵，就說在是上半連續(xù)的(upper semicontinuous)。若在既是下半連續(xù)的又是上半連續(xù)的,就說在是連續(xù)的(continuous)。集值映射的兩種半連續(xù)性和連續(xù)性,都是單值映射的通常的連續(xù)性概念的推廣。事實(shí)上，如果把單值映射看作在定義域的每點(diǎn)取值域的一個(gè)單點(diǎn)集的集值映射，則作為集值映射的下半連續(xù)性、上半連續(xù)性和連續(xù)性，都與作為單值映射的通常的連續(xù)性吻

25、合。圖9.1對(duì)于集值映射，下半連續(xù)性和上半連續(xù)性是不同的。請(qǐng)看下面的例子。例9.1.1 設(shè)是實(shí)數(shù)軸上的一個(gè)閉區(qū)間，集值映射由圖9.1給出。容易驗(yàn)證，在任一點(diǎn)，連續(xù)性是不成問題的。即在任一點(diǎn)，既是下半連續(xù)的又是上半連續(xù)的。但在，是下半連續(xù)的而不是上半連續(xù)的。例9.1.2 仍取為閉區(qū)間，集值映射由圖9.2給出。容易驗(yàn)證，在任一點(diǎn)，連續(xù)性是不成問題的，但在，是上半連續(xù)的卻不是下半連續(xù)的。圖9.2定義9.1.4若在的每個(gè)點(diǎn)都是下半連續(xù)的，就說在是下半連續(xù)的。若在的每個(gè)點(diǎn)都是上半連續(xù)的，就說在是上半連續(xù)的。若在的每個(gè)點(diǎn)都是連續(xù)的，就說在是連續(xù)的。為了下面討論的方便，我們引入集值映射的逆象的概念。定義9.

26、1.5設(shè)是一個(gè)集值映射，是的一個(gè)子集。稱為的下逆象,或的相交逆；稱為的上逆象,或的包含逆。基于上述定義，馬上可以證明下面的定理?！径ɡ?.1.1】是下半連續(xù)的充要條件是“開集的相交逆為開集”，即若是的開集，則是的開集。是上半連續(xù)的充要條件是“開集的包含逆為開集”，即若是的開集，則是的開集。利用這個(gè)定理，易知例9.1.1的是下半連續(xù)的，因?yàn)殚_集的相交逆都是開集，但不是上半連續(xù)的，因?yàn)殚_集的包含逆不都是開集。同樣,對(duì)于例9.1.2的，因?yàn)殚_集的包含逆都是開集，所以是上半連續(xù)的，但開集的相交逆不都是開集，所以不是下半連續(xù)的。下面是一個(gè)更為方便的上半連續(xù)性判別法。為行文方便，歐氏空間的子空間也稱為歐氏

27、空間。注意在歐氏空間中，子集作為子空間的緊致性與有界閉性等價(jià)?！径ɡ?.1.2】設(shè)和是歐氏空間，并且緊致，集值映射使得對(duì)每個(gè)，是的緊致子集。那么，為上半連續(xù)的充要條件是:的圖像表現(xiàn)是中的一個(gè)閉子集。根據(jù)這個(gè)定理，僅僅因?yàn)槔?.1.1中的映射的圖像表現(xiàn)的閉性在處遭到破壞，我們馬上知道不是上半連續(xù)的。但例9.1.2中的集值映射的圖像表現(xiàn)是中的閉集，即知是上半連續(xù)的。二、Kakutani不動(dòng)點(diǎn)定理我們主要關(guān)心有強(qiáng)烈應(yīng)用背景的歐氏空間凸子集到其非空緊致凸子集族的集值映射。設(shè)為歐氏空間的凸集，我們約定，記的非空緊致凸子集族為。當(dāng)然，。定義1設(shè)是歐氏空間的凸集，是集值映射。如果使得，就說是集值映射的一個(gè)不

28、動(dòng)點(diǎn)。為區(qū)別起見,常常把由定義的不動(dòng)點(diǎn)稱為Brouwer不動(dòng)點(diǎn)，而把由定義的不動(dòng)點(diǎn)稱為Kakutani不動(dòng)點(diǎn)。后者是前者在集值映射情形的推廣。Brouwer不動(dòng)點(diǎn)定理說，閉胞腔的連續(xù)自映射必有不動(dòng)點(diǎn)。而Kakutani不動(dòng)點(diǎn)定理說，緊凸集的上半連續(xù)的集值自映射必有不動(dòng)點(diǎn)。三、Nash定理的一般證明（重點(diǎn)，講！）我們首先在博弈的一般表示之下將Nash均衡的概念加以推廣,使之包含混合策略的情形。 設(shè)為一個(gè)有個(gè)參與人的博弈, ,每個(gè)為第個(gè)參與人的一個(gè)純策略。上的一個(gè)概率分布為第個(gè)參與人的一個(gè)混合策略,這里, , ,并且。這時(shí),為這個(gè)博弈的參與人分別采用混合策略時(shí)，第個(gè)參與人所得到的期望支付。為符號(hào)方

29、便,我們?nèi)缜坝浂x1設(shè)博弈,，第個(gè)參與人的混合策略為,為第個(gè)參與人的期望支付。個(gè)參與人的一組混合策略稱為博弈的一個(gè)Nash均衡，如果對(duì)任意的參與人及參與人的任意混合策略,有下面我們就證明Nash定理?！径ɡ?】設(shè)博弈,這里為有限正整數(shù)，每個(gè)為有限集,則博弈至少存在一個(gè)Nash均衡。注意,這個(gè)均衡既可能是純策略均衡,也可能是混合策略均衡。 證明(0)對(duì)于任意的,記其概率空間為每個(gè)為第個(gè)參與人的一個(gè)混合策略。顯然是一個(gè)前面講過的維標(biāo)準(zhǔn)單純形。對(duì)以下單純形的笛卡爾積，如前引進(jìn)簡(jiǎn)便記法: (1)記第個(gè)參與人的最佳反應(yīng)對(duì)應(yīng)為:,這里表示的所有非空緊致凸子集的集合。對(duì)任意顯然是的非空閉子集，所以是的非空緊

30、致子集。因?yàn)槠谕Ц妒羌儾呗灾Ц逗瘮?shù)的線性組合(事實(shí)上還是凸組合),所以是的凸子集?？梢?對(duì)任意是的非空緊致凸子集。這時(shí), 表示除第個(gè)參與人之外的其余個(gè)參與人采用策略時(shí),第個(gè)參與人的一個(gè)最佳混合策略。 定義總的最優(yōu)反應(yīng)對(duì)應(yīng)映射為，,這里表示的所有子集的集合。(2)如果有Kakutani不動(dòng)點(diǎn),即有,則憐顯然就是該博弈的一個(gè)Nash均衡。(3)利用Kakutani不動(dòng)點(diǎn)定理證明確實(shí)存在Kakutani不動(dòng)點(diǎn)。我們來驗(yàn)證確實(shí)滿足Kakutani不動(dòng)點(diǎn)定理的條件即: 為非空緊致凸集,對(duì)任一,為的非空緊致凸子集,并且為上半連續(xù)的集值映射。首先由于都是維標(biāo)準(zhǔn)單純形，因而是非空緊致凸的,這樣很顯然就是非空緊致凸集。對(duì)于任意,因?yàn)楦魇欠强站o致集,所以各非空緊致,所以也是非空緊致集。如果,那么對(duì)每個(gè)，已經(jīng)達(dá)到最大。設(shè)是和的任意凸組合,那么也達(dá)到這個(gè)最大,可見。由此可見, 是凸集。這樣可以寫作,這里同樣表示的所有非空緊致凸子集的集合。 剩下只須驗(yàn)證的上半連續(xù)性，而這只須驗(yàn)證的圖像是閉集即可。設(shè),且,我們來證明。由于，也就是,即對(duì)所有,有.由于是線性因而是連續(xù)的,當(dāng)時(shí),上述不等關(guān)系保持不變,即有對(duì)所有,，也即,這就說明證畢。=33