【正文】 中人的策略。這樣，每個局中人的收益都是局勢集合上的實值函數(shù)。用表示局中人的收益函數(shù)，則當(dāng)局中人采取策略，而其他人采取策略(時，局中人的收益為 。作了這些說明之后，這個人博弈便可簡便地表示成：從各個局中人的收益函數(shù)可以得到博弈的收益映射，其定義為：于是，人博弈也可表示成為：。如果對任何，都有，則稱為人零和博弈。當(dāng)然，也有人常和博弈、非常和博弈的概念，其含義是明顯的。當(dāng)人博弈的局勢集合有限集合時，則稱為有限博弈；否則，稱為無限博弈。本節(jié)討論人有限博弈。對于無限博弈，待留第九節(jié)中討論。設(shè)為人有限博弈，其中。當(dāng)局中人1采取策略，局中人2采取策略，…，局中人采取策略時，我們把局中人的收益簡記作，即。于是，收益函數(shù)可用矩陣(維陣)表示，這個維陣也稱為局中人的收益表。同二人博弈情形一樣，局中人為了使自己的行動具有隱秘性，可采取混合策略，即以一定的概率來選擇某種純策略，這就引出了人博弈的混合擴充概念。局中人以概率選擇純策略，則概率分布表示著局中人的一種混合策略。所有可能的混合策略構(gòu)成了局中人的混合策略集合： 是歐氏空間的非空有界閉凸子集。純策略可看作局中人以概率1選擇，以概率0選擇其他策略的這么一種混合策略，因此。當(dāng)局中人1選擇了混合策略，局中人2選擇了混合策略，…，局中人選擇了混合策略時，構(gòu)成博弈的一個混合局勢。由所有這些混合局勢組成的集合：稱為博弈的混合局勢集合。顯然，混合局勢集合擴大了原來的局勢集合，即，并且是歐氏空間中的非空有界閉凸子集。在混合局勢下下，局中人的預(yù)期收益為：可見預(yù)期收益是混合局勢集合上的一個實值連續(xù)函數(shù)，并且具有重線性性，即關(guān)于每個都是線性的：對任何及任何實數(shù)，都有在混合策略的意義下，局中人追求的是預(yù)期收益的最大化，因此代表著一個人博弈，稱為純策略博弈的混合擴充。作了上面一般性描述之后，表面上看似乎人博弈只是局中人數(shù)的增加。其實，事實并非如此。一方面，人博弈繼承了二人博弈的一些性質(zhì)，因而是二人博弈的推廣。另一方面，人博弈絕不是簡單地增加局中人數(shù)，它與二人博弈有著本質(zhì)的不同。這種質(zhì)的區(qū)別，表現(xiàn)為局中人之間的合作與非合作。人非合作博弈是矩陣博弈的推廣，但人合作博弈則表現(xiàn)出十分復(fù)雜的性態(tài)。下面我們來討論人非合作博弈中局中人的最優(yōu)選擇問題。二．納什均衡在人博弈中，如果局中人之間沒有形成任何的合作聯(lián)盟，每個局中人都是獨立地選擇自己的策略，那么這樣的博弈就稱為人非合作博弈。前節(jié)討論的矩陣博弈是典型的非合作博弈，其特點是參加博弈的局中人雙方利害沖突，不是你輸，就是你贏，沒有任何調(diào)和的余地。矩陣博弈中局中人之間不會產(chǎn)生聯(lián)盟，因為一旦出現(xiàn)聯(lián)盟，就不能成為博弈。人非合作博弈，繼承了矩陣博弈的這一特點，即局中人獨立行動，獨自決策，但每個人的收益都與各個局中人的行動有關(guān)，每個人的目標(biāo)都是要在其他局中人行動已定的情況下使自己的收益達到最大。這樣，人非合作博弈的最優(yōu)解就是矩陣博弈最優(yōu)解概念的推廣。設(shè)是人純策略博弈的混合擴充，其中 。博弈是非合作的，即的各個局中人獨自行動，獨自選擇自己的純策略和混合策略。對于的任何一個混合局勢以及局中人的任何一個混合策略，在混合局勢中把局中人的策略用替代，其他局中人的策略不變，這樣就得到一個新的混合局勢：顯然的含義是說，在其他局中人選擇策略的情況下，局中人選擇了策略。局中人作出這種選擇的預(yù)期收益為。混合局勢叫做在混合策略意義下的最優(yōu)解（即的最優(yōu)解），是指對每個局中人以及對任何混合策略，都有。當(dāng)是博弈在混合策略意義下的最優(yōu)解時，也稱是的最優(yōu)混合解或混合均衡或混合納什均衡或混合古諾納什均衡，或者叫做的均衡或納什均衡或古諾納什均衡。均衡中的策略，就叫做局中人的最優(yōu)混合策略。顯然，混合局勢是的混合均衡當(dāng)且僅當(dāng)對一切成立。這正是博弈均衡的含義之所在，用通俗的話來說就是，在均衡點處，任何局中人都不能從單方面改變策略來提高自己的收益。納什均衡存在嗎？對此，我們作一分析。對于任何混合局勢，令即表示在其他局中人選擇策略的情況下，使局中人的收益達到最大的策略的全體。顯然，只與局勢中其他局中人的策略有關(guān)，而與局中人的策略無關(guān)。稱為局中人對其他局中人的行動的反應(yīng)集合。由于是的連續(xù)函數(shù)，且是的非空有界閉子集，因此函數(shù)在上必有最大值，這就保證了反應(yīng)集合是非空集合，而且還是閉集合。記這實際上給出了一個從混合局勢集合到的集值映射。稱這個集值映射為博弈的反應(yīng)集值映射。容易看出，混合局勢是博弈的混合納什均衡當(dāng)且僅當(dāng)，即當(dāng)且僅當(dāng)是反應(yīng)集值映射的不動點。可見，納什均衡的存在性問題，歸結(jié)為集值映射的不動點問題。下面的角古定理給出了集值映射不動點存在的條件。角古不動點定理(Kakutani39。s Fixed Point Theorem)．設(shè)是有限維歐氏空間的非空有界凸閉子集，是集值映射。如果上半連續(xù)，并且對任何，都是非空凸閉集，那么必有不動點，即存在使得。這條定理是角古靜夫(Kakutani)在1941年證明的，它是對Brouwer不動點定理(1911)的推廣。從該定理可知，為了說明納什均衡的存在性，只需驗證上面定義的集值映射滿足角古不動點定理的條件。首先，前面已經(jīng)指出，混合局勢集合是歐氏空間的非空有界凸閉子集，并且是非空閉集，因此也是非空閉集。其次，預(yù)期收益函數(shù)的重線性性保證了是凸集，因而也是凸集。最后，應(yīng)用第四章第一節(jié)關(guān)于集值映射上半連續(xù)性的定理來說明的上半連續(xù)性，即來證明下述事實：對于任何和，以及序列和，如果收斂于并且收斂于，則。記,，, 。現(xiàn)在，已知，且。就是說，也即對每個局中人以及任何，都有。令，則從的連續(xù)性可知，對一切局中人和一切成立。這說明，即。的上半連續(xù)性得證。至此，反應(yīng)集值映射滿足角不動點古定理的全部條件，所以有不動點。這就得到下面的納什均衡存在性定理。納什均衡存在定理(Nash,1950)．任何人有限純策略博弈在混合策略意義下必有最優(yōu)解，即混合納什均衡必然存在。下面，我們給出用純策略來判斷混合納什均衡的一個簡便辦法。納什均衡的簡化．設(shè)是人純策略博弈博弈的混合擴充，其中。是的混合納什均衡當(dāng)且僅當(dāng)對每個局中人及任何策略都成立。證明：必要性是顯然的，以下證明充分性。為此，設(shè)對每個局中人及任何純策略都成立。注意，因此，對每個局中人以及對任何混合策略，都有這就證明了是的混合納什均衡。證完。從以上討論可以看出，對于非合作博弈而言，人博弈和二人博弈的情況差不多。進一步，同二人博弈一樣，由于均衡的不唯一，人博弈也有相應(yīng)的占優(yōu)策略、半占優(yōu)策略和被占優(yōu)策略這些相應(yīng)的概念，也要對被占優(yōu)策略進行剔除，最好是能夠找到占優(yōu)均衡，最后使納什均衡得以精化，使均衡數(shù)目得以減少。然而在尋找人非合作博弈最優(yōu)解問題的研究上，迄今為止取得的實質(zhì)性進展并不很大，遇到的困難主要是概念性的，因而還不能完全拋棄納什均衡的基本思想，去從一個新的角度來研究非合作博弈。第八節(jié) 多人合作博弈現(xiàn)實生活中，多人博弈常常出現(xiàn)于這樣的情況下：局中人之間具有合作的動機或行動，他們彼此交換情報，互換信息，協(xié)調(diào)行動，事先商量如何選擇策略，以便取得對自己有利的結(jié)果。這種相互配合，團結(jié)一致，彼此協(xié)作的現(xiàn)象，就是合作博弈的原型。由于存在合作的動機或行動，因此一部分局中人會結(jié)成聯(lián)盟，在博弈中采取一致行動，并且最終把聯(lián)盟所得的收益重新分配給聯(lián)盟的各個成員。那么，在一個博弈中，哪些人結(jié)成聯(lián)盟？如何聯(lián)盟？聯(lián)盟中各個局中人采取什么行動才是恰當(dāng)?shù)模裁葱袆邮怯泻Φ?？諸如此類的這些問題，都是博弈論中應(yīng)研究的問題。博弈論的近期發(fā)展中，對合作博弈的研究是一個十分豐富和活躍的領(lǐng)域。本節(jié)討論人合作博弈，重點介紹馮諾伊曼(von Neumann)建立的理論。一．特征函數(shù)在人合作博弈中，各個局中人如何選擇策略已不是主要考慮的問題，應(yīng)當(dāng)強調(diào)的乃是聯(lián)盟的形成。在現(xiàn)實生活中，結(jié)成聯(lián)盟的形式是多種多樣的，因而也是十分復(fù)雜的。聯(lián)盟的形成可能是由局中人的收支情況決定的，也可能是由某些政治的、感情的、心理的因素等來決定的?？傊?，如要討論形成聯(lián)盟的原因，那這就是一個相當(dāng)復(fù)雜的問題。這里，我們的重點不應(yīng)放在形成聯(lián)盟的原因討論上，而應(yīng)強調(diào)聯(lián)盟的形成。我們認(rèn)為，在一個聯(lián)盟內(nèi)，既然這些局中人已經(jīng)結(jié)盟，他們之間就可以充分交換意見，傳遞信息，采取彼此協(xié)調(diào)的行動。關(guān)于合作博弈與聯(lián)盟問題，馮諾伊曼建立的理論，尤其是他提出的特征函數(shù)概念，成為這方面研究的基石。馮諾伊曼理論包含了一些有發(fā)展前途的、合理的內(nèi)容，在此基礎(chǔ)上進一步討論和發(fā)展新的理論，無疑是相當(dāng)有作用的。對于具體的博弈現(xiàn)象而言，馮諾伊曼理論可用來指導(dǎo)各個局中人的行動，并對博弈現(xiàn)象進行解釋。而馮諾伊曼的特征函數(shù)的重要性，正如馮諾伊曼所說：“我們希望把人零和競賽的全部理論建立在這個函數(shù)的基礎(chǔ)之上”，這里所說的競賽，就是我們所講的博弈。下面我們將會看到，通過特征函數(shù)可以把有關(guān)局中人之間的聯(lián)盟，每一個聯(lián)盟之內(nèi)局中人之間進行的補償，以及兩個聯(lián)盟之間的合并與斗爭等問題，都能確定下來。(一) 聯(lián)盟設(shè)是人純策略有限博弈的混合擴充。用表示博弈的局中人集合。局中人之間的相互合作，表現(xiàn)為局中人的結(jié)盟，也即一部分局中人形成聯(lián)盟。當(dāng)然，這個聯(lián)盟就是局中人集合的一個子集。經(jīng)濟學(xué)分析局中人的結(jié)盟時，著眼點并不放在分析這個聯(lián)盟是出于何種原因形成的。聯(lián)盟的特征在于它表現(xiàn)為的子集，因此可以把的任何一個子集都叫做聯(lián)盟。這就給出下面的定義：定義．博弈中的一個聯(lián)盟是指局中人集合的一個子集。在這個定義中，以下三點值得注意：第一，如果是聯(lián)盟，那么的余集也是聯(lián)盟，稱為聯(lián)盟的余聯(lián)盟。因此，任何一個聯(lián)盟都把局中人分成了兩個聯(lián)盟，一個是，另一個是余聯(lián)盟。第二，全部局中人的集合和空集都可看作聯(lián)盟，并且和互為余聯(lián)盟。我們把空集稱為空聯(lián)盟。第三，只含一個局中人的集合(即的單點子集)也是聯(lián)盟，叫做單人聯(lián)盟。這是聯(lián)盟的特殊情形，實際上單人聯(lián)盟并沒有真正的結(jié)盟意義。現(xiàn)在，設(shè)是博弈中的一個聯(lián)盟。為了書寫上的方便，記，即用表示的余聯(lián)盟。把局中人分成兩個聯(lián)盟和，聯(lián)盟中各個局中人在選擇策略時互通信息，彼此合作，協(xié)調(diào)行動。同樣，聯(lián)盟中各個局中人也是如此。這樣一來，我們可把當(dāng)做博弈的局中人甲，而把當(dāng)做博弈的局中人乙來看待。按照這種觀點，原來的人博弈就變成了一個只有兩個局中人甲和乙的二人純策略博弈：，其中。博弈的局勢集合可看成的局勢集合，之所以可以這樣看待，是因為。的局勢可看成是的局勢，其中是由聯(lián)盟的各個成員在局勢中采取的策略構(gòu)成的，是由的各個成員在局勢中采取的策略構(gòu)成的。的收益函數(shù)可視為：；的收益函數(shù)可視為：。于是，我們得到如下事實：博弈的任何聯(lián)盟都把變成為一個可等同看待的二人博弈，其中為的余聯(lián)盟。聯(lián)盟能把博弈變成為二人博弈，同樣也能把的混合擴充變成為二人博弈。注意，二人博弈又有自己的混合擴充。因此，我們需要討論和之間的關(guān)系，主要是看和是否是同樣的博弈。為了書寫上的方便，不放設(shè)，其中。則我們有以下的表示：其中。由此可見，(1) 對于，令,則；(2) 對于，從下面方程組求解出所有的：則， ，從而；(3) 對于，令,則；(4) 對于，從下面方程組求解出所有的：則， ，從而。以上結(jié)論說明，與可等同看待，與可等同看待。下面再來看一下博弈和的收益情況。在變換下，的局勢可與的局勢等同看待。因此，對于任何，都有：這說明與可等同看待，與可等同看待。既然博弈和的局勢集合與收益函數(shù)都可等同看待，和就是同樣的博弈。這樣，我們就可把和統(tǒng)一寫成：。所以，聯(lián)盟在把人博弈變成為二人博弈的同時，也把的混合擴充變成為二人博弈的混合擴充。(二)特征函數(shù)的概念與性質(zhì)通過聯(lián)盟，人博弈化簡為二人博弈，由此可引出博弈的特征函數(shù)概念。定義．設(shè)是人博弈的混合擴充，是的局中人集合，為的冪集，即由中的所有聯(lián)盟組成的集合。對于任一聯(lián)盟,，把看成由和構(gòu)成的二人博弈，則。令則定義了集合上的一個實值函數(shù)，稱這個函數(shù)為博弈的特征函數(shù)。當(dāng)為人零和博弈時，通過聯(lián)盟，變成為二人博弈。可以看出，和也都是零和博弈，并且就是的博弈值(參見上一節(jié)的內(nèi)容)?？梢?，特征函數(shù)概念是博弈值概念的推廣。對于一般的人博弈而言，特征函數(shù)的值表達了聯(lián)盟在博弈中至少可以得到的收入，即不論聯(lián)盟外的局中人采取什么行動，聯(lián)盟得到的收入不會低于。下面，我們看一看特征函數(shù)的性質(zhì)。性質(zhì)1. 對于空聯(lián)盟來說。這是因為空聯(lián)盟中一個局中人也沒有，因而不會有收入或支出的發(fā)生，即。性質(zhì)2. 若且，則。這是因為 表示和不合作時聯(lián)盟至少能得到的收入，而表示和合作時至少能得到的收入，從而必有。這里，我們應(yīng)用有關(guān)特征函數(shù)的直接意義給出了性質(zhì)2的證明，這種證明容易化為根據(jù)特征函數(shù)的精確定義進行的證明。從直接意義出發(fā)的證明，能讓我們更清楚地看到問題的本質(zhì)所在，簡單明了，避免了繁雜的演算，而且不存在任何本質(zhì)上的困難。如果把性質(zhì)2中的不等式換為等式，即要求特征函數(shù)滿足：對任何不相交的，都有，那么就稱具有可加性。對于具有可加性的特征函數(shù)來說，由于單點集也是聯(lián)盟，并且，因此。這表明：當(dāng)特征函數(shù)具有可加性時，局中人結(jié)盟與不結(jié)盟沒有什么差別?？梢?，在合作博弈研究中，特征函數(shù)的可加性不能揭示合作的意義，因而人們對可加性并不感興趣。鑒于此，凡是特征函數(shù)具有可加性的博弈，都稱為是非本質(zhì)博弈。人們感興趣的是本質(zhì)博弈。性質(zhì)3. 當(dāng)為零和博弈時，對任何，都有。特別是當(dāng)時。這是因為，當(dāng)為零和博弈時，通過聯(lián)盟所轉(zhuǎn)化成為的二人博弈及其混合擴充也都是零和博弈，故聯(lián)盟的收入就是余聯(lián)盟的支出，即。為什么把如上定義的函數(shù)叫做博弈的特征函數(shù)？一般來說，特征二字是不能隨便使用的。如果說一種性質(zhì)是某個對象的特征，那么這種性質(zhì)就要能夠完全刻劃這個對象。特征函數(shù)能夠完全刻劃博弈嗎？下面的性質(zhì)4肯定地回答了這個問題。性質(zhì)4. 設(shè)，滿足條件：且對一切不相交的成立，則存在一個人有限博弈使得正好是的特征函數(shù)。進一步，如果還滿足條件：對一切成立，那么必存在一個人有限零和博弈使得正好是的特征函數(shù)。這條性質(zhì)的證明過于復(fù)雜，這里就不去證明了。本性質(zhì)表明，我們可以不聯(lián)系任何具體的博弈，只從滿足這兩個或三