《基於聯盟結構組合合作對策的算法研究》是依託中國海洋大學，由方奇志擔任項目負責人的面上項目。
基本介紹
- 中文名：基於聯盟結構組合合作對策的算法研究
- 項目類別：面上項目
- 項目負責人：方奇志
- 依託單位：中國海洋大學
中文摘要,結題摘要,
中文摘要
現代計算機科學和網路技術的發展，促使算法成為對策論研究的重要組成部分。具有聯盟結構的合作對策是當前國際上熱點研究領域，本項目從算法和計算複雜性角度對這一領域的問題進行深入研究，所涉及的對策模型是具有組合最佳化背景的組合合作對策。項目主要研究內容包括：（1）在給定的聯盟結構下，合作對策近似解的計算複雜性和近似算法；（2）基於聯盟結構的對策解（將聯盟穩定性與支付合理性兩部分作為整體同時考慮）的計算複雜性和算法；（3）基於機制設計理論的合作聯盟形成機制問題的算法。這三方面內容緊密關聯，是一個有機的整體。本項目屬於對策論、組合最最佳化和算法理論的交叉領域。項目的預期成果，將為合作對策提供一些新的思想、研究方法和理論結果，並具有廣泛的套用前景。本項目的研究也將推動國內在該領域研究的發展。
結題摘要
具有聯盟結構的合作對策是當前國際上研究熱點。本項目從算法和計算複雜性角度對這一領域的問題進行研究，所涉及的對策模型是具有組合最佳化背景（特別是網路最佳化）的組合合作對策。主要研究內容包括：一是在給定的聯盟結構下合作對策近似解和基於聯盟結構的對策解的計算複雜性和算法；二是基於機制設計理論的聯盟形成機制的算法。 本項目的主要成果有以下幾個方面： （ 1）針對閾值匹配合作對策，利用線性規劃對偶和匹配理論給出了有關對策解Least-core、Nucleolus的刻畫和有效求解算法；證明了一般圖上閾值匹配對策的Shapley值計算是#P-hard、而在某些特殊圖類上存在有效算法； （2）針對點、邊通路聯盟對策，給出了具有聯盟結構的Core和Least-core的刻畫和相應算法，得到了Least-core和相應非合作攔截對策的Nash均衡之間的對應關係；建立了通路聯盟對策與網路流對策的Nucleolus之間的關係、由此給出通路聯盟對策的Nucleolus的多項式時間算法； （3）基於箱覆蓋問題，建立箱覆蓋合作對策模型並給出其具有聯盟結構的Core和Least-core的算法和計算複雜性，特別研究了Least-core的值的近似算法；針對具有自私局中人的箱覆蓋問題/裝箱問題，給出了具有較好PoA的機制設計方案和理論分析； （4）將對策理論和算法套用到實際問題中，其一是研究了社會傳播網路中對策模型，研究了近似Nash均衡的求解算法；其二是利用進化對策理論，建立基因網路中團的結構與關鍵致病基因模組之間的關係，並通過數值實驗驗證結果的有效性。 本項目共完成發表（或線上發表）相關學術論文19篇。本項目研究的內容屬於對策論、組合最最佳化和理論計算機的交叉領域，項目取得的成果可為合作對策提供一些新的思想、研究方法和理論結果，也具有較好的套用前景。項目組培養相關領域研究生10餘名，組主辦了兩次算法博弈和運籌學算法方面的學術研討會，邀請國際知名專家講學並組織定期的研討班，積極參與國內外學術會議和交流研討，積極推動國內組合最佳化和算法博弈領域的發展。
