基于联盟结构组合合作对策的算法研究

With the development of compter science and network technology, algorithim approach has been promoted to be one of the most important parts in the research of Game Theory. Currently, study on coalition sturcture in coooperative game models has proven a hot area and has attracted more and more attentions. In this project, we study the algorithmic and complexity aspects of coalition structure problems in combinatorial cooperative games, where the game models are estabilished on some combinatorial optimization problems. The main content of this project is as follows: 1) Under some given coalition structures, we study the algorithmic and complexity issues on approximate game solutions; 2) We also study algorithm and complexity on game solutions with coalition structures, i.e., considering the stability of coaltion and rationality of players' payoff as a whole; 3) Making use of the theory of mechanism design, we study the algoirhtms on the problems of coalition forming. The three parts are closely inter-related, and can be regarded as integrity. The anticipated results will shed some new light on the research ideas, techniques and methodologies. The study of this project has extensive applied foreground, and will promote domestic development in this research area.

现代计算机科学和网络技术的发展，促使算法成为对策论研究的重要组成部分。具有联盟结构的合作对策是当前国际上热点研究领域，本项目从算法和计算复杂性角度对这一领域的问题进行深入研究，所涉及的对策模型是具有组合优化背景的组合合作对策。项目主要研究内容包括：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余名，组主办了两次算法博弈和运筹学算法方面的学术研讨会，邀请国际知名专家讲学并组织定期的研讨班，积极参与国内外学术会议和交流研讨，积极推动国内组合优化和算法博弈领域的发展。