圖聯(lián)盟結(jié)構(gòu)核的求解算法*

尚傳啟，劉驚雷

煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山東 煙臺(tái) 264005

1 引言

聯(lián)盟博弈是處理幾個(gè)實(shí)體間競(jìng)爭(zhēng)、合作的策略，它假定所有的Agent都是理性的，即每一個(gè)Agent都會(huì)為了尋求自身利益的最大化，選擇與他人合作（聯(lián)盟）。正因?yàn)锳gent具有自由聯(lián)盟的能力，吸引了AI和MAS（multi-agent system）更多的關(guān)注[1]。然而在實(shí)際生活中聯(lián)盟博弈具有復(fù)雜性和多樣性，例如聯(lián)盟的生成往往受到各種條件的限制，聯(lián)盟行為具有動(dòng)態(tài)性，無(wú)法快速達(dá)到穩(wěn)定狀態(tài)等問(wèn)題。這些問(wèn)題使得聯(lián)盟中的成員無(wú)法快速獲得最大利益，長(zhǎng)時(shí)間處于轉(zhuǎn)換聯(lián)盟的動(dòng)蕩中，設(shè)計(jì)帶有限制的聯(lián)盟生成機(jī)制和構(gòu)造穩(wěn)定聯(lián)盟結(jié)構(gòu)及其分配的算法已經(jīng)成為一個(gè)重要的研究目標(biāo)。

一直以來(lái)對(duì)于合作博弈的研究，大都假定任意聯(lián)盟可行，對(duì)于聯(lián)盟的生成問(wèn)題，僅從聯(lián)盟內(nèi)部因素考慮，忽略了外部環(huán)境對(duì)于聯(lián)盟生成的影響。然而在外部環(huán)境中往往會(huì)存在許多限制和阻礙，比如距離、時(shí)間等因素，甚至與用戶的性格有關(guān)。尋找一種方法，模擬現(xiàn)實(shí)中的各種限制，直觀、簡(jiǎn)單地表現(xiàn)出聯(lián)盟的生成關(guān)系就顯得十分必要。本文采用約束圖作為約束條件，來(lái)約束聯(lián)盟的生成。下面通過(guò)對(duì)一個(gè)熱點(diǎn)問(wèn)題的分析來(lái)展示約束圖的表現(xiàn)效果。圖1表現(xiàn)的是無(wú)線合作文件共享系統(tǒng)[2]。由圖可以發(fā)現(xiàn)用戶間的聯(lián)盟生成關(guān)系：用戶1、3由于距離的原因無(wú)法組成聯(lián)盟{(lán)1,3}，但是可以通過(guò)用戶2作為“橋梁”來(lái)組建聯(lián)盟 {1,2,3}，用戶3、4、5可以自由組建聯(lián)盟，由于距離的限制，用戶4、5無(wú)法與用戶1、2進(jìn)行通信，需要借助用戶3作為“橋梁”。通過(guò)上述的分析，可以發(fā)現(xiàn)由于外部環(huán)境的影響，聯(lián)盟的生成變得復(fù)雜，通過(guò)交互圖可以模擬實(shí)際應(yīng)用中聯(lián)盟生成的障礙。

Fig.1 Wireless file sharing system圖1 無(wú)線合作共享系統(tǒng)

Agent加入聯(lián)盟的目的是為了獲得更大的利益，然而在傳統(tǒng)研究中默認(rèn)聯(lián)盟利益滿足超加性（若兩個(gè)聯(lián)盟合并，那么合并后的聯(lián)盟具有的利益至少是合并前兩個(gè)聯(lián)盟的利益之和），這就使得大聯(lián)盟（包含所有Agent的聯(lián)盟）一定具有最大的社會(huì)福利。事實(shí)上Agent間組成聯(lián)盟需要花費(fèi)一定的代價(jià)，有時(shí)代價(jià)甚至大于聯(lián)盟的收益，因此聯(lián)盟利益滿足超加性具有理想化的特點(diǎn)，運(yùn)用它來(lái)解決現(xiàn)實(shí)中出現(xiàn)的問(wèn)題并不適合。將聯(lián)盟花費(fèi)的概念引入，研究非超加性聯(lián)盟博弈更具現(xiàn)實(shí)意義。多數(shù)文章在研究合作博弈時(shí)，考慮如何令聯(lián)盟的結(jié)果有利于社會(huì)的發(fā)展（即找到最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)），很少研究聯(lián)盟利益分配的問(wèn)題。出于理性考慮，Agent組成聯(lián)盟的動(dòng)力就是獲得更大的利益，僅找到具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)，而不將利益公平地分配給聯(lián)盟的參與者是不合理的。在一些存在分配的研究中，大都采用夏普利值[3]作為分配方案，雖然這種方案具有公平性，但是產(chǎn)生的分配卻可能不滿足理性條件（Agent可能在聯(lián)盟中分得的利益小于自己?jiǎn)为?dú)工作的利益）。這違背了Agent聯(lián)盟的初衷，Agent將離開(kāi)聯(lián)盟，造成聯(lián)盟破裂，因此這種分配方案并不具有穩(wěn)定性和實(shí)用性。采用按勞分配作為初始分配方案將聯(lián)盟利益分配給聯(lián)盟中的每一位參與者，然后調(diào)整初始分配，使得聯(lián)盟中的Agent獲得最大利益，這樣得到的分配兼具理性和公平性。

在現(xiàn)實(shí)社會(huì)中聯(lián)盟的生成問(wèn)題是動(dòng)態(tài)的、持續(xù)的。事實(shí)上，舊聯(lián)盟的破裂與新聯(lián)盟的生成時(shí)刻都在發(fā)生，但是新舊間的替換并不是無(wú)跡可尋的。Agent組成聯(lián)盟的目的是追尋更大的利益，那么一定存在一個(gè)可以使大多數(shù)或全部Agent獲得最大利益的穩(wěn)定聯(lián)盟。然而，在現(xiàn)實(shí)中由于聯(lián)盟數(shù)目眾多，信息不明確等問(wèn)題，無(wú)法快速找到最優(yōu)的聯(lián)盟，只能一次次嘗試不同的聯(lián)盟。本文算法采用核、談判集、穩(wěn)定成本等概念，快速求解穩(wěn)定聯(lián)盟結(jié)構(gòu)和利益分配，可以保證大多數(shù)Agent獲得最大利益。相較于傳統(tǒng)聯(lián)盟博弈的研究，本文具有的特點(diǎn)和貢獻(xiàn)在于：

（1）在傳統(tǒng)生成聯(lián)盟的基礎(chǔ)上考慮了外部約束，采用圖形拓?fù)浣Y(jié)構(gòu)約束聯(lián)盟的生成，并且引入聯(lián)盟花費(fèi)的概念，使得生成的聯(lián)盟利益不再具有超加性，符合現(xiàn)實(shí)聯(lián)盟生成和利益的特點(diǎn)，更好地將合作博弈的理論應(yīng)用到實(shí)際領(lǐng)域中。

（2）采用按勞分配作為聯(lián)盟的初始利益，運(yùn)用談判集、穩(wěn)定成本作為初始利益調(diào)整方案，使得調(diào)整后的分配滿足核的定義，即使在合作博弈不滿足超加性的情況下，仍然滿足每個(gè)Agent的理性條件，保證聯(lián)盟的穩(wěn)定性。

（3）設(shè)計(jì)了有效的求解聯(lián)盟核算法，去除了不符合實(shí)際的聯(lián)盟的生成，降低了求解聯(lián)盟結(jié)構(gòu)核的時(shí)間，算法復(fù)雜度為O(3n)，相較于以往的時(shí)間復(fù)雜度為O(nn)的研究具有快速性[4]。

2 相關(guān)工作

本文將從聯(lián)盟生成、聯(lián)盟利益分配、聯(lián)盟穩(wěn)定性三方面，簡(jiǎn)要地描述圖聯(lián)盟收益分配的相關(guān)工作。

在傳統(tǒng)聯(lián)盟博弈理論中，假定大聯(lián)盟一定是最優(yōu)的，對(duì)于聯(lián)盟利益分配的研究也僅限于大聯(lián)盟之中。傳統(tǒng)理論對(duì)于大聯(lián)盟的利益分配問(wèn)題提供了多種方案，比如核[5]、夏普利值[3]、核仁[6]。最近，AI和MAS的研究人員一直在研究大聯(lián)盟形成的可能性，發(fā)現(xiàn)生成大聯(lián)盟存在多種限制，而且大聯(lián)盟可能不是最優(yōu)的聯(lián)盟結(jié)構(gòu)，反而多個(gè)小的聯(lián)盟組成的聯(lián)盟結(jié)構(gòu)具有更好的可實(shí)現(xiàn)性和最優(yōu)性。這個(gè)問(wèn)題也被稱為聯(lián)盟結(jié)構(gòu)生成（coalition structure generation，CSG）問(wèn)題，在AI和MAS上一直是一個(gè)活躍的研究課題[1]。關(guān)于帶有約束圖的聯(lián)盟博弈，Myerson在1976年就已經(jīng)提出[7]，但是只對(duì)它進(jìn)行了理論分析，并沒(méi)有利用它來(lái)解決實(shí)際問(wèn)題。最近Myerson的這篇文章由于其在自然領(lǐng)域的適用性，受到了越來(lái)越多的關(guān)注。例如Skibski等人將它應(yīng)用到了恐怖主義網(wǎng)絡(luò)的研究當(dāng)中[8-9]，Zhang等人分析了它在現(xiàn)實(shí)社會(huì)中的利益分配問(wèn)題[10]。利用約束圖作為聯(lián)盟生成的約束條件，剔除不切實(shí)際的聯(lián)盟，能夠降低算法的時(shí)間復(fù)雜度。Yeh首次提出了動(dòng)態(tài)規(guī)劃（dynamic programming，DP）算法[11]，并用來(lái)解決集合劃分問(wèn)題。徐廣斌等人基于DP算法求最優(yōu)聯(lián)盟的問(wèn)題，提出了聯(lián)盟約束動(dòng)態(tài)規(guī)劃（coalition constrain dynamic programming，CCDP）算法[12]。本文吸取Myerson的理論，采用簡(jiǎn)單的圖形拓?fù)潢P(guān)系模擬現(xiàn)實(shí)中的約束，并吸取CCDP算法動(dòng)態(tài)生成最優(yōu)聯(lián)盟的思想，改進(jìn)CCDP算法生成最優(yōu)聯(lián)盟結(jié)構(gòu)。

合作博弈最困難也最有挑戰(zhàn)性之處在于建立一個(gè)統(tǒng)一解（分配）的概念，即從各種各樣的具有不同良好性質(zhì)的解中挑選出唯一的配置。近年來(lái)，利用夏普利值進(jìn)行聯(lián)盟利益分配成為很多文章的分配選擇，這種方案最大的優(yōu)點(diǎn)就在于它的公平性[13]。若博弈具有超加性，夏普利值可以作為一個(gè)分配，且滿足理性約束條件φ(xi)≥v({i})，即Agent在聯(lián)盟中個(gè)人所得利益一定大于單獨(dú)工作的利益。但當(dāng)博弈不具有超加性時(shí)，夏普利值并不滿足理性約束條件。本文研究的圖聯(lián)盟博弈不具有超加性，因此夏普利值并不適用于本文的研究。本文將按勞分配[14]作為初始分配方案，將聯(lián)盟中每個(gè)Agent單獨(dú)工作時(shí)的獲利當(dāng)作它對(duì)聯(lián)盟收益的貢獻(xiàn)。根據(jù)每個(gè)Agent的貢獻(xiàn)按比例將聯(lián)盟利益分配給聯(lián)盟成員，得到的分配兼具理性和公平性。

聯(lián)盟博弈假定所有的Agent都是理性的，要使一個(gè)聯(lián)盟結(jié)構(gòu)具有穩(wěn)定性，必然要令聯(lián)盟結(jié)構(gòu)中所有聯(lián)盟都穩(wěn)定，這要求聯(lián)盟的成員在聯(lián)盟中獲取最大的利益。在現(xiàn)實(shí)中令聯(lián)盟達(dá)到穩(wěn)定十分困難，存在各種各樣的問(wèn)題。最近Sless等人對(duì)社會(huì)網(wǎng)絡(luò)的復(fù)雜性進(jìn)行了研究，發(fā)現(xiàn)如果尋找穩(wěn)定狀態(tài)，必須將所有聯(lián)盟利益和分配進(jìn)行對(duì)比，找出最優(yōu)的聯(lián)盟結(jié)構(gòu)及其利益分配。Sandholm等人在Sless的后續(xù)工作中，通過(guò)研究發(fā)現(xiàn)CSG問(wèn)題的復(fù)雜性在最壞情況下為O(nn)[15]。Rahwan等人為了降低問(wèn)題的時(shí)間復(fù)雜度，基于動(dòng)態(tài)規(guī)劃編寫(xiě)頂級(jí)算法，時(shí)間復(fù)雜度為O(3n)[4]，節(jié)省了大量的運(yùn)算時(shí)間。然而在他們提出的模型中，Agent可以任意地組成聯(lián)盟，而且并未對(duì)聯(lián)盟結(jié)構(gòu)進(jìn)行利益的分配。Chalkiadakis等人2016年發(fā)表在人工智能上的一篇文章中[2]，提出了以圖作為約束條件約束聯(lián)盟生成，并尋找穩(wěn)定分配的問(wèn)題，在這篇文章中發(fā)現(xiàn)，最穩(wěn)定的分配必然存在于具有最大利益的聯(lián)盟結(jié)構(gòu)中，并對(duì)它進(jìn)行證明，但是并沒(méi)有給出尋找穩(wěn)定分配的算法。核作為一個(gè)最早的穩(wěn)定分配概念，經(jīng)常被人們用在聯(lián)盟博弈中，從Breton等人的文章中了解到[16]，根據(jù)Scarf的引理[17]，如果聯(lián)盟博弈是超加性的，那么它的核一定不是空集，但是他們卻沒(méi)有提出一個(gè)有效的快速找核的算法。Demange在后續(xù)工作中不僅驗(yàn)證了超加性聯(lián)盟博弈具有非空的核，也驗(yàn)證了非超加性聯(lián)盟博弈也具有非空核，還提供了一個(gè)關(guān)于計(jì)算核的程序，但是Demange的算法并不能求得非超加性聯(lián)盟博弈的核。本文提出的SCP（stable core programming）算法可以求得超加性和非超加性的聯(lián)盟博弈的核，快速尋找具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)。

3 圖聯(lián)盟博弈與分配方案的相關(guān)定義

3.1 圖聯(lián)盟博弈的相關(guān)定義

本節(jié)主要通過(guò)介紹一些背景和相關(guān)符號(hào)來(lái)形式化框架。一個(gè)Agent集合N={1,2,…,n}，集合N的基為n，即|N|=n，用G=(N,E)表示一個(gè)由n個(gè)Agent組成的約束圖[18]。

定義1（約束圖）約束圖由一個(gè)二元組(N,E)組成，即G=(N,E)，N為圖中Agent的集合，E為圖中Agent間的通信關(guān)系，當(dāng)且僅當(dāng)E(x,y)=1時(shí)，Agentx和y可以組成聯(lián)盟。

將復(fù)雜的通信網(wǎng)絡(luò)圖劃分成簡(jiǎn)單的約束圖，其目的是簡(jiǎn)化社會(huì)通信網(wǎng)絡(luò)，降低圖中聯(lián)盟的數(shù)量，從而降低算法求解時(shí)間。而降低求解時(shí)間則是為了更快地刷新最優(yōu)聯(lián)盟結(jié)構(gòu)，規(guī)避聯(lián)盟博弈的動(dòng)態(tài)性和不穩(wěn)定性帶來(lái)的問(wèn)題。下面介紹幾種特殊的圖形拓?fù)浣Y(jié)構(gòu)。

零散圖（scattered graph），如圖2（a）所示，當(dāng)圖中包含的約束條件最多時(shí)，即圖中沒(méi)有任何兩個(gè)Agent間存在連接，禁止任何聯(lián)盟的生成，可行的聯(lián)盟個(gè)數(shù)為0，稱這種約束圖為零散圖。

完全圖（complete graph），如圖2（b）所示，當(dāng)G中存在的約束條件最少時(shí)，即所有Agent間都存在連接，任意兩個(gè)Agent都可以建立聯(lián)盟。若|N|=n，可生成的聯(lián)盟個(gè)數(shù)為2n-1，稱這種約束圖為完全圖。

鏈狀圖（chain graph），如圖2（c）所示，圖中包含的所有Agent通過(guò)一條線串聯(lián)起來(lái)形成一條通路，這種結(jié)構(gòu)具有的約束條件為：只有兩個(gè)臨近的Agent可以組成聯(lián)盟，但是兩個(gè)距離較遠(yuǎn)的Agent，可以通過(guò)它們之間所有的Agent作為“橋梁”構(gòu)建聯(lián)盟，若鏈狀圖中一個(gè)Agent出現(xiàn)問(wèn)題發(fā)生斷裂，不但發(fā)生斷裂的Agent無(wú)法與其相鄰的Agent組成聯(lián)盟，而且原來(lái)以它為“橋梁”的所有聯(lián)盟都無(wú)法生成，鏈狀圖中可行的聯(lián)盟個(gè)數(shù)為0.5(n2+n)。

星狀圖（star graph），如圖2（d）所示，圖中以一個(gè)Agent為中心，其他所有Agent能且只能與位于中心位置的Agent建立連接。處于中心位置的Agent是所有聯(lián)盟生成的核心Agent，任何聯(lián)盟的生成都需要核心Agent的加入，當(dāng)除了核心點(diǎn)外的其他Agent失去與核心Agent連接時(shí)，將只能選擇自己?jiǎn)为?dú)工作，無(wú)法加入任何聯(lián)盟。同樣，當(dāng)核心Agent消失，約束圖就變?yōu)榱闵D，星狀圖中可行的聯(lián)盟個(gè)數(shù)為n+2n-1-1。

Fig.2 Graph topology圖2 圖形拓?fù)浣Y(jié)構(gòu)

混合型拓?fù)浣Y(jié)構(gòu)（hybrid topology），就是含有兩種或兩種以上的拓?fù)浣Y(jié)構(gòu)同時(shí)使用的約束圖。

定義2（圖約束聯(lián)盟）若Agent集合N的非空子集C中的Agent在約束圖G中所誘導(dǎo)的子圖G[C]=1，稱C為圖約束聯(lián)盟，數(shù)學(xué)形式定義為：

在一個(gè)滿足約束圖約束條件的聯(lián)盟中，所有成員合作產(chǎn)生的回報(bào)（收益）為聯(lián)盟收益，賦值函數(shù)v:P(N)→R，其中P(N)表示集合N的冪集。例如v({1,2,3})=66，表示成員1、2、3組成聯(lián)盟 {1,2,3}所能產(chǎn)生的收益為66。

定義3（圖聯(lián)盟博弈）圖聯(lián)盟博弈是由N、v、G組成的三元組，即Γ={N,v,G}，其中N表示所有參與博弈的Agent形成的集合，v為每一個(gè)可行聯(lián)盟的收益，G代表圖聯(lián)盟博弈的約束圖。

定義4（聯(lián)盟結(jié)構(gòu)）在Γ={N,v,G}中，一個(gè)或數(shù)個(gè)互不相交的可行聯(lián)盟組成集合，若集合中包含所有的Agent，那么將此集合稱為聯(lián)盟結(jié)構(gòu)，并用符號(hào)Λ表示，其數(shù)學(xué)形式定義為：約束圖G上所有可行的聯(lián)盟結(jié)構(gòu)在下文中均用Cs(G)表示，可行的聯(lián)盟結(jié)構(gòu)應(yīng)滿足3個(gè)要求[19]：

（1）Λ中包含參與聯(lián)盟博弈的所有Agent，即滿足式子C1?C2?…?Ck=N。

（2）Λ中的聯(lián)盟為滿足約束圖G=(N,E)約束條件的可行聯(lián)盟。

（3）Λ中的任意兩個(gè)聯(lián)盟的交集為? ，即一個(gè)Agent只能加入一個(gè)聯(lián)盟。

定義5（社會(huì)福利）聯(lián)盟結(jié)構(gòu)Λ中所有聯(lián)盟Ci的聯(lián)盟收益之和稱為社會(huì)福利，并用符號(hào)Sw(Λ)表示，其數(shù)學(xué)形式化定義為：

在圖聯(lián)盟博弈Γ={N,v,G}中，最大社會(huì)福利用符號(hào)Swm(Γ)表示，Cs(G)中具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)用符號(hào)Cs*表示。

定義6（個(gè)人所得利益）聯(lián)盟C中的Agenti可以從聯(lián)盟利益v(C)中分得的利益稱為個(gè)人所得利益，用符號(hào)xi表示，并且xi滿足等式：

定義6保證了將v(C)無(wú)保留地分配給聯(lián)盟中的成員，因?yàn)槁?lián)盟C中單個(gè)Agent的個(gè)人所得利益之和等于v(C)且v(C)是一個(gè)定值，所以無(wú)法在不損害其他Agent的個(gè)人所得利益的情況下，單獨(dú)增加一個(gè)Agent的個(gè)人所得利益，因此定義6的定義滿足帕累托效率性（Pareto efficiency）。

為了更好地理解上述的定義，下面通過(guò)例1來(lái)進(jìn)行說(shuō)明。

例1給定圖聯(lián)盟博弈Γ={{1,2,3},v,G1}，假設(shè)參與博弈的用戶集合N={1,2,3}，約束圖為圖3所示的鏈狀圖，聯(lián)盟收益v滿足下列等式：

Fig.3 Chain graphG1圖3 鏈狀圖G1

根據(jù)聯(lián)盟結(jié)構(gòu)的定義4，可以尋得可行的聯(lián)盟結(jié)構(gòu)Cs(G)：

根據(jù)定義5，Sw(Λ)依次為18、14、20、18，Swm(Γ)=20，Cs*={1},{2,3}。

3.2 初始分配方案

本節(jié)主要介紹對(duì)于聯(lián)盟利益所采用的初始分配方案和方案特點(diǎn)，以及它相較于夏普利值的優(yōu)點(diǎn)。

本文選用按勞分配作為初始分配方案[14]，簡(jiǎn)單來(lái)說(shuō)，按勞分配就是將每一個(gè)Agent單獨(dú)工作所能獲得的利益，看作他們?cè)诼?lián)盟中所能做出的貢獻(xiàn)，然后根據(jù)每一個(gè)Agent的貢獻(xiàn)值，公平地將聯(lián)盟利益分配給聯(lián)盟的參與者。對(duì)聯(lián)盟利益進(jìn)行初始分配是調(diào)整分配得到穩(wěn)定分配的基礎(chǔ)。

定義7（按勞分配）在圖聯(lián)盟博弈Γ={N,v,G}中，按照單個(gè)Agent所提供給聯(lián)盟C的貢獻(xiàn)量分配聯(lián)盟利益v(C)，單個(gè)Agenti在聯(lián)盟C中可獲得的個(gè)人所得利益xi滿足等式：

采用夏普利值作為分配方案，就是根據(jù)Agent的邊際貢獻(xiàn)（Agent每可以加入一個(gè)聯(lián)盟，均產(chǎn)生收益）計(jì)算每個(gè)Agent應(yīng)得的利益，分配結(jié)果滿足匿名性、有效性、可加性和虛擬性的特點(diǎn)。本文研究的圖聯(lián)盟博弈Γ={N,v,G}不具有超可加性。若采用夏普利值作為分配方案將聯(lián)盟利益分配給單個(gè)Agent，得到的分配結(jié)果可能并不是一個(gè)分配，即不滿足理性約束條件φ(xi)≥v({i})。當(dāng)處在聯(lián)盟狀態(tài)的Agenti個(gè)人所得利益xi小于自己?jiǎn)为?dú)工作所獲得利益v({i})時(shí)，Agenti會(huì)選擇脫離聯(lián)盟，單獨(dú)工作或加入其他聯(lián)盟，破壞原有聯(lián)盟結(jié)構(gòu)的穩(wěn)定性，形成新的聯(lián)盟結(jié)構(gòu)。因此夏普利值對(duì)于本文研究的圖聯(lián)盟博弈并不適用。

如下的例2，利用按勞分配將聯(lián)盟利益分配給單個(gè)Agent，給出了按勞分配的分配特點(diǎn)。

例2給定圖聯(lián)盟博弈Γ={{1,2,3},v,G2}，假設(shè)參與博弈的用戶集合N={1,2,3}，約束圖為圖4所示的鏈狀圖，聯(lián)盟收益v滿足下列等式：

Fig.4 Chain graphG2圖4 鏈狀圖G2

根據(jù)聯(lián)盟結(jié)構(gòu)的定義4，可以尋得可行的聯(lián)盟結(jié)構(gòu)Cs(G)：

根據(jù)定義5，Sw(Λ)依次為 23、33、20、24,Swm(Γ)=33，Cs*={1,3},{2}。

根據(jù)按勞分配的定義7，對(duì)聯(lián)盟結(jié)構(gòu)Λ依次進(jìn)行初始利益分配：

4 穩(wěn)定分析和初始分配調(diào)整方案

以下分析了穩(wěn)定的聯(lián)盟結(jié)構(gòu)及分配所具有的特點(diǎn)，并發(fā)現(xiàn)采用按勞分配方案產(chǎn)生的分配結(jié)果可能是不穩(wěn)定的。為了使聯(lián)盟穩(wěn)定往往需要滿足每一個(gè)Agent的理性要求，但很多時(shí)候，由于聯(lián)盟利益的限制，該要求是無(wú)法實(shí)現(xiàn)的，這使得尋找穩(wěn)定分配具有復(fù)雜性。本文將分析復(fù)雜性并提出相應(yīng)的分配調(diào)整方案，使得最終分配結(jié)果具有穩(wěn)定性。

4.1 穩(wěn)定分析

在Chalkiadakis等人的研究中發(fā)現(xiàn)，穩(wěn)定的分配必然存在于具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)內(nèi)[2]，因此尋找的穩(wěn)定聯(lián)盟結(jié)構(gòu)就是具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*。若Cs*中處于聯(lián)盟狀態(tài)的Agent，均可以在Cs*中同時(shí)獲得自身的最大期望利益，那么分配具有穩(wěn)定性，這樣的分配滿足核的定義，因此將核的概念引入，將核作為主要考慮的穩(wěn)定因素，定義它為實(shí)現(xiàn)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)及其分配。

定義8（核）在圖聯(lián)盟博弈Γ={N,v,G}中，Λ∈Cs*，xi∈Λ，對(duì)于任意一個(gè)聯(lián)盟結(jié)構(gòu)Λ∈Cs(G)，都有x(C)≥v(C)，稱(Λ,(xi))為聯(lián)盟結(jié)構(gòu)的核，其數(shù)學(xué)形式定義為：

需要說(shuō)明的是核有可能是空的，當(dāng)聯(lián)盟結(jié)構(gòu)中所有處于聯(lián)盟狀態(tài)的Agent可獲得的最大期望利益之和大于最大社會(huì)福利時(shí)，核為空。

通過(guò)一個(gè)簡(jiǎn)單的例3來(lái)表述核的定義。

例3給定圖聯(lián)盟博弈Γ={{1,2,3},v,G1}，假設(shè)參與博弈的用戶集合N={1,2,3}，約束圖為圖3所示的鏈狀圖，聯(lián)盟收益v滿足下列等式：

根據(jù)聯(lián)盟結(jié)構(gòu)的定義4，可以尋得可行的聯(lián)盟結(jié)構(gòu)Cs(G)：

根據(jù)定義5，Sw(Λ)依次為 24、22、34、20,Swm(Γ)=34，Cs*={1},{2,3}。

根據(jù)按勞分配的定義7，對(duì)聯(lián)盟結(jié)構(gòu)Λ依次進(jìn)行初始利益分配：

聯(lián)盟結(jié)構(gòu) {1},{2,3}為實(shí)現(xiàn)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*，并且在此聯(lián)盟結(jié)構(gòu)中，所有處于聯(lián)盟狀態(tài)的Agent均獲得了最大期望利益，因此({1},{2,3},(4,12,18))滿足定義8，是聯(lián)盟博弈的核，Cs-core(Γ)=({1},{2,3},(4,12,18))。

然而在實(shí)際應(yīng)用中往往不會(huì)和例3一樣，Cs*的初始分配結(jié)果正好滿足核的定義，會(huì)出現(xiàn)以下3種情況：

（1）具有多個(gè)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*，即具有多個(gè)互不相同的聯(lián)盟結(jié)構(gòu)Λ，它們的社會(huì)福利均為最大社會(huì)福利Swm(Γ)。

（2）利用按勞分配作為初始分配方案，得到分配結(jié)果可能不是最優(yōu)的，即存在個(gè)別處于聯(lián)盟狀態(tài)的Agent獲利小于其他形式的聯(lián)盟，不滿足核的定義。

（3）無(wú)法令所有處于聯(lián)盟狀態(tài)的Agent同時(shí)獲得最大利益，即核為空的情況。

4.2 解決方案

本節(jié)根據(jù)4.1節(jié)中可能發(fā)生的3種情況，提出了對(duì)應(yīng)的解決方案，并用實(shí)例驗(yàn)證了方案的可行性。

情況（1）具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)有多個(gè)，提出次穩(wěn)定聯(lián)盟結(jié)構(gòu)Λ*的定義，在多個(gè)具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*中，尋找最優(yōu)的聯(lián)盟結(jié)構(gòu)作為次穩(wěn)定聯(lián)盟結(jié)構(gòu)Λ*。在現(xiàn)實(shí)博弈中，可以令多數(shù)Agent同時(shí)獲得最大利益的聯(lián)盟結(jié)構(gòu)才更加具有穩(wěn)定性，因此選取令多數(shù)Agent獲得最大利益的Cs*作為Λ*。

定義9（次穩(wěn)定聯(lián)盟結(jié)構(gòu)）假設(shè)圖聯(lián)盟博弈Γ={N,v,G}存在多個(gè)Cs*，選取多數(shù)Agent獲得最大利益的聯(lián)盟結(jié)構(gòu)Λ作為Λ*，并用符號(hào)Λ*表示。

若次穩(wěn)定結(jié)構(gòu)Λ*及其分配滿足定義8，那么稱(Λ*,(xi))為次穩(wěn)定核，用符號(hào)Cs-score(Γ)表示，Csscore(Γ)=(Λ*,(xi))。

例4給出了次穩(wěn)定聯(lián)盟結(jié)構(gòu)的應(yīng)用。

例4給定圖聯(lián)盟博弈Γ={{1,2,3},v,G1}，假設(shè)參與博弈的用戶集合N={1,2,3}，約束圖為圖3所示的鏈狀圖，聯(lián)盟收益v滿足下列等式：

根據(jù)聯(lián)盟結(jié)構(gòu)的定義4，可以尋得可行的聯(lián)盟結(jié)構(gòu)Cs(G)：

根據(jù)定義5，Sw(Λ)依次為35、40、40、40，Swm(Γ)=34，發(fā)現(xiàn)具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)的個(gè)數(shù)為3，且它們的利益分配結(jié)構(gòu)依次為：

(9.3,10.7,20);(7,9.4,23.6);(8,9.1,22.9)

通過(guò)比較初始利益分配的結(jié)果，發(fā)現(xiàn)在聯(lián)盟結(jié)構(gòu) {1},{2,3}中x2、x3同時(shí)取得自身利益最大值9.4和23.6，即用戶2、3同時(shí)獲得自身最大利益，獲得最大利益的Agent個(gè)數(shù)最多。根據(jù)次穩(wěn)定核的定義9，選多數(shù)Agent獲得最大利益的聯(lián)盟結(jié)構(gòu) {1},{2,3}作為Λ*，當(dāng)用戶1想要破壞聯(lián)盟{(lán)2,3}的穩(wěn)定性時(shí)，用戶2、3出于理性考慮，不會(huì)放棄最大利益離開(kāi)原聯(lián)盟。因此聯(lián)盟結(jié)構(gòu) {1},{2,3}具有穩(wěn)定性，并且Λ*及其初始分配(7,9.4,23.6)滿足核的定義，Cs-core(Γ)=({1,2},{3},(9.3,10.7,20))。

情況（2）使用按勞分配方案得到的初始分配結(jié)果不是最優(yōu)的，引入談判集的概念調(diào)整初始分配，得到一個(gè)令所有Agent都滿意的分配，并且這個(gè)分配滿足核的定義。

定義10（談判集）若C∈Cs*，i∈C，Agenti在Cs*中獲取的利益xi小于Agenti在其他聯(lián)盟中的利益，它可以向聯(lián)盟C發(fā)出異議，要求重新劃分利益，增加自身利益至期望值，其他Agent考慮是否接受，商量出一個(gè)可行的分配結(jié)果。

談判集（bargaining set）最早是由Aumann等人于1964年提出的[20]，它是根據(jù)局中人之間可能出現(xiàn)的互相談判而提出的合作博弈的解的概念，聯(lián)盟C中的參與人i向聯(lián)盟中其他參與人j提出異議，要求偏離現(xiàn)有的配置x，如果符合條件y(C)=v(C),yk＞xk,?k∈S，其中S∈Γij≡ {C∈2N|i∈C,j?C},y=(yk)k∈S，那么這種威脅就是可行的。參與人i提出異議的目的并不是阻止達(dá)成合作，而是希望能夠從參與人j處得到轉(zhuǎn)移利益（transfer of money），即在可行集內(nèi)部改變財(cái)富的分配。

設(shè)置談判的上下限均為Agent的最大利益期望，即相比于其他聯(lián)盟，發(fā)起異議的Agent只能提出增大自身利益至最大利益期望的要求，接受異議的Agent只有在轉(zhuǎn)移自身利益后，剩余利益依然滿足自身的最大利益期望時(shí)，才會(huì)接受劃分自身利益，談判才能成功，接受異議的Agent將自身利益作為轉(zhuǎn)移利益分給提出異議的Agent完成談判。

例5給出了談判集的應(yīng)用。

例5給定圖聯(lián)盟博弈Γ={{1,2,3},v,G1}，假設(shè)參與博弈的用戶集合N={1,2,3}，約束圖為圖3所示的鏈狀圖，聯(lián)盟收益v滿足下列等式：

根據(jù)聯(lián)盟結(jié)構(gòu)的定義4，可以尋得可行的聯(lián)盟結(jié)構(gòu)Cs(G)：

根據(jù)定義5，Sw(Λ)依次為16、24、31、20，Swm(Γ)=31，Cs*={1},{2,3} 。

根據(jù)按勞分配的定義7，對(duì)聯(lián)盟結(jié)構(gòu)Λ依次進(jìn)行初始利益分配：

由上式可以看出在聯(lián)盟結(jié)構(gòu){1,{2,3}}中用戶2的個(gè)人所得利益x2為5，而在Cs*中x2為1，這樣的初始分配結(jié)果，用戶2是無(wú)法接受的，破環(huán)Cs*的穩(wěn)定性。根據(jù)談判集的定義，用戶2發(fā)現(xiàn)在聯(lián)盟{(lán)2,3}中的利益小于在聯(lián)盟{(lán)1,2}中的利益，向聯(lián)盟{(lán)2,3}發(fā)出異議，聯(lián)盟中的其他成員判斷是否接受異議，并將自己的利益作為轉(zhuǎn)移利益分與成員2，C即使分3個(gè)利益點(diǎn)給成員2，增加成員2的個(gè)人所得利益x2至最大值5，成員3依然在聯(lián)盟{(lán)2,3}中取得自身的最大利益25，因此談判成功。初始分配調(diào)整后為(1,5,25)，調(diào)整后的分配結(jié)果滿足核的定義，Cs-core(Γ)=({1},{2,3},(1,5,25))。

情況（3）無(wú)法令所有處于聯(lián)盟狀態(tài)的Agent同時(shí)獲得最大利益，即核為空，盡管Cs*具有最大社會(huì)福利Swm(Γ)，也可能發(fā)生所有處于聯(lián)盟狀態(tài)的Agent無(wú)法同時(shí)獲得最大利益的情況。對(duì)于這種情況，次穩(wěn)定結(jié)構(gòu)Λ*，談判集無(wú)法令一個(gè)核為空的博弈存在核，而穩(wěn)定成本則可以解決這個(gè)問(wèn)題。

定義11（穩(wěn)定成本）若圖聯(lián)盟博弈Γ={N,v,G}的核為空，向Cs*中不穩(wěn)定的聯(lián)盟利益v(C)加一個(gè)最小的Δ，令聯(lián)盟博弈的核不為空，那么稱這個(gè)Δ為穩(wěn)定成本，具有穩(wěn)定成本的核用符號(hào)Cs-core(ΓΔ)表示，其數(shù)學(xué)形式化表示為：

穩(wěn)定成本從聯(lián)盟博弈外部條件考慮，向外部環(huán)境借用最少的利益Δ，使聯(lián)盟內(nèi)部的成員都可以獲得最大利益，Δ能夠保證圖聯(lián)盟結(jié)構(gòu)具有非空核[21]。這里說(shuō)的外部環(huán)境具有多樣性，可以簡(jiǎn)單地將這個(gè)外部環(huán)境考慮為上層調(diào)控。

例6給出了穩(wěn)定成本Δ的應(yīng)用。

例6給定圖聯(lián)盟博弈Γ={{1,2,3,4},v,G3}，假設(shè)參與博弈的用戶集合N={1,2,3,4}，約束圖為圖5所示的混合拓?fù)浣Y(jié)構(gòu)，聯(lián)盟收益v滿足下列等式：

Fig.5 Hybrid topologyG3圖5 混合拓?fù)浣Y(jié)構(gòu)G3

通過(guò)計(jì)算可以求得Swm(Γ)=8.2，Cs*={1,2,3},{4}。對(duì)部分有特點(diǎn)的聯(lián)盟結(jié)構(gòu)Λ進(jìn)行利益分配可得：

從上述特殊的分配中發(fā)現(xiàn)，Cs*中處于聯(lián)盟狀態(tài)的用戶1、2、3可以獲得的最大利益均為2.5。但是聯(lián)盟利益v({1,2,3})=7.2，不能同時(shí)令所有用戶都獲得最大利益，圖聯(lián)盟博弈的核為空，根據(jù)穩(wěn)定成本定義有：

5 構(gòu)造圖聯(lián)盟結(jié)構(gòu)核的算法

下面介紹構(gòu)造圖聯(lián)盟博弈穩(wěn)定核的SCP算法，該算法在構(gòu)造圖聯(lián)盟博弈穩(wěn)定核時(shí)，可以分為兩部分：

第一部分的輸入為圖聯(lián)盟博弈Γ={N,v,G}，輸出為最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*及其初始分配B[Cs*]和每個(gè)Agent可獲得最大利益的數(shù)組S[N]。此部分在構(gòu)造Cs*和B[Cs*]時(shí)，不但吸收CCDP算法的最優(yōu)子結(jié)構(gòu)和子問(wèn)題重疊的性質(zhì)[12]，并以此為基礎(chǔ)加入利益分配，對(duì)可行的每個(gè)聯(lián)盟進(jìn)行初始分配，生成每個(gè)Agent可獲得的最大利益數(shù)組S[N]。

第二部分的輸入為第一部分的輸出，輸出為滿足定義8的聯(lián)盟結(jié)構(gòu)核。這部分對(duì)第一部分得到的初始分配B[Cs*]和S[N]進(jìn)行分析，并根據(jù)4.2節(jié)提供的解決方案，調(diào)整初始分配B[Cs*]，最終找到Cs*的穩(wěn)定分配并形成核。這兩部分分別在5.1節(jié)、5.2節(jié)中詳細(xì)描述。綜合以上兩部分，SCP算法的輸入是圖聯(lián)盟博弈Γ={N,v,G}，輸出是聯(lián)盟結(jié)構(gòu)核，即具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*及其穩(wěn)定分配。該算法的形式化描述如算法1所示。

算法1構(gòu)造圖聯(lián)盟結(jié)構(gòu)核算法

輸入：圖聯(lián)盟博弈Γ={N,v,G}。

輸出：圖聯(lián)盟結(jié)構(gòu)核。

//Step1調(diào)用算法2，構(gòu)造最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*，初始分配B[Cs*]，每個(gè)Agent可獲得最大利益數(shù)組S[N]。

調(diào)用算法2；

//Step2調(diào)用算法3，采用定義11判斷核是否為空，計(jì)算穩(wěn)定成本，采用定義9尋找次穩(wěn)定結(jié)構(gòu)，采用定義10調(diào)整B[Cs*]。

調(diào)用算法3；

5.1 構(gòu)造最優(yōu)聯(lián)盟結(jié)構(gòu)Cs*及其初始分配B[Cs*]的算法

算法2首先根據(jù)圖G生成N={1,2,…,n}，所有可行的子集組成集合Z，根據(jù)生成子集所包含的Agent個(gè)數(shù)m，將子集分為L(zhǎng)m層，求解每層每個(gè)聯(lián)盟C的優(yōu)結(jié)構(gòu)M[C]、優(yōu)值F[C]、分配B[C]。Ln層為包含所有Agent的大聯(lián)盟，Ln層生成的優(yōu)結(jié)構(gòu)為Cs*，優(yōu)值為Swm(Γ)，分配給Cs*的初始分配為B[Cs*]，最后從各個(gè)聯(lián)盟的初始分配中，找到每一個(gè)Agent可獲得的最大利益，組成最大利益數(shù)組S[N]。

算法2生成聯(lián)盟結(jié)構(gòu)及其初始分配算法

輸入：圖聯(lián)盟博弈Γ={N,v,G}。

輸出：具有最大社會(huì)福利聯(lián)盟結(jié)構(gòu)，初始分配，最大利益數(shù)組。

//Step1根據(jù)輸入中給定的N、v、G,生成滿足G約束的聯(lián)盟C，根據(jù)|C|將生成的聯(lián)盟分為L(zhǎng)n層，m≤n，并初始化聯(lián)盟值v(C)，設(shè)置優(yōu)值F[C]，優(yōu)結(jié)構(gòu)M[C]，初始利益分配B[C]。

//Step2求出每層每個(gè)聯(lián)盟的優(yōu)結(jié)構(gòu)M[C]，調(diào)整優(yōu)值F[C]，初始分配B[Cs*]。

下面對(duì)算法2進(jìn)行詳細(xì)描述，在圖聯(lián)盟博弈Γ={N,v,G}中，集合的基|N|=n，滿足圖G約束的所有可行子集組成的集合為Z，聯(lián)盟C中含有的Agent個(gè)數(shù)為m，n≥m，聯(lián)盟的優(yōu)結(jié)構(gòu)為M[C]，優(yōu)值為F[C]，聯(lián)盟的初始分配為B[C]，最大利益數(shù)組為S[N]。

步驟1對(duì)算法進(jìn)行初始化，輸入圖聯(lián)盟博弈Γ={N,v,G}，即輸入?yún)⑴c聯(lián)盟博弈的Agent組成的集合N，對(duì)聯(lián)盟生成存在約束的約束圖G，和滿足圖G約束的聯(lián)盟利益v，生成滿足圖G約束的所有聯(lián)盟C，以聯(lián)盟C的基|C|=m為分層條件，將所有可行聯(lián)盟分為L(zhǎng)m層，對(duì)每層每個(gè)聯(lián)盟的參數(shù)初始賦值，優(yōu)值F[C]初始賦值為v(C)，優(yōu)結(jié)構(gòu)M[C]初始賦值為聯(lián)盟C，初始分配B[C]初始賦值為 ({v{1},v{2},…,v{n}},i∈C)，以上過(guò)程如算法2的Step1所示。

步驟2通過(guò)自上向下的方式搜索聯(lián)盟結(jié)構(gòu)，即從第一層向下層逐層求出每層每個(gè)聯(lián)盟C的優(yōu)結(jié)構(gòu)M[C]，優(yōu)值F[C]，并采用按勞分配對(duì)聯(lián)盟C進(jìn)行初始利益分配，得到聯(lián)盟C的初始分配B[C]，將分配結(jié)果(x1,x2,…,xn,xi∈C)存入B[C]。從L2層到Ln層依次搜索計(jì)算：比較給出的聯(lián)盟利益F[C]和劃分成兩個(gè)劃分塊的利益F[C-C′]+F[C′]，這里C′?C,C′∈Z,CC′∈Z,|C′|≤ 0.5m。如果F[C-C′]+F[C′]＞F[C]，即劃分成兩個(gè)劃分塊的聯(lián)盟利益和大于聯(lián)盟C的初始利益，那么優(yōu)值F[C]=F[C-C′]+F[C′]，優(yōu)結(jié)構(gòu)M[C]={CC′,C′}，如果F[C]＞F[C-C′]+F[C′]，即聯(lián)盟C初始利益大于劃分成兩個(gè)劃分塊的聯(lián)盟值時(shí)，那么優(yōu)值F[C]=F[C]，優(yōu)結(jié)構(gòu)M[C]=C；如果F[C-C′]+F[C′]=F[C]，即聯(lián)盟初始值等于劃分成兩個(gè)劃分塊的聯(lián)盟值，那么優(yōu)值F[C]=F[C]，優(yōu)結(jié)構(gòu)M1[C]=C,M2[C]={C-C′,C′}，即通過(guò)公式F[C]=max{F[C],F[C-C′]+F[C′]}，尋找聯(lián)盟C的最優(yōu)結(jié)構(gòu)M[C]、F[C]。根據(jù)式（5）將聯(lián)盟優(yōu)值F[C]分配給優(yōu)結(jié)構(gòu)M[C]中的Agent，并將初始分配(x1,x2,…,xn,i∈C)存入B[C]。以上過(guò)程如算法2的Step2所示。

步驟3自頂向下構(gòu)造具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)Cs*及其初始分配B[Cs*]，搜索包含Agenti的所有B[Cs*]，選取B[C]中Agenti可獲得的最大個(gè)人利益xi存入集合S[N]。首先對(duì)Cs*初始賦值，將Ln層的優(yōu)結(jié)構(gòu)M[C]作為初始值賦予Cs*，若M[C]的個(gè)數(shù)P=1，則Cs*=M[C]，若C∈Cs*且聯(lián)盟M[C]≠C，則Cs*={(Cs*-C)?M[C]}。搜索Cs*中包含的聯(lián)盟C，將聯(lián)盟C的初始分配方案B[C]存入B[Cs*]，生成所有B[Cs*]，若M[C]的個(gè)數(shù)P大于1，則生成多個(gè)Cs*，重復(fù)上述P=1的步驟，生成多個(gè)Cs*和B[Cs*]，然后搜索每層B[Cs*]，將每個(gè)Agent在所有初始分配B[C]中可獲得的最大利益存入S[N]。以上過(guò)程如算法2的Step3所示。

5.2 生成穩(wěn)定聯(lián)盟結(jié)構(gòu)的算法

本節(jié)對(duì)SCP算法第二部分——生成聯(lián)盟核算法進(jìn)行詳細(xì)的描述。算法的輸入為算法2的返回值Cs*、B[Cs*]、S[N]，輸出為圖聯(lián)盟結(jié)構(gòu)的核。算法根據(jù)輸入，分析Cs*、B[Cs*]屬于4.1節(jié)的何種問(wèn)題，并通過(guò)4.2節(jié)的解決方案生成核。

算法3生成聯(lián)盟結(jié)構(gòu)核算法

輸入：Cs*、B[Cs*]、S[N]。

輸出：聯(lián)盟結(jié)構(gòu)核。

//Step1利用次穩(wěn)定結(jié)構(gòu)概念優(yōu)化的Cs*個(gè)數(shù)，得到唯一的操作對(duì)象core*。

//Step2運(yùn)用穩(wěn)定成本和談判集的概念尋找聯(lián)盟博弈的穩(wěn)定結(jié)構(gòu)及其分配。

步驟1判斷輸入的Cs*的個(gè)數(shù)P是否為1，若為1，將Cs*及其初始分配B[Cs*]賦予core*，即core*=(Cs*,(B[Cs*]))，若P≠1，則采用次穩(wěn)定結(jié)構(gòu)的概念得到次穩(wěn)定結(jié)構(gòu)Λ*，并將次穩(wěn)定結(jié)構(gòu)及其分配賦予core*，core*=(Λ*,(B[Λ*]))。以上過(guò)程如算法3的Step1所示。

步驟2選取core*中的所有聯(lián)盟C，判斷聯(lián)盟收益v(C)與聯(lián)盟C中Agent的最大利益加和的大小。若v(C)小，說(shuō)明核為空，采用穩(wěn)定成本的概念，計(jì)算穩(wěn)定成本Δ，并將穩(wěn)定成本分配給core*中的xi，使聯(lián)盟C中所有Agent獲得最大個(gè)人所得利益，core*中的B[Cs*]經(jīng)過(guò)調(diào)整后滿足核的定義；若v(C)大，那么判斷聯(lián)盟C中的Agent是否全部獲得了最大利益，若是，core*滿足核的定義，若不是采用談判集的概念，調(diào)整初始分配B[Cs*]，直到所有處于聯(lián)盟狀態(tài)的Agent在Cs*中獲得最大利益，core*滿足核的定義。最后判斷輸出核的類型：若Δ≠0且P≠1，返回Csscore(ΓΔ)←core*；若只有Δ≠ 0，則返回Cs-core(ΓΔ)←core*；若只有P≠ 1，則返回Cs-score(Γ)←core*；若Δ=0且P=1，返回Cs-score(Γ)←core*。以上過(guò)程如算法3的Step2所示。

5.3 算法求解過(guò)程實(shí)例

例7存在圖聯(lián)盟博弈Γ={{1,2,3,4},v,G4}，|N|=5，約束圖為圖6所示的星型圖G4，聯(lián)盟利益為v（表1中第3列下劃線標(biāo)記）。下面根據(jù)算法步驟生成圖聯(lián)盟結(jié)構(gòu)核。

Fig.6 Star graphG4圖6 星狀圖G4

生成最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)及其初始分配算法。表1用表格的形式表現(xiàn)此算法的求解過(guò)程。

步驟1輸入圖聯(lián)盟博弈Γ={N,v,G4}，輸入的聯(lián)盟和聯(lián)盟利益在表1中由下橫線標(biāo)出，根據(jù)聯(lián)盟的基，|N|=5將聯(lián)盟分為L(zhǎng)5層。初始化算法：分別設(shè)置每層每個(gè)聯(lián)盟C的優(yōu)值F[C]、最優(yōu)結(jié)構(gòu)M[C]、聯(lián)盟初始分配B[C]。

步驟2由L1向L5層分別求出每一層每一個(gè)聯(lián)盟C的M[C]、F[C]、B[C]，并根據(jù)式（5）求得每一個(gè)可行聯(lián)盟的初始分配B[C]。表1給出了SCP算法這兩步具體的求解過(guò)程。

步驟3構(gòu)造Cs*、B[Cs*]、S[N]，表1中L5層得到了兩個(gè)實(shí)現(xiàn)最大福利的聯(lián)盟結(jié)構(gòu)Cs*，分別為 {1},{2,3,4,5}和 {2},{1,3,4,5}，最大社會(huì)福利Swm(Γ)=125，具有最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)的個(gè)數(shù)P=2，初始分配B[Cs*]分別為(20,16.6,33.2,44.2,11)和(22,15,33,44,11)。搜索每層每個(gè)聯(lián)盟C的初始分配B[C]，將每個(gè)Agent在所有初始分配B[C]中可獲得的最大利益存入S[N]，S[N]=[22,16.6,33.2,44.2,11]。最后輸出求得的Cs*、B[Cs*]、S[N]。

生成穩(wěn)定聯(lián)盟核算法。表2用表格的形式表現(xiàn)此算法的求解過(guò)程。

步驟1輸入算法 2 求得的Cs*、B[Cs*]、S[N]，因?yàn)閷?shí)現(xiàn)最大福利的聯(lián)盟結(jié)構(gòu)Cs*的個(gè)數(shù)P為2，采用次穩(wěn)定核的概念，在兩個(gè)聯(lián)盟結(jié)構(gòu) {1},{2,3,4,5}、{2},{1,3,4,5}中，選取令多數(shù)Agent獲得最大利益的 {1},{2,3,4,5} 作為Λ*，并將 {1},{2,3,4,5}，(20,16.6,33.2,44.2,11)賦予core*。

步驟2選取core*中聯(lián)盟C(聯(lián)盟C中包含的Agent的數(shù)量大于1)，發(fā)現(xiàn)core*中的聯(lián)盟C均滿足公式，因此不需要穩(wěn)定成本來(lái)調(diào)節(jié)，Δ=0。對(duì)比core*中處于聯(lián)盟狀態(tài)的Agent所獲得的分配(16.6，33.2，44.2，11)與S[N]中Agent最大利益期望[16.3,33.2,44.2,11]，可知core*中Agent均已獲得了自身的最大利益，滿足核的定義，因?yàn)镻=2，Δ=0，所以輸出Cs-score(Γ)=({1},{2,3,4,5},(20,16.3,33.2,44.2,11))。

Cs-score(Γ)包含兩個(gè)聯(lián)盟，其中{1}為單個(gè)用戶，因此用戶1只能獲得初始利益20，聯(lián)盟{(lán)2,3,4,5}包含4個(gè)用戶，利益分配為(16.6，33.2，44.2，11)，并且聯(lián)盟中的所有Agent可以在聯(lián)盟中獲得自身的最大利益，因此結(jié)果是穩(wěn)定的。

Table 1 Generation process ofCs*and initial allocation under constraints of star graph表1 星狀圖約束下的最優(yōu)聯(lián)盟結(jié)構(gòu)Cs*及其初始分配生成過(guò)程

Table 2 Generation process of coalition structure core表2 生成穩(wěn)定聯(lián)盟結(jié)構(gòu)核的算法求解過(guò)程

6 算法的性質(zhì)分析

下面對(duì)生成聯(lián)盟博弈核的SCP算法在時(shí)間復(fù)雜度、正確性方面進(jìn)行分析。算法的時(shí)間復(fù)雜度是衡量算法效率的基本要素；算法的正確性則主要刻畫(huà)若進(jìn)程能夠按照所設(shè)計(jì)的算法來(lái)執(zhí)行，其得到的運(yùn)行結(jié)果一定是正確的。

6.1 算法時(shí)間復(fù)雜度分析

定理1（二項(xiàng)式定理）令n為一個(gè)正整數(shù)，且所有的x、y滿足：

定理2SCP算法在最壞情況下的時(shí)間復(fù)雜度為O(3n)。

證明最壞情況下，圖聯(lián)盟博弈約束圖Γ={N,v,G}為完全圖，不限制任意聯(lián)盟的生成，因此可行聯(lián)盟的個(gè)數(shù)為2n-1，將可行的聯(lián)盟根據(jù)聯(lián)盟的基分為L(zhǎng)n層。Agent形成聯(lián)盟時(shí)，依次取m個(gè)Agent組成小聯(lián)盟C，從n個(gè)Agent中取m個(gè)的方法有種，將m個(gè)Agent分成兩組的劃分方法有2m-1-1種，需要搜索的次數(shù)用二項(xiàng)式表示為：

根據(jù)以上分析，SCP算法在求解聯(lián)盟核時(shí)算法時(shí)間復(fù)雜度在最壞的情況下為O(3n)。

6.2 算法的正確性分析

定理3將聯(lián)盟利益全部分給博弈的參與者，并且Agent在聯(lián)盟中的個(gè)人所得利益滿足理性條件，只有同時(shí)滿足上述條件的聯(lián)盟才是穩(wěn)定的[16]。

證明假設(shè)聯(lián)盟C中滿足式子，或存在Agent在其他聯(lián)盟D獲得比聯(lián)盟C更大的利益，那么Agent會(huì)選擇離開(kāi)聯(lián)盟單獨(dú)工作，或加入聯(lián)盟D來(lái)最大化自身利益，這樣聯(lián)盟C是不穩(wěn)定的，進(jìn)而造成聯(lián)盟結(jié)構(gòu)的不穩(wěn)定，假設(shè)錯(cuò)誤，定理成立。

定理4存在圖聯(lián)盟博弈Γ={N,v,G}，其穩(wěn)定的分配一定存在于實(shí)現(xiàn)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)中。

證明存在聯(lián)盟博弈Γ={N,v,G}，假設(shè)有聯(lián)盟結(jié)構(gòu)核 (Λ,xi)，Λ∈Cs*，xi∈Λ，對(duì)于任意一個(gè)可行的聯(lián)盟結(jié)構(gòu)Λ′∈Cs(G)和任何一個(gè)x′i∈Λ′，從每個(gè)Agent的理性考慮，當(dāng)xi≥x′i時(shí)，才是穩(wěn)定的分配。因?yàn)棣械穆?lián)盟是互不相交的而且完全覆蓋N，得到式子Sw(Λ)=，所以Sw(Λ)＞Sw(Λ′)。綜上所述，其穩(wěn)定的分配一定存在于實(shí)現(xiàn)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)中。

定理5正確性：SCP算法求解出的核一定具有穩(wěn)定性。

證明SCP算法解出每層最優(yōu)的聯(lián)盟結(jié)構(gòu)，并根據(jù)按勞分配方案得到初始分配，通過(guò)自頂向下的方式構(gòu)造實(shí)現(xiàn)最大社會(huì)福利的聯(lián)盟結(jié)構(gòu)，并調(diào)整分配方案，最終解得的核同時(shí)滿足定理3、定理4，因此SCP算法得到的核一定是正確的。

7 實(shí)驗(yàn)

7.1 實(shí)驗(yàn)環(huán)境與評(píng)估標(biāo)準(zhǔn)

本文實(shí)驗(yàn)是在計(jì)算機(jī)上進(jìn)行的，計(jì)算機(jī)的系統(tǒng)環(huán)境是Windows7 64 bit，配有4 GB DDR 3內(nèi)存，主頻為3.2 GHz的i5-3470英特爾處理器。程序編寫(xiě)語(yǔ)言是C語(yǔ)言，運(yùn)行環(huán)境是MicrosoftVisual Studio 2008。實(shí)驗(yàn)數(shù)據(jù)是隨機(jī)生成的聯(lián)盟及其聯(lián)盟收益。

本文將算法的運(yùn)行時(shí)間作為效率的評(píng)估標(biāo)準(zhǔn),從兩方面分析算法的效率：一方面研究參與聯(lián)盟博弈的Agent的個(gè)數(shù)N對(duì)運(yùn)行時(shí)間的影響；另一方面研究不同結(jié)構(gòu)的約束圖對(duì)運(yùn)行時(shí)間的影響。

7.2 |N|對(duì)SCP算法求解時(shí)間的影響

本節(jié)研究|N|對(duì)SCP算法求核時(shí)間的影響。通過(guò)建立圖聯(lián)盟博弈Γ={N,v,G}，|N|=n，分別設(shè)定約束圖為零散圖、鏈狀圖、星狀圖、混合型拓?fù)浣Y(jié)構(gòu)，并改變不同約束圖中含有的Agent個(gè)數(shù)，即改變|N|的數(shù)量，記錄生成聯(lián)盟核所需要的時(shí)間，實(shí)驗(yàn)結(jié)果如表3，折線圖如圖7。折線圖以參與博弈的人數(shù)n為橫坐標(biāo)，求解時(shí)間為縱坐標(biāo)，每一條折線代表具有相同約束圖結(jié)構(gòu)、不同參與人數(shù)參與聯(lián)盟博弈時(shí)，SCP算法的求解時(shí)間變化。

通過(guò)對(duì)圖7、表3的觀察分析容易發(fā)現(xiàn)，若約束圖為零散圖，SCP算法求解時(shí)間不受|N|數(shù)量的影響。因?yàn)樵诹闵D約束下，任意|N|值可以生成滿足圖約束的聯(lián)盟個(gè)數(shù)為0。若約束圖是除零散圖以外的其他類型的約束圖，隨著|N|的數(shù)量的增加，算法運(yùn)行時(shí)間逐漸增加。因?yàn)閰⑴c聯(lián)盟人數(shù)增加，形成可行聯(lián)盟的個(gè)數(shù)會(huì)增大。

Fig.7 Influence of the number ofnon running time圖7 n的個(gè)數(shù)對(duì)求解時(shí)間的影響

Table 3 Running time of SCP algorithm with differentn表3 不同Agent個(gè)數(shù)n對(duì)應(yīng)SCP算法的求解時(shí)間

7.3 約束圖G在不同結(jié)構(gòu)下對(duì)SCP算法求解時(shí)間的影響

本節(jié)研究約束圖G具有不同結(jié)構(gòu)時(shí)對(duì)SPC算法求解時(shí)間的影響。建立圖聯(lián)盟博弈Γ={N,v,G},設(shè)定參與博弈的人數(shù)|N|為10至50，改變不同|N|下約束圖的結(jié)構(gòu)（零散圖、鏈狀圖、星狀圖、混合型拓?fù)浣Y(jié)構(gòu)），記錄生成核所需要的時(shí)間，實(shí)驗(yàn)結(jié)果如表3所示，折線圖如圖8。折線圖以圖形結(jié)構(gòu)的種類為橫坐標(biāo)，求解時(shí)間為縱坐標(biāo)，每一條折線代表相同個(gè)數(shù)Agent在不同結(jié)構(gòu)的約束圖下，SCP算法的求解時(shí)間的變化。

通過(guò)對(duì)圖8、表3的分析可以發(fā)現(xiàn)，當(dāng)約束圖約束結(jié)構(gòu)不同時(shí)，算法的求解速度是不同的。當(dāng)約束圖為零散圖時(shí)，即所有的聯(lián)盟都不可以生成，只能形成一種聯(lián)盟結(jié)構(gòu)，且分配為每一個(gè)Agent的初始利益。因此求解時(shí)間非?？?，求解時(shí)間不受N的影響，符合約束的聯(lián)盟數(shù)量最大，求解時(shí)間最長(zhǎng)。可以看出，SCP算法的運(yùn)行時(shí)間隨著零散圖、鏈狀圖、混合型拓?fù)浣Y(jié)構(gòu)的順序逐漸增大。因?yàn)檫@些約束圖按順序依次允許更多的聯(lián)盟生成，所以SCP算法求核時(shí)間主要和滿足圖約束的聯(lián)盟個(gè)數(shù)有關(guān)。

Fig.8 Influence of graph structure on running time圖8 約束圖結(jié)構(gòu)對(duì)算法求解時(shí)間的影響

7.4 對(duì)比算法

本節(jié)對(duì)比SCP算法和CCDP算法在求解最優(yōu)聯(lián)盟時(shí)的優(yōu)點(diǎn)。

CCDP算法是由徐廣斌等人編寫(xiě)的求解帶有聯(lián)盟個(gè)數(shù)約束的最優(yōu)結(jié)構(gòu)算法，該算法基于DP思想引入了聯(lián)盟劃分塊的概念，通過(guò)比較初始聯(lián)盟值和分成兩個(gè)劃分塊的聯(lián)盟值之和，得到2n-1個(gè)聯(lián)盟的劃分?jǐn)?shù)，求得最優(yōu)的聯(lián)盟結(jié)構(gòu)。聯(lián)盟個(gè)數(shù)的約束就是通過(guò)判斷聯(lián)盟劃分?jǐn)?shù)得到符合條件的聯(lián)盟結(jié)構(gòu)[12]。

CCDP算法需要將2n-1個(gè)聯(lián)盟分解，算法假定所有的聯(lián)盟都是可行的。而本文提出的SCP算法在開(kāi)始就對(duì)聯(lián)盟的生成進(jìn)行了約束，減少了可行聯(lián)盟個(gè)數(shù)，減少了算法在生成最優(yōu)聯(lián)盟時(shí)所需處理的數(shù)據(jù)，降低了算法的求解時(shí)間。

表4是CCDP算法生成最優(yōu)聯(lián)盟結(jié)構(gòu)的時(shí)間，將表4與表3中SCP求解時(shí)間進(jìn)行對(duì)比可以發(fā)現(xiàn)，SCP算法求解時(shí)間遠(yuǎn)遠(yuǎn)小于CCDP算法，并且參與聯(lián)盟的Agent個(gè)數(shù)越多效果越明顯。因?yàn)锳gent個(gè)數(shù)越多，受約束圖約束的聯(lián)盟個(gè)數(shù)越多，兩個(gè)算法所處理的可行聯(lián)盟個(gè)數(shù)差異越大。

Table 4 Running time of CCDP with differentn表4 不同Agent個(gè)數(shù)n對(duì)應(yīng)CCDP算法的求解時(shí)間

8 結(jié)論和未來(lái)工作

本文給出了圖形聯(lián)盟博弈的定義，分析了多種圖形拓?fù)浣Y(jié)構(gòu)在圖聯(lián)盟博弈中的應(yīng)用，刻畫(huà)了聯(lián)盟收益分配的穩(wěn)定性的概念，分析了求解穩(wěn)定結(jié)構(gòu)和分配的復(fù)雜性，給出了相應(yīng)的解決方案。基于CCDP算法設(shè)計(jì)了一種有效的求解聯(lián)盟結(jié)構(gòu)核的算法，該算法首先改進(jìn)CCDP算法的約束條件，利用圖形拓?fù)浣Y(jié)構(gòu)約束聯(lián)盟的生成，利用CCDP算法分層生成最優(yōu)子結(jié)構(gòu)，避免了重復(fù)計(jì)算。然后將按勞分配作為初始分配方案，公平地將聯(lián)盟收益分配給聯(lián)盟成員，運(yùn)用穩(wěn)定成本、談判集的概念，調(diào)整初始分配，得到滿足核定義的聯(lián)盟結(jié)構(gòu)和穩(wěn)定分配。最后通過(guò)實(shí)驗(yàn)，得出SCP算法在不同N和約束圖結(jié)構(gòu)下的運(yùn)行時(shí)間，并總結(jié)出算法的求解時(shí)間與生成可行聯(lián)盟的個(gè)數(shù)正相關(guān)，并且可生成的聯(lián)盟個(gè)數(shù)受|N|和約束圖結(jié)構(gòu)控制。

未來(lái)工作包括:

（1）加入夏普利值分配方案，當(dāng)聯(lián)盟滿足超加性時(shí)，采用夏普利值進(jìn)行分配，得到滿足核要求的分配。

（2）在分配方案上將單個(gè)Agent的貢獻(xiàn)細(xì)分化，將腦力勞動(dòng)、體力勞動(dòng)、成本和邊際貢獻(xiàn)[22]加入到分配方案中，使分配方案更貼近現(xiàn)實(shí)博弈。

（3）細(xì)化約束條件，例如引入?yún)⑴c聯(lián)盟的Agent的偏好，進(jìn)一步約束聯(lián)盟的生成，刪去不符合邏輯的聯(lián)盟，降低算法的時(shí)間復(fù)雜度。

[1]IwasakiA,Ueda S,Hashimoto N,et al.Finding core for coalition structure utilizing dual solution[J].Artificial Intelligence,2015,222(5):49-66.

[2]Chalkiadakis G,Greco G,Markakis E.Characteristic function games with restricted agent interactions:core-stability and coalition structures[J].Artificial Intelligence,2016,232(1):76-113.

[3]Tan Chunqiao.Shapley value fornpersons games with interval fuzzy coalition based on Choquet extension[J].Journal of Systems Engineering,2010,25(4):451-458.

[4]Rahwan T,Jennings N R.An improved dynamic programming algorithm for coalition structure generation[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems,Estoril,May 12-16,2008.New York:ACM,2008:1417-1420.

[5]Billera L J.Some theorems on the core of ann-person game without side-payments[J].SIAM Journal on Applied Mathematics,1970,18(3):567-579.

[6]Schmeidler D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.

[7]Myerson R B.Graphs and cooperation in games[J].Mathematics of Operations Research,1977,2(3):225-229.

[8]Skibski O,Michalak T P,Rahwan T,et al.Algorithms for the Shapley and Myerson values in graph-restricted games[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems,Paris,May 5-9,2014.New York:ACM,2014:197-204.

[9]Michalak T P,Rahwan T,Szczepanski P L,et al.Computational analysis of connectivity games with applications to the investigation of terrorist networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2014:293-301.

[10]de Weerdt M,Zhang Yingqian,Klos T.Multiagent task allocation in social networks[J].Autonomous Agents and Multi-Agent Systems,2012,25(1):46-86.

[11]Yeh D Y.A dynamic programming approach to the complete set partitioning problem[J].BIT Numerical Mathematic,1986,26(4):467-474.

[12]Xu Guangbin,Liu Jinglei.The optimal coalition structure generation with the constrained number of coalition[J].Journal of Nanjing University:Natural Sciences,2015,51(4):601-613.

[13]Yang Xiangfeng,Gao Jinwu.Uncertain core for coalitional game with uncertain payoffs[J].Journal of Uncertain Systems,2014,8(1):13-21.

[14]Guan Baichun.New interpretation of distribution according to one's performance—an explanation of innovation pursuit[J].Theory Journal,2005(3):35-39.

[15]Sandholm T,Larson K,Andersson M,et al.Coalition structure generation with worst case guarantees[J].Artificial Intelligence,1999,111(1/2):209-238.

[16]Breton M L,Owen G,Weber S.Strongly balanced cooperative games[J].International Journal of Game Theory,1992,20(4):419-427.

[17]Scarf H E.The core of anNperson game[J].Econometrica,1965,35(1):50-69.

[18]Voice T,Polukarov M,Jennings N R.Coalition structure generation over graphs[J].Journal of Artificial Intelligence Research,2012,45(1):165-195.

[19]Bachrach Y,Meir R,Jung K,et al.Coalitional structure generation in skill games[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2011:703-708.

[20]Aumann R J,Maschler M.The bargaining set for cooperative games[J].Advances in Game Theory,1964,52(1):443-476.

[21]Bachrach Y,Elkind E,Meir R,et al.The cost of stability in coalitional games[C]//LNCS 5814:Proceedings of the 2nd International Symposium on Algorithmic Game Theory,Paphos,Oct 18-20,2009.Berlin,Heidelberg:Springer,2009:122-134.

[22]Aurangzeb M,Lewis F L.Internal structure of coalitions in competitive and altruistic graphical coalitional games[J].Automatica,2014,50(2):335-348.

附中文參考文獻(xiàn):

[3]譚春橋.基于Choquet延拓具有區(qū)間模糊聯(lián)盟n人對(duì)策的Shapley值[J].系統(tǒng)工程學(xué)報(bào),2010,25(4):451-458.

[12]徐廣斌,劉驚雷.帶有聯(lián)盟個(gè)數(shù)約束的最優(yōu)聯(lián)盟結(jié)構(gòu)生成[J].南京大學(xué)學(xué)報(bào):自然科學(xué),2015,51(4):601-613.

[14]關(guān)柏春.按勞分配新論——一種追求變革的解說(shuō)[J].理論學(xué)刊,2005(3):35-39.