Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

ملخص تقني: الاستبعاد المتسلسل وقيمة شابلي للاتحاد لتقييم المجموعات في الألعاب الائتلافية

بيان المشكلة
في نظرية الألعاب التعاونية والمجالات ذات الصلة مثل المركزية الشبكية وتقييم البيانات في تعلم الآلة، يبرز تحدٍ جوهي يتمثل في توسيع نطاق تقييمات اللاعبين الفرديين ليشمل المجموعات. تعتمد الطرق الحالية عادةً على نهجين مباشرين:
١. الجمع: تجميع القيم الفردية (مثل مجموع قيم شابلي). وهذا يتجاهل البنية الأساسية للتعاون والاعتماد المتبادل بين اللاعبين.
٢. الدمج: معاملة المجموعة كعنصر واحد مدمج وتقييمه (مثل قيمة شابلي للدمج). وهذا يغير بنية اللعبة ويفشل في التمييز بين اللاعبين المستقلين واللاعبين شديدي الاعتماد على بعضهم البعض.

كلا النهجين غالباً ما يفشلان في رصد الاعتمادات داخل المجموعات بدقة. فعلى سبيل المثال، في لعبة حيث تولد زوجان من اللاعبين المنفصلين قيمة بشكل مستقل، فإن جمع القيم الفردية أو دمج المجموعات قد يؤدي إلى تخصيص أهمية متساوية لزوج من اللاعبين المتعاونين وزوج من اللاعبين المستقلين، مما يفشل في عكس التباين في تأثيرهما النسقي.

المنهجية
يقترح المؤلفون ويحللون نهجاً ثالثاً يعتمد على الاستبعاد المتسلسل. في هذا الإطار، يتم إزالة عناصر المجموعة واحداً تلو الآخر، ويتم تجميع تقييماتها في الألعاب المختزلة الناتلة. وتتمثل الفرضية الأساسية في أن هذه الطريقة تقيس بطبيعتها صافي مساهمة المجموعة من خلال خصم التأثيرات المتداخلة والتركيز على الضرر الناجم عن غياب المجموعة.

تستند الدراسة إلى تحليل بديهي شامل لقيم المجموعات في الألعاب الائتلافية. وتتضمن المنهجية ما يلي:

• تعريف فئات البديهيات: يقدم المؤلفون فئة من القيم شبه المتسقة للمجموعات (group weak consistent semivalues). وهي قيم مجموعات تحقق الخطية، والتناظر، والرتابة الضعيفة، وخروج اللاعب الصفري، وبديهية اللاعب الصوري (Dummy Player). كما يعرّفون فئة مقابلة من القيم شبه التآزرية (synergy semivalues)، والتي تستبدل بديهية اللاعب الصوري ببديهية اللاعب المُميِّز (Dummifying Player) (التي قدمها غرابيش وروبنز).
• التمديد المتسلسل: يثبت البحث أن قيمة اللاعب تقبل تمديداً متسلسلاً إذا وفقط إذا كانت تحقق خاصية المساهمات المتوازنة. وقد ثبت أن كل قيمة شبه متسقة (تحقق شرط خروج اللاعب الصفري) تقبل تمديداً متسلسلاً فريداً.
• دالة الإمكان (Potential Function): يستخدم المؤلفون دالة الإمكان التي قدمها هارت وماس كول، لتوصيف التمديد المتسلسل لقيمة شابلي.

المساهمات والنتائج الرئيسية

١. قيمة شابلي للاتحاد (Union Shapley Value):
يقدم المؤلفون قيمة شابلي للاتحاد باعتبارها التمديد المتسلسل الفريد لقيمة شابلي. وتُعرف بأنها الفرق بين إمكان اللعبة الأصلية وإمكان اللعبة بعد إزالة المجموعة:
$$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
حيث $\Delta v(T)$ هي عوائد هارساني (Harsanyi dividends).

• التفسير: تقيس هذه القيمة "الضرر" الذي يلحق باللعبة عند مغادرة مجموعة ما. وهي تجمع المساهمات بحيث تُحتسب عوائد كل ائتلاف مرة واحدة على الأكثر، حتى لو احتوت المجموعة على عدة أعضاء من ذلك الائتلاف.
• التوصيف بالبديهيات: تتميز قيمة شابلي للاتحاد بشكل فريد من خلال بديهيات الإمكان (أو المساهمات المتوازنة) مقترنة بـ الكفاءة. كما تتميز أيضاً بشكل فريد بين قيم المجموعات شبه المتسقة من خلال تساوي المجموعات (جميع المجموعات في لعبة الإجماع لها نفس الأهمية).

٢. التصنيف البديهي لقيم المجموعات:
يميز البحث بين نوعين من تقييم المجموعات:

• القيمة الإجمالية: القيم التي تقيم القيمة الإجمالية لمجموعة (مثل تمديد الجمع، وقيمة شابلي للدمج، وقيمة شابلي للاتحاد). ويتم استيعاب هذه القيم عبر القيم شبه المتسقة للمجموعات.
• التآزر: القيم التي تقيس تآزر مجموعة (مثل مؤشر التفاعل). ويتم استيعاب هذه القيم عبر القيم شبه المتسقة للتآزر.
  ويقدم المؤلفون مراسلة وظيفية بين هاتين الفئتين. وتحديداً، يوضح البحث أن قيمة شابلي للدمج تقابل مؤشر التفاعل (وهو نظير تآزري)، وأن قيمة شابلي للاتحاد تقابل قيمة تآزرية جديدة تسمى قيمة شابلي للتقاطع.

٣. قيمة شابلي للتقاطع (Intersection Shapley Value):
تُعرف بأنها مجموع عوائد الائتلافات التي تحتوي المجموعة بأكملها:
$$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
تقيس هذه القيمة تقاطع المساهمات. بالنسبة لمجموعة مكونة من عنصرين، فإن مجموع قيمة شابلي للاتحاد وقيمة شابلي للتقاطع يساوي مجموع القيم الفردية لشابلي:
$$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
يسمح هذا التفكيك بفصل القيمة المشتركة للمجموعة إلى جزء "اتحاد" (يحسب المساهمات مرة واحدة) وجزء "تقاطع" (التآزر).

٤. المقارنة مع الأعمال السابقة:
يوضح التحليل العلاقة بين القيم المقترحة والأدبيات الموجودة:

• أظهر البحث أن قيمة شابلي للدمج (ماريتشال وآخرون) هي القيمة شبه المتسقة الوحيدة للمجموعات التي تحقق بديهية الائتلاف الصوري (Dummy Coalition).
• تم تحديد مؤشر التفاعل (غرابيش وروبنز) كقيمة شبه متسقة للتآزر، وهي تختلف عن القيم شبه المتسقة للمجموعات لأنها تنتهك بديهية اللاعب الصوري القياسية لصالح بديهية اللاعب المُميِّز.
• يثبت البحث أن نهج التمديد المتسلسل متين نظرياً، حيث ينطبق على جميع القيم شبه المتسقة ويؤدي إلى قيم ذات خصائص بديهية قوية.

الأهمية
يزعم البحث أن نهج التمديد المتسلسل، وبالتحديد قيمة شابلي للاتحاد، يشكل أحد أكثر التمديدات الطبيعية والراسخة نظرياً لقيم اللاعبين إلى المجموعات في الألعاب الائتلافية. ومن خلال التمييز بين تقييم القيمة الإجمالية وقياس التآزر، يوفر المؤلفون إطاراً موحداً يوضح الاختلافات بين المفاهيم الموجودة في الأدبيات. إن تقديم قيمتي "التقاطع" و"الاتحاد" يوفر أدوات جديدة لتحليل التفاعلات، لا سيما في السيناريوهات التي يجب فيها خصم تداخل المساهمات (الاتحاد) أو حيث يجب عزل التآزر الصافي (التقاطع). ويؤسس هذا العمل لهذه القيم ليس كمجرد استدلالات عشوائية، بل كقيم محددة بشكل فريد بواسطة بديهيات أساسية مثل المساهمات المتوازنة، والإمكان، وتساوي المجموعات.