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

尚傳啟，劉驚雷

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

1 引言

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

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