Efficient Stabilization of Cooperative Matching Games
Efficient Stabilization of Cooperative Matching Games
复制标题
DOI：
10.1016/j.tcs.2017.03.020
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Y. Okamoto
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Y. Okamoto
合作匹配游戏已经引起了很大的兴趣，部分是因为在网络环境中的讨价还价解决方案的连接。然而，并不总是保证被调查的网络会产生稳定的讨价还价结果。为了解决这个问题，我们考虑一个修改过程，称为稳定化，产生一个网络的稳定结果，其中修改应该尽可能小。因此，该问题被转换为图中的组合优化问题。最近，边缘去除的稳定化被证明是NP难的。相反，在本文中，我们表明，其他可能的方式，即边添加，顶点删除和顶点添加，都是多项式时间可解的。因此，我们得到了一个完整的复杂性理论分类的自然四个变量的网络稳定问题。我们进一步研究了带权的变式，证明了用于边增加和顶点删除的变式是NP-困难的。
Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, calledstabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to beNP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal areNP-hard.