原文：
Caprara, A., & Letchford, A. N. (2010). New techniques for cost sharing in combinatorial optimization games. Mathematical programming, 124, 93-118. https://doi.org/10.1007/s10107-010-0357-7.
原文作者：
Alberto Caprara, Adam N. Letchford

编者按：

合作博弈理论（cooperative game theory）是研究多人协作决策的理论，强调集体理性，相比于竞争，局中人（player）结成联盟（coalition），共同合作争取联盟效用最大化或成本最小化，并在联盟内部进行分配。本文中，我们将介绍由Caprara和Letchford[1]提出的一类通用的合作博弈和其成本分摊的计算框架。

1 合作博弈基础知识

一个（具有可转移效用的）合作博弈可以这样描述：有$n$个局中人，每个局中人都需要使用其拥有的特定资源以最低成本完成特定任务。局中人可以通过结成联盟，汇集资源协作完成所有任务，目标是最小化总成本。包含所有局中人的集合被称为大联盟。合作博弈关注的问题即是如何以合意的方式分配大联盟产生的成本，从而使得每一个局中人都没有动机脱离大联盟，即成本分摊问题。

核（core）是合作博弈最重要的解概念之一。粗略的说，核是一个成本分摊的集合。令$V$是局中人的集合，$|V|=n$，所有可能结成的联盟的集合为 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}，$c$则表示成本特征函数。则对于一个合作博弈$(V,c)$，核被定义为：
Core ( V , c ) = { w ∈ R v : ∑ i ∈ S w i ≤ c ( S ) , ∀ S ∈ S , and ∑ i ∈ V w i = c ( V ) } \text{Core}(V, c)=\{w\in\mathbb{R}^v:\sum_{i \in S} w_i \leq c(S), \forall S \in \mathcal{S}, \text{and} \sum_{i \in V} w_i = c(V)\} Core(V,c)={w∈Rv:i∈S∑​wi​≤c(S),∀S∈S,andi∈V∑​wi​=c(V)}
这里的$w_i$就是对$i\in V$的成本分摊的集合。如上，核有两个约束：（1）联盟稳定约束，每个局中人不会通过脱离大联盟形成子联盟而达到更小的成本；（2）预算平衡约束，成本分摊的和等于大联盟的成本。可以直观地看出，如果核是非空的，则大联盟是稳定的，那么这个合作博弈就是一个平衡博弈。同时，核的约束是苛刻的，很多合作博弈，如设施选址博弈、车辆路径规划博弈等，其核是空的，属于非平衡博弈。而在很多情况下形成大联盟能达到社会最优，合作的动机也很普泛，所以大联盟稳定解得到了广泛的研究。

大部分大联盟稳定解的思想是松弛核的约束。其中一种策略为补贴（subsidization），比如$\gamma$-core：
$$\sum _{i\in V}{w}_i\ge \gamma c(V)$$
其中$\gamma \in [0,1]$，则$\gamma$代表可以确保大联盟稳定的最大成本分摊，$1-\gamma$就代表了外部需要给大联盟的最小补贴。在这篇文章中，关注的是与$\gamma$-core相关的最优成本分摊问题（Optimal Cost Allocation Problem, OCAP），相当于求解以下线性规划（LP）
$$\max \left\{\sum _{i\in V}{w}_i:\sum _{i\in S}{w}_i\le c(S),S\in \mathcal{S}\right\}.(3)$$
简单理解，这时成本分摊的和比大联盟的最小成本少，对于每个在大联盟中的局中人来说成本可能就更少，不容易超过偏离大联盟形成子联盟的成本，所以OCAP问题的目标就是计算出在大联盟稳定的前提下，最多可以分摊多少成本。

2 整数最小化博弈

上文提到，许多MS/OR领域中重要的成本分摊博弈是组合优化博弈，其中$c(S)$可以通过求解一个组合优化问题来获得。因此该文定义了一种整数最小化(Integer Minimization, IM)博弈,简称IM博弈，包含了多种组合优化博弈。

定义1 如果满足下列条件，合作博弈$(V,c)$可以被称作IM博弈：

— 正整数$p$和$m$，

— 矩阵$A\in {\mathbb{Z}}^{p\times m}$，

— 矩阵$B\in {\mathbb{Z}}^{p\times n}$，

— 右侧向量$d\in {\mathbb{Z}}^p$，

— 目标函数向量$c\in {\mathbb{Z}}^m$，

— 对于任意的$S\in \mathcal{S}$，成本$c(S)$由下面的整数线性规划（ILP）给出：
$$c(S)=\min \left\{cx:Ax\ge By(S)+d,x\in {\mathbb{Z}}_{+}^m\right\}.(4)$$
$y(S)$是$S$的入射向量，即如果$i\in S$，则$y_i(S)=1$，$x$是决策变量。

回过头看，我们可以发现，求解OCAP公式(3)是一个困难的工作。首先，潜在的联盟有$2^n-1$个，OCAP的约束是指数级的。另外，特征函数$c(S)$的值的求解公式(4)本身也可能是$\mathcal{NP}\text{-hard}$的。

3 计算成本分摊的方法

很多重要博弈的OCAP都被证明是$\mathcal{NP}\text{-hard}$的。该文使用了列生成、行生成或两者结合来计算”好“的成本分摊。写出OCAP公式(3)的对偶问题：
$$\min \left\{\sum _{S\in \mathcal{S}}c(S)z_S:\sum _{S\ni i}{z}_S=1,i\in V,z_S\ge 0,S\in \mathcal{S}\right\}.(11)$$
上述问题可以看为一个集合划分问题的LP松弛，局中人对应约束，联盟对应变量。对偶在合作博弈的非空性检验上有重要作用，著名的Bondareva–Shapley定理[2]说明当且仅当公式(11)的最优值不少于$c(V)$公式(10)时，核是非空的。后面的每种情况也都与计算大联盟成本$c(V)$本身下界的方法有很强的联系，即公式(10)的下界：
$$\min \left\{cx:Ax\ge B1+d,x\in {\mathbb{Z}}_{+}^m\right\}.(10)$$

3.1 列生成

第一种基于列生成的方法可以比较直接地推导出。首先我们来看$c(V)$，其是下面的ILP的解：
$$c(V):=\min \left\{cx:Ax\ge By+d,y=1,x\in {\mathbb{Z}}_{+}^m\right\}.$$
该文使用Dantzig–Wolfe分解[3]来处理该ILP，使等式$y=1$留在主问题中。为此，该文用$Q^{xy}$来表示ILPs公式(4)对$S\in \mathcal{S}$的整体解集，也就是子联盟最小成本的整体解集。

Q x y : = { x ∈ Z + m , y ∈ { 0 , 1 } n : A x ≥ B y + d , y = y ( S ) for some  S ∈ S } .  Q^{x y}:=\left\{x \in \mathbb{Z}_{+}^m, y \in\{0,1\}^n: A x \geq B y+d, y=y(S) \text { for some } S \in \mathcal{S}\right\} \text {. } Qxy:={x∈Z+m​,y∈{0,1}n:Ax≥By+d,y=y(S) for some S∈S}. 
接下来对每个$(\bar{x},\bar{y})\in Q^{xy}$，定义成本$c\bar{x}$的变量$z_{(\bar{x},\bar{y})}$，则主LP是：
$$\min \left\{\sum _{(\bar{x},\bar{y})\in Q^{xy}}(c\bar{x})z_{(\bar{x},\bar{y})}:\sum _{(\bar{x},\bar{y})\in Q^{xy}}{\bar{y}}_i{z}_{(\bar{x},\bar{y})}=1,i\in V,z_{(\bar{x},\bar{y})}\ge 0,(\bar{x},\bar{y})\in Q^{xy}\right\}.(12)$$
在这里，比特征函数$c(S)$大的$c\bar{x}$和$\bar{y}=y(S)$对最优值是没有影响的，公式（12）是和公式（11）等价的。因此：

观察3 对于一个IM博弈，成本分摊集合和对偶解集LP公式(12)重合。

LP公式(12)的定价（列生成）问题相当于优化$ Q^{xy}$。定价不改变约束集合，通过以恰当的方法扩大变量集合来使得其更容易处理。这相当于在原问题公式(3)中增加额外约束，是一种松弛，导致可能得到一个次优成本分摊。其优势是定价问题可能是能多项式时间求解或伪多项式时间求解的。

在求解中，参考列生成的流程。第一步，先给定一个含有多项式数目元素的限制集合，求解主问题的对偶解。第二步，找到定价问题的最优集合。第三步，若存在使得定价问题的值为负的集合，将其添加到限制集合，然后返回第一步；若不存在，则主问题已求得最优解，进行第四步。第四步，根据更新的集合和其对应的特征值，求解博弈的最优稳定成本分摊。

3.2 行生成

行生成是使用（强）有效不等式作为割平面的方法，重点在于用多面体和有效线性不等式来解释前文的Dantzig–Wolfe reformulation。为此，该文定义了如下多面体。

ILP公式(10)的整数解的凸包的多面体：
$$P_I^x:=\mathrm{conv}\left\{x\in {\mathbb{Z}}_{+}^m:Ax\ge B1+d\right\}$$
公式(10)的LP松弛的可行解集的多面体：
$$P^x:=\left\{x\in {\mathbb{R}}_{+}^m:Ax\ge B1+d\right\}$$
根据这些，又可以定义出其他集合。一个在$(x,y)$-空间的关联”主“多面体：
$$P_I^{xy}:=\mathrm{conv}{Q}^{xy}$$
注意$P_I^x$可以由$P_I^{xy}$和对于$y_i=1\text{for all}i\in V$定义的超平面相交，然后投影到$x$-空间而得。即是：
$$P_I^x={\mathrm{proj}}_x\left(P_I^{xy}\cap \left\{(x,y)\in {\mathbb{R}}^{m+n}:y=1\right\}\right).$$
最后，介绍锥包：
$$C^{xy}:=\mathrm{cone}{Q}^{xy},$$
以及其在$x$-空间的投影：
$$C^x={\mathrm{proj}}_x\left(C^{xy}\cap \left\{(x,y)\in {\mathbb{R}}^{m+n}:y=1\right\}\right).$$
注意$P_I^{xy}\subseteq C^{xy}$，因此$P_I^x\subseteq C^x$。接下来，我们可以用这些多面体来表示我们前文的规划问题。下文的定理和引理的证明不再详细阐述，感兴趣的读者可以阅读原论文。

将$z_{(\bar{x},\bar{y})}$变量看作为在$ Q^{x y}$中各点的锥包中的系数，我们可以得到引理1：

引理1 最优成本分摊的值等于 min ⁡ { c x : x ∈ C x } \min \left\{c x: x \in C^x\right\} min{cx:x∈Cx}。

当$d\ge 0$时，$P_I^x\subseteq C^x\subseteq P^x
$，对于这类博弈，最优成本分摊的值不小于求解等式(10)的LP松弛得到的下界。上述结果，该文使用可分配不等式（assignable inequalities）来表示。

定义2 一个对$P_I^x$有效的不等式$\alpha x\ge \beta$被称为可分配的，如果存在一个不等式$\alpha x\ge \gamma y$对$P_I^{xy}$有效，${\sum }_{i\in V}{\gamma }_i=\beta$。

换句话说，一个对$P_I^x$有效的不等式对应一个对$P_I^{xy}$有效的齐次不等式（homogeneous inequalities），那么它是可分配的。

引理2 $C^x$是 ${\mathbb{R}}^m$中满足所有可分配不等式的点的集合。

根据引理1和引理2，可以直观得出：

定理1 对于一个IM博弈，最优成本分摊的值等于所有可分配不等式约束下的$cx$的最小值。

推论1 对于一个IM博弈，当且仅当对于$S=V$的ILP公式(4)的最优值，与在所有可分配不等式约束下最小化$cx$得到的下界一致时，核是非空的。

注意，上面的定理并没有在给定可分配不等式集合和相应LP松弛的解的情况下给出一个定义成本分摊的直接方法。这是通过以下方法实现的：

定理2 考虑一个IM博弈，其可分配不等式集合$Dx>f$对应对$P_I^{xy}$有效的齐次不等式集合$Dx>Ey$，有$f=E1$。假设有一个对于不等式$Dx>f$的分离算法，多项式时间为$m$，$n$和$\log \left|e_{\max }\right|$，这里$e_{\max }$是$(D,E)$的最大项（绝对值）。那么成本分摊：
min ⁡ { c x : D x ≥ f } ( 13 ) \min \left\{c x: Dx \geq f \right\} \qquad (13) min{cx:Dx≥f}(13)
可以在多项式时间$m$，$n$和$\log \left|e_{\max }\right|$内找到。

该文通过椭球法证明了定理2，在实践中可以采用标准的基于单纯形的割平面法来实现该方法。定理2使得存在有多项式时间内求得一个好的成本分摊的可能，是该文的主要贡献。可以通过如下定理来总结该节的内容：

定理3 如果$d>0$，那么$ C^x\subseteq P^x$，因此最优成本分摊的值至少和当$S=V$时的公式(4)的LP松弛的值一样大。

在实际的应用中，行生成的步骤与上文提到的列生成的步骤相似。除了行生成和列生成，该文还提出了一个行列生成结合的方法，感兴趣的读者可以阅读原文。除此外，上述内容没有假设成本分摊$w_i$非负，上述的方法也可以调整应用到这种情况。

4 算法应用

最后，我们通过经典的设施选址博弈[4]来简单说明该文的应用。根据 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}，$d=0$和$c(S)$，设施选址博弈的形式如下：
$$\begin{array}{c}c(S)=\min \{\sum _{j=1}^q{f}_j{v}_j+\sum _{i\in V}\sum _{j=1}^q{c}_{ij}{u}_{ij}:\sum _{j=1}^q{u}_{ij}=y_i(S),i\in V,\\ \left(v_j,u_{1j},\dots ,u_{nj}\right)\in F_j,j=1,\dots ,q\},\end{array}(5)$$

这里， F j = { ( 0 , … , 0 ) } ∪ { ( 1 , y ( R ) ) : R ∈ R j } , for  j = 1 , … , q F_j=\{(0, \ldots, 0)\} \cup\left\{(1, y(R)): R \in \mathcal{R}_j\right\},\text { for } j=1, \ldots, q Fj​={(0,…,0)}∪{(1,y(R)):R∈Rj​}, for j=1,…,q ，其中 R j ⊆ 2 V \ { ∅ } \mathcal{R}_j\subseteq 2^V \backslash\{\emptyset\} Rj​⊆2V\{∅} ，$y(R)$ 是集合$R\in {\mathcal{R}}_j$的入射向量。 { 1 , … , q } \left\{1, \ldots, q\right\} {1,…,q}代表潜在设施的集合，${\mathcal{R}}_j$ 是可以被设施$j$ 服务的局中人子集的可能集合。注意公式(5)并不是一个ILP，但可以根据实际情况，说明${\mathcal{R}}_j$的特殊结构，转化为一个IM博弈。例如，在无约束情况下， R j ⊆ 2 V \ { ∅ } for  j = 1 , … , q \mathcal{R}_j\subseteq 2^V \backslash\{\emptyset\} \text { for } j=1, \ldots, q Rj​⊆2V\{∅} for j=1,…,q，则约束$\left(v_j,u_{1j},\dots ,u_{nj}\right)\in F_j$可以表示为$u_{ij}\le v_j\le 1$$，$$u_{ij},v_j\in {\mathbb{Z}}_{+}\text{for}i\in V$。

对于该博弈，使用小节3.2的方法可以观察到：

观察6 对于一个在 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}和$d=0$的情况下由公式(5)定义的IM博弈，
$$C^{xy}=\left\{(v,u,y)\in {\mathbb{R}}^{q+nq+n}:\sum _{j=1}^q{u}_{ij}=y_i(i\in V),\left(v_j,u_{1j},\dots ,u_{nj}\right)\in \text{ cone }{F}_j(j=1,\dots ,q)\right\}。$$
证明 让$D:=\left\{(v,u,y)\in {\mathbb{R}}^{q+nq+n}:{\sum }_{j=1}^q{u}_{ij}=y_i(i\in V),\left(v_j,u_{1j},\dots ,u_{nj}\right)\in \text{ cone }{F}_j(j=1,\dots ,q)\right\}$。注意到：
Q x y = { ( v , u ) ∈ Z + q + n q , y ∈ { 0 , 1 } n : ∑ j = 1 q u i j = y i , i ∈ V , ( v j , u 1 j , … , u n j ) ∈ F j , j = 1 , … , q } Q^{xy}=\left\{(v, u) \in \mathbb{Z}^{q+n q}_+ ,y\in\left\{0,1\right\}^n: \sum_{j=1}^q u_{i j}=y_i, i\in V,\left(v_j, u_{1 j}, \ldots, u_{n j}\right) \in F_j ,j=1, \ldots, q\right\} Qxy={(v,u)∈Z+q+nq​,y∈{0,1}n:j=1∑q​uij​=yi​,i∈V,(vj​,u1j​,…,unj​)∈Fj​,j=1,…,q}。
要证明$\text{ cone }{Q}^{xy}=D$，首先$\text{ cone }{Q}^{xy}\subseteq D$$是显然的。相反，给定一个点$$(v,u,y{)}^{\prime }\in D$$，$$(v_j^{\prime },u_{1j}^{\prime },\dots ,u_{nj}^{\prime })={\sum }_{R\in {\mathcal{R}}_j}{\lambda }_R^{\prime }(1,y(R))\text{for}j=1,\dots ,q$，我们有$(v,u,y{)}^{\prime }={\sum }_{j=1}^q{\sum }_{R\in {\mathcal{R}}_j}{\lambda }_R(v,u,y{)}^R$，其中，对于$j=1,\dots ,q$和$R\in {\mathcal{R}}_j$，向量$(v,u,y{)}^R\in Q^{xy}$在$1$有$v_j$和$u_{ij},y_i\text{for}i\in R$表示的分量。因此$\text{ cone }{Q}^{xy}=D$，证毕。

除此外，该文的方法还可以适用于旅行商博弈、车辆路径博弈等问题，原论文中也有较为详细的介绍。

合作博弈关注的是合作所能带来的结果以及最终结果的分配方式，“稳定”是其要解决的主要问题。通过前文的介绍，我们不难发现解决这个问题所需要的计算是困难的。Caprara和Letchford的这篇论文[1]为我们提供了一个通用的解决组合优化博弈的成本分摊问题的框架，意义不言而喻。不幸的是，天妒英才，论文的作者之一Alberto Caprara在2012年因登山事故意外去世，年仅44岁，他在组合优化领域做出了杰出的贡献，致以最深切的敬意。

参考文献

[1] Caprara, A., & Letchford, A. N. (2010). New techniques for cost sharing in combinatorial optimization games. Mathematical programming, 124, 93-118.

[2] Shapley, L. S. (1967). On balanced sets and cores. Naval research logistics quarterly, 14(4), 453-460.

[3] Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations research, 8(1), 101-111.

[4] Goemans, M. X., & Skutella, M. (2004). Cooperative facility location games. Journal of Algorithms, 50(2), 194-214.