合作聯(lián)盟博弈課件

博弈論

經(jīng)濟與管理學(xué)院劉洋博士

1博弈論經(jīng)濟與管理學(xué)院劉洋博士1博弈論經(jīng)濟與管理學(xué)院劉洋博士1博弈論經(jīng)濟與管理學(xué)合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)2合作博

合作博弈

COOPERATIVEGAMES熊、狼、狐貍一起抓了一只兔子，民主協(xié)商如何分配。狐貍對熊說：平均分只能各得1/3，這樣吧，我們倆聯(lián)合起來，平分如何？熊要答應(yīng)，狼急了，于是狐貍對狼說：怎么樣，我和熊聯(lián)合起來可以讓你什么也得不到，我可以和你合作，不過我要3/4。狼感激的點頭，熊琢磨過味來，對狼說：別聽那個兩面三刀的，和我合作，我給你1/3。狐貍見勢不妙，對狼說：別，我給你2/3，我只要1/3。狼成了搶手貨，正得意，沒留神狐貍和熊又開始嘀咕起來，有再次把自己晾在一邊的不妙趨勢，連忙鉆去繼續(xù)討價還價。結(jié)果呢？3合作博弈

COOPERATIVEGAM合作博弈

COOPERATIVEGAM如果在實際博弈問題中，具有有力的保障使局中人能夠進行協(xié)商、談判，聯(lián)合選擇行動，共同分享利益，我們就面對一個合作博弈問題。本章通過合作博弈模型的介紹，討論在合作博弈中，局中人如何進行協(xié)商談判、結(jié)成聯(lián)盟及分享利益。1、聯(lián)盟博弈2、聯(lián)盟博弈的分配3、核和穩(wěn)定集4、沙普利值4444導(dǎo)論先回憶一下囚徒困境的例子：

在囚徒困境中，還有另外一個策略組合<抵抗，抵抗>，該組合為參與人帶來的支付是<-1,-1>。由<-8,-8>到<-1,-1>，每個參與人的支付都增加了，即得到一個帕累托改進。坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-15導(dǎo)論先回憶一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1導(dǎo)論先回憶一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1導(dǎo)論

<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人理性。在參與人選擇抵抗的情況下，每個參與人都有動機偏離這個組合，通過投機行為謀取超額收益1。如果兩個參與人在博弈之前，簽署了一個協(xié)議：兩個人都承諾選擇抵抗，為保證承諾的實現(xiàn)，參與人雙方向第三方支付價值大于1的保證金；如果誰違背了這個協(xié)議，則放棄保證金。有了這樣一個協(xié)議，<抵抗，抵抗>就稱為一個均衡，每個人的收益都得到改善。上述分析表明，通過一個有約束力的協(xié)議，原來不能實現(xiàn)的合作方案現(xiàn)在可以實現(xiàn)。這就是合作博弈與非合作博弈的區(qū)別。二者的主要區(qū)別在于人們的行為相互作用時,當(dāng)事人是否達成一個具有約束力的協(xié)議。如果有,就是合作博弈；反之,則是非合作博弈。6導(dǎo)論<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人導(dǎo)論<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人合作博弈的概念及其表示

合作博弈，非合作博弈的對稱，一種博弈類型。參與者能夠聯(lián)合達成一個具有約束力且可強制執(zhí)行的協(xié)議的博弈類型。合作博弈強調(diào)的是集體理性,強調(diào)效率、公正、公平。合作博弈最重要的兩個概念是聯(lián)盟和分配。每個參與者從聯(lián)盟中分配的收益正好是各種聯(lián)盟形式的最大總收益,每個參與者從聯(lián)盟中分配到的收益不小于單獨經(jīng)營所得收益。7合作博弈的概念及其表示合作博弈，非合合作博弈的概念及其表示合作博弈，非合合作博弈的概念及其表示

合作博弈的結(jié)果必須是一個帕累托改進，博弈雙方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受損害。合作博弈采取的是一種合作的方式，合作之所以能夠增進雙方的利益，就是因為合作博弈能夠產(chǎn)生一種合作剩余。至于合作剩余在博弈各方之間如何分配，取決于博弈各方的力量對比和制度設(shè)計。

合作博弈的核心問題是參與人如何結(jié)盟以及如何重新分配結(jié)盟的支付。8合作博弈的概念及其表示合作博弈的結(jié)果必合作博弈的概念及其表示合作博弈的結(jié)果必合作博弈的概念及其表示

定義1

在人博弈中，參與人集用表示，的任意子集稱為一個聯(lián)盟（coalition）。

空集和全集也可以看成是一個聯(lián)盟，當(dāng)然單點集也是一個聯(lián)盟。定義2

給定一個人博弈，是一個聯(lián)盟，是指和的兩人博弈中的最大效用，稱為聯(lián)盟的特征函數(shù)（characteristicfunction）。

規(guī)定。根據(jù)定義，表示參與人與全體其他人博弈時的最大效用值，表示為。用表示參與人集為，特征函數(shù)為的合作博弈，其中是定義在上的實值映射。在很多情況下，一個聯(lián)盟能獲得的支付依賴于其他參與人所采取的行動。有時被解釋為聯(lián)盟獨立于聯(lián)盟的行動可保證的最大支付。9合作博弈的概念及其表示定義1在人博弈合作博弈的概念及其表示定義1在人博弈合作博弈的概念及其表示

合作對策的分類主要是根據(jù)特征函數(shù)的性質(zhì)。下面根據(jù)特征函數(shù)的性質(zhì)介紹幾類特殊的合作對策。如果僅與的個數(shù)有關(guān)，則稱作對稱博弈。如果，則稱作常和博弈。如果，則稱作簡單博弈。例如，在投票博弈中，每個參與人的權(quán)重，

如果，則稱作凸博弈。10合作博弈的概念及其表示合作對策的分類主要是根據(jù)特征函合作博弈的概念及其表示合作對策的分類主要是根據(jù)特征函合作博弈的概念及其表示

之所以稱為特征函數(shù)，是因為這個合作博弈的性質(zhì)基本由決定。由此可見對合作博弈的重要性。定理設(shè)是參與人集合上的特征函數(shù)，則有如下的超可加性：對于聯(lián)盟和，如果，則上式說明，特征函數(shù)只有滿足超加性，才有形成新聯(lián)盟的必要性。否則，如果一個合作博弈的特征函數(shù)不滿足超可加性，那么，其成員沒有動機形成聯(lián)盟，已經(jīng)形成的聯(lián)盟將面臨解散的威脅。11合作博弈的概念及其表示之所以稱為特征函數(shù)，是因合作博弈的概念及其表示之所以稱為特征函數(shù)，是因例：

局中人1（賣主）要把一件物品賣掉，局中人2和3（買主）分別出價9元和10元。如果局中人1將物品賣給局中人2的要價是x

元，則局中人2贏利9-x元。聯(lián)盟的總收益為9元。類似，聯(lián)盟的總贏利為10元。于是有。另一方面，單個局中人或者兩個買主在一起都不可能贏利，即，。當(dāng)三個局中人在一起交易時，局中人1顯然要把物品賣給局中人3，從而v({1,2,3})=10，顯然滿足超可加性，于是我們建立了聯(lián)盟博弈。特征函數(shù)是研究聯(lián)盟博弈的基礎(chǔ)，確定特征函數(shù)過程實際就是一個建立合作博弈模型的過程。有的問題，特征函數(shù)可以容易地得到，有的問題需要仔細分析，甚至需要一些專業(yè)知識。12例：局中人1（賣主）要把一件物品賣掉，局中人2和3（買主例：局中人1（賣主）要把一件物品賣掉，局中人2和3（買主由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0V(1)=0V(2)=5V(1,2)=10局中人2LR局中人1U-1，25，5D0，100，10最小最大值法：聯(lián)盟外局中人將采取行動使該聯(lián)盟的總和收益最小（極度悲觀），聯(lián)盟選擇策略－－最大化這些最小值。13由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0局中人2LR局中人由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0局中人2LR局中人例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民每天產(chǎn)生一袋垃圾，這些垃圾只能扔在這一區(qū)域的某一戶人家領(lǐng)地（區(qū)域中沒有空地）。記Vn(n=0,1,…,7)表示任意n個局中人組成的特征函數(shù)值，在合作博弈條件下，有：

V0=V()=0

V1=-6

V2=-5V3=-4，V4=-3，V5=-2

V6=-1，V7=-714例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各有兩個純策略。當(dāng)三人不合作時，其支付見下表。假設(shè)采用最穩(wěn)妥策略，即最壞情況下選擇最好，求合作博弈的支付函數(shù)15合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各合作博弈的概念及其表示解：用表示一個聯(lián)盟，表示聯(lián)盟中參與人的個數(shù)。當(dāng)＝0，自然，有。當(dāng)＝1，有3個，以為例。當(dāng)，則。的策略集合，策略組合。與進行如下矩陣對策：16合作博弈的概念及其表示解：用表示一個聯(lián)盟，合作博弈的概念及其表示解：用表示一個聯(lián)盟，合作博弈的概念及其表示

上述矩陣對策沒有純策略，的混合策略是，的混合策略是。的均衡值是。故。同理，可以求出。當(dāng)＝2，有3個，以為例。當(dāng)，則。的策略集合,

策略組合。與進行如下矩陣對策：17合作博弈的概念及其表示上述矩陣對策沒有純策略，合作博弈的概念及其表示上述矩陣對策沒有純策略，合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值是3。故。同理，可以求出。當(dāng)＝3，有1個，，最大的聯(lián)盟。的策略空間。有。至此特征函數(shù)的值已全部求出。18合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值分配

所謂分配就是博弈的一個維向量集合，之所以是維向量，是由于每個參與人都要得到相應(yīng)的分配。維的分配向量稱為博弈的“解”。定義3

對于合作博弈，對每個參與人，給予一個實值參數(shù)，形成維向量且其滿足：

則稱是聯(lián)盟的一個分配方案。19分配所謂分配就是博弈的一個維向量集合，之分配所謂分配就是博弈的一個維向量集合，之分配

分配的定義中，是基于個人理性，合作中的收益不能小于非合作中的收益，反映了參與人的參與約束。如果，那么，參與人是不可能參加聯(lián)盟的。是基于集體理性，每個參與人的分配之和不能超過集體剩余。另外若沒有全部被分配，顯然不是一個帕累托最優(yōu)的分配方案，不會參與人所接受。20分配分配的定義中，分配分配的定義中，

在前面的例子分配中，分配顯然不是一個，而是無限個，無限個分配形成一個分配集合。對于實質(zhì)博弈，其分配總是有無限個。例如，對于實質(zhì)博弈，由于存在無限個正向量，滿足。顯然如下的都是分配，其中。用表示一個博弈的所有分配方案組成的集合。分配21在前面的例子分配中，分配顯然不是一個，而是無限個，無在前面的例子分配中，分配顯然不是一個，而是無限個，無分配中的優(yōu)超定義4

設(shè)的兩個分配和，是一個聯(lián)盟。如果分配方案和滿足（i），；（ii）。則稱分配方案在上優(yōu)超于，或稱分配方案在上劣于，記為。如果分配方案在上優(yōu)超于，則聯(lián)盟會拒絕分配方案，方案得不到切實執(zhí)行。因為從到，中的每個參與人的收益都得到改善，創(chuàng)造的剩余又足以滿足他們在中的分配。22分配中的優(yōu)超定義4設(shè)的兩個分配和分配中的優(yōu)超定義4設(shè)的兩個分配和分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：1.單人聯(lián)盟不可能有優(yōu)超關(guān)系。2.全聯(lián)盟上也不可能有優(yōu)超關(guān)系。因此，如果在上有優(yōu)超關(guān)系，則。3.優(yōu)超關(guān)系是集合上的序關(guān)系，這種序關(guān)系一般情況下不具有傳遞性和反身性。4.對于相同的聯(lián)盟，優(yōu)超關(guān)系具有傳遞性，即，，則有。5.對于不同的聯(lián)盟，優(yōu)超關(guān)系不具有傳遞性。23分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：23分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：23分配中的優(yōu)核心

盡管可行分配集合中有無限個分配，但實際上，有許多分配是不會被執(zhí)行的，或者不可能被參與人所接受的。很顯然，聯(lián)盟的每一個成員都不偏好于劣分配方案，因此，真實可行的分配方案應(yīng)該剔除劣分配方案。定義5

在一個人合作博弈中，全體優(yōu)分配方案形成的集合稱為博弈的核心(core)，記為。顯然有。24核心盡管可行分配集合中有核心盡管可行分配集合中有核心說明：

1.核心是中的一個閉凸集。

2.若，則將中的向量作為分配，既滿足個人理性，又滿足集體理性。

3.用核心作為博弈的解，其最大缺陷是可能是空集。25核心說明：25核心說明：25核心說明：25核心定理1

分配方案在核心中的充要條件是：（i），，

(ii)。證明如果，滿足（i）、(ii)，則不可能被優(yōu)超，即。反證法，設(shè)存在，使。根據(jù)優(yōu)超的定義，有:則有，矛盾。如果，不滿足(ii)，則一定被優(yōu)超，即。26核心定理1分配方案核心定理1分配方案核心對于，存在聯(lián)盟，有，則定義，定義，使得在中平均分配，在中平均分配，從而得到一個新的分配如下：顯然如此定義得向量是個分配，且有。27核心對于，存在聯(lián)盟，有核心對于，存在聯(lián)盟，有例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)，若由定理1易知,該博弈的核由下面不等式組確定：易知，，，。故該博弈的核其圖形為單純形內(nèi)以為頂點的四邊形，如圖1所示。}10,20,40,5),,{()(321321321￡￡￡￡￡￡=++=xxxxxxxxxvc28例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)}10,20,4例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)}10,20,4圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)(4,0,1)29圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：，，，，求其核心。

解由核心定義，若，則它必滿足30核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：解由核核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：解由核解線形不等式組：該不等式組無解，即。上面三個例子說明了求解核心的方法。核心練習(xí)2考慮如下的合作博弈，特征函數(shù)如下：，；。31解線形不等式組：解線形不等式組：核心

在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即的穩(wěn)定性。對于中的每一個分配，每個聯(lián)盟都沒有反對意見，都沒有更好的分配，每個分配都可以得到執(zhí)行。當(dāng)然，用代替也有致命的缺陷，即可能是空集，而。定理2

對于人的聯(lián)盟博弈，核心非空的充分必要條件是線性規(guī)劃有解。

，32核心在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即核心在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即核心

定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)解一定屬于；若，則中的每個向量都是可行解，自然線性規(guī)劃（L）有最優(yōu)解。對于原線性規(guī)劃（P），寫出它的對偶規(guī)劃（DP）：

，33核心定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)核心定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)核心定理對策有的充分必要條件是：對于滿足的向量，有。定義設(shè)是個0-1簡單對策，若存在一個參與人，滿足，則稱作一個否決人。定理

簡單對策中，充分必要條件是中存在一個否決人。34核心定理對策有核心定理對策有核心證明設(shè)是中一個否決人，定義，1處于第的位置。根據(jù)定理2，

是一個分配，且。用反證法。設(shè)，且不存在否決人，即。，則。故有，從而。也即，矛盾。35核心證明設(shè)是中一個否決人，定義核心證明設(shè)是中一個否決人，定義核仁為評估對滿意性，定義如下的被稱作超出一個指標：

的大小反映了對滿意性。越大，對越不滿意，因為中所有參與人的分配之和遠沒有達到其所創(chuàng)造的合作剩余；越小，對越滿意，當(dāng)為負值時，中所有參與人不但分配了其所創(chuàng)造的合作剩余，還分配了其他聯(lián)盟所創(chuàng)造的價值。

36核仁為評估對滿意性，定義如下的被稱作超出一核仁為評估對滿意性，定義如下的被稱作超出一核仁

對于同一個，共有個，可以表示為。故可以計算出個。聯(lián)盟對的滿意性取決于中的最大的，故可以對個由大到小排列，得到一個的向量：其中。聯(lián)盟對的滿意性取決于的大小，越小，聯(lián)盟對越滿意。37核仁對于同一個，共有個，可以表核仁對于同一個，共有個，可以表核仁

對于兩個不同的分配，分別計算出。如果是小的，則聯(lián)盟對的滿意性大于聯(lián)盟對的滿意性，自然優(yōu)于。當(dāng)然這種向量大小的比較不同于數(shù)字的比較，是采用字典序的比較方法。字典序的比較方法的比較方法如下：對于向量和，存在一個下標，使得，，則稱字典序小于，用符號表示。有了上述的定義，就可以給出核仁的定義了。38核仁對于兩個不同的分配，分別計核仁對于兩個不同的分配，分別計核仁

定義

對于合作博弈，核仁是一些分配的集合，即，使得任取一個，都是字典序最小的，即。定理4

對于合作博弈，其核仁，且只包含一個元素。定理5對于合作博弈，如果核心，則有。39核仁定義對于合作博弈，核核仁定義對于合作博弈，核核仁

例5

考慮如下的合作博弈，，特征函數(shù)如下：；；。求該博弈的核仁。解先求出該博弈的核心，再求核仁。根據(jù)核心的條件，充分必要條件：解此不等式組，得到。40核仁例5考慮如下的合作博弈，核仁例5考慮如下的合作博弈，核仁

，故有。下面開始求。對于核心，開始求，。，有＝4－4＝0；，有＝0－＝；，有＝0－＝；，有＝5－＝；，有＝7－＝；，有＝6－＝0；，有＝10－10＝0；當(dāng)，。上式在達到，故有＝。該結(jié)果驗證了，。41核仁，故有核仁，故有Shapley值

分配是合作博弈最重要的概念，但遺憾的是在一個博弈中，分配有無限個，且許多根本就得不到執(zhí)行。利用優(yōu)超的概念，對分配進行了分類，形成了核心的概念，但遺憾的是，許多博弈中核心可能是空集。為此，引入了超出這一指標，尋求最大超出最小化的分配，即核仁。核仁這一解的優(yōu)勢體現(xiàn)在核仁總存在，且是唯一的，這一解的缺陷就是計算太復(fù)雜，因為共有個。本節(jié)引入了一個很直觀的解的概念，即Shapley值。參與人按照Shapley值進行分配。42Shapley值分配是合作博弈最重要的概念，但遺憾的Shapley值分配是合作博弈最重要的概念，但遺憾的Shapley值

定理6

對每個博弈，存在唯一的Shapley值，其中（8.5.1）下面對這一計算公式給出非數(shù)學(xué)化的解釋：1、，就是按照參與人的平均貢獻來安排的分配設(shè)計。2、在一個博弈中，每個人的所得應(yīng)該與其貢獻成正比。對于聯(lián)盟，其合作剩余。如加入，則新聯(lián)盟的合作剩余是。因此的貢獻是。43Shapley值定理6對每個博弈Shapley值定理6對每個博弈Shapley值3、在博弈中，不包含的有個，對每個都有一個貢獻值，因此，Shapley值的計算公式中有項。4、即使對于一個固定的，與中參與人的排列順序無關(guān)，與中參與人的順序無關(guān)。因此的系數(shù)中存在。為什么系數(shù)中有？主要是為了計算的平均值。44Shapley值3、在博弈中，不包含Shapley值3、在博弈中，不包含Shapley值5、對于也可以作出這樣解釋：加入，其貢獻是。加入的概率是多少？如果個局中人以次參加博弈，當(dāng)加入該博弈時，其前面已有一些參與人，加入后，后繼的參與人集合。和中參與人的順序與無關(guān)。加入的概率是，的數(shù)學(xué)期望（或者平均值）就是Shapley值。

6、Shapley值不一定是個分配，即理性約束可能不滿足。45Shapley值5、對于Shapley值5、對于Shapley值例1假設(shè)聯(lián)合國安理會進行投票，部分國家可以形成聯(lián)盟。該博弈的特征函數(shù)為：而對所有其他，。為了求，對所有包含參與人1的聯(lián)盟按Shapley值求和。與有差異的聯(lián)盟只有、、、、、和，對于其他的，＝0。所以有

類似地，。于是，，。這樣，參與人1、2比參與人3、4、5重要得多。46Shapley值例1假設(shè)聯(lián)合國安理會進行投票，部分國家可以Shapley值例1假設(shè)聯(lián)合國安理會進行投票，部分國家可以Shapley值定理若博弈滿足超加性，即,,則Shapley向量，即Shapley值是分配。證明滿足超加性，則。47Shapley值定理若博弈滿足超加性，即Shapley值定理若博弈滿足超加性，即謝謝！48謝謝！48謝謝！48謝謝！48博弈論

經(jīng)濟與管理學(xué)院劉洋博士

49博弈論經(jīng)濟與管理學(xué)院劉洋博士1博弈論經(jīng)濟與管理學(xué)院劉洋博士49博弈論經(jīng)濟與管理合作博弈

（COOPERATIVEGAMES)50合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)50合作

合作博弈

COOPERATIVEGAMES熊、狼、狐貍一起抓了一只兔子，民主協(xié)商如何分配。狐貍對熊說：平均分只能各得1/3，這樣吧，我們倆聯(lián)合起來，平分如何？熊要答應(yīng)，狼急了，于是狐貍對狼說：怎么樣，我和熊聯(lián)合起來可以讓你什么也得不到，我可以和你合作，不過我要3/4。狼感激的點頭，熊琢磨過味來，對狼說：別聽那個兩面三刀的，和我合作，我給你1/3。狐貍見勢不妙，對狼說：別，我給你2/3，我只要1/3。狼成了搶手貨，正得意，沒留神狐貍和熊又開始嘀咕起來，有再次把自己晾在一邊的不妙趨勢，連忙鉆去繼續(xù)討價還價。結(jié)果呢？51合作博弈

COOPERATIVEGAM合作博弈

COOPERATIVEGAM如果在實際博弈問題中，具有有力的保障使局中人能夠進行協(xié)商、談判，聯(lián)合選擇行動，共同分享利益，我們就面對一個合作博弈問題。本章通過合作博弈模型的介紹，討論在合作博弈中，局中人如何進行協(xié)商談判、結(jié)成聯(lián)盟及分享利益。1、聯(lián)盟博弈2、聯(lián)盟博弈的分配3、核和穩(wěn)定集4、沙普利值524524導(dǎo)論先回憶一下囚徒困境的例子：

在囚徒困境中，還有另外一個策略組合<抵抗，抵抗>，該組合為參與人帶來的支付是<-1,-1>。由<-8,-8>到<-1,-1>，每個參與人的支付都增加了，即得到一個帕累托改進。坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-153導(dǎo)論先回憶一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1導(dǎo)論先回憶一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1導(dǎo)論

<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人理性。在參與人選擇抵抗的情況下，每個參與人都有動機偏離這個組合，通過投機行為謀取超額收益1。如果兩個參與人在博弈之前，簽署了一個協(xié)議：兩個人都承諾選擇抵抗，為保證承諾的實現(xiàn)，參與人雙方向第三方支付價值大于1的保證金；如果誰違背了這個協(xié)議，則放棄保證金。有了這樣一個協(xié)議，<抵抗，抵抗>就稱為一個均衡，每個人的收益都得到改善。上述分析表明，通過一個有約束力的協(xié)議，原來不能實現(xiàn)的合作方案現(xiàn)在可以實現(xiàn)。這就是合作博弈與非合作博弈的區(qū)別。二者的主要區(qū)別在于人們的行為相互作用時,當(dāng)事人是否達成一個具有約束力的協(xié)議。如果有,就是合作博弈；反之,則是非合作博弈。54導(dǎo)論<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人導(dǎo)論<抵抗，抵抗>構(gòu)不成一個均衡是基于參與人的個人合作博弈的概念及其表示

合作博弈，非合作博弈的對稱，一種博弈類型。參與者能夠聯(lián)合達成一個具有約束力且可強制執(zhí)行的協(xié)議的博弈類型。合作博弈強調(diào)的是集體理性,強調(diào)效率、公正、公平。合作博弈最重要的兩個概念是聯(lián)盟和分配。每個參與者從聯(lián)盟中分配的收益正好是各種聯(lián)盟形式的最大總收益,每個參與者從聯(lián)盟中分配到的收益不小于單獨經(jīng)營所得收益。55合作博弈的概念及其表示合作博弈，非合合作博弈的概念及其表示合作博弈，非合合作博弈的概念及其表示

合作博弈的結(jié)果必須是一個帕累托改進，博弈雙方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受損害。合作博弈采取的是一種合作的方式，合作之所以能夠增進雙方的利益，就是因為合作博弈能夠產(chǎn)生一種合作剩余。至于合作剩余在博弈各方之間如何分配，取決于博弈各方的力量對比和制度設(shè)計。

合作博弈的核心問題是參與人如何結(jié)盟以及如何重新分配結(jié)盟的支付。56合作博弈的概念及其表示合作博弈的結(jié)果必合作博弈的概念及其表示合作博弈的結(jié)果必合作博弈的概念及其表示

定義1

在人博弈中，參與人集用表示，的任意子集稱為一個聯(lián)盟（coalition）。

空集和全集也可以看成是一個聯(lián)盟，當(dāng)然單點集也是一個聯(lián)盟。定義2

給定一個人博弈，是一個聯(lián)盟，是指和的兩人博弈中的最大效用，稱為聯(lián)盟的特征函數(shù)（characteristicfunction）。

規(guī)定。根據(jù)定義，表示參與人與全體其他人博弈時的最大效用值，表示為。用表示參與人集為，特征函數(shù)為的合作博弈，其中是定義在上的實值映射。在很多情況下，一個聯(lián)盟能獲得的支付依賴于其他參與人所采取的行動。有時被解釋為聯(lián)盟獨立于聯(lián)盟的行動可保證的最大支付。57合作博弈的概念及其表示定義1在人博弈合作博弈的概念及其表示定義1在人博弈合作博弈的概念及其表示

合作對策的分類主要是根據(jù)特征函數(shù)的性質(zhì)。下面根據(jù)特征函數(shù)的性質(zhì)介紹幾類特殊的合作對策。如果僅與的個數(shù)有關(guān)，則稱作對稱博弈。如果，則稱作常和博弈。如果，則稱作簡單博弈。例如，在投票博弈中，每個參與人的權(quán)重，

如果，則稱作凸博弈。58合作博弈的概念及其表示合作對策的分類主要是根據(jù)特征函合作博弈的概念及其表示合作對策的分類主要是根據(jù)特征函合作博弈的概念及其表示

之所以稱為特征函數(shù)，是因為這個合作博弈的性質(zhì)基本由決定。由此可見對合作博弈的重要性。定理設(shè)是參與人集合上的特征函數(shù)，則有如下的超可加性：對于聯(lián)盟和，如果，則上式說明，特征函數(shù)只有滿足超加性，才有形成新聯(lián)盟的必要性。否則，如果一個合作博弈的特征函數(shù)不滿足超可加性，那么，其成員沒有動機形成聯(lián)盟，已經(jīng)形成的聯(lián)盟將面臨解散的威脅。59合作博弈的概念及其表示之所以稱為特征函數(shù)，是因合作博弈的概念及其表示之所以稱為特征函數(shù)，是因例：

局中人1（賣主）要把一件物品賣掉，局中人2和3（買主）分別出價9元和10元。如果局中人1將物品賣給局中人2的要價是x

元，則局中人2贏利9-x元。聯(lián)盟的總收益為9元。類似，聯(lián)盟的總贏利為10元。于是有。另一方面，單個局中人或者兩個買主在一起都不可能贏利，即，。當(dāng)三個局中人在一起交易時，局中人1顯然要把物品賣給局中人3，從而v({1,2,3})=10，顯然滿足超可加性，于是我們建立了聯(lián)盟博弈。特征函數(shù)是研究聯(lián)盟博弈的基礎(chǔ)，確定特征函數(shù)過程實際就是一個建立合作博弈模型的過程。有的問題，特征函數(shù)可以容易地得到，有的問題需要仔細分析，甚至需要一些專業(yè)知識。60例：局中人1（賣主）要把一件物品賣掉，局中人2和3（買主例：局中人1（賣主）要把一件物品賣掉，局中人2和3（買主由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0V(1)=0V(2)=5V(1,2)=10局中人2LR局中人1U-1，25，5D0，100，10最小最大值法：聯(lián)盟外局中人將采取行動使該聯(lián)盟的總和收益最小（極度悲觀），聯(lián)盟選擇策略－－最大化這些最小值。61由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0局中人2LR局中人由策略型博弈導(dǎo)出特征函數(shù)型博弈V()=0局中人2LR局中人例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民每天產(chǎn)生一袋垃圾，這些垃圾只能扔在這一區(qū)域的某一戶人家領(lǐng)地（區(qū)域中沒有空地）。記Vn(n=0,1,…,7)表示任意n個局中人組成的特征函數(shù)值，在合作博弈條件下，有：

V0=V()=0

V1=-6

V2=-5V3=-4，V4=-3，V5=-2

V6=-1，V7=-762例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民例：垃圾博弈－－分析博弈局勢在一區(qū)域中住著7戶居民，每戶居民合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各有兩個純策略。當(dāng)三人不合作時，其支付見下表。假設(shè)采用最穩(wěn)妥策略，即最壞情況下選擇最好，求合作博弈的支付函數(shù)63合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各合作博弈的概念及其表示例：設(shè)有一個3人合作對策，每個參與人各合作博弈的概念及其表示解：用表示一個聯(lián)盟，表示聯(lián)盟中參與人的個數(shù)。當(dāng)＝0，自然，有。當(dāng)＝1，有3個，以為例。當(dāng)，則。的策略集合，策略組合。與進行如下矩陣對策：64合作博弈的概念及其表示解：用表示一個聯(lián)盟，合作博弈的概念及其表示解：用表示一個聯(lián)盟，合作博弈的概念及其表示

上述矩陣對策沒有純策略，的混合策略是，的混合策略是。的均衡值是。故。同理，可以求出。當(dāng)＝2，有3個，以為例。當(dāng)，則。的策略集合,

策略組合。與進行如下矩陣對策：65合作博弈的概念及其表示上述矩陣對策沒有純策略，合作博弈的概念及其表示上述矩陣對策沒有純策略，合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值是3。故。同理，可以求出。當(dāng)＝3，有1個，，最大的聯(lián)盟。的策略空間。有。至此特征函數(shù)的值已全部求出。66合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值合作博弈的概念及其表示上述矩陣對策有純策略，的均衡值分配

所謂分配就是博弈的一個維向量集合，之所以是維向量，是由于每個參與人都要得到相應(yīng)的分配。維的分配向量稱為博弈的“解”。定義3

對于合作博弈，對每個參與人，給予一個實值參數(shù)，形成維向量且其滿足：

則稱是聯(lián)盟的一個分配方案。67分配所謂分配就是博弈的一個維向量集合，之分配所謂分配就是博弈的一個維向量集合，之分配

分配的定義中，是基于個人理性，合作中的收益不能小于非合作中的收益，反映了參與人的參與約束。如果，那么，參與人是不可能參加聯(lián)盟的。是基于集體理性，每個參與人的分配之和不能超過集體剩余。另外若沒有全部被分配，顯然不是一個帕累托最優(yōu)的分配方案，不會參與人所接受。68分配分配的定義中，分配分配的定義中，

在前面的例子分配中，分配顯然不是一個，而是無限個，無限個分配形成一個分配集合。對于實質(zhì)博弈，其分配總是有無限個。例如，對于實質(zhì)博弈，由于存在無限個正向量，滿足。顯然如下的都是分配，其中。用表示一個博弈的所有分配方案組成的集合。分配69在前面的例子分配中，分配顯然不是一個，而是無限個，無在前面的例子分配中，分配顯然不是一個，而是無限個，無分配中的優(yōu)超定義4

設(shè)的兩個分配和，是一個聯(lián)盟。如果分配方案和滿足（i），；（ii）。則稱分配方案在上優(yōu)超于，或稱分配方案在上劣于，記為。如果分配方案在上優(yōu)超于，則聯(lián)盟會拒絕分配方案，方案得不到切實執(zhí)行。因為從到，中的每個參與人的收益都得到改善，創(chuàng)造的剩余又足以滿足他們在中的分配。70分配中的優(yōu)超定義4設(shè)的兩個分配和分配中的優(yōu)超定義4設(shè)的兩個分配和分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：1.單人聯(lián)盟不可能有優(yōu)超關(guān)系。2.全聯(lián)盟上也不可能有優(yōu)超關(guān)系。因此，如果在上有優(yōu)超關(guān)系，則。3.優(yōu)超關(guān)系是集合上的序關(guān)系，這種序關(guān)系一般情況下不具有傳遞性和反身性。4.對于相同的聯(lián)盟，優(yōu)超關(guān)系具有傳遞性，即，，則有。5.對于不同的聯(lián)盟，優(yōu)超關(guān)系不具有傳遞性。71分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：23分配中的優(yōu)超在優(yōu)超關(guān)系中，聯(lián)盟的特征：71分配中的優(yōu)核心

盡管可行分配集合中有無限個分配，但實際上，有許多分配是不會被執(zhí)行的，或者不可能被參與人所接受的。很顯然，聯(lián)盟的每一個成員都不偏好于劣分配方案，因此，真實可行的分配方案應(yīng)該剔除劣分配方案。定義5

在一個人合作博弈中，全體優(yōu)分配方案形成的集合稱為博弈的核心(core)，記為。顯然有。72核心盡管可行分配集合中有核心盡管可行分配集合中有核心說明：

1.核心是中的一個閉凸集。

2.若，則將中的向量作為分配，既滿足個人理性，又滿足集體理性。

3.用核心作為博弈的解，其最大缺陷是可能是空集。73核心說明：25核心說明：73核心說明：25核心定理1

分配方案在核心中的充要條件是：（i），，

(ii)。證明如果，滿足（i）、(ii)，則不可能被優(yōu)超，即。反證法，設(shè)存在，使。根據(jù)優(yōu)超的定義，有:則有，矛盾。如果，不滿足(ii)，則一定被優(yōu)超，即。74核心定理1分配方案核心定理1分配方案核心對于，存在聯(lián)盟，有，則定義，定義，使得在中平均分配，在中平均分配，從而得到一個新的分配如下：顯然如此定義得向量是個分配，且有。75核心對于，存在聯(lián)盟，有核心對于，存在聯(lián)盟，有例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)，若由定理1易知,該博弈的核由下面不等式組確定：易知，，，。故該博弈的核其圖形為單純形內(nèi)以為頂點的四邊形，如圖1所示。}10,20,40,5),,{()(321321321￡￡￡￡￡￡=++=xxxxxxxxxvc76例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)}10,20,4例2設(shè)有三人聯(lián)盟對策，其特征函數(shù)}10,20,4圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)(4,0,1)77圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1圖1(5,0,0)（0,5,0）（0,0,5）(2,2,1核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：，，，，求其核心。

解由核心定義，若，則它必滿足78核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：解由核核心練習(xí)1：設(shè)3人合作博弈的特征函數(shù)如下：解由核解線形不等式組：該不等式組無解，即。上面三個例子說明了求解核心的方法。核心練習(xí)2考慮如下的合作博弈，特征函數(shù)如下：，；。79解線形不等式組：解線形不等式組：核心

在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即的穩(wěn)定性。對于中的每一個分配，每個聯(lián)盟都沒有反對意見，都沒有更好的分配，每個分配都可以得到執(zhí)行。當(dāng)然，用代替也有致命的缺陷，即可能是空集，而。定理2

對于人的聯(lián)盟博弈，核心非空的充分必要條件是線性規(guī)劃有解。

，80核心在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即核心在合作博弈中，用核心代替分配具有明顯得優(yōu)點，即核心

定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)解一定屬于；若，則中的每個向量都是可行解，自然線性規(guī)劃（L）有最優(yōu)解。對于原線性規(guī)劃（P），寫出它的對偶規(guī)劃（DP）：

，81核心定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)核心定理的直觀意義很明顯，線性規(guī)劃（L）若有解，則最優(yōu)核心定理對策有的充分必要條件是：對于滿足的向量，有。定義設(shè)是個0-1