圖聯盟結構核的求解算法*

尚傳啟，劉驚雷

煙臺大學 計算機與控制工程學院，山東 煙臺 264005

1 引言

聯盟博弈是處理幾個實體間競爭、合作的策略，它假定所有的Agent都是理性的，即每一個Agent都會為了尋求自身利益的最大化，選擇與他人合作（聯盟）。正因為Agent具有自由聯盟的能力，吸引了AI和MAS（multi-agent system）更多的關注[1]。然而在實際生活中聯盟博弈具有復雜性和多樣性，例如聯盟的生成往往受到各種條件的限制，聯盟行為具有動態性，無法快速達到穩定狀態等問題。這些問題使得聯盟中的成員無法快速獲得最大利益，長時間處于轉換聯盟的動蕩中，設計帶有限制的聯盟生成機制和構造穩定聯盟結構及其分配的算法已經成為一個重要的研究目標。

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

Fig.1 Wireless file sharing system圖1 無線合作共享系統

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

在現實社會中聯盟的生成問題是動態的、持續的。事實上，舊聯盟的破裂與新聯盟的生成時刻都在發生，但是新舊間的替換并不是無跡可尋的。Agent組成聯盟的目的是追尋更大的利益，那么一定存在一個可以使大多數或全部Agent獲得最大利益的穩定聯盟。然而，在現實中由于聯盟數目眾多，信息不明確等問題，無法快速找到最優的聯盟，只能一次次嘗試不同的聯盟。本文算法采用核、談判集、穩定成本等概念，快速求解穩定聯盟結構和利益分配，可以保證大多數Agent獲得最大利益。相較于傳統聯盟博弈的研究，本文具有的特點和貢獻在于：

（1）在傳統生成聯盟的基礎上考慮了外部約束，采用圖形拓撲結構約束聯盟的生成，并且引入聯盟花費的概念，使得生成的聯盟利益不再具有超加性，符合現實聯盟生成和利益的特點，更好地將合作博弈的理論應用到實際領域中。

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

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

2 相關工作

本文將從聯盟生成、聯盟利益分配、聯盟穩定性三方面，簡要地描述圖聯盟收益分配的相關工作。

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

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

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

3 圖聯盟博弈與分配方案的相關定義

3.1 圖聯盟博弈的相關定義

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

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

將復雜的通信網絡圖劃分成簡單的約束圖，其目的是簡化社會通信網絡，降低圖中聯盟的數量，從而降低算法求解時間。而降低求解時間則是為了更快地刷新最優聯盟結構，規避聯盟博弈的動態性和不穩定性帶來的問題。下面介紹幾種特殊的圖形拓撲結構。

零散圖（scattered graph），如圖2（a）所示，當圖中包含的約束條件最多時，即圖中沒有任何兩個Agent間存在連接，禁止任何聯盟的生成，可行的聯盟個數為0，稱這種約束圖為零散圖。

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

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

星狀圖（star graph），如圖2（d）所示，圖中以一個Agent為中心，其他所有Agent能且只能與位于中心位置的Agent建立連接。處于中心位置的Agent是所有聯盟生成的核心Agent，任何聯盟的生成都需要核心Agent的加入，當除了核心點外的其他Agent失去與核心Agent連接時，將只能選擇自己單獨工作，無法加入任何聯盟。同樣，當核心Agent消失，約束圖就變為零散圖，星狀圖中可行的聯盟個數為n+2n-1-1。

Fig.2 Graph topology圖2 圖形拓撲結構

混合型拓撲結構（hybrid topology），就是含有兩種或兩種以上的拓撲結構同時使用的約束圖。

定義2（圖約束聯盟）若Agent集合N的非空子集C中的Agent在約束圖G中所誘導的子圖G[C]=1，稱C為圖約束聯盟，數學形式定義為：

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

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

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

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

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

（3）Λ中的任意兩個聯盟的交集為? ，即一個Agent只能加入一個聯盟。

定義5（社會福利）聯盟結構Λ中所有聯盟Ci的聯盟收益之和稱為社會福利，并用符號Sw(Λ)表示，其數學形式化定義為：

在圖聯盟博弈Γ={N,v,G}中，最大社會福利用符號Swm(Γ)表示，Cs(G)中具有最大社會福利的聯盟結構用符號Cs*表示。

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

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

為了更好地理解上述的定義，下面通過例1來進行說明。

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

Fig.3 Chain graphG1圖3 鏈狀圖G1

根據聯盟結構的定義4，可以尋得可行的聯盟結構Cs(G)：

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

3.2 初始分配方案

本節主要介紹對于聯盟利益所采用的初始分配方案和方案特點，以及它相較于夏普利值的優點。

本文選用按勞分配作為初始分配方案[14]，簡單來說，按勞分配就是將每一個Agent單獨工作所能獲得的利益，看作他們在聯盟中所能做出的貢獻，然后根據每一個Agent的貢獻值，公平地將聯盟利益分配給聯盟的參與者。對聯盟利益進行初始分配是調整分配得到穩定分配的基礎。

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

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

如下的例2，利用按勞分配將聯盟利益分配給單個Agent，給出了按勞分配的分配特點。

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

Fig.4 Chain graphG2圖4 鏈狀圖G2

根據聯盟結構的定義4，可以尋得可行的聯盟結構Cs(G)：

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

根據按勞分配的定義7，對聯盟結構Λ依次進行初始利益分配：

4 穩定分析和初始分配調整方案

以下分析了穩定的聯盟結構及分配所具有的特點，并發現采用按勞分配方案產生的分配結果可能是不穩定的。為了使聯盟穩定往往需要滿足每一個Agent的理性要求，但很多時候，由于聯盟利益的限制，該要求是無法實現的，這使得尋找穩定分配具有復雜性。本文將分析復雜性并提出相應的分配調整方案，使得最終分配結果具有穩定性。

4.1 穩定分析

在Chalkiadakis等人的研究中發現，穩定的分配必然存在于具有最大社會福利的聯盟結構內[2]，因此尋找的穩定聯盟結構就是具有最大社會福利的聯盟結構Cs*。若Cs*中處于聯盟狀態的Agent，均可以在Cs*中同時獲得自身的最大期望利益，那么分配具有穩定性，這樣的分配滿足核的定義，因此將核的概念引入，將核作為主要考慮的穩定因素，定義它為實現最大社會福利的聯盟結構及其分配。

定義8（核）在圖聯盟博弈Γ={N,v,G}中，Λ∈Cs*，xi∈Λ，對于任意一個聯盟結構Λ∈Cs(G)，都有x(C)≥v(C)，稱(Λ,(xi))為聯盟結構的核，其數學形式定義為：

需要說明的是核有可能是空的，當聯盟結構中所有處于聯盟狀態的Agent可獲得的最大期望利益之和大于最大社會福利時，核為空。

通過一個簡單的例3來表述核的定義。

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

根據聯盟結構的定義4，可以尋得可行的聯盟結構Cs(G)：

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

根據按勞分配的定義7，對聯盟結構Λ依次進行初始利益分配：

聯盟結構 {1},{2,3}為實現最大社會福利的聯盟結構Cs*，并且在此聯盟結構中，所有處于聯盟狀態的Agent均獲得了最大期望利益，因此({1},{2,3},(4,12,18))滿足定義8，是聯盟博弈的核，Cs-core(Γ)=({1},{2,3},(4,12,18))。

然而在實際應用中往往不會和例3一樣，Cs*的初始分配結果正好滿足核的定義，會出現以下3種情況：

（1）具有多個最大社會福利的聯盟結構Cs*，即具有多個互不相同的聯盟結構Λ，它們的社會福利均為最大社會福利Swm(Γ)。

（2）利用按勞分配作為初始分配方案，得到分配結果可能不是最優的，即存在個別處于聯盟狀態的Agent獲利小于其他形式的聯盟，不滿足核的定義。

（3）無法令所有處于聯盟狀態的Agent同時獲得最大利益，即核為空的情況。

4.2 解決方案

本節根據4.1節中可能發生的3種情況，提出了對應的解決方案，并用實例驗證了方案的可行性。

情況（1）具有最大社會福利的聯盟結構有多個，提出次穩定聯盟結構Λ*的定義，在多個具有最大社會福利的聯盟結構Cs*中，尋找最優的聯盟結構作為次穩定聯盟結構Λ*。在現實博弈中，可以令多數Agent同時獲得最大利益的聯盟結構才更加具有穩定性，因此選取令多數Agent獲得最大利益的Cs*作為Λ*。

定義9（次穩定聯盟結構）假設圖聯盟博弈Γ={N,v,G}存在多個Cs*，選取多數Agent獲得最大利益的聯盟結構Λ作為Λ*，并用符號Λ*表示。

若次穩定結構Λ*及其分配滿足定義8，那么稱(Λ*,(xi))為次穩定核，用符號Cs-score(Γ)表示，Csscore(Γ)=(Λ*,(xi))。

例4給出了次穩定聯盟結構的應用。

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

根據聯盟結構的定義4，可以尋得可行的聯盟結構Cs(G)：

根據定義5，Sw(Λ)依次為35、40、40、40，Swm(Γ)=34，發現具有最大社會福利的聯盟結構的個數為3，且它們的利益分配結構依次為：

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

通過比較初始利益分配的結果，發現在聯盟結構 {1},{2,3}中x2、x3同時取得自身利益最大值9.4和23.6，即用戶2、3同時獲得自身最大利益，獲得最大利益的Agent個數最多。根據次穩定核的定義9，選多數Agent獲得最大利益的聯盟結構 {1},{2,3}作為Λ*，當用戶1想要破壞聯盟{2,3}的穩定性時，用戶2、3出于理性考慮，不會放棄最大利益離開原聯盟。因此聯盟結構 {1},{2,3}具有穩定性，并且Λ*及其初始分配(7,9.4,23.6)滿足核的定義，Cs-core(Γ)=({1,2},{3},(9.3,10.7,20))。

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

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

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

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

例5給出了談判集的應用。

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

根據聯盟結構的定義4，可以尋得可行的聯盟結構Cs(G)：

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

根據按勞分配的定義7，對聯盟結構Λ依次進行初始利益分配：

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

情況（3）無法令所有處于聯盟狀態的Agent同時獲得最大利益，即核為空，盡管Cs*具有最大社會福利Swm(Γ)，也可能發生所有處于聯盟狀態的Agent無法同時獲得最大利益的情況。對于這種情況，次穩定結構Λ*，談判集無法令一個核為空的博弈存在核，而穩定成本則可以解決這個問題。

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

穩定成本從聯盟博弈外部條件考慮，向外部環境借用最少的利益Δ，使聯盟內部的成員都可以獲得最大利益，Δ能夠保證圖聯盟結構具有非空核[21]。這里說的外部環境具有多樣性，可以簡單地將這個外部環境考慮為上層調控。

例6給出了穩定成本Δ的應用。

例6給定圖聯盟博弈Γ={{1,2,3,4},v,G3}，假設參與博弈的用戶集合N={1,2,3,4}，約束圖為圖5所示的混合拓撲結構，聯盟收益v滿足下列等式：

Fig.5 Hybrid topologyG3圖5 混合拓撲結構G3

通過計算可以求得Swm(Γ)=8.2，Cs*={1,2,3},{4}。對部分有特點的聯盟結構Λ進行利益分配可得：

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

5 構造圖聯盟結構核的算法

下面介紹構造圖聯盟博弈穩定核的SCP算法，該算法在構造圖聯盟博弈穩定核時，可以分為兩部分：

第一部分的輸入為圖聯盟博弈Γ={N,v,G}，輸出為最大社會福利的聯盟結構Cs*及其初始分配B[Cs*]和每個Agent可獲得最大利益的數組S[N]。此部分在構造Cs*和B[Cs*]時，不但吸收CCDP算法的最優子結構和子問題重疊的性質[12]，并以此為基礎加入利益分配，對可行的每個聯盟進行初始分配，生成每個Agent可獲得的最大利益數組S[N]。

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

算法1構造圖聯盟結構核算法

輸入：圖聯盟博弈Γ={N,v,G}。

輸出：圖聯盟結構核。

//Step1調用算法2，構造最大社會福利的聯盟結構Cs*，初始分配B[Cs*]，每個Agent可獲得最大利益數組S[N]。

調用算法2；

//Step2調用算法3，采用定義11判斷核是否為空，計算穩定成本，采用定義9尋找次穩定結構，采用定義10調整B[Cs*]。

調用算法3；

5.1 構造最優聯盟結構Cs*及其初始分配B[Cs*]的算法

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

算法2生成聯盟結構及其初始分配算法

輸入：圖聯盟博弈Γ={N,v,G}。

輸出：具有最大社會福利聯盟結構，初始分配，最大利益數組。

//Step1根據輸入中給定的N、v、G,生成滿足G約束的聯盟C，根據|C|將生成的聯盟分為Ln層，m≤n，并初始化聯盟值v(C)，設置優值F[C]，優結構M[C]，初始利益分配B[C]。

//Step2求出每層每個聯盟的優結構M[C]，調整優值F[C]，初始分配B[Cs*]。

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

步驟1對算法進行初始化，輸入圖聯盟博弈Γ={N,v,G}，即輸入參與聯盟博弈的Agent組成的集合N，對聯盟生成存在約束的約束圖G，和滿足圖G約束的聯盟利益v，生成滿足圖G約束的所有聯盟C，以聯盟C的基|C|=m為分層條件，將所有可行聯盟分為Lm層，對每層每個聯盟的參數初始賦值，優值F[C]初始賦值為v(C)，優結構M[C]初始賦值為聯盟C，初始分配B[C]初始賦值為 ({v{1},v{2},…,v{n}},i∈C)，以上過程如算法2的Step1所示。

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

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

5.2 生成穩定聯盟結構的算法

本節對SCP算法第二部分——生成聯盟核算法進行詳細的描述。算法的輸入為算法2的返回值Cs*、B[Cs*]、S[N]，輸出為圖聯盟結構的核。算法根據輸入，分析Cs*、B[Cs*]屬于4.1節的何種問題，并通過4.2節的解決方案生成核。

算法3生成聯盟結構核算法

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

輸出：聯盟結構核。

//Step1利用次穩定結構概念優化的Cs*個數，得到唯一的操作對象core*。

//Step2運用穩定成本和談判集的概念尋找聯盟博弈的穩定結構及其分配。

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

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

5.3 算法求解過程實例

例7存在圖聯盟博弈Γ={{1,2,3,4},v,G4}，|N|=5，約束圖為圖6所示的星型圖G4，聯盟利益為v（表1中第3列下劃線標記）。下面根據算法步驟生成圖聯盟結構核。

Fig.6 Star graphG4圖6 星狀圖G4

生成最大社會福利的聯盟結構及其初始分配算法。表1用表格的形式表現此算法的求解過程。

步驟1輸入圖聯盟博弈Γ={N,v,G4}，輸入的聯盟和聯盟利益在表1中由下橫線標出，根據聯盟的基，|N|=5將聯盟分為L5層。初始化算法：分別設置每層每個聯盟C的優值F[C]、最優結構M[C]、聯盟初始分配B[C]。

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

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

生成穩定聯盟核算法。表2用表格的形式表現此算法的求解過程。

步驟1輸入算法 2 求得的Cs*、B[Cs*]、S[N]，因為實現最大福利的聯盟結構Cs*的個數P為2，采用次穩定核的概念，在兩個聯盟結構 {1},{2,3,4,5}、{2},{1,3,4,5}中，選取令多數Agent獲得最大利益的 {1},{2,3,4,5} 作為Λ*，并將 {1},{2,3,4,5}，(20,16.6,33.2,44.2,11)賦予core*。

步驟2選取core*中聯盟C(聯盟C中包含的Agent的數量大于1)，發現core*中的聯盟C均滿足公式，因此不需要穩定成本來調節，Δ=0。對比core*中處于聯盟狀態的Agent所獲得的分配(16.6，33.2，44.2，11)與S[N]中Agent最大利益期望[16.3,33.2,44.2,11]，可知core*中Agent均已獲得了自身的最大利益，滿足核的定義，因為P=2，Δ=0，所以輸出Cs-score(Γ)=({1},{2,3,4,5},(20,16.3,33.2,44.2,11))。

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

Table 1 Generation process ofCs*and initial allocation under constraints of star graph表1 星狀圖約束下的最優聯盟結構Cs*及其初始分配生成過程

Table 2 Generation process of coalition structure core表2 生成穩定聯盟結構核的算法求解過程

6 算法的性質分析

下面對生成聯盟博弈核的SCP算法在時間復雜度、正確性方面進行分析。算法的時間復雜度是衡量算法效率的基本要素；算法的正確性則主要刻畫若進程能夠按照所設計的算法來執行，其得到的運行結果一定是正確的。

6.1 算法時間復雜度分析

定理1（二項式定理）令n為一個正整數，且所有的x、y滿足：

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

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

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

6.2 算法的正確性分析

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

證明假設聯盟C中滿足式子，或存在Agent在其他聯盟D獲得比聯盟C更大的利益，那么Agent會選擇離開聯盟單獨工作，或加入聯盟D來最大化自身利益，這樣聯盟C是不穩定的，進而造成聯盟結構的不穩定，假設錯誤，定理成立。

定理4存在圖聯盟博弈Γ={N,v,G}，其穩定的分配一定存在于實現最大社會福利的聯盟結構中。

證明存在聯盟博弈Γ={N,v,G}，假設有聯盟結構核 (Λ,xi)，Λ∈Cs*，xi∈Λ，對于任意一個可行的聯盟結構Λ′∈Cs(G)和任何一個x′i∈Λ′，從每個Agent的理性考慮，當xi≥x′i時，才是穩定的分配。因為Λ中的聯盟是互不相交的而且完全覆蓋N，得到式子Sw(Λ)=，所以Sw(Λ)＞Sw(Λ′)。綜上所述，其穩定的分配一定存在于實現最大社會福利的聯盟結構中。

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

證明SCP算法解出每層最優的聯盟結構，并根據按勞分配方案得到初始分配，通過自頂向下的方式構造實現最大社會福利的聯盟結構，并調整分配方案，最終解得的核同時滿足定理3、定理4，因此SCP算法得到的核一定是正確的。

7 實驗

7.1 實驗環境與評估標準

本文實驗是在計算機上進行的，計算機的系統環境是Windows7 64 bit，配有4 GB DDR 3內存，主頻為3.2 GHz的i5-3470英特爾處理器。程序編寫語言是C語言，運行環境是MicrosoftVisual Studio 2008。實驗數據是隨機生成的聯盟及其聯盟收益。

本文將算法的運行時間作為效率的評估標準,從兩方面分析算法的效率：一方面研究參與聯盟博弈的Agent的個數N對運行時間的影響；另一方面研究不同結構的約束圖對運行時間的影響。

7.2 |N|對SCP算法求解時間的影響

本節研究|N|對SCP算法求核時間的影響。通過建立圖聯盟博弈Γ={N,v,G}，|N|=n，分別設定約束圖為零散圖、鏈狀圖、星狀圖、混合型拓撲結構，并改變不同約束圖中含有的Agent個數，即改變|N|的數量，記錄生成聯盟核所需要的時間，實驗結果如表3，折線圖如圖7。折線圖以參與博弈的人數n為橫坐標，求解時間為縱坐標，每一條折線代表具有相同約束圖結構、不同參與人數參與聯盟博弈時，SCP算法的求解時間變化。

通過對圖7、表3的觀察分析容易發現，若約束圖為零散圖，SCP算法求解時間不受|N|數量的影響。因為在零散圖約束下，任意|N|值可以生成滿足圖約束的聯盟個數為0。若約束圖是除零散圖以外的其他類型的約束圖，隨著|N|的數量的增加，算法運行時間逐漸增加。因為參與聯盟人數增加，形成可行聯盟的個數會增大。

Fig.7 Influence of the number ofnon running time圖7 n的個數對求解時間的影響

Table 3 Running time of SCP algorithm with differentn表3 不同Agent個數n對應SCP算法的求解時間

7.3 約束圖G在不同結構下對SCP算法求解時間的影響

本節研究約束圖G具有不同結構時對SPC算法求解時間的影響。建立圖聯盟博弈Γ={N,v,G},設定參與博弈的人數|N|為10至50，改變不同|N|下約束圖的結構（零散圖、鏈狀圖、星狀圖、混合型拓撲結構），記錄生成核所需要的時間，實驗結果如表3所示，折線圖如圖8。折線圖以圖形結構的種類為橫坐標，求解時間為縱坐標，每一條折線代表相同個數Agent在不同結構的約束圖下，SCP算法的求解時間的變化。

通過對圖8、表3的分析可以發現，當約束圖約束結構不同時，算法的求解速度是不同的。當約束圖為零散圖時，即所有的聯盟都不可以生成，只能形成一種聯盟結構，且分配為每一個Agent的初始利益。因此求解時間非常快，求解時間不受N的影響，符合約束的聯盟數量最大，求解時間最長。可以看出，SCP算法的運行時間隨著零散圖、鏈狀圖、混合型拓撲結構的順序逐漸增大。因為這些約束圖按順序依次允許更多的聯盟生成，所以SCP算法求核時間主要和滿足圖約束的聯盟個數有關。

Fig.8 Influence of graph structure on running time圖8 約束圖結構對算法求解時間的影響

7.4 對比算法

本節對比SCP算法和CCDP算法在求解最優聯盟時的優點。

CCDP算法是由徐廣斌等人編寫的求解帶有聯盟個數約束的最優結構算法，該算法基于DP思想引入了聯盟劃分塊的概念，通過比較初始聯盟值和分成兩個劃分塊的聯盟值之和，得到2n-1個聯盟的劃分數，求得最優的聯盟結構。聯盟個數的約束就是通過判斷聯盟劃分數得到符合條件的聯盟結構[12]。

CCDP算法需要將2n-1個聯盟分解，算法假定所有的聯盟都是可行的。而本文提出的SCP算法在開始就對聯盟的生成進行了約束，減少了可行聯盟個數，減少了算法在生成最優聯盟時所需處理的數據，降低了算法的求解時間。

表4是CCDP算法生成最優聯盟結構的時間，將表4與表3中SCP求解時間進行對比可以發現，SCP算法求解時間遠遠小于CCDP算法，并且參與聯盟的Agent個數越多效果越明顯。因為Agent個數越多，受約束圖約束的聯盟個數越多，兩個算法所處理的可行聯盟個數差異越大。

Table 4 Running time of CCDP with differentn表4 不同Agent個數n對應CCDP算法的求解時間

8 結論和未來工作

本文給出了圖形聯盟博弈的定義，分析了多種圖形拓撲結構在圖聯盟博弈中的應用，刻畫了聯盟收益分配的穩定性的概念，分析了求解穩定結構和分配的復雜性，給出了相應的解決方案。基于CCDP算法設計了一種有效的求解聯盟結構核的算法，該算法首先改進CCDP算法的約束條件，利用圖形拓撲結構約束聯盟的生成，利用CCDP算法分層生成最優子結構，避免了重復計算。然后將按勞分配作為初始分配方案，公平地將聯盟收益分配給聯盟成員，運用穩定成本、談判集的概念，調整初始分配，得到滿足核定義的聯盟結構和穩定分配。最后通過實驗，得出SCP算法在不同N和約束圖結構下的運行時間，并總結出算法的求解時間與生成可行聯盟的個數正相關，并且可生成的聯盟個數受|N|和約束圖結構控制。

未來工作包括:

（1）加入夏普利值分配方案，當聯盟滿足超加性時，采用夏普利值進行分配，得到滿足核要求的分配。

（2）在分配方案上將單個Agent的貢獻細分化，將腦力勞動、體力勞動、成本和邊際貢獻[22]加入到分配方案中，使分配方案更貼近現實博弈。

（3）細化約束條件，例如引入參與聯盟的Agent的偏好，進一步約束聯盟的生成，刪去不符合邏輯的聯盟，降低算法的時間復雜度。

[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.

附中文參考文獻:

[3]譚春橋.基于Choquet延拓具有區間模糊聯盟n人對策的Shapley值[J].系統工程學報,2010,25(4):451-458.

[12]徐廣斌,劉驚雷.帶有聯盟個數約束的最優聯盟結構生成[J].南京大學學報:自然科學,2015,51(4):601-613.

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