合作对策(Cooperative Game),也称联盟对策,是理性局中人通过共同合作取得尽可能大的利益的竞争决策分析模型。在合作对策过程中,局中人要考虑如何结成联盟以及如何分配联盟的收益。一个合作对策模型表示为G=(N,g),其中,{}N=1,2,,n是局中人集合、g:2N?R是特征函数,满足g(?)=0。对于任意联盟SíN,g(S)表示联盟S中各局中人通过合作所能得到的最大收益。合作对策的核心问题是寻找一个或一组对总收益g(N)的公平合理的分配,使得每个局中人都按照这组分配来得到各自的支付。总收益g(N)的分配通常要求保证合作的稳定性,即任何局中人或局中人的联盟都不能通过逃离整体联盟合作而获得更多收益。总收益的各种不同的分配被称为对策的解。从稳定性角度来定义的合作对策解主要有:核心(core)、Least-核心(Least-core)、核仁(nucleolus)等。给定对策G=(N,g)的某个解p,从算法和计算复杂性角度主要有以下三个问题:　　(1)非空性判定问题:如何判断解p是否存在或p是否非空?　　(2)构造性问题:如果解p存在或非空,如何求解出p中的某个分配?　　(3)归属性判定问题:给定一个总收益的分配,如何判断它是否属于p?　　本文主要研究一类基于网络的合作对策模型:通路对策模型。通路对策定义在一个有向图()D= V,E;s,t上,其中V,E分别是图D的顶点集和边集,s,t分别是图 D的发点和收点。D上的通路对策有两种形式,分别是以边集作为局中人集合的边通路对策GE=(E,g)和以顶点集作为局中人集合的点通路对策()VG= V,g。通路对策的特征函数定义为:　　本文针对通路对策(包括边通路对策和点通路对策)中上述三个算法和计算复杂性问题进行了研究,主要研究结果有:　　(1)对于核心:利用简单对策核心非空的等价性条件,给出通路对策核心非空的等价条件,即核心非空当且仅当D中只包含一条边(点)不交的(s,t)-路。由此利用图中路搜索算法可证明关于核心的非空性判定、构造性和归属性判定问题都是多项式时间可解的。　　(2)对于Least-核心:首先利用求解Least-核心的线性规划模型和最大流最小割定理给出了通路对策Least-核心的刻画,即图上最小割的凸组合除以D中最大流值;由此可知在通路对策中,求解Least-核心的值、构造性和归属性判定问题也都是多项式时间可解的。　　(3)对于核仁:针对求解边通路对策核仁的序列线性规划模型,分析其中真正起作用的约束是单边和路联盟的合理性约束,从而将序列线性规划进行简化;利用网络流对策中已有的关于核仁的算法结果证明了在边通路对策中,计算核仁以及判断给定的解是否是核仁都是多项式时间可解的。对于点通路对策,通过图的构造,将点通路对策模型转化为具有公共福利边的边通路模型,从而证明了在点通路对策中有关核仁的计算和判定也都是多项式时间可解的。