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

项目名称： 基于联盟结构组合合作对策的算法研究

项目编号： No.11271341

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 方奇志

作者单位： 中国海洋大学

项目金额： 60万元

中文摘要： 现代计算机科学和网络技术的发展，促使算法成为对策论研究的重要组成部分。具有联盟结构的合作对策是当前国际上热点研究领域，本项目从算法和计算复杂性角度对这一领域的问题进行深入研究，所涉及的对策模型是具有组合优化背景的组合合作对策。项目主要研究内容包括：1）在给定的联盟结构下，合作对策近似解的计算复杂性和近似算法；2）基于联盟结构的对策解（将联盟稳定性与支付合理性两部分作为整体同时考虑）的计算复杂性和算法；3）基于机制设计理论的合作联盟形成机制问题的算法。这三方面内容紧密关联，是一个有机的整体。本项目属于对策论、组合最优化和算法理论的交叉领域。项目的预期成果，将为合作对策提供一些新的思想、研究方法和理论结果，并具有广泛的应用前景。本项目的研究也将推动国内在该领域研究的发展。

中文关键词： 组合合作对策；对策解；算法；计算复杂性；机制设计

英文摘要： 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.

英文关键词： combinatorial optimization game；solution；algorithm；computational complexity；mechanism design