本文主要是介绍优化|计算合作博弈的成本分摊,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原文:
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 n n个局中人,每个局中人都需要使用其拥有的特定资源以最低成本完成特定任务。局中人可以通过结成联盟,汇集资源协作完成所有任务,目标是最小化总成本。包含所有局中人的集合被称为大联盟。合作博弈关注的问题即是如何以合意的方式分配大联盟产生的成本,从而使得每一个局中人都没有动机脱离大联盟,即成本分摊问题。
核(core)是合作博弈最重要的解概念之一。粗略的说,核是一个成本分摊的集合。令 V V V是局中人的集合, ∣ V ∣ = n \lvert V \rvert=n ∣V∣=n,所有可能结成的联盟的集合为 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}, c c c则表示成本特征函数。则对于一个合作博弈 ( V , c ) (V, 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 w_i wi就是对 i ∈ V i\in V i∈V的成本分摊的集合。如上,核有两个约束:(1)联盟稳定约束,每个局中人不会通过脱离大联盟形成子联盟而达到更小的成本;(2)预算平衡约束,成本分摊的和等于大联盟的成本。可以直观地看出,如果核是非空的,则大联盟是稳定的,那么这个合作博弈就是一个平衡博弈。同时,核的约束是苛刻的,很多合作博弈,如设施选址博弈、车辆路径规划博弈等,其核是空的,属于非平衡博弈。而在很多情况下形成大联盟能达到社会最优,合作的动机也很普泛,所以大联盟稳定解得到了广泛的研究。
大部分大联盟稳定解的思想是松弛核的约束。其中一种策略为补贴(subsidization),比如 γ \gamma γ-core:
∑ i ∈ V w i ≥ γ c ( V ) \sum_{i \in V} w_i \geq \gamma c(V) i∈V∑wi≥γc(V)
其中 γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ∈[0,1],则 γ \gamma γ代表可以确保大联盟稳定的最大成本分摊, 1 − γ 1-\gamma 1−γ就代表了外部需要给大联盟的最小补贴。在这篇文章中,关注的是与 γ \gamma γ-core相关的最优成本分摊问题(Optimal Cost Allocation Problem, OCAP),相当于求解以下线性规划(LP)
max { ∑ i ∈ V w i : ∑ i ∈ S w i ≤ c ( S ) , S ∈ S } . ( 3 ) \max \left\{\sum_{i \in V} w_i: \quad \sum_{i \in S} w_i \leq c(S), \quad S \in \mathcal{S}\right\}. \qquad (3) max{i∈V∑wi:i∈S∑wi≤c(S),S∈S}.(3)
简单理解,这时成本分摊的和比大联盟的最小成本少,对于每个在大联盟中的局中人来说成本可能就更少,不容易超过偏离大联盟形成子联盟的成本,所以OCAP问题的目标就是计算出在大联盟稳定的前提下,最多可以分摊多少成本。
2 整数最小化博弈
上文提到,许多MS/OR领域中重要的成本分摊博弈是组合优化博弈,其中 c ( S ) c(S) c(S)可以通过求解一个组合优化问题来获得。因此该文定义了一种整数最小化(Integer Minimization, IM)博弈,简称IM博弈,包含了多种组合优化博弈。
定义1 如果满足下列条件,合作博弈 ( V , c ) (V, c) (V,c)可以被称作IM博弈:
— 正整数 p p p和 m m m,
— 矩阵 A ∈ Z p × m A\in \mathbb{Z}^{p\times m} A∈Zp×m,
— 矩阵 B ∈ Z p × n B\in \mathbb{Z}^{p\times n} B∈Zp×n,
— 右侧向量 d ∈ Z p d\in \mathbb{Z}^{p} d∈Zp,
— 目标函数向量 c ∈ Z m c\in \mathbb{Z}^{m} c∈Zm,
— 对于任意的 S ∈ S S\in \mathcal{S} S∈S,成本 c ( S ) c(S) c(S)由下面的整数线性规划(ILP)给出:
c ( S ) = min { c x : A x ≥ B y ( S ) + d , x ∈ Z + m } . ( 4 ) c(S)=\min \left\{c x: A x \geq B y(S)+d, x \in \mathbb{Z}_{+}^m\right\} . \qquad (4) c(S)=min{cx:Ax≥By(S)+d,x∈Z+m}.(4)
y ( S ) y(S) y(S)是 S S S的入射向量,即如果 i ∈ S i\in S i∈S,则 y i ( S ) = 1 y_i(S)=1 yi(S)=1, x x x是决策变量。
回过头看,我们可以发现,求解OCAP公式(3)是一个困难的工作。首先,潜在的联盟有 2 n − 1 2^n-1 2n−1个,OCAP的约束是指数级的。另外,特征函数 c ( S ) c(S) c(S)的值的求解公式(4)本身也可能是 N P -hard \cal{NP}\text{-hard} NP-hard的。
3 计算成本分摊的方法
很多重要博弈的OCAP都被证明是 N P -hard \cal{NP}\text{-hard} NP-hard的。该文使用了列生成、行生成或两者结合来计算”好“的成本分摊。写出OCAP公式(3)的对偶问题:
min { ∑ S ∈ S c ( S ) z S : ∑ S ∋ i z S = 1 , i ∈ V , z S ≥ 0 , S ∈ S } . ( 11 ) \min \left\{\sum_{S \in \mathcal{S}} c(S) z_S: \sum_{S \ni i} z_S=1, \quad i \in V, \quad z_S \geq 0, \quad S \in \mathcal{S}\right\} . \qquad (11) min{S∈S∑c(S)zS:S∋i∑zS=1,i∈V,zS≥0,S∈S}.(11)
上述问题可以看为一个集合划分问题的LP松弛,局中人对应约束,联盟对应变量。对偶在合作博弈的非空性检验上有重要作用,著名的Bondareva–Shapley定理[2]说明当且仅当公式(11)的最优值不少于 c ( V ) c(V) c(V)公式(10)时,核是非空的。后面的每种情况也都与计算大联盟成本 c ( V ) c(V) c(V)本身下界的方法有很强的联系,即公式(10)的下界:
min { c x : A x ≥ B 1 + d , x ∈ Z + m } . ( 10 ) \min \left\{c x: A x \geq B \mathbf{1}+d, x \in \mathbb{Z}_{+}^m\right\} . \qquad (10) min{cx:Ax≥B1+d,x∈Z+m}.(10)
3.1 列生成
第一种基于列生成的方法可以比较直接地推导出。首先我们来看 c ( V ) c(V) c(V),其是下面的ILP的解:
c ( V ) : = min { c x : A x ≥ B y + d , y = 1 , x ∈ Z + m } . c(V):=\min \left\{c x: A x \geq B y+d, y=\mathbf{1}, x \in \mathbb{Z}_{+}^m\right\} . c(V):=min{cx:Ax≥By+d,y=1,x∈Z+m}.
该文使用Dantzig–Wolfe分解[3]来处理该ILP,使等式 y = 1 y=\mathbf{1} y=1留在主问题中。为此,该文用 Q x y Q^{xy} Qxy来表示ILPs公式(4)对 S ∈ S S\in \mathcal{S} S∈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}.
接下来对每个 ( x ˉ , y ˉ ) ∈ Q x y (\bar{x},\bar{y}) \in Q^{xy} (xˉ,yˉ)∈Qxy,定义成本 c x ˉ c\bar{x} cxˉ的变量 z ( x ˉ , y ˉ ) z_{(\bar{x},\bar{y})} z(xˉ,yˉ),则主LP是:
min { ∑ ( x ˉ , y ˉ ) ∈ Q x y ( c x ˉ ) z ( x ˉ , y ˉ ) : ∑ ( x ˉ , y ˉ ) ∈ Q x y y ˉ i z ( x ˉ , y ˉ ) = 1 , i ∈ V , z ( x ˉ , y ˉ ) ≥ 0 , ( x ˉ , y ˉ ) ∈ Q x y } . ( 12 ) \min \left\{\sum_{(\bar{x}, \bar{y}) \in Q^{x y}}(c \bar{x}) z_{(\bar{x}, \bar{y})}: \sum_{(\bar{x}, \bar{y}) \in Q^{x y}} \bar{y}_i z_{(\bar{x}, \bar{y})}=1, \quad i \in V, \quad z_{(\bar{x}, \bar{y})} \geq 0, \quad(\bar{x}, \bar{y}) \in Q^{x y}\right\}. \qquad (12) min⎩ ⎨ ⎧(xˉ,yˉ)∈Qxy∑(cxˉ)z(xˉ,yˉ):(xˉ,yˉ)∈Qxy∑yˉiz(xˉ,yˉ)=1,i∈V,z(xˉ,yˉ)≥0,(xˉ,yˉ)∈Qxy⎭ ⎬ ⎫.(12)
在这里,比特征函数 c ( S ) c(S) c(S)大的 c x ˉ c\bar{x} cxˉ和 y ˉ = y ( S ) \bar{y}=y(S) yˉ=y(S)对最优值是没有影响的,公式(12)是和公式(11)等价的。因此:
观察3 对于一个IM博弈,成本分摊集合和对偶解集LP公式(12)重合。
LP公式(12)的定价(列生成)问题相当于优化$ Q^{xy}$。定价不改变约束集合,通过以恰当的方法扩大变量集合来使得其更容易处理。这相当于在原问题公式(3)中增加额外约束,是一种松弛,导致可能得到一个次优成本分摊。其优势是定价问题可能是能多项式时间求解或伪多项式时间求解的。
在求解中,参考列生成的流程。第一步,先给定一个含有多项式数目元素的限制集合,求解主问题的对偶解。第二步,找到定价问题的最优集合。第三步,若存在使得定价问题的值为负的集合,将其添加到限制集合,然后返回第一步;若不存在,则主问题已求得最优解,进行第四步。第四步,根据更新的集合和其对应的特征值,求解博弈的最优稳定成本分摊。
3.2 行生成
行生成是使用(强)有效不等式作为割平面的方法,重点在于用多面体和有效线性不等式来解释前文的Dantzig–Wolfe reformulation。为此,该文定义了如下多面体。
ILP公式(10)的整数解的凸包的多面体:
P I x : = conv { x ∈ Z + m : A x ≥ B 1 + d } P_I^x:=\operatorname{conv}\left\{x \in \mathbb{Z}_{+}^m: A x \geq B \mathbf{1}+d\right\} PIx:=conv{x∈Z+m:Ax≥B1+d}
公式(10)的LP松弛的可行解集的多面体:
P x : = { x ∈ R + m : A x ≥ B 1 + d } P^x:=\left\{x \in \mathbb{R}_{+}^m: A x \geq B \mathbf{1}+d\right\} Px:={x∈R+m:Ax≥B1+d}
根据这些,又可以定义出其他集合。一个在 ( x , y ) (x,y) (x,y)-空间的关联”主“多面体:
P I x y : = conv Q x y P_I^{xy}:=\operatorname{conv} Q^{x y} PIxy:=convQxy
注意 P I x P_I^x PIx可以由 P I x y P_I^{xy} PIxy和对于 y i = 1 for all i ∈ V y_i=1 \text{for all} i\in V yi=1for alli∈V定义的超平面相交,然后投影到 x x x-空间而得。即是:
P I x = proj x ( P I x y ∩ { ( x , y ) ∈ R m + n : y = 1 } ) . P_I^x=\operatorname{proj}_x\left(P_I^{x y} \cap\left\{(x, y) \in \mathbb{R}^{m+n}: y=\mathbf{1}\right\}\right) . PIx=projx(PIxy∩{(x,y)∈Rm+n:y=1}).
最后,介绍锥包:
C x y : = cone Q x y , C^{xy}:=\operatorname{cone} Q^{x y}, Cxy:=coneQxy,
以及其在 x x x-空间的投影:
C x = proj x ( C x y ∩ { ( x , y ) ∈ R m + n : y = 1 } ) . C^x=\operatorname{proj}_x\left(C^{x y} \cap\left\{(x, y) \in \mathbb{R}^{m+n}: y=\mathbf{1}\right\}\right) . Cx=projx(Cxy∩{(x,y)∈Rm+n:y=1}).
注意 P I x y ⊆ C x y P_I^{xy}\subseteq C^{xy} PIxy⊆Cxy,因此 P I x ⊆ C x P_I^x\subseteq C^x PIx⊆Cx。接下来,我们可以用这些多面体来表示我们前文的规划问题。下文的定理和引理的证明不再详细阐述,感兴趣的读者可以阅读原论文。
将 z ( x ˉ , y ˉ ) z_{(\bar{x},\bar{y})} z(xˉ,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 ≥ 0 d\geq0 d≥0时,$P_I^x\subseteq C^x\subseteq P^x
$,对于这类博弈,最优成本分摊的值不小于求解等式(10)的LP松弛得到的下界。上述结果,该文使用可分配不等式(assignable inequalities)来表示。
定义2 一个对 P I x P^{x}_{I} PIx有效的不等式 α x ≥ β \alpha x \geq \beta αx≥β被称为可分配的,如果存在一个不等式 α x ≥ γ y \alpha x \geq \gamma y αx≥γy对 P I x y P^{xy}_{I} PIxy有效, ∑ i ∈ V γ i = β \sum_{i \in V} \gamma_i=\beta ∑i∈Vγi=β。
换句话说,一个对 P I x P^{x}_{I} PIx有效的不等式对应一个对 P I x y P^{xy}_{I} PIxy有效的齐次不等式(homogeneous inequalities),那么它是可分配的。
引理2 C x C^x Cx是 R m \mathbb{R}^m Rm中满足所有可分配不等式的点的集合。
根据引理1和引理2,可以直观得出:
定理1 对于一个IM博弈,最优成本分摊的值等于所有可分配不等式约束下的 c x cx cx的最小值。
推论1 对于一个IM博弈,当且仅当对于 S = V S=V S=V的ILP公式(4)的最优值,与在所有可分配不等式约束下最小化 c x cx cx得到的下界一致时,核是非空的。
注意,上面的定理并没有在给定可分配不等式集合和相应LP松弛的解的情况下给出一个定义成本分摊的直接方法。这是通过以下方法实现的:
定理2 考虑一个IM博弈,其可分配不等式集合 D x > f Dx>f Dx>f对应对 P I x y P^{xy}_{I} PIxy有效的齐次不等式集合 D x > E y Dx>Ey Dx>Ey,有 f = E 1 f=E\mathbf{1} f=E1。假设有一个对于不等式 D x > f Dx>f Dx>f的分离算法,多项式时间为 m m m, n n n和 log ∣ e max ∣ \log \left|e_{\max }\right| log∣emax∣,这里 e max e_{\max } emax是 ( D , E ) (D,E) (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 m m, n n n和 log ∣ e max ∣ \log \left|e_{\max }\right| log∣emax∣内找到。
该文通过椭球法证明了定理2,在实践中可以采用标准的基于单纯形的割平面法来实现该方法。定理2使得存在有多项式时间内求得一个好的成本分摊的可能,是该文的主要贡献。可以通过如下定理来总结该节的内容:
定理3 如果 d > 0 d>0 d>0,那么$ C^x\subseteq P^x ,因此最优成本分摊的值至少和当 ,因此最优成本分摊的值至少和当 ,因此最优成本分摊的值至少和当S=V$时的公式(4)的LP松弛的值一样大。
在实际的应用中,行生成的步骤与上文提到的列生成的步骤相似。除了行生成和列生成,该文还提出了一个行列生成结合的方法,感兴趣的读者可以阅读原文。除此外,上述内容没有假设成本分摊 w i w_i wi非负,上述的方法也可以调整应用到这种情况。
4 算法应用
最后,我们通过经典的设施选址博弈[4]来简单说明该文的应用。根据 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}, d = 0 d=0 d=0和 c ( S ) c(S) c(S),设施选址博弈的形式如下:
c ( S ) = min { ∑ j = 1 q f j v j + ∑ i ∈ V ∑ j = 1 q c i j u i j : ∑ j = 1 q u i j = y i ( S ) , i ∈ V , ( v j , u 1 j , … , u n j ) ∈ F j , j = 1 , … , q } , ( 5 ) \begin{gathered} c(S)=\min \left\{\sum_{j=1}^q f_j v_j+\sum_{i \in V} \sum_{j=1}^q c_{i j} u_{i j}: \sum_{j=1}^q u_{i j}=y_i(S), \quad i \in V,\right. \\ \left.\left(v_j, u_{1 j}, \ldots, u_{n j}\right) \in F_j, \quad j=1, \ldots, q\right\}, \end{gathered} \qquad (5) c(S)=min{j=1∑qfjvj+i∈V∑j=1∑qcijuij:j=1∑quij=yi(S),i∈V,(vj,u1j,…,unj)∈Fj,j=1,…,q},(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 ) y(R) y(R) 是集合 R ∈ R j R \in \mathcal{R}_j R∈Rj的入射向量。 { 1 , … , q } \left\{1, \ldots, q\right\} {1,…,q}代表潜在设施的集合, R j \mathcal{R}_j Rj 是可以被设施 j j j 服务的局中人子集的可能集合。注意公式(5)并不是一个ILP,但可以根据实际情况,说明 R j \mathcal{R}_j Rj的特殊结构,转化为一个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,则约束 ( v j , u 1 j , … , u n j ) ∈ F j \left(v_j, u_{1 j}, \ldots, u_{n j}\right) \in F_j (vj,u1j,…,unj)∈Fj可以表示为 u i j ≤ v j ≤ 1 u_{i j} \leq v_j \leq 1 uij≤vj≤1 , , , u i j , v j ∈ Z + for i ∈ V u_{i j}, v_j \in \mathbb{Z}_+ \text{for} i \in V uij,vj∈Z+fori∈V。
对于该博弈,使用小节3.2的方法可以观察到:
观察6 对于一个在 S ⊆ 2 V \ { ∅ } \mathcal{S} \subseteq 2^V \backslash\{\emptyset\} S⊆2V\{∅}和 d = 0 d=0 d=0的情况下由公式(5)定义的IM博弈,
C x y = { ( v , u , y ) ∈ R q + n q + n : ∑ j = 1 q u i j = y i ( i ∈ V ) , ( v j , u 1 j , … , u n j ) ∈ cone F j ( j = 1 , … , q ) } 。 C^{xy}=\left\{(v, u, y) \in \mathbb{R}^{q+n q+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 \text { cone } F_j (j=1, \ldots, q)\right\}。 Cxy={(v,u,y)∈Rq+nq+n:j=1∑quij=yi(i∈V),(vj,u1j,…,unj)∈ cone Fj(j=1,…,q)}。
证明 让 D : = { ( v , u , y ) ∈ R q + n q + n : ∑ j = 1 q u i j = y i ( i ∈ V ) , ( v j , u 1 j , … , u n j ) ∈ cone F j ( j = 1 , … , q ) } D:=\left\{(v, u, y) \in \mathbb{R}^{q+n q+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 \text { cone } F_j (j=1, \ldots, q)\right\} D:={(v,u,y)∈Rq+nq+n:∑j=1quij=yi(i∈V),(vj,u1j,…,unj)∈ cone Fj(j=1,…,q)}。注意到:
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∑quij=yi,i∈V,(vj,u1j,…,unj)∈Fj,j=1,…,q}。
要证明 cone Q x y = D \text { cone } Q^{x y} = D cone Qxy=D,首先 cone Q x y ⊆ D \text { cone } Q^{x y} \subseteq D cone Qxy⊆D 是显然的。相反,给定一个点 是显然的。相反,给定一个点 是显然的。相反,给定一个点 ( v , u , y ) ′ ∈ D (v,u,y)'\in D (v,u,y)′∈D , , , ( v j ′ , u 1 j ′ , … , u n j ′ ) = ∑ R ∈ R j λ R ′ ( 1 , y ( R ) ) for j = 1 , … , q (v'_j, u'_{1 j}, \ldots, u'_{n j})=\sum_{R \in \mathcal{R}_j} \lambda_R^{\prime}(1, y(R)) \text{for} j=1,\ldots,q (vj′,u1j′,…,unj′)=∑R∈RjλR′(1,y(R))forj=1,…,q,我们有 ( v , u , y ) ′ = ∑ j = 1 q ∑ R ∈ R j λ R ( v , u , y ) R (v, u, y)^{\prime}=\sum_{j=1}^q \sum_{R \in \mathcal{R}_j} \lambda_R(v, u, y)^R (v,u,y)′=∑j=1q∑R∈RjλR(v,u,y)R,其中,对于 j = 1 , … , q j=1,\ldots,q j=1,…,q和 R ∈ R j R \in \mathcal{R}_j R∈Rj,向量 ( v , u , y ) R ∈ Q x y (v, u, y)^R\in Q^{xy} (v,u,y)R∈Qxy在 1 1 1有 v j v_j vj和 u i j , y i for i ∈ R u_{ij}, y_i \text{for} i\in R uij,yifori∈R表示的分量。因此 cone Q x y = D \text { cone } Q^{x y} = D cone Qxy=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.
这篇关于优化|计算合作博弈的成本分摊的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!