李壯闊，常凱旋

桂林電子科技大學 商學院，廣西 桂林541004

1944年，von Neumann和Morgenstern的專著Theory of games and economic behavior的問世，標志著博弈論的誕生。在該書中，作者用大量篇幅討論了合作博弈的相關理論，同時考慮了聯(lián)盟的內部穩(wěn)定性和外部穩(wěn)定性，從占優(yōu)的角度提出了穩(wěn)定集，這為合作博弈的發(fā)展奠定了理論基礎[1]。此后，許多學者從不同方向探討了合作博弈的解概念。合作博弈求解的核心思想是合作均衡，經典合作博弈的解概念可以分為兩類：以核為代表的優(yōu)超法和以Shapley值為代表的賦值法[2]。占優(yōu)法以“占優(yōu)”和“異議”為主要準則，體現(xiàn)了穩(wěn)定性和聯(lián)盟信息。Gillies考慮局中人的個體理性和聯(lián)盟的有效性，從占優(yōu)角度出發(fā)，提出核的概念來研究穩(wěn)定集[3]。Aumann和Maschler將分配結果的形成過程視作局中人的談判過程，提出了談判解，體現(xiàn)了分配方案的合理性[4]。Davis和Maschler通過引入了內核的概念來研究談判解，主要分析了不同局中人對分配方案異議大小的度量的相關問題[5]。Schmeidler提出了核仁的概念，利用超出值來度量局中人對分配方案的不滿意程度，從而找出聯(lián)盟對分配方案集中不滿意程度最低的分配方案[6]。賦值法構造一種考慮沖突各方要求的折中的合理結果，通過公理化方法描述解的性質，進而得到唯一的分配方案。Shapley從分配方式的合理性與公平性出發(fā)，通過不同局中人對聯(lián)盟的邊際貢獻來計算局中人的分配，提出了Shapley值[7]。Myerson提出并研究了具有圖限制結構的合作博弈，在Shapley值基礎上給出了圖限制結構合作博弈的解——Myerson值[8]?；贛yerson的工作，Herings利用圖限制博弈和有向樹定義了平均樹解（A-T解）[9]。Banzhaf考慮聯(lián)盟中各局中人的權力不同，將局中人的權力大小看作獲勝聯(lián)盟中的關鍵加入者的個數(shù)，使用權力指數(shù)比來刻畫Banzhaf權力指數(shù)[10]。

經典的合作博弈解概念中的假設與現(xiàn)實博弈環(huán)境相比過于簡單，并且沒有考慮到現(xiàn)實中聯(lián)盟的形成方式。英國著名經濟學者布勞格認為：博弈論的全部力量都用于滿足經濟學家對形式主義模型的沉溺，卻不關心模型的現(xiàn)實性如何[11]。合作博弈的求解目標是要找到一個能夠形成與維系聯(lián)盟的分配方案?，F(xiàn)實中，聯(lián)盟分配方案的達成通常是局中人互相影響，不斷調整、妥協(xié)和趨同的互動過程。如何描述局中人為了合作而競爭，同時又在談判中趨同是建立合作博弈求解模型的難點。近年來，有學者嘗試將復雜的多目標優(yōu)化問題模型與合作博弈結合在一起。葉文海等提出Isight的博弈多目標優(yōu)化設計方法，通過合作博弈模型解決多目標系統(tǒng)的求解問題，建立了兩者之間的聯(lián)系，并用遺傳算法進行求解[12]。劉雨瀟等針對云任務調度優(yōu)化問題，提出一種基于納什議價解的多目標合作博弈調度算法[13]。潘穎慧等研究了不確定性多智能體在交互環(huán)境下如何優(yōu)化本身決策，并總結歸納了模型的具體表達方式和求解方法，克服了傳統(tǒng)的博弈論求解多智能體決策的局限性[14]。侯德飛等將合作博弈理論應用于部隊彈藥調度策略問題之中，分別建立合作、競爭合作競爭博弈框架，并用遺傳算法對模型進行求解[15]。Xu等將執(zhí)行器的控制精度優(yōu)化問題看作一種多目標優(yōu)化問題，結合合作博弈理論提出了一種分布式模型預測方法[16]。丁陽等針對配電網重構問題，將目標函數(shù)作為合作博弈的局中人，通過螢火蟲算法計算最終的重構方案[17]。

現(xiàn)實中聯(lián)盟最終分配方案的達成通常是局中人基于個體理性與判斷進行多輪談判，互相影響、相互妥協(xié)、最終趨同的結果。對此，本文將合作博弈的求解過程視作局中人個體博弈和群體趨同的多目標優(yōu)化問題?？紤]到談判過程中局中人的個體調整和群體趨同行為，引入分配方案、理性因子與控制因子等現(xiàn)實影響因素，構建考慮互動行為的合作博弈模型。在此過程中，對傳統(tǒng)連續(xù)優(yōu)化蟻群算法進行改進，提出合作博弈的連續(xù)蟻群優(yōu)化算法對合作博弈模型進行求解。

1 考慮互動行為的合作博弈模型

傳統(tǒng)的合作博弈模型是基于團隊合作的求解，是集中控制下的資源配置。這種方法存在一個問題，集中配置很容易引發(fā)不滿，影響局中人間的合作關系。從多個局中人競爭的角度研究聯(lián)盟分配問題是新的思路，但也需滿足合作的要求。相比于傳統(tǒng)的求解方法，建模的難點在于如何分析局中人競爭行為與達成共同接受的分配方案兩者的協(xié)調關系。

聯(lián)盟中的利益分配過程實際上是一種談判協(xié)商過程，聯(lián)盟成員會在分配利益時進行談判博弈。博弈的基本要素有局中人、局中人的分配方案、信息和行動等。在談判開始前，局中人會根據(jù)信息及偏好提出預分配方案。受局中人個體理性，個體偏好和成員關系等因素影響，不同局中人對最優(yōu)策略的評判標準往往各不相同。因此，在求解過程中需要一個確定的適應度函數(shù)作為分配方案的統(tǒng)一評價標準。在每輪談判過程中，使用談判檔案作為局中人的間接通訊機制，談判檔案可以提供信息流通的渠道進而實現(xiàn)局中人在談判中的互動行為。局中人通過對談判檔案中的信息進行收集和處理，得到個體最優(yōu)信息和群體最優(yōu)信息，依據(jù)自身策略、理性、學習情況調整自己的分配方案。局中人對這兩種信息的重視程度分別體現(xiàn)了局中人的兩種博弈態(tài)度。第一種為競爭，局中人追求更高的個人收益，會更看重個體最優(yōu)信息；第二種為合作，局中人更希望達成合作，會更看重群體最優(yōu)信息。現(xiàn)實中，局中人對兩種信息的重視程度會隨局勢不斷變化，通常表現(xiàn)為前期更看重個體最優(yōu)信息，后期更看重群體最優(yōu)信息。最終，通過多輪談判實現(xiàn)分配方案的趨同。

n人合作博弈記作(N,v)，參與博弈的人稱為局中人，所有局中人構成了局中人集N={1,2,…,n},N的任意一個非空子集S為一個聯(lián)盟，由全體局中人組成的聯(lián)盟稱為大聯(lián)盟N。大聯(lián)盟給局中人j分配的收益記為x({j}),x({j})表示局中人j不加入任何聯(lián)盟時獲得的最大收益，v(S)表示聯(lián)盟S獨立活動時獲得的最大收益。下面本文將對考慮互動行為的合作博弈模型的相關概念進行定義，并證明相關定理。

在第m輪談判中，設局中人i提出的分配方案為表示局中人i給j分配的收益，分配方案應滿足以下約束：

式（1）為分配方案的有效性約束，即聯(lián)盟將收益全部分配給聯(lián)盟成員。式（2）為分配方案的個體理性約束，即局中人的分配不小于自己單干或加入小聯(lián)盟時的收益。所有局中人提出的分配方案構成了分配方案矩陣Xm：

在談判過程中，局中人對某條分配方案的評價標準主要考慮兩個要素，即個體最優(yōu)信息和群體平均信息。

定義1個體最優(yōu)信息體現(xiàn)了局中人對自己收益最大化的追求，局中人i的個體最優(yōu)分配方案是在除了局中人i自己所提出的分配方案外的其他分配方案中，使局中人i收益最大的分配方案。即在第m輪談判協(xié)商中，找出當前分配方案矩陣中對局中人i分配收益的最大值該最大值所在的分配方案為局中人i的個體最優(yōu)分配方案，記為局中人對個體最優(yōu)信息的學習表示為

定義2群體平均信息為聯(lián)盟對局中人的收益分配的平均值，體現(xiàn)了聯(lián)盟整體對個體的判斷與偏好，即

定義3分配方案的適應度定義為局中人對分配方案的滿意程度，第i條分配方案的適應度為：

在談判過程中，本文采用談判檔案作為局中人間的信息交流機制，從而實現(xiàn)局中人在談判過程中的互動行為。采用這種非直接通信的方式好處在于當局中人的數(shù)目增加時，整個系統(tǒng)的通信開銷的增幅較小，使得群體智能算法具有較好的擴展性。談判檔案的結構包括分配方案和適應度兩個部分。談判檔案的構造過程為：通過適應度函數(shù)計算分配方案的適應度，按照適應度從小到大的順序對分配方案排序，將分配方案和適應度存入談判檔案中。具體形式如圖1所示。

圖1 談判檔案結構Fig.1 Structure of solution archive

定義4群體最優(yōu)信息為使聯(lián)盟群體最滿意的一條分配方案，即適應度最小的分配方案，也是談判檔案中第一條分配方案，記為局中人對個體最優(yōu)信息的學習表示為

在現(xiàn)實博弈世界中，由于局中人在個體信息、形勢判斷、利益訴求等方面與理想狀態(tài)存在差距，因此局中人在談判過程中追求的是有限理性。在談判過程中，局中人會對個體最優(yōu)信息和群體最優(yōu)信息進行一定程度的學習。本文使用理性因子來描述局中人的有限理性，使用控制因子來描述局中人對不同信息的學習程度。

定義6局中人的控制因子θm(θm∈[0,1])表示局中人對個體最優(yōu)信息和群體最優(yōu)信息的偏重程度，體現(xiàn)了不同談判階段局中人對個體最優(yōu)和群體最優(yōu)追求的變化。通常局中人在談判前期更追求個體最優(yōu)分配，在談判后期為了維持聯(lián)盟而更側重群體最優(yōu)分配。較大的控制因子可以提高全局搜索能力，避免陷入局部最優(yōu)，較小的控制因子可以提高局部開發(fā)能力，從而加快收斂速度?？刂埔蜃拥娜≈捣绞接芯€性策略和非線性策略兩類，采用線性策略會使得控制因子在迭代過程中呈線性變化，易使收斂速度過慢和陷入局部最優(yōu)，無法適應實際情況。本文采用一種反余弦的非線性策略來調整控制因子，基本思想是前期加快控制因子的改變速度，從而較快地進入局部搜索，避免陷入局部最優(yōu)，后期通過較大的控制因子使算法更注重群體信息，保持解的多樣性。反余弦控制因子構造方式如下：

其中，mmax為預設的最大迭代次數(shù)，θs、θe表示控制因子的迭代初值和終值，在[0，1]范圍內取值且θe＞θs。當0≤θm≤1/2時，局中人更加重視個體最優(yōu)信息。當1/2＜θm≤1時，局中人更加重視群體最優(yōu)信息。

控制因子隨迭代次數(shù)變化曲線如圖2所示。由圖2可知，控制因子的變化幅度為[θs,θe]，當設定的θs＞1/2或θe＜1/2時，會導致算法只考慮一種最優(yōu)信息，影響算法的收斂精度與速度，因此在設定參數(shù)時需保證θs＜1/2＜θe。

通過控制因子對迭代次數(shù)m求導可知控制因子的變化速度為：

因此，控制因子的變化速度與(θe-θs)同向變化，與mmax反向變化。為了避免陷入局部最優(yōu)，前期加快控制因子的改變速度，(θe-θs)取值不宜過小，mmax取值不宜過大。

綜合群體最優(yōu)信息和個體最優(yōu)信息，局中人采用混合策略調整分配方案，局中人在第m輪談判的調整值為：

局中人在m輪談判后的分配方案為：

定理1談判過程中分配方案始終滿足有效性約束。

∴談判過程中分配方案始終滿足有效性約束。

定理2談判過程中分配方案始終滿足個體理性約束。

∴談判過程中分配方案始終滿足個體理性約束。

2 合作博弈的連續(xù)蟻群算法求解

連續(xù)蟻群算法是由Socha和Dorigo提出的一種用于求解連續(xù)變量組合優(yōu)化問題的智能優(yōu)化算法[18]，這種算法具有局部搜索能力強，收斂速度快等特點，目前已被許多學者應用到現(xiàn)實中的優(yōu)化問題之中。針對原始連續(xù)蟻群算法尋優(yōu)能力差、易陷入局部最優(yōu)等問題，許多學者從不同角度提出了改進方案。Mahamed等引入Lévy分布和隨機游走選擇機制提高了算法的全局搜索能力，避免了早熟[19]。夏媛等提出了一種基于跨鄰域搜索的改進連續(xù)蟻群算法，提高了算法的尋優(yōu)能力和穩(wěn)定性[20]。Can等將人工蜂群算法和遺傳算法與連續(xù)蟻群算法相結合，提高了算法的性能[21]。本文將對原始連續(xù)蟻群算法進行改進，引入理性因子與控制因子，并將其應用于合作博弈的求解之中。

在使用連續(xù)蟻群算法求解聯(lián)盟的收益分配問題時，將聯(lián)盟中的局中人視為一群螞蟻，螞蟻的爬行路徑視為該局中人的分配方案，該路徑上每個維度的值相當于對不同局中人分配的收益。每輪談判后螞蟻會根據(jù)個體最優(yōu)信息和群體最優(yōu)信息有偏向地調整自己前行的路徑，螞蟻對路徑的調整映射為局中人對分配方案的調整。理性的局中人既希望能達成共同接受的分配方案，又希望達成對自己效用最大的分配方案，既有共同目標，又有個體目標。在計算過程中，群體最優(yōu)信息體現(xiàn)出群體的共同目標，個體最優(yōu)信息體現(xiàn)出個體的不同目標，不斷調整局中人對兩種信息的學習程度體現(xiàn)了局中人選擇策略規(guī)則的變化。隨著不斷迭代調整，所有螞蟻匯聚在同一條路徑上，所有分配方案的適應度相等且取得最小值0，這條路徑所對應的分配方案即為被所有局中人接受的分配方案。

合作博弈的連續(xù)蟻群算法分為六步，具體求解步驟如下：

步驟1設置算法參數(shù)。設置理性因子、最大迭代次數(shù)、控制因子的初值和終值等初始參數(shù)。

步驟2所有局中人提出初始分配方案，為了使各局中人不會因為對分配方案不滿而退出聯(lián)盟，局中人提出的分配方案必須滿足個體理性和有效性。所有分配方案構成了分配方案矩陣X0。

步驟3計算分配方案的適應度，排序后存入談判檔案中。通過式（4）計算分配方案的適應度，按照適應度從小到大的順序對分配方案進行排序，將排序后的分配方案存儲在談判檔案中，此時談判檔案中分配方案的適應度滿足，根據(jù)談判檔案計算個體最優(yōu)信息和群體最優(yōu)信息。

步驟4判斷談判檔案中分配方案的適應度是否相等且為0。若是，此時談判檔案中所有分配方案相同，得到最優(yōu)分配方案，迭代結束。否則，進入下一步。

步驟5判斷是否達到預設的最大迭代次數(shù)。若達到最大迭代次數(shù)，無法取得令所有局中人都滿意的最優(yōu)分配方案，停止迭代，輸出談判檔案；否則，進入下一步。

步驟6構建新的分配方案。根據(jù)當前的個體最優(yōu)信息和群體最優(yōu)信息調整談判檔案中的分配方案，通過式（6）計算局中人的調整值，通過式（7）計算局中人的調整后的分配方案。轉至步驟3。

合作博弈的連續(xù)蟻群算法求解流程如圖3所示。

圖3 求解流程圖Fig.3 Solving process

3 算例分析

三家企業(yè)決定建立聯(lián)盟生產某種產品投入市場，單獨生產的收益為r1=1 200,r2=2 000,r3=900。兩兩合作生產的收益為r12=3 500,r13=1 600,r23=3 300。三家企業(yè)合作生產的收益為r123=4 540。當三家企業(yè)結成聯(lián)盟合作進行生產時，應如何分配聯(lián)盟的收益。

3.1 Shapley值法求解

Shapley值是目前應用最廣的合作博弈解概念，它根據(jù)局中人i對聯(lián)盟S的邊際貢獻來確定對局中人i分配的收益，具體計算方式為：

Shapley值法是一種衡量局中人邊際貢獻的均值方法，體現(xiàn)了分配方式的公平性，但對于非凸博弈來說，不能保證聯(lián)盟的穩(wěn)定性（即不能保證滿足聯(lián)盟個體和子聯(lián)盟的合理性）。在本例中，由Shapley值計算得到局中人1的分配為1 180，小于其單干時的收益1 200，因此聯(lián)盟會由于局中人1的退出而破裂。

3.2 改進連續(xù)蟻群算法求解

三家企業(yè)通過談判來分配收益。將連續(xù)蟻群算法的參數(shù)設置為理性因子在[0，1]范圍內隨機取值，最大迭代次數(shù)mmax=500，控制因子初值θs=0，終值θe=1。

設企業(yè)i提出的分配方案為xi=(xi1,xi2,xi3)，各企業(yè)提出的分配方案需要滿足個體理性和有效性：

其中，x·j表示分配方案對企業(yè)j的分配。三家企業(yè)根據(jù)自身的偏好在約束條件下提出各自的初始分配方案，形成初始分配方案矩陣：

根據(jù)式（4）計算各分配方案的適應度，按照適應度從小到大的順序將分配方案存入談判檔案中，談判檔案的形式為：

第一次談判后各分配方案的適應度不等于0，迭代次數(shù)未達到預設的最大迭代次數(shù)。進入下一輪談判，依次循環(huán)迭代134次，各分配方案的適應度函數(shù)為0，談判檔案中的分配方案不再變化，求解得到的最終談判檔案為：

圖4 給出了談判檔案中適應度最小的分配方案的適應度的收斂曲線圖。結果表明，適應度隨迭代次數(shù)不斷收斂，在迭代134次后趨于平穩(wěn)，三家企業(yè)的最終分配方案為[1 234.463 4，2 366.176 7，939.359 9]。

圖4 適應度隨迭代次數(shù)收斂圖Fig.4 Value of optimal objective function varying with iteration times

算例表明：連續(xù)域蟻群算法經過多次迭代后，談判檔案中的分配方案趨于一致并不再變化，即聯(lián)盟成員經過多次談判可以得到一條使全體成員都滿意的分配方案，且該分配方案滿足個體理性和有效性。

3.3 實驗結果分析

為增加對比性，分析本文算法有效性，采用MATLAB R2018a進行仿真實驗，對原始連續(xù)蟻群算法和文獻[20]基于跨鄰域搜索的連續(xù)蟻群算法與本文改進后的算法進行分析對比，得出以下實驗結果。各算法的適應度收斂曲線如圖5所示。各算法實驗數(shù)據(jù)如表1所示。

圖5 不同算法收斂曲線對比圖Fig.5 Comparison of convergence curves of different algrithms

表1 3種算法的實驗數(shù)據(jù)Table 1 Experimental data of 3 algorithms

實驗結果表明，在求解合作博弈問題時，相較于其他兩種算法，本文提出的改進算法跳出局部極值的能力強，收斂速度快，收斂精度高。相較于原始連續(xù)蟻群算法易陷入局部最優(yōu)，收斂速度慢，收斂精度低等缺點，本文提出的考慮互動行為等改進策略可以明顯提高算法的性能。

4 結束語

目前，合作博弈在理論研究和解概念的數(shù)量上取得了巨大發(fā)展，但有效的現(xiàn)實應用依然偏少。產生這種情況的原因很多，其中一個根本性原因是沒有考慮現(xiàn)實博弈環(huán)境中聯(lián)盟分配方案的形成過程。這是目前合作博弈研究中被忽略的研究領域，但也是一個非常有潛力且與現(xiàn)實中的合作問題更加契合的研究領域?？紤]到現(xiàn)實中合作收益（成本、風險等）的分配方案通常是經過多輪的談判形成的，本文基于策略博弈理論和優(yōu)化思想將合作博弈求解處理為基于個體博弈與群體趨同的多目標優(yōu)化問題，引入了理性因子和現(xiàn)實因子構建考慮互動行為的合作博弈求解模型，提出了合作博弈的連續(xù)蟻群優(yōu)化算法對合作博弈進行求解。相比合作博弈的經典解概念，這種求解思路與方法可以更好地描述局中人之間的互動決策行為，更加符合現(xiàn)實中自然人的博弈過程。這為求解合作博弈提供了新的思路與方法，對現(xiàn)實中人們描述、分析和預測聯(lián)盟分配時具有決策支持作用。