第五章 合作博弈

章多人合作博弈模型

一、問題引入二、多人結(jié)盟博弈的基本概念三、多人結(jié)盟博弈的解四、常用解法2021/6/271一、問題引入例1：（爵士樂隊(duì)博弈，AJazzBandGounce）

一位歌手（S），一位鋼琴家（P）和一位鼓手（D）組成一個(gè)小樂隊(duì)在俱樂部同臺演出能得到演出費(fèi)1000元，若歌手和鋼琴家一起演出能得800元。而只有鋼琴家和鼓手一起演出能得到650元，鋼琴獨(dú)奏表演能得300元，鋼琴家沒有其它收入。然而，歌手和鼓手在地鐵中表演能掙500元，歌手獨(dú)奏可以從TheTerasses掙200元，而鼓手單獨(dú)什么也掙不到。問題：如何在這三人爵士樂隊(duì)中合理分配共同演出費(fèi)1000元？2021/6/272例2：成本分?jǐn)倖栴}（ACostGame） 三個(gè)城鎮(zhèn)A，B，C欲與附近的一座電站連接起來，其可能的線路及其成本如下網(wǎng)絡(luò)圖表示：這三個(gè)鎮(zhèn)可相互聯(lián)合建設(shè)，試問如何在這三個(gè)小鎮(zhèn)合理分?jǐn)傔@筆建設(shè)費(fèi)？ABC2021/6/273二、多人結(jié)盟博弈的基本概念多人結(jié)盟博弈：局中人多于二人時(shí)的博弈稱為多人博弈。這種博弈中如果局中人可以和其它局中人聯(lián)合成一體統(tǒng)一行動與其它局中人對抗，這種博弈稱為多人結(jié)盟博弈。這種博弈有三個(gè)基本要素:局中人N＝{1,2,…,n}；結(jié)盟S；特征函數(shù)V（S）。一般可用<N,V>表示一個(gè)多人結(jié)盟博弈。2021/6/2741、局中人與結(jié)盟（1）N＝{1,2,…,n}表示局中人集合。（2）結(jié)盟S，表示一個(gè)聯(lián)盟，即一局多人對策中，一部份局中人聯(lián)合成一體像一個(gè)“局中人”一樣選擇策略，這種聯(lián)合稱為結(jié)盟。顯然結(jié)盟S是局中人集合N

的子集，S

N。（3）2n是局中人可能形成結(jié)盟的個(gè)數(shù)。2021/6/2752、特征函數(shù)V(S)（1）V(S)表示當(dāng)若干局中人聯(lián)合成一個(gè)結(jié)盟S時(shí),在這局博弈中能獲得的最大收益值,即當(dāng)形成結(jié)盟S,只要S內(nèi)每一個(gè)局中人共同策略,選擇相應(yīng)策略結(jié)盟S能保證獲得,而與聯(lián)盟外局人采用什么策略無關(guān)。若S=

,V(

)=0。（2）超可加性 若一個(gè)多人博弈的特征函數(shù)具有下列性質(zhì),即對任意結(jié)盟S,T

N,S∩T=

,滿足 V(S∪T)≥V(S)+V(T).稱這個(gè)多人博弈具有超可加性。如果特征函數(shù)不滿足超可加性，博弈中的結(jié)盟是不穩(wěn)定的。2021/6/276例1：（爵士樂隊(duì)博弈，AJazzBandGounce）一位歌手（S），一位鋼琴家（P）和一位鼓手（D）組成一個(gè)小樂隊(duì)在俱樂部同臺演出能得到演出費(fèi)1000元，若歌手和鋼琴家一起演出能得800元。而只有鋼琴家和鼓手一起演出能得到650元，鋼琴獨(dú)奏表演能得300元，鋼琴家沒有其它收入。然而，歌手和鼓手在地鐵中表演能掙500元，歌手獨(dú)奏可以從TheTerasses掙200元，而鼓手單獨(dú)什么也掙不到。問題：如何在這三人爵士樂隊(duì)中合理分配共同演出費(fèi)1000元？2021/6/277這個(gè)問題可歸為一個(gè)三人合作博弈，它的特征函數(shù)V（S）為：很容易驗(yàn)證此博弈是具有超可加性的。

結(jié)盟S{S,P,D}{S,P}{S,D}{P,D}{S}{P}{D}V(S)100080050065020030002021/6/278例2:（產(chǎn)品博弈AProductionGame）從M1、M2、M3、M4四種原材料中各取一個(gè)單位能生產(chǎn)1個(gè)單位的某種產(chǎn)品，這個(gè)產(chǎn)品的價(jià)格要比它的原材料成本高出1000元，現(xiàn)有三個(gè)人，他們擁有這四種材料情況如下表:問：若這三人聯(lián)合起來生產(chǎn)這種產(chǎn)品，他們之間該如何分配所得利潤？原材料人M1M2M3M411/21/20021/2010301/2012021/6/279將此問題轉(zhuǎn)化為三人博弈，其特征函數(shù)如下：局中人2，3，通過合作生產(chǎn)，但由于他們共有四種原材料只能生產(chǎn)1/2個(gè)單位產(chǎn)品，所以能掙500元。S

{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}V(S)00000050010002021/6/2710例3：成本分?jǐn)倖栴}（ACostGame） 三個(gè)城鎮(zhèn)A，B，C欲與附近的一座電站連接起來，其可能的線路及其成本如下網(wǎng)絡(luò)圖表示：這三個(gè)鎮(zhèn)可相互聯(lián)合建設(shè)，試問如何在這三個(gè)小鎮(zhèn)合理分?jǐn)傔@筆建設(shè)費(fèi)？ABC2021/6/2711這個(gè)問題的合作博弈對<N,C>，N={A,B,C}，成本分?jǐn)偛┺牡奶卣骱瘮?shù)V(S)為成本節(jié)省，如下表：

博弈<W,V>的特征函數(shù)值V(S)，由下式得出S

{A}{B}{C}{A,B}{A,C}{B,C}{A,B,C}C(S)0100140130150130160150V(S)0000901001102202021/6/271222090110100Ａ0Ｂ0Ｃ0150150130160Ａ100Ｂ140Ｃ1302021/6/2713三、多人結(jié)盟博弈的解多人結(jié)盟博弈的解的概念 多人結(jié)盟博弈中，每個(gè)局中人都希望通過結(jié)盟的形式去得到更多，而博弈解的問題是如何合理確定這局博弈中每個(gè)局中人的分配收益，博弈解一般用

X＝(x1,x2,…xn) 表示n個(gè)局中人的得失向量，xi

表示第i個(gè)局中人之所得。2021/6/27141、合理分配（Imputation）作為一個(gè)博弈的解X，即在博弈中對N個(gè)局中人得失的合理分配，至少應(yīng)滿足兩個(gè)條件：（1）（個(gè)人合理性）（2）（集體合理性）條件（1）稱為：“個(gè)人合理性”（IndividualRationality），表示局中人i所分配值xi不小于特征函數(shù)中規(guī)定他至少能得到的值V(i)。條件（2）稱為“集體合理性”條件（GroupRationality），表示對于一個(gè)博弈解，所有局中人分配得失之和應(yīng)等于所有局中人聯(lián)合起來形成一個(gè)大聯(lián)盟時(shí)得到的收益值，也就是這局博弈中的最大收益值V(N)。由超可加性2021/6/2715滿足上述兩種條件的X=(x1……xn)稱為“合理分配”，即有顯然，作為多人結(jié)盟博弈的一個(gè)解X，至少必須是一個(gè)合理分配，即2021/6/2716例4：一局博弈，<N,V>，N={1,2,3}，特征函數(shù)如下：

V(φ)=0，V({1})=V({2})=V({3})=0

V({1,2})=V({1,3})=V({2,3})=0

V({1,2,3})=1合理分配集合而就是其中兩合理分配。2021/6/27172、支配（Domination）多人結(jié)盟博弈求解問題實(shí)際是在合理分配集I(V)中，按某種準(zhǔn)則選擇一個(gè)或一組合理分配，作為對策的解。但一個(gè)對策中，不可能存在一個(gè)合理分配優(yōu)于另一個(gè)合理分配，即滿足，這是因?yàn)?/p>

但是對于某一個(gè)聯(lián)盟S，只要滿足成立（這是可能的），則對S聯(lián)盟而言可認(rèn)為X分配優(yōu)于Y分配，即得出支配概念2021/6/2718定義：對于兩個(gè)合理分配X，Y，若對于某一聯(lián)盟S，有（1）（2） 則稱合理分配X通過聯(lián)盟S支配Y，記為解釋： 條件（1）表示對于聯(lián)盟S來講，X優(yōu)于Y。 條件（2）表示聯(lián)盟S有足夠的能力保證它的局中人I通過合作能獲得合理分配定義：在博弈中，只要存在某一聯(lián)盟S，且X通過S支配Y，則也稱X支配Y，記為2021/6/2719四、常用解法1、穩(wěn)集法2、核法3、Shaply值法4、多目標(biāo)規(guī)劃方法2021/6/27201、穩(wěn)集穩(wěn)集的基本思想 是選擇這樣一個(gè)合理分配的集合作為對策的解：不在這集合內(nèi)的任何合理分配總能被這個(gè)集合中某個(gè)合理分配所支配，且這個(gè)集合內(nèi)的合理分配互相不被支配。定義：對于一個(gè)對策，存在一組合理分配滿足（1），則X，Y互相不被支配。（2）對任合理分配，則必存在 則稱這樣一組合理分配S(V)為此對策的穩(wěn)集。穩(wěn)集被看作多人結(jié)盟對策的一種形式。2021/6/2721例5：有一三人結(jié)盟博弈<N,V>，N={1,2,3}，V(S)為 V(φ)=V({1})=V({2})=V({3})=0 V({1,2})=V({1,3})=V({2,3})=V({1,2,3})=2很容易證明：

S(V)={(1,1,0),(1,0,1),(0,1,1)}是此博弈的一個(gè)穩(wěn)集。2021/6/2722（1）先驗(yàn)證這三個(gè)合理分配間不相互支配。對任一個(gè)不可能成立。例如對在三個(gè)分配中任兩個(gè)之間不可能同時(shí)成立。（2）設(shè)任一的合理分配分別討論的情況。2021/6/2723穩(wěn)集作為解，從支配角度具有合理性，但存在如下問題：（1）多數(shù)結(jié)盟博弈可能有多個(gè)穩(wěn)集，（2）有的博弈都不存在穩(wěn)集

Lucas（1968）舉出一個(gè)無穩(wěn)集的10人博弈例子；Lucas和Rboie（1980）又舉出一個(gè)無穩(wěn)集的13人博弈的例子。2021/6/27242、核（TheCore）核的主要思想也是基于支配概念，即從合理分配集I(V)中選擇一組合理分配，它們對任何聯(lián)盟來說都不被其他合理分配所支配，把這組合理分配，稱為“核”，作為博弈的一種解的形式。定義：博弈<N,V>，若存在一組合理分配，對任何聯(lián)盟S，滿足

稱這組合理分配為博弈的核，并用C(V)表示，記為2021/6/27252、核（TheCore）定義：設(shè)X是聯(lián)盟博弈<N,V>的一個(gè)合理分配，若存在一聯(lián)盟S，使得則稱聯(lián)盟S瓦解分配X。所以，核是不會被任何聯(lián)盟瓦解的合理分配的集合。2021/6/2726例：三人（分別記為1,2,3）有機(jī)會分享300元，分配方案由民主表決通過（少數(shù)服從多數(shù)），如果達(dá)不成協(xié)議則失去這個(gè)機(jī)會。特征函數(shù)：2021/6/2727實(shí)際問題中，經(jīng)濟(jì)問題的博弈通常是有核的，而在政治科學(xué)的一些多人博弈問題常常是沒有核存在，為了解決此問題，提出弱核的概。核作為博弈解的合理性：

核中的分配肯定不會被任何聯(lián)盟推翻，因此在聯(lián)盟博弈中具有穩(wěn)定性。核作為博弈解的缺點(diǎn)：并非每一個(gè)博弈均有非空的核。2021/6/2728通過求解下列LP問題，求得一個(gè)非空弱核。s.t.稱根據(jù)合理分配、穩(wěn)集、核的定義有下面關(guān)系成立，

即核必定在穩(wěn)集內(nèi)，穩(wěn)集必定在合理分配集合內(nèi)。

2021/6/27293、沙波利值（TheShapleyValue）多人結(jié)盟博弈的TheShapleyValue解的概念是Shapley在1953年提出的，這個(gè)解的概念不同于前面介紹的核和穩(wěn)集的概念。用核作為博弈解的思想是基于選擇不被支配的合理分配去作博弈的解，而穩(wěn)集是基于選擇能支配一切不在這個(gè)集合內(nèi)的合理分配的合理分配作為博弈的解，而Shapley則是基于期望邊際收入思想上提出的，他從局中人角度分析在博弈之前，每個(gè)局中人應(yīng)該期望得到多少。2021/6/2730在一局博弈<N，V>中，Shapley值由下式給出：

對于一個(gè)n人合作博弈<N,V>，存在唯一的一個(gè)向量函數(shù)其中，|S|表示聯(lián)盟S中人的個(gè)數(shù)，則稱為Shapley值。2021/6/2731Shapely法是一種期望邊際收入思想。表示由于局中人參加了聯(lián)盟而帶來的數(shù)值，即局中人i對聯(lián)盟S的邊際貢獻(xiàn)，而表示局中人參加S的概率。（局中人i在（N-S）個(gè)局中人前，（S-{i}）個(gè)局中人之后參加S的概率。）2021/6/2732例7：該博弈的特征函數(shù)如下

V({1})=a

V({2})=V({3})=V({2,3})=0

V({1,2})=b

V({1,3})=V({1,2,3})=c求Φi(V)，先把包括局中人1的聯(lián)盟抄列