單調重疊聯盟下的最優聯盟結構生成

郭志鵬，劉驚雷

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

0 引言

agent 理論和技術研究起源于分布式人工智能，它是人工智能的一個非常重要的研究方向。隨著計算機科學和技術的發展，agent 理論和技術趨于成熟，相關課題逐漸脫離分布式人工智能，它可以應對計算機支持的多種應用需求，如協同工作［1］、虛擬企業［2］、應急資源分配［3］、無線傳感器網［4］等。多agent 系統（Multi-Agent System，MAS）作為agent 理論的核心內容為一些獨立的agent提供了一種協作模式，這種協作模式可以使這些agent 在一定的時間內自發地形成一個針對特定任務的協作團隊，形成的團隊形式一般被稱為聯盟［5-6］。因此，聯盟形成（Coalition Formation，CF）是一組agent 為了完成一系列任務而進行資源共享和分配的過程，它可以提高單個agent 效益并且有效地完成任務。如何在agent 之間形成高效的聯盟是MAS和人工智能一個重要的研究課題。

一般來說，CF 的研究是圍繞著聯盟結構生成（Coalition Structure Generation，CSG）問題展開的。世界上一些權威學者對CSG 問題進行了深入的研究，并提出了自己一些獨特的見解［7-9］。他們的大部分工作是圍繞非重疊聯盟展開的，即在MAS 中，agent 活動范圍內只有一個聯盟。此外，當聯盟形成時，所有加入聯盟的agent 即使擁有足夠的資源，也不能加入其他聯盟。然而，這種情況是不合理的。首先MAS 內會出現資源浪費的情況，其次擁有豐富資源的agent為了獲取更多的利益，往往會參與多個聯盟。例如，投資公司擁有豐富的投資資源，但他們往往不會把所有的資源都投資在一個項目上。相反，他們把資源分成幾部分用于投資，這樣不僅可以獲得更多的利潤，而且可以有效降低投資失敗風險。重疊聯盟的概念由此產生，即agent 活動的范圍可以是多個聯盟，它們通過劃分各自的資源參與到多個聯盟中來完成不同的任務。這種方式不僅可以提高系統資源的利用率，還可以提高任務完成的效率和整個系統的效益。因此，重疊聯盟結構生成（Overlapping Coalition Structure Generation，OCSG）問題吸引了越來越多研究人員的目光。

本文研究的主要內容是重疊聯盟的合作博弈框架（Framework of cooperative games with Overlapping Coalitions，OCF games）中的OCSG 問題，該問題的搜索空間的大小通常與agent 的數量呈指數關系。例如，為了表示一個擁有n個agent 的傳統博弈，就需要為2n-1 種玩家子集（聯盟）分配一個數值。這個問題在OCF 博弈中更加突出，博弈不僅僅需要為每個聯盟分配數值，還需要表示agent的資源分配情況。因此，任何需要知道所有聯盟值的算法都不可能在多項式時間內運行，OCSG 問題一般是NP-hard。為了解決OCSG 的計算困難問題，首先要使用一種簡單有效的模型來限制重疊聯盟結構生成的規模，然后利用博弈中的某些特性實現OCSG 問題的剪枝搜索，這是解決OCSG問題的一般步驟。

在此背景下，主要貢獻如下：

1）在2.2 節中引入了一種帶有聯盟數量k約束的OCF 博弈（OCF games with number of coalitionkconstraints，kOCF games）模型。這種博弈不僅可以約束一個agent 如何很好地分割資源，而且可以限制重疊聯盟結構生成的規模。

2）為了解決OCSG 計算困難問題，引入一種相似度量來度量兩個聯盟結構的相似程度。此外，基于相似度量定義9闡述了kOCF 博弈的單調性。該性質意味著一個聯盟結構越相似于最優聯盟結構，它的聯盟值就越大。

3）對于一個具有單調性的kOCF 博弈，設計了聯盟約束貪心（Coalition Constraints Greed，CCG）算法來解決OCSG 問題。在定理3 中證明了該算法時間復雜度至多為O(n2k+1)，并且是固定參數可解的。

4）通過實驗分析了agent 個數、最大聯盟數量k值和不同聯盟值分布對算法性能的影響。實驗結果驗證了當k值被常數約束時CCG 算法的搜索次數隨著agent 個數基本呈線性增長這一優點。通過與Zick 等［10］提出的算法在算法類型、約束條件等多方面上進行了對比，說明了CCG 算法擁有更好的適用性。

1 相關工作

本章簡要介紹了聯盟結構生成和重疊聯盟形成的相關工作。目前的主要工作是在這兩者的基礎上進行和擴展的。

1.1 聯盟結構生成

聯盟結構生成中的難點就是如何在龐大的搜索空間中找到最優聯盟結構，使得該聯盟結構的聯盟值是最大的［11］。目前國內外關于CSG 的研究已取得了一定成功，專家們一般是利用博弈中某些特性來設計算法尋找最優聯盟結構，并且分析了其計算的復雜性。

計算最優聯盟結構的相關問題在人工智能文獻中得到了廣泛關注，其中包括Sandholm 等［12］、Larson 等［13］的重要論文。動態規劃算法是解決這一問題的最早算法之一。針對CSG問題，Yeh［14］提出了第一個動態規劃算法；根據聯盟間的同構關系，張新良等［15］提出了一種快速動態生成算法，算法首先對聯盟結構圖進行剪枝，然后再利用動態規劃方法搜索最優聯盟結構。

隨著agent 個數不斷地增加，CSG 問題搜索空間爆炸式增長［16］。任意時間算法意味著解的質量隨計算時間的增加而單調增加，比非任意時間算法具有更好的實際應用價值。Sandholm 等［12］通過將搜索空間劃分成不相交的詳盡的子空間，并保證在一定約束下找到一個有保障的目前最優解，提出了最壞保證算法；Rahwan 等［17-18］將動態規劃方法與任意時間方法相結合，提出了改進動態規劃等算法。

有一些特殊的博弈，agent 之間或者agent 與聯盟之間有一種特殊的關系。例如，Greco等［19］研究了加權匹配和加權分配博弈，其中的聯盟值由圖（可能是加權圖）上匹配問題的最優值決定。在許多現實的情況下，聯盟值的大小可能會受到其他agent 聯盟形成的影響。為了模擬這種情況，Lucas 等［20］提出了配分函數博弈（Partition Function Games，PFGs）。Rahwan 等［21］在PFGs 模型的基礎上，引入了外部性的性質，并設計了相應的算法；Fatima 等［8］考慮了帶有玩家序列的特殊博弈，并引入了值函數的單調性性質，設計了一種貪心算法在多項式時間內解決了CSG問題。

1.2 重疊聯盟形成

1996 年，Shehory 和Kraus 在人工智能會議上首次提出了重疊聯盟形成的概念，但他們只是簡單地假設任務是串行的，并沒有解決重疊聯盟的資源沖突問題；Chalkiadakis 等［22］提出了OCF 博弈模型，該模型可用于agent 分配資源的場景建模，并通過元組的形式有效地表示出了重疊聯盟博弈。Zick等［10］基于OCF 博弈提出了離散重疊聯盟形成（discrete Overlapping Coalition Formation，dOCF）博弈概念，將agent 資源分配描述進行了量化和離散化，使重疊聯盟的表示和計算更加方便。

重疊聯盟結構生成是重疊聯盟形成重要研究內容之一，與CSG 問題不同的是它涉及到agent 之間可以形成重疊聯盟的情景。專家們通過對博弈增加一些約束或者利用博弈中存在的特殊性質來解決OCSG 問題。Zick 等［10］在dOCF 博弈的基礎上增加了通信圖約束解決了OCSG 問題，并將其結果推廣到通信圖接近于樹，即有界樹寬的情況。魏冰茹等［23］構建了以聯盟結構成本最小化為優化目標的OCSG 數學模型，并提出了一種基于動態規劃的OCSG算法。

2 相關定義

2.1 重疊聯盟和聯盟結構

在本節中，首先說明了使用的符號，然后簡要介紹OCF博弈和聯盟結構的基本概念。特別地，使用大寫字母表示集合，用黑體字母表示向量。表1為使用的基本符號。

表1 符號描述Tab.1 Symbol description

傳統合作博弈G可以用元組來表示，其中N={1，2，…，n}是玩家（或agent）集合，u：2N→R+是一個可以為玩家集合子集S?N分配一個實值（聯盟值）的函數，子集S又被稱為聯盟。傳統合作博弈中的聯盟結構是一組agent 的劃分，用Sc={S1，S2，…，Sm}來表示它。傳統合作博弈具有以下兩個性質：

1）對于1 ≤j≤m

2）對于任意j≠k，Sj∩Sk=?。

在傳統的聯盟中，每個agent只能參與一個聯盟。雖然在部分情景中這是一個有效的假設，但現實中資源豐富的agent應該參與多個聯盟，并將其資源分配給多個任務，形成重疊的聯盟來獲取更多的利潤。以此為背景，Chalkiadakis 等［22］提出了OCF博弈模型，具體定義如下。

定義1 OCF博弈取消了每個agent只能參與一個聯盟的限制。一個OCF博弈也可以用一個元組來表示，其中N={1，2，…，n}是玩家集合，u：[0，1]n→R+是特征函數。

玩家集合N中的一個部分聯盟表示為向量c=(c1，c2…，cn)∈[0，1]n，為了簡潔，當談到這樣的聯盟經常會省略限定詞“部分”，稱c是一個聯盟。c的第i個坐標分量表示玩家i貢獻給聯盟c的資源比例。與傳統博弈不同是，v是一個特征函數，它定義在形式為[0，1]n的所有向量上，并為每個聯盟c分配一個非負的實值。在這種情況下，如果想要完全定義一個OCF 博弈，需要在[0，1]n的每個實點上指定特征函數v的值。由于一個聯盟結構可以包含很多聯盟，在agent數目比較多的情況下，OCF 博弈很難表示和計算。為了解決這個問題，本文引入了OCF博弈的離散化版本。

定義2一個dOCF 博弈是一個元組其中N={1，2，…，n}是玩家集合，向量W={W1，W2，…，Wn}表示玩家擁有權值，W的分量Wi對應著agenti∈N所擁有的權值，v是特征函數。

集合WA是agent為單個任務貢獻資源的所有可能方法的集合。與傳統的OCF 博弈不同的是，離散化OCF 博弈中是通過權重向量c∈WA來表示聯盟。向量c的每個分量ci表示agenti∈N對聯盟c的貢獻值。特別地，特征函數在dOCF 博弈中被定義為v：WA→R+，接受聯盟c∈WA作為輸入值，輸出值表示該聯盟所能產生的收益（聯盟值）。

定義3OCF 博弈中的聯盟結構定義為一個有限的聯盟列表CS=(c1，c2，…，cm)，其中

特別地，采用上標號形式可以表示不同的聯盟結構CSi，用|CS|來表示聯盟結構CS中聯盟的數量，并且用v(CS)來表示聯盟結構CS的收益，即v(CS)=同時用CSA來表示所有可能由N中成員組成的聯盟結構集合。

例1 考慮到以下4 個玩家參與的dOCF 博弈，其中玩家組成重疊聯盟來完成一組任務。玩家的權值表示為W={2，2，1，1}。有以下6種類型的任務：

1）類型為t12的任務需要玩家1 和玩家2 一半的資源來完成，收益為4。

2）類型為t14需要玩家1 一半的資源和玩家4 所有的資源來完成，收益為4。

3）類型為t24需要玩家2 一半的資源和玩家4 所有的資源來完成，收益為5。

4）類型為T23需要玩家2 和玩家3 所有的資源來完成，收益為6。

5）類型為T34需要玩家3 和玩家4 所有的資源來完成，收益為3。

6）類型為t1234需要所有玩家都貢獻出一個資源來完成，收益為9。

考慮聯盟結構CS1=(c1，c2)和CS2=其中：

根據特征函數v的定義，可以得到：

那么很容易可以算出v(CS1)=13。似乎v(CS2)=但事實上，聯盟結構CS2是無效的，因為玩家2 消耗的權重超過了它實際擁有的。

定義4重疊聯盟結構生成問題是在玩家集合N上找到一個聯盟值最大的聯盟結構，這樣的聯盟結構被稱為最優聯盟結構，即：

在例1 中，可以很容易地計算得到CSOPT=CS1。接下來將介紹一種帶有約束了聯盟結構中聯盟最大數量的特殊OCF博弈，也被稱為kOCF博弈。

2.2 kOCF博弈

考慮到一個有n個玩家的dOCF 博弈G=并假設玩家所擁有的最大權值為Wmax，即Wmax=

這個博弈G可以用|WA|=≤(Wmax+1)n個非負值列表來描述，其中每一個實值都代表agent可能形成的聯盟。對于所有的i∈N都有Wi≥1，這種表示形式的大小是以玩家數目n為指數，而聯盟結構的數目往往是更高數量級的，這對于大多數的應用程序是不可接受的。為了解決這個問題，往往是對博弈增加某種約束來限制聯盟結構生成的規模。在日常工作中，一個系統被分配的任務數量往往是有限的。例如在一個公司部門中，他們有多個客戶同時委派一些項目，那么就需要把員工們劃分成固定數量的小組，即形成相應的聯盟去完成任務。換句話說，這是一種約束了聯盟結構中最大聯盟數量的博弈。下面給出滿足約束的kOCF 博弈具體定義。

定義5給定一個dOCF 博弈G=如果對于所有的CS∈CSA且|CS|＞k，都有v(CS)=0，那么該博弈被稱為kOCF博弈。

簡單來說，在kOCF 博弈中所有聯盟結構CS∈CSA包含的聯盟數量都是小于等于k的。對于聯盟數量大于k的聯盟結構，由于增加了其特征函數為0 的設定，意味著agent 通過參與聯盟合作不會產生任何利潤，同時也違背了合作博弈的個體合理性原則，從而約束了聯盟結構的生成規模。

在dOCF 博弈中，聯盟是由向量c表示的，其中向量中的分量ci表示agenti∈N對聯盟的貢獻。為了更好地描述下節中的單調性性質，在kOCF博弈中，定義ci的取值是0或1，即：

那在kOCF 博弈中，聯盟可以使用玩家編號的形式來表示，將向量中所有非0 分量的編號寫入到聯盟C中。同時定義一種SFi(j)函數，它可以遍歷出標識為i的聯盟結構中擁有玩家編號j(l＜j≤n)的所有聯盟編號。例1 中的聯盟結構CS1=(c1，c2)就等價于CS={C1，C2}，其中C1={1，2}，C2={1，2，3，4}，對應有SF(1)={1，2}，即在聯盟結構CS中玩家1同時出現在C1和C2中。

命題1 OCSG 問題在kOCF 博弈中是計算困難的，即使是在聯盟結構中聯盟數量約束k值和玩家最大權重Wmax值比較較小的情況，該命題依舊成立。

證明 由于聯盟結構中的聯盟最大數量是k，聯盟結構初始化為CS={?，?，…，?}，即聯盟結構CS中含有k個空集。OSCG 問題形成的搜索空間就是一個組合排列問題。假設所有集合N={1，2，…，n}中的玩家都擁有相同數量的資源，即所有玩家的權值都為Wmax。由于玩家最多貢獻一個單位的權值到單個聯盟中，玩家資源數量較多、形成聯盟數量較小的博弈研究意義較小，所以k值應該大于Wmax。那么對于任意一個玩家，有最多Wmax個該玩家編號插入到空集中形成聯盟，插入的所有可能性最多有種。那么對于N中的所有玩家，OCSG 問題的搜索空間大小為是n的指數級，所以是計算困難的。

為了解決kOCF 博弈中的OCSG 計算困難問題，需要利用博弈中的一種特殊性質稱之為單調性來簡化計算問題，實現聯盟結構的減枝搜索。

2.3 相似度量與單調性

生活中的很多例子可以表明，兩個事物如果擁有較高的相似度，那么兩者會存在相同或者相似的性質。如果把這種相似性引入到OCSG 問題中，認為與最優聯盟結構越相似的聯盟結構，它的值就越大，這種性質被稱為單調性。在本節中，首先介紹了玩家序列性質，這是單調性的基礎；然后引入了一種相似度量來度量兩個聯盟結構的相似程度；最后在kOCF博弈中定義了單調性性質，并證明了滿足這種性質的博弈是存在的。

在kOCF 博弈中，聯盟是一組玩家編號。聯盟的最小元素是集合中最小的玩家編號，且空集的最小元素認為是+∞。

例如，對于聯盟C1={1，2，3}，聯盟C1的最小元素是1，即minC1=1。給定一個kOCF 博弈G=其中非空玩家子集N={1，2，…，n}。在不失一般性的前提下，對于1 ≤m≤k，假設聯盟結構CS={C1，C2，…，Cm}按照以下定義排序。

定義6玩家序列。所有的玩家都應參與到聯盟中，即對于任意的1 ≤i＜j≤m，聯盟Ci和Cj中的最小元素只存在以下兩種情況：

1）聯盟Ci的最小元素小于聯盟Cj的最小元素，即minCi＜minCj。

2）聯盟Ci的最小元素等于聯盟Cj的最小元素。設相同最小元素集合為S，將其從聯盟Ci和Cj去除再比較兩者的最小元素，直至出現1）中的情況。等價為：

注意，此方法定義的聯盟結構具有以下性質：如果前i-1個玩家都在前l(1 ≤l≤k)個非空聯盟中，則玩家i一定屬于其中的前min {k，l+Wi}個聯盟。簡單來說，這種玩家序列性質可以有效地縮小OCSG問題搜索空間。

在日常工作中，滿足玩家序列的kOCF 博弈也是有跡可循的。回想2.2節中部門員工之間形成的kOCF 博弈情景，在這個情景中，由于每個員工的能力不同，擅長完成的項目也不同。部門可以按照這個標準對員工進行等級評判，同時按照任務的難度、利潤對項目編號排序。其中高等級的員工對應著編號較小的agent，高難度、高利潤的項目對應編號較小的聯盟。對于高等級的員工（也就是企業中常說的“核心員工”），部門會盡可能地將其分配到高難度、高利潤的項目中，這樣不僅可以充分利用人力資源，還可以提高整個部門完成項目的效率和收益。為了方便起見，之后所提及的kOCF 博弈均滿足該性質。

為了可以量化并計算兩個聯盟結構的相似程度，接下來介紹了一種特殊的輔助運算。對于1 ≤i≤n，集合{1，2，…，i}表示為[i]。

定義7一個聯盟結構CS=(C1，C2，…)到[i]的約束CS|[i]定義為：

基于這種約束，聯盟結構的相似度量定義如下：

定義8相似度量。給定一個kOCF 博弈G=其中玩家子集N={1，2，…，n}。對于任意兩個聯盟結構CS1，CS2∈CSA，若存在中的集合是中對應位置集合的子集，那么認為相似度增加1，并且用|[i]|表示存在這種關系集合的數量。相似度量Δ定義為：

該相似度量的實際意義是，按照玩家1，2，…，n的次序，兩個聯盟結構每有一個相同位置的玩家編號，相似度量的值就會至少增加1。

定理1對于n個玩家的kOCF 博弈，任意兩個聯盟結構CS1，CS2的相似度量取值范圍在1 到nk之間，即1 ≤Δ(CS1，CS2)≤nk。

證明 由于博弈滿足玩家序列的性質，且每個玩家都要參與到聯盟中，那么在任意聯盟結構中玩家1 一定是在第一個聯盟中的。對于CS1和CS2到[1]上的約束一定存在定義8中的對應子集關系，所以它們的相似度量一定是大于等于1的正整數。在kOCF 博弈中，聯盟結構中最大聯盟數量是k，則| [i]|的取值最大為k。由式（6）可得，Δ(CS，CS′)最大值為nk。

定理1 說明了任意兩個聯盟結構的相似度量都是存在且有界的。有了這種相似度量就可以度量任何聯盟結構與最優聯盟結構之間的相似程度。然后基于這種相似度量，提出kOCF 博弈的單調性定義，并且通過引理1 證明了這種單調性是存在的。

定義9kOCF 博弈的單調性。給定一個kOCF 博弈G=如果它的特征函數v滿足以下兩條性質，它就是一個單調的kOCF博弈。

1）只有一個最優值，也就是只有一種最優聯盟結構。

2）特征函數v在聯盟結構與CSOPT的相似度量上是單調遞增的。即對于聯盟結構CS1和CS2，有

引理1存在單調的kOCF博弈。

證明 表2 是一個kOCF 博弈G=的例子，更確切來說是3OCF 博弈，其中N={1，2，3}，W={2，2，1}。特別地該博弈假設每個任務只可以完成一次，即聯盟結構中不允許有重復的聯盟出現。該kOCF 博弈滿足定義9中的單調性，其中最優聯盟結構CSOPT=({1，2，3}，{1，2})。

表2 單調的3OCF博弈實例Tab.2 Example of monotonous 3OCF games

引理1 通過列舉一個3OCF 博弈實例證明了單調的kOCF博弈是存在的。這是第3 章中算法1 和重要定理2 的前提條件。

3 基于單調kOCF博弈的CCG算法設計

在本章中，對于單調的kOCF 博弈使用了貪心方法設計了CCG 算法來解決最優聯盟結構生成問題。假設所求的最優聯盟結構如果一個聯盟結構CS中玩家i的位置與CSOPT中情況相同，則稱玩家i在最優位置上。最優聯盟結構可以認為是所有玩家都在其對應的最優位置上的聯盟結構。聯盟約束貪心算法是通過逐步確定玩家1，2，…，n的最優位置來解決OCSG問題，具體算法如下

算法1 基于單調kOCF博弈的聯盟約束貪心算法。

輸入 單調kOCF博弈G=和最大聯盟數量k。

輸出 最優聯盟結構CSOPT。

3.1 求解過程

在2.2 節中，kOCF 博弈中聯盟可以用玩家編號的形式來表示，所以一個聯盟結構可以認為是插入不同玩家種類和多個玩家編號形成的。例如，在一個kOCF 博弈G=中，其中N={1，2，3}，玩家的權值向量W={2，2，2}。由于玩家的數量有3個且每個玩家的權值都是2，在算法處理中認為有3種不同的玩家種類，且每個玩家種類都包含2個編號。算法需要解決的問題由確定每個玩家的最優位置轉向到如何將這些玩家編號一一插入到最優聯盟結構當中。下面給出算法的關鍵定理及其證明。

定理2給定一個單調的kOCF 博弈G=，假設前i-1(1 ≤i≤n)個玩家均在最優位置上，且它們都屬于前l個聯盟中，換句話說l代表的是前i-1 玩家都在最優位置上的最大聯盟編號。那么玩家i所在聯盟編號取值一定是在1到min{k，l+Wi}之間，即i∈{C1，C2，…，對于玩家i，假設CS1是玩家i在最優位置上的聯盟結構，即SF1(i)=SFOPT(i)，聯盟結構CS2則相反。由于定義9 的單調性性質，CS1是唯一的，而CS2可以有多種情況。那么一定有

證明 在單調kOCF 博弈中，如果前i-1 個玩家都屬于前l個聯盟中，由于定義6 和式（3）的限制，玩家i所在聯盟編號取值一定是在1到l+Wi之間。根據式（6）有：

其中Wi代表的是玩家i的權值，是一個大于等于1 的正整數。那么根據式（7）單調性的性質可得v(CS1)＞v(CS2)。

簡單來說，定理2 的作用是根據前i-1 個玩家所在聯盟位置可以確定玩家i所在聯盟位置的范圍。相對于遍歷搜索空間解決OCSG 問題，它僅僅需要搜索少數聯盟結構，可以有效地縮小算法的搜索空間。在這些被搜索的聯盟結構中，通過比較聯盟值來確定玩家i的最優位置SFOPT(i)。特別地，參與比較的聯盟結構是不可以隨意選取的。這是因為玩家i+1，i+2，…，n參與聯盟結構的消耗的權值不同，聯盟結構與最優聯盟結構的相似度也會受到影響，違背了算法研究的是單調kOCF 博弈的前提，所以采用最大玩家權重原則來生成比較使用的聯盟結構。所謂最大玩家權重原則是指讓玩家i+1，i+2，…，n盡可能地形成規模較大的聯盟來插入到聯盟結構中，如果聯盟結構中有空集的情況下，則優先插入到空集中。這種方式旨在提高系統里多個agent的資源利用率，進而提高整個系統的收益，同時保證單調kOCF博弈的算法前提。

算法1是利用了貪心方法解決了單調kOCF中的OCSG問題。算法的總體流程是按照玩家編號的順序，將玩家1，2，…，n分別插入到其對應最優位置。其中玩家1，2，…，n的最優位置SFOPT(i)確定是通過定理2 來判別的。當循環結束時，也就是每個玩家都插入到了其對應的最優位置，算法生成的聯盟結構就是最優聯盟結構。

3.2 算法實例

為了簡潔明了地描述算法實例，使用了表2 中的博弈聯盟值。

例2 給定一個3OCF 博弈G=其中N={1，2，3}，W={2，2，1}。算法的具體步驟如下。

初始化 初始化CSOPT=(?，?，?)，和當前最大玩家聯盟編號l=0。

確定玩家1 的最優位置 由于當前最大玩家聯盟編號為0，玩家1 的最大權值為2，那么根據定義6 玩家1 可能參與了一個或兩個聯盟，且所在聯盟編號范圍在1和2之間。可能的聯盟位置如下：

1）1 ∈C1；

2）1 ∈C1并且1 ∈C2。

按照玩家權重最大原則，對于第1）種情況生成的聯盟結構為CS1=({1}，{2，3}，{2})，即SF1(1)={1}。對于第2）種情況生成的聯盟結構為CS2=({1，2}，{1}，{2，3})，即SF2(1)={1，2}。由于v(CS1)＜v(CS2)，所以SFOPT(1)=SF2(1)。此時的最優聯盟結構CSOPT=({1}，{1}，?)，更新l=2。

確定玩家2 的最優位置 玩家2 可能的聯盟位置有以下4種情況：

1）2 ∈C1；

2）2 ∈C1并且2 ∈C2；

3）2 ∈C3；

4）2 ∈C1并且2 ∈C3。

注意，2 ∈C2和2 ∈C2并且2 ∈C3這種情況是不存在的，因為它違背了定義6 中的玩家序列定義。按照玩家最大權重準則，對于第1）種情況生成的聯盟結構為CS1=({1，2}，{1}，{3})，SF1(2)={1}；對于第2）種情況生成的聯盟結構為CS2=({1，2，3}，{1，2})，SF2(2)={1，2}；對于第3）種情況生成的聯盟結構為CS3=({1，3}，{1}，{2})，SF3(2)={3}；第4）種情況生成的聯盟結構為CS2=({1，2，3}，{1}，{2})，SF4(2)={1，3}。由于v(CS2)＞v(CS4)＞v(CS1)＞v(CS3)，有SFOPT(2)=SF2(2)。此時的最優聯盟結構CSOPT=({1，2}，{1，2})，更新l=2。

確定玩家3的最優位置 同理，玩家3可能的聯盟位置只可能有一種：

3 ∈C1

這是因為玩家3 的權值只有1，如果玩家3 出現聯盟2 或聯盟3中，那么它會違背玩家序列的定義。所以玩家3只能在聯盟1 中。算法計算得到的最優聯盟結構CSOPT=({1，2，3}，{1，2})。

這樣通過4 次比較（1 次比較為玩家1 尋找最優位置，3 次比較為玩家2 尋找最優位置，0 次比較為玩家3 尋找最優位置）找到了最優聯盟結構。相對于搜索表2 中全部的17 種聯盟結構，CCG算法只搜索6次就解決了OCSG問題。

3.3 復雜度分析

定理3對于單調kOCF 博弈，CCG 算法可以在至多O(n2k+1)時間內確定CSOPT，并且是參數可解的。

證明 在算法1中，第1）～2）行初始化操作的時間復雜度為O(k)。第4）～8）行的循環遍歷出玩家i擁有不同權重時所在最優位置的所有可能性。循環生成的聯盟結構有種。如果忽略玩家序列的限制，且假設每個玩家i的最優位置選擇范圍q都為最大值k（聯盟結構的中聯盟數量最大值為k，實際中編號前一部分玩家的最優位置選擇范圍是小于k的）。所有玩家的權值都為Wmax=k，即玩家的資源足夠參與到所有的聯盟中（對于一個博弈來說，Wmax=是比較合理的，即每個玩家最多可以參加聯盟結構中一半的聯盟）。對于這種最壞的情況，生成的聯盟結構種類數目有那么第4）～8）行操作的時間復雜度為O(2k)。第9）行操作是遍歷生成的聯盟結構并找到一個聯盟值最大的情況，時間復雜度也是O(2k)。第10）行操作需要遍歷聯盟結構中的每個聯盟插入玩家編號，時間復雜度為O(k)。算法1 是對玩家1，2，…，n的循環操作，所以整體的時間復雜度至多為O(n2k+1)。當k值固定時，CCG 算法復雜度是關于n的多項式，所以是固定參數可解的。

4 算法的實驗分析

本章首先對不同參數對CCG 算法的影響進行了實驗和分析，然后與Zick 等［10］基于有界樹寬通信圖提出的OCSG 算法進行對比，目的是評估本文提出CCG算法的性能。

4.1 實驗環境

所有算法均使用Matlab R2017a 實現。實驗是在一臺配備2.20 GHz Intel Core CPU、8.0 GB RAM 和Windows 10 操作系統的計算機上進行的。每個實驗重復5～8 次，取平均結果為最終實驗結果。

4.2 實驗結果分析

算法的運行時間和搜索次數可以作為評價算法性能的標準，主要是利用控制變量法實驗并分析了agent 個數、最大聯盟數量值k和不同聯盟值分布對CCG算法性能的影響。

4.2.1 agent個數對CCG算法性能的影響

在重疊聯盟結構生成算法中，agent 個數是影響算法性能的主要因素。隨著agent 個數的不斷增加，OCSG 問題的搜索空間也變得極其龐大。在接下來的CCG 算法參數實驗中，取玩家集合中agent個數從16增加到20，其中聯盟最大數量k值取為［24］，聯盟值分布的情況采用后文中的Normal 型分布，對CCG算法運算時間和搜索次數進行了統計。

通過表3和圖1可以分析得出，CCG算法擁有較短的運行時間。此外相對于遍歷整個搜索空間，表3和圖2中的數據說明了CCG 算法實現了聯盟結構的減枝搜索，僅僅需要搜索少量的聯盟結構就解決了OCSG問題。

表3 不同agent個數下CCG算法的運行時間和搜索次數Tab.3 Running time and search times of CCG algorithm with different agent numbers

圖1 不同agent個數下CCG算法運行時間Fig.1 Running time of CCG algorithm with different agent numbers

圖2 不同agent個數下CCG算法搜索次數Fig.2 Search times of CCG algorithm with different agent numbers

圖3 是固定k值為8 到10 得出的實驗數據，它說明了在k值固定的情況下，CCG 算法的搜索次數與agent個數基本呈線性關系。這與定理3 中證明的算法復雜度是O(n2k+1)相符合的，并且是固定參數可解的，同時也是CCG 算法的優點之一。

圖3 k值固定時不同agent個數下CCG算法搜索次數Fig.3 Search times of CCG algorithm with different agent numbers under fixed k value

4.2.2k值對CCG算法性能的影響

研究使用的kOCF 博弈模型是一種限制了聯盟結構中聯盟最大數量的博弈，所以k值的取值范圍也可能是影響CCG算法的重要因素之一。本文在不同agent數目下對不同k值的CCG 算法進行了實驗測試。實驗結果如圖4 所示，可以分析得到以下結論：在k值較小的情況下，CCG 算法的運行時間基本與k值呈指數關系。當k值較大的時候，k值的增長對CCG算法搜索次數的影響逐漸變小，這也從側面驗證了CCG 算法復雜度證明的正確性。

這是由于定理3 是在最壞假設下證明的，其中每個玩家擁有的權值都為Wmax且與k值相等。在實際實驗中，雖然k值是逐漸增大的，但生成的玩家權值集合是固定的。不失一般性，在算法實驗中假設每個玩家的可能的最大權值為4，且玩家權值是符合均勻分布的，即每個玩家擁有的權值都會小于k。相比于最壞情況下的假設，實際情況k值對CCG 算法搜索次數影響更小，所以隨著k值的增大，CCG 算法的搜索次數增長速度逐漸減緩。

圖4 不同k值下的CCG算法搜索次數Fig.4 Search times of CCG algorithm under different k values

4.2.3 聯盟值分布對CCG算法性能的影響

Rahwan 等［25］研究發現，對于他們提出的IP（Integer-Partition based）算法如果實驗使用的聯盟值數據符合正態分布和均勻分布，算法會生成更小聯盟數量的解，從而，他們得出了某些算法實驗聯盟值分布如果采用正態分布和均勻分布定義可以優于其他算法的結論。

CCG 算法最重要的一步是根據玩家編號不同的分布情況，按照最大玩家權重原則生成聯盟結構并挑選出聯盟值最大的聯盟結構，所以聯盟值分布也是可能影響算法性能的因素之一。接下來的實驗研究了不同聯盟值分布對CCG 算法性能的影響。具體來說，本文使用了文獻［13，25］中的以下標準分布：

1）Normal：v(C)～|C|× N(μ，σ2)，其中μ=1且σ=0.1。

2）Uniform：v(C)～|C|× U(a，b)，其中a=0且b=1。

3）NDCS：v(C)～N(μ，σ2)，其中μ=|C|且σ=

然后取玩家集合中agent 個數從16 增加到20，其中聯盟最大數量k值取為，玩家的權值集合W符合均勻分布。對以上三種聯盟值分布分別進行了實驗并統計運行時間和搜索次數。

綜合分析圖5和圖6中的數據很容易得到以下結論：CCG算法在聯盟值為NDCS 類型分布的情況下擁有較短的運行時間和較少的搜索次數，即更好的算法性能。

圖5 不同聯盟值分布下CCG算法運行時間Fig.5 Running time of CCG algorithm under different coalition value distributions

圖6 不同聯盟值分布下CCG算法搜索次數Fig.6 Search times of CCG algorithm under different coalition value distributions

4.3 算法對比

為了更好地體現CCG 算法的有效性和適用性，將CCG 算法和Zick 等［10］基于有界樹寬通信圖約束提出的OCSG 算法進行了方法類型、約束條件等以下方面的對比分析，如表4所示。

兩種算法使用的貪心方法和動態規劃方法都是解決OCSG 問題有效的方法之一。兩種算法同樣都使用了離散化OCF博弈模型，該模型更有利于進行復雜的理論分析。OCSG問題中約束條件是必不可少的，它可以有效地縮小算法的搜索范圍。通信圖約束是指在通信圖中只有鄰接點之間才可以形成聯盟。這種約束固定了聯盟結構中聯盟的種類和agent成員，而玩家系列約束實際是對玩家和任務等級的一種排序，相比之下玩家序列約束較為寬松且適用于多種情景。

表4 CCG算法和Zick等［10］提出算法的對比Tab.4 Comparison between CCG algorithm and the algorithm proposed by Zick et al.［10］

時間復雜度的計算與約束條件息息相關，CCG 算法中約束了聯盟結構中最大聯盟數量，且模糊了聯盟中agent的資源分配（聯盟c的分量是0或1），再加上重疊聯盟博弈本身agent權值限制，可以很好地限制聯盟結構的生成規模，它的時間復雜度只和agent個數n和最大聯盟數量k有關，且固定參數k可解。Zick提出的算法只討論了聯盟中最大agent數量k′=2和k′=3的情況，從通信圖葉子節點到根節點分別使用動態規范的方法進行計算，它的時間復雜度與agent最大權值Wmax和當前節點i的子節點數目|Ci|有關。當k′值比較大時，Zick 提出的算法過程就顯得極其復雜。CCG算法是通過插入玩家編號來生成最優聯盟結構，適用于需要計算最優聯盟結構中的聯盟種類和成員的博弈。Zick提出的算法是基于有界樹寬通信圖上的計算，適用于需要計算出agent 之間合作程度（agent 資源分配情況）的博弈。總的來說，相對于Zick 提出的算法，CCG算法擁有更好的適用性。

5 結語

本文主要研究了OCF 博弈中最優聯盟結構生成問題。為了簡化計算問題，使用了約束了最大聯盟數量的離散OCF博弈。對于滿足玩家序列定義的kOCF 博弈，引入了一種相似度度量來度量任意一對聯盟結構之間的相似度。基于這種相似度量又定義了單調性性質，該性質認為與最優聯盟結構相似度越高的聯盟結構的值越大。針對單調kOCF 博弈，利用貪心方法提出了CCG 算法來解決OCSG 問題。并通過實驗分析了agent 個數、最大聯盟數量k和不同聯盟值分布對算法性能的影響，實驗結果驗證了CCG算法的搜索次數與agent個數基本呈線性關系這一優點，這說明算法是固定參數可解的。最后通過與Zick 提出的算法在約束條件等多方面的對比，說明了CCG算法擁有更好的適用性。

有多種方法可以進行進一步的研究。目前使用的模型是kOCF 博弈，該博弈對參與者的序列有一定嚴格的設定，但在許多聯盟博弈中，玩家是無序的。如何將所提出的方法推廣到這類博弈中仍有待研究。在agent 個數和玩家最大權值較大的情況下，隨機生成單調的kOCF 博弈在實際中運行時間是比較長的，如何快速地生成這種博弈也是可以進一步研究的。