کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6853034 | 1436973 | 2018 | 60 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Forming k coalitions and facilitating relationships in social networks
ترجمه فارسی عنوان
تشکیل ائتلاف ها و تسهیل روابط در شبکه های اجتماعی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تشکیل ائتلاف، بازی های هدیونی جداگانه افزودنی، شبکه های اجتماعی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
We show that, when the number of coalitions, k, is fixed and there are not many negative edges, it is possible to find the coalition structure that maximizes the social welfare in polynomial time. Furthermore, an organizer can efficiently find the optimal set of edges to add to the network, and we experimentally demonstrate the effectiveness of this approach. In addition, we show that in our setting even when k is fixed and there are not many negative edges, finding a member of the core is intractable. However, we provide a heuristic for efficiently finding a member of the core that also guarantees a social welfare within a factor of 1/2 of the optimal social welfare. We also show that checking whether a given coalition structure is a member of the core can be done in polynomial time. Finally, we consider the problem faced by an organizer who would like to add edges to the network in order to stabilize a specific coalition structure core: we show that this problem is intractable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 259, June 2018, Pages 217-245
Journal: Artificial Intelligence - Volume 259, June 2018, Pages 217-245
نویسندگان
Liat Sless, Noam Hazon, Sarit Kraus, Michael Wooldridge,