中文摘要：

组合合作对策是一类建立在组合优化模型上的合作对策，而计算复杂性是衡量这类合作对策解的合理性的一个重要标准。本项目将从算法和计算复杂性角度对组合合作对策进行讨论一是研究现有对策模型中有关对策解的计算复杂性公开问题；二是探讨在某些对策解集为空集或关于解的计算是NP-困难的情况下，如何建立合理的对策近似解的概念及其有效算法；三是建立具有实际应用背景的新的组合合作对策模型，并研究相应的算法和复杂性问题。本项目属于对策论、组合最优化和理论计算机的交叉领域，是国际上的一个前沿研究方向。项目的预期成果，将为组合合作对策提供一些新的思想、研究方法和理论结果，并具有很好的应用前景。

结论摘要：

组合合作对策是一类建立在组合优化模型上的合作对策，计算复杂性是衡量这类合作对策解的合理性的一个重要标准。本项目从算法和计算复杂性角度对若干组合合作对策模型及相应的对策解进行了讨论一是研究现有对策模型中有关对策解的计算复杂性公开问题，并探讨在关于解的计算是NP-困难的情况下，如何建立合理的对策近似解的概念及其有效算法；二是建立具有实际应用背景的新的组合合作对策模型，并研究相应的算法和复杂性问题。项目的主要结果有1）经典的网络流对策中核子的算法和计算复杂性；2）覆盖对策的均衡性刻画，及关于核心的计算和判定等问题的算法和计算复杂性；3）若干对策模型具有稳定核心的充要条件和核心稳定性判定的计算复杂性；4）新的对策解（多项式可判定核心）的定义和相关性质。本项目属于对策论、组合最优化和理论计算机的交叉领域，是国际上一个前沿研究方向。项目研究中对于核心和核子计算的公开问题的解决为组合合作对策提供一些新的研究方法和理论结果；对于新模型和新的对策解的研究则拓宽了研究问题的广度。这些成果，推动了这一领域的研究，并具有较好的应用前景。