當前位置:成語大全網 - 新華字典 - 合作博弈:聯盟、分配和核心core

合作博弈:聯盟、分配和核心core

@[toc]

合作博弈:非合作博弈的對稱,壹種博弈類型。參與者能夠聯合達成壹個具有約束力且可強制執行的協議的博弈類型。合作博弈強調的是集體理性,強調效率、公正、公平。

合作博弈最重要的兩個概念是 聯盟和分配 。每個參與者從聯盟中分配的收益正好是各種聯盟形式的最大總收益每個參與者從聯盟中分配到的收益不小於單獨經營所得收益。

合作博弈的基本形式是 聯盟博弈 ,它隱含的假設是存在壹個在參與者之間可以自由流動的交換媒介(如貨幣),每個參與者的效用與它是線性相關的。這些博弈被稱為"單邊支付"博弈,或可轉移效用(Transferable Utility ,TU)博弈。

合作博弈的結果必須是壹個 帕累托改進 ,博弈雙方的利益都有所增加,或者至少是壹方的利益增加,而另壹方的利益不受損害。合作博弈研究人們達成合作時如何分配合作得到的收益,即收益分配問題。合作博弈采取的是壹種合作的方式,合作之所以能夠增進雙方的利益,就是因為合作博弈能夠產生壹種 合作剩余 。至於合作剩余在博弈各方之間如何分配,取決於博弈各方的力量對比和制度設計。因此,合作剩余的分配既是合作的結果,又是達成合作的條件。

合作博弈的核心問題是參與人如何結盟以及如何重新分配結盟的支付。下面首先分析結盟的概念。與結盟相關聯的就是特征函數。

在n人博弈中,參與人集用 表示,N 的任意子集S稱為壹個聯盟(coalition)。空集 和全集N也可以看成壹個聯盟,單點集{i}也是壹個聯盟。

給定壹個n人博弈,S是壹個聯盟,v(S)是指S和 的兩人博弈中S的最大效用, 稱為聯盟S的特征函數(characteristic function)。

規定 。根據定義, 表示參與人i與全體其他人博弈時的最大效用值,表示為 。

用(N,v)表示參與人集為N,特征函數為v的合作博弈,其中v是定 義在 上的實值映射。

在很多情況下,壹個聯盟能獲得的支付依賴於其他參與人所采取的行動。 有時被解釋為聯盟S獨立於聯盟N-S的行動可保證的最大支付。

合作對策的分類主要是根據特征函數的性質。下面根據特征函數的性質介紹幾類特殊的合作對策。

例如,在投票博弈中,每個參與人的權重 ,

如果 ,則(N,v)稱作凸博弈。

v之所以稱為特征函數,是因為這個合作博弈的性質基本由v決定。由此可見v對合作博弈的重要性。

上式說明,特征函數只有滿足超加性,才有形成新聯盟的必要性。否則,如果壹個合作博弈的特征函數不滿足超可加性,那麽其成員沒有動機形成聯盟,已經形成的聯盟將面臨解散的威脅。

定理3的逆命題也是正確的,即:N是壹個集合,v是定義在 上的壹個非負實值函數。v滿足: ,如果 ,則存在壹個N上的合作博弈,使v成為該合作博弈的特征函數。

對於合作博弈 ,特征函數v滿足超加性,自然有:

根據上述不等式,特征函數v分成兩種類型:

類型1:v滿足 。即大連盟的效用是每個參 與人的效用之和。這說明通過聯盟並沒有創造新的合作剩余,聯盟沒有價值,這種聯盟也不可能維持。這種對策稱為 非實質性對策 ,沒有研究價值,不是本章研究的範疇。

對於非實質性對策,有 ,如果 。

類型2:v滿足 。即大連盟的效用大於每個參與人的效用之和。這說明通過聯盟創造了新的合作剩余,聯盟有意義,這種聯盟能否維持,取決於如何分配合作剩余,使每個參與人的支付都有改善。這種對策稱為 實質性對策 ,是本章研究的範疇。

所謂分配就是博弈的壹個n維向量集合,之所以是n維向量,是由於每個參與人都要得到相應的分配。n維的分配向量稱為博弈的“解”。

對於合作博弈 ,對每個參與人 ,給予壹個實值參數 ,形成n維向量 且其滿足:

則稱x是聯盟S的壹個分配方案。

分配的定義中, 是基於個人理性,合作中的收益不能小於非合作中的收益,反映了參與人的參與約朿。如果 ,那麽,參與人i是不可能參加聯盟的。 是基於集體理性,每個參與人的分配之和不能超過集體剩余v(N)。另外若v(N)沒有全部被分配,顯 然X不是壹個帕累托最優的分配方案,不會參與人所接受。

在例8.1分配中,分配顯然不是壹個,而是無限個,無限個分配形成壹個分配集合。對於實質博弈,其分配總是有無限個。例如,對於實質博弈(N,v),由於

存在無限個正向量 ,滿足 .顯然如下的 都是分配,其中 .用E(v)表示壹個博弈v的所有分配方案組成的集合。

設E(v)的兩個分配x和y,S是壹個聯盟。如果分配方案x和y滿足

(i)

(ii)

則稱分配方案x在上優超於y,或稱分配方案y在S上劣於x,記為

如果分配方案x在S上優超於y ,則聯盟S會拒絕分配方案y, y方案得不到切實執行。因為從y到x,S中的每個參與人的收益都得到改善,S創造的剩余v(S)又足以滿足他們在x中的分配。

在優超關系中,聯盟S的特征:

盡管可行分配集合E(v)有無限個分配,但實際上,有許多分配是不會被執行的,或者不町能被參與人所接受的。很顯然,聯盟的每壹個成員都不偏好於劣分配方案, 因此,真實可行的分配方案應該剔除劣分配方案。

在壹個n人合作博弈(N,v)中,全體優分配方案形成的集合稱為博弈的 核心(core) ,記為C(v)。顯然 有 .

說明:

1 .核心C(v)是E(v)中的壹個閉凸集。

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

3.用核心作為博弈的解,其最大缺陷是C(v)可能是空集。

分配方案 在核心C(v)中的充要條件是:

(i)

(ii)

證明:如果 ,x滿足(i)(ii),則x不可能被優超,即

反證法:設存在S,使 。根據優超的定義,有:

則有 ,矛盾。

如果 ,x不滿足(ii),則x壹定被優超,即 。

對於 ,存在聯盟S,有 ,則定義 ,使得 在S中平均分配, 在N-S中平均分配,從而得到壹個新的分配 如下:

顯然如此定義的向量 是個分配,且有 。

在合作博弈中,用核心代替分配具有明顯的優點,即C(v) 的穩定性。對於C(v)中的每壹個分配,每個聯盟都沒有反對意見,都沒有更好的分配,每個分配都可以得到執行。 當然,用C(v)代替E(v)也有致命的缺陷,即C(v)有可能是空集, 而 。

對於n人的聯盟博弈,核心C(v)非空的充分必要條件是線性規劃(P)有解。

定理的直觀意義很明顯,線性規劃(L)若有解,則最優解壹定屬於C(v);若 ,則C(v)中的每個向量都是可行解,自然線性規劃(L)有最優解解。

對於原線性規劃(P),寫出它的對偶規劃(DP)

定理:對策(N,v)有 的充分必要條件是:

對於滿足 的向量 ,有

定義:設(N,v)是個0-1簡單對策,若存在壹個參與人i ,滿足 ,則i稱作壹個否決人。

定理:簡單對策(N,v)中, 充分必要條件是N中存在壹個否決人。

證明:設j是N中壹個否決人,定義$e_i =( 0,0,…,1,0,…,0), 1處於 第i的位置。

根據定理8.3.2, 是壹個分配,且 。

用反證法。設 ,且不存在否決人,即

故有 ,從而 矛盾。

為評估S對X滿意性,定義如下的被稱作超出壹個指標:

e(S,x)的大小反映了 S對x的滿意性。e(S,x)越大,S對x越不滿意,因為S中所有參與人的分配之和遠沒有達到其所創造的合作剩余v(S); e(S,x)越小,S對X越滿意, 當e(S,x)為負值時,S中所有參與人不但分配了其所創造的合作剩余v(S),還分配了其他聯盟所創造的價值。

對於同壹個x, S***有 個,可以表示為 。 故可以計算出 個 。聯盟對x的滿意性取決於 中的最大的 ,故可以對 個 由大到小排列,得到壹個 的向量:

其中 。聯盟對x的滿意性取決於 的大小, 越小,聯盟對x越滿意。

對於兩個不同的分配x,y ,分別計算出 。如果 小的,則聯盟對x的滿意性大於聯盟對y的滿意性,自然x優於y。當然這種向量大小的比較不同於數字 的比較,是釆用字典序的比較方法。字典序的比較方法的 比較方法如下:

對於向量 和

存在-個下標左,使得 則稱 字典序小於 _,用符號表示 。有了上述的定義,就可以給岀核仁的定義了。

定義:對於合作博弈(N,v),核仁是壹些分配的集合,即 ,使得任取壹個 都是字典序最小 的,即

對於合作博弈(N,v),其核仁 ,且 只包含壹個元素x。

對於合作博弈(N,v),如果核心 ,則有 。

證明:用反證法。設存在壹個分配

根據核心的性質,由居頃知:必存在壹個聯盟S,滿足2><心), 由此可知*,》)= *)-

考慮如下的合作博弈(N,v),N = {1,2,3},特征函數如下:

v({1}) = 4,v({2}) = v({3}) = 0 ;

v({1, 2}) = 5, v({1,3}) = 7, v({2,3}) = 6 ; v({1,2,3}) = 10。 求該博弈的核仁。

解:先求出該博弈的核心,再求核仁。

根據核心的條件 充分必要條件:

解此不等式組,得到

,故有 .下面開始求核仁。

對於核心 開始求

當 上式在x=4 達到,故有 。該結果驗證了