信任和效用關系約束的聯盟結構生成

童向榮 任子儀

(煙臺大學計算機與控制工程學院 煙臺 264005)

1 引言

5G網絡切片、導頻分配和云計算等資源分配問題是研究的熱點，但是該問題通常是NP難的，近年來，聯盟和可信聯盟逐漸被應用到資源分配領域，智慧等人[1]用聯盟分裂形式的思想，即隨機劃分的方法提出了一種聯合用戶分組和聯盟博弈的動態導頻分配方案，用戶被分成若干個互不相交的子聯盟。聯盟形成(Coalition Formation, CF)是多智能體系統(Multi-智能體 System, MAS)的重要研究內容之一，通過對智能體集合進行劃分得到聯盟結構(Coalition Structure, CS)，其中包含若干不相交的集合，即聯盟(Coalition, C)。CF的過程通常以最大化社會福利和個體效用為目標[2]，稱為聯盟結構生成(Coalition Structure Generation, CSG)。合作博弈論是CF研究的基礎，例如特征函數博弈[3]、不可轉移效用的博弈[4]和享樂博弈[5]。聯盟博弈論一般假設特征函數具有超加性，即生成的主聯盟是最優的。核[6]、Shapley值[7]為聯盟博弈提供了劃分收益的解決方案。最近，研究人員考慮特征函數不是超加性的情況，有的模型使用對稱可加性可分離特征博弈[8]。

CSG存在著諸多約束[9]，如通常情況下信任是合作的基礎，信任是一方對另一方實現承諾的主觀評估。信任程度越高越容易形成長期穩定的合作關系，而信任的傳遞性可以促進不熟悉的智能體之間的合作關系。信任關系對最終效用有直接的影響，因而，將信任信息融入到效用中是合理的。王海艷等人[10]提出了基于可信聯盟的服務推薦方法，將信任關系融入相似度計算；Sless等人[11]將社交關系引入聯盟形成，負值社交關系表示合作很難成功。童向榮等人[12]和Wang等人[13]對信任傳遞的特性進行了研究。Mao等人[14]提出信任傳遞取最小信任值或信任值相乘的方式，信任聚合取最大信任值或對多條路徑信任值進行加權平均。

近年來，研究人員在圖上研究博弈，假設有向帶權圖的邊表示智能體之間的關系。邊收縮方法可以枚舉智能體集的所有可行分區，Karger[15]應用該方法解決Min-Cut問題，但未應用在聯盟形成中。圖割將圖劃分為互不相交的區域，在同一區域內的特征具有較高的相似性，而不同的區域內的特征則具有明顯的差異性，其原理正是一種劃分。受圖割s-t-cut算法的啟發，研究了基于信任和效用關系約束的CSG，在保證智能體理性和聯盟穩定(無塊)的情況下，使用信任和效用關系對網絡進行切割，從而形成聯盟。由此，提出了兩種多項式時間的精確算法：信任約束下CSG和信任效用關系約束下CSG，均能夠求解設定情況下的最優CS。仿真實驗結果驗證了所提方法的有效性。

本文主要貢獻：(1)將CF的效用關系擴展為信任和效用關系，即不僅關注效用約束，還關注信任約束，并用信任和效用二元組表示，以此作為CSG的依據。(2) 在保證智能體個體理性和聯盟穩定(不存在塊)的前提下，用分割信任網絡的方法，生成有k個聯盟的穩定CS，提出了兩種多項式時間的精確算法。

2 基本定義

傳統的聯盟形成只基于效用關系，沒有考慮社交關系對效用的影響，近年來，學者們注意到社交關系對合作成功有必然的影響，因此，信任關系應該與效用關系一起考慮，這能提高聯盟形成的效率和速度。

如果CS的智能體可以通過組建一個新聯盟，在不降低新聯盟內其它智能體收益的前提下，達到提高自身收益的目的，那么這個新聯盟將破壞原有的CS，該CS是不穩定的。而這個新聯盟是有更大信任和效用值的聯盟，稱為塊。

圖1 不同聯盟結構的效用

圖2 智能體信任網絡

根據定義3易知，如果有一個聯盟是塊，那么CS中的智能體傾向于離開原聯盟而形成新的聯盟，這說明塊破壞了聯盟結構的穩定性，因此在滿足超加性的前提下，沒有可能的塊就成為了聯盟穩定的條件。若聯盟的數量固定為常數k，則不允許出現塊，要求智能體集合恰好生成k個聯盟，當k＝2時，分別記為聯盟s和t，s和t組成新的聯盟結構。

3 信任傳遞

圖3 2-聯盟核成員

信任網絡中，智能體之間能否形成聯盟與其信任值直接相關，信任值越大，概率越高，通過歸一化處理后，ai與aj在t時刻能夠形成聯盟的條件概率記為pij(t)。

圖4 信任網絡

可以證明h步信任生成概率，證明：根據邊緣分布

4 MT-s-t-cut和MTU-s-t-cut算法

定義5k-切割:Cut2(C1,C2)表示將信任網絡G根據信任值切割成互不相交的兩部分，每部分組成一個聯盟，稱為2-切割。Cutk(C1,C2,···,Ck)表示將信任網絡G切割成互不相交的k個部分，組成k個聯盟，稱為k-切割。

4.1 MT-s-t-cut算法

表1 算法1：MT-s-t-cut算法

4.2 MTU-s-t-cut算法

除了考慮信任對于社會福利的影響，還應該綜合考慮信任和效用關系。給定信任網絡G＝＜A,E,ω,ρ ＞，cf(p)為尋找路徑的殘余容量 (路徑p中最小的切割對象，此處為信任效用關系)。根據G的信任關系和效用關系計算Pij和?ij。然后計算智能體之間的信任和效用關系fρ,ω(ai,aj)。循環智能體點，根據fρ,ω(ai,aj)的值進行圖割，并輸出最優社會福利的CS及其最優社會福利值。具體步驟見表2的算法2。

表2 算法2：MTU-s-t-cut算法

算法2的詳細描述：第(1)步，算法初始化。根據式(1)–式(4)計算得到聯盟形成的生成概率Pij與智能體之間的效用值?ij；第(2)步，將第(1)步計算結果應用于信任效用關系函數的計算，綜合考慮信任和效用關系在聯盟形成過程中的影響；第(3)步，根據信任效用關系將智能體集劃分為互不相交的兩部分，即兩個聯盟，并輸出最優社會福利的CS及其最優社會福利。

5 實驗

仿真實驗驗證了智能體數量、算法運行時間與最終得到的社會福利之間的關系，并與幾種典型算法進行了對比，驗證了所提算法的效率。

5.1 實驗環境與數據

計算機的系統環境是Windows7，64位操作系統，8 GB內存，3.2 GHz主頻，i5-6500英特爾處理器。軟件設計采用Java程序語言，Eclipse運行環境。實驗數據規模即為智能體數量，隨機生成從1個到25個智能體，實驗數據滿足超加性，智能體數量最大設置為25個，25個智能體的聯盟結構生成，如果使用精確算法，DP和ODP-IP需要的時間是325，是指數級的，本文提出的算法的復雜度是2 53，是多項式級的。

實驗所用方法為求解s-t-cut的經典算法最大流FF(Ford-Fulkerson)算法，圖的最小cut問題可以轉換為最大流問題，即最小割問題和最大流問題是等價的。

5.2 對比算法

本文所提算法與以下幾種算法進行對比。

(1) 動態規劃法(Dynamic Programming,DP)：Yeh[17]提出使用DP方法用于解決完整的集合劃分問題，進而求解CSG問題，通過DP所求得的聯盟結構為最優聯盟結構。

(2) ODP-IP算法：Michalak等人[18]在2015年結合任意時間算法和DP方法開發的一種稱為ODPIP的算法。

(3) MT-s-t-cut算法：本文提出的第1個算法。

(4) MTU-s-t-cut算法：本文提出的第2個算法。

(5) CSG-UCT算法：Wu等人[19]在2020年基于蒙特卡羅樹的搜索方法。

5.3 評價指標

將效用和時間作為評估CSG的指標。一方面研究信任對聯盟效用的影響，另一方面研究智能體的基|A|對社會福利和算法運行時間的影響。

5.4 參數設置與實驗結果

0＜ρ ＜0.5為低信任關系，0.5≤ρ ＜1為高信任關系，而高低信任為同時存在高、低信任關系。

5.4.1 |A|對社會福利的影響

如圖5所示，橫坐標表示智能體數量，縱坐標表示生成的聯盟結構社會福利。

通常情況下，社會福利隨著智能體數量增加而增加。分析圖5易知，隨著|A|的數量增多，MT-st-cut算法、MTU-s-t-cut算法和DP算法的社會福利均增加，并且增幅基本一致。這說明在CSG過程中，智能體具有個體理性，即符合超加性原則。

圖5 |A|對社會福利的影響

5.4.2 |A|對運行時間的影響

通過信任網絡，分別對不同數量的智能體集進行CSG，記錄CSG所需的時間。圖6表示兩種算法的智能體數量與運行時間的關系，圖7表示MT-s-tcut算法與MTU-s-t-cut算法的運行時間對比，3個圖的橫坐標表示CSG的智能體數量，縱坐標為算法運行時間，單位為ms。

分析圖6的易知，隨著|A|的增大，兩種算法的運行時間均相應增加，但不受信任關系的影響。觀察圖7，易知MTU-s-t-cut的算法運行時間一直比MT-s-t-cut算法的運行時間短。原因在于，使用信任效用函數后，智能體間的非對稱信任效用關系被轉換為對稱關系，節省了最后一步生成聯盟的時間。

圖6 兩種算法的智能體數量與運行時間的關系

圖7 算法運行時間對比

5.4.3 運行時間對比

由圖8可知，隨著智能體數量的增加，DP算法和ODP-IP算法的工作量增加量要遠大于MT-s-t-cut算法和MTU-s-t-cut算法。

圖8 工作量對比

運行時間如圖9所示，橫坐標表示智能體數量，縱坐標表示運行時間，單位是ms。如圖9所示，所提兩種算法的運行時間遠小于DP算法與ODP-IP算法，并且隨智能體數量的增加效果越明顯。

圖9 前4種算法時間對比

Wu等人[19]在2020年基于蒙特卡羅樹的搜索方法對聯盟結構圖進行采樣迭代展開搜索樹，提出一種可擴展的Anytime聯盟形成方法。CSG-UCT算法找到最優解的時間取決于實驗的迭代次數，每次迭代都需要進行一次蒙特卡羅樹搜索過程，在尋找最優解的過程中需要進行大量的迭代。當智能體數量越多時，需要的時間越多。CSG-UCT算法與MTU-s-t-cut算法時間對比如圖10。隨著智能體數量的增多，MTU-s-t-cut算法運行時間遠少于CSGUCT算法，智能體數量越多，運行效果越明顯。

圖10 與CSG-UCT算法對比

6 結束語

本文研究了基于信任和效用關系的CSG問題，給出了兩個多項式時間算法計算最優聯盟結構。根據信任的傳遞性進行信任和效用的傳遞；然后對傳遞后的信任網絡進行圖割，得到最優社會福利的聯盟結構。最后通過仿真實驗，驗證了信任關系能夠影響CSG的過程，并對所得聯盟結構的社會福利造成影響。隨智能體數量的增加，算法的運行時間相應增加，但遠小于DP算法和ODP-IP算法的運行時間。聯盟結構中聯盟核問題及其穩定性進行分析會是未來的研究重點。