کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952098 1442012 2017 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient stabilization of cooperative matching games
ترجمه فارسی عنوان
تثبیت موثر بازی های همکاری بازی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 677, 16 May 2017, Pages 69-82
نویسندگان
, , , , ,