TY - GEN
T1 - Efficient stabilization of cooperative matching games
AU - Ito, Takehiro
AU - Kakimura, Naonori
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Okamoto, Yoshio
N1 - Funding Information:
Supported by JSPS KAKENHI Grant Numbers 25330003, 15H00849. Supported by JST, ERATO, Kawarabayashi Large Graph Project, and by JSPS KAKENHI Grant Numbers 25730001, Supported by JST, PRESTO. Supported by JST, ERATO, Kawarabayashi Large Graph Project, and by JSPS KAKENHI Grant Numbers 24106002, 24700004. Supported by JSPS KAKENHI Grant Numbers 24106005, 24700008, 24220003, 15K00009.
Publisher Copyright:
Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2016
Y1 - 2016
N2 - 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, called stabilization, 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 be NP-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 are NP-hard.
AB - 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, called stabilization, 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 be NP-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 are NP-hard.
UR - http://www.scopus.com/inward/record.url?scp=85014285231&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85014285231&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85014285231
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 41
EP - 49
BT - AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016
Y2 - 9 May 2016 through 13 May 2016
ER -