کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
12235860 | 685009 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms for computing the Shapley value of cooperative games on lattices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study algorithms to compute the Shapley value for a cooperative game on a lattice LΣ=(FΣ,â) where FΣ is the family of closed sets given by an implicational system Σ on a set N of players. The first algorithm is based on the generation of the maximal chains of the lattice LΣ and computes the Shapley value in O(|N|3.|Σ|.|Ch|) time complexity using polynomial space, where Ch is the set of maximal chains of LΣ. The second algorithm proceeds by building the lattice LΣ and computes the Shapley value in O(|N|3.|Σ|.|FΣ|) time and space complexity. Our main contribution is to show that the Shapley value of weighted graph games on a product of chains with the same fixed length is computable in polynomial time. We do this by partitioning the set of feasible coalitions relevant to the computation of the Shapley value into equivalence classes in such a way that we need to consider only one element of each class in the computation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 249, 20 November 2018, Pages 91-105
Journal: Discrete Applied Mathematics - Volume 249, 20 November 2018, Pages 91-105
نویسندگان
Khaled Maafa, Lhouari Nourine, Mohammed Said Radjef,