Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

إليك ملخص تقني مفصل لورقة البحث بعنوان "التعلم غير المتصل (Offline Learning) لهياكل التحالفات المستقرة وفق توازن ناش مع احتمالية تداخل التحالفات" للباحث سار كوهين.

1. بيان المشكلة

تتناول الورقة تحدي تكوين التحالفات (Coalition Formation) في بيئات تتسم بما يلي:

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

الهدف المحدد هو تعلم استراتيجية مشتركة (تقسيم الوكلاء إلى تحالفات) تكون مستقرة وفق توازن ناش بمقدار $\epsilon$ ($\epsilon$-Nash Stable). تكون الاستراتيجية $\epsilon$-NS إذا لم يتمكن أي وكيل من الانحراف من جانب واحد لتحسين منفعته بأكثر من $\epsilon$.

2. المنهجية

2.1 نموذج اللعبة

• لعبة POCF: تُعرف بـ $G = (N, \{A_i\}_{i \in N})$، حيث $N$ هي مجموعة الوكلاء و $A_i$ هي مجموعة المجموعات الفرعية الممكنة من التحالفات المرشحة التي يمكن للوكيل الانضمام إليها.
• التفضيلات: تركز الورقة على التفضيلات الجمعية المنفصلة والمتماثلة (S-ASHG). منفعة الوكيل هي مجموع المنافع الثنائية مع الأعضاء الآخرين في تحالفاته المختارة. ومن الأهمية بمكان أن المنافع الثنائية يمكن أن تختلف اعتماداً على أي تحالف يتواجد فيه الزوج (على سبيل المثال: قد يتعاون مستشاران بشكل جيد في الخدمات اللوجستية ولكن بشكل سيء في التمويل).
• الاستقرار: يثبت المؤلفون أن ألعاب POCF المتماثلة هي ألعاب إمكانات (Potential Games)، مما يضمن وجود توازن ناش نقي واحد على الأقل.

2.2 نماذج التغذية المرتدة (Feedback Models)

تحلل الورقة نوعين من التغذية المرتدة المتاحة في مجموعة البيانات غير المتصلة $S = \{(a_m, v_m)\}_{m=1}^M$:

1. التغذية المرتدة شبه-المنظمة (Semi-Bandit Feedback): تحتوي مجموعة البيانات على تغذيات مرتدة للمنفعة على مستوى الوكيل. لكل وكيل $i$ وكل تحالف $\ell$ انضم إليه، تلاحظ الخوارزمية المنفعة المحددة المستمدة من كل وكيل آخر $j$ في ذلك التحالف ($v_{i,j}^\ell$).
2. التغذية المرتدة من نوع "بانديت" (Bandit Feedback): تحتوي مجموعة البيانات فقط على تغذيات مرتدة للمنفعة على مستوى التحالف (العالمي). تلاحظ الخوارزمية إجمالي المنفعة $v_i(a_m)$ للوكيل $i$ ولكن لا يمكنها تفكيكها إلى تفاعلات ثنائية.

2.3 الإطار الخوارزمي: تقليل البديل (Surrogate Minimization)

الخوارزمية الأساسية (الخوارزمية 1) هي نهج تقليل البديل المصمم للتعامل مع عدم اليقين:

1. التقدير: إنشاء مُقدّر $\hat{v}_i(a)$ لمتوسط منفعة الوكيل $i$ تحت الإجراء المشترك $a$.
2. مكافأة الاستكشاف: إضافة مكافأة استكشاف $b_i^\delta(a)$ لإنشاء حدود عليا وسفلى للثقة (UCB/LCB) لتقديرات المنفعة. يضمن ذلك أن تكون الخوارزمية "متفائلة" بشأن الإجراءات غير المستكشفة.
3. التحسين: تسعى الخوارزمية للبحث عن استراتيجية مختلطة مشتركة $\phi_{out}$ تقلل من الفجوة المزدوجة (الفرق بين أفضل استجابة ممكنة والاستراتيجية الحالية) بناءً على هذه الحدود المتفائلة/المتشائمة:
   $$\min_{\phi} \max_{i \in N} \left[ V_i^{\star, \delta}(\phi_{-i}) - V_i^\delta(\phi) \right]$$
   حيث تمثل $V^\delta$ حدود المنفعة المقدرة.

3. المساهمات الرئيسية

3.1 الافتراضات النظرية للقابلية للتعلم

تحدد الورقة الشروط الضرورية والكافية لتغطية مجموعة البيانات المطلوبة لتعلم نتيجة مستقرة.

• بالنسبة للتغذية المرتدة شبه-المنظمة (الافتراض 1 - تغطية حجم التحالف):

  • الشرط: يجب أن تغطي مجموعة البيانات جميع أحجام التحالفات التي يمكن أن تنتج عن الانحرافات أحادية الجانب من استراتيجية مستقرة وفق توازن ناش (NS).
  • الضرورة: يثبت المؤلفون أن هذا الافتراض ضروري. إذا كانت مجموعة البيانات تفتقر حتى إلى حجم تحالف واحد محدد يمكن الوصول إليه عبر انحراف أحادي الجانب، فلا يمكن لأي خوارزمية تعلم استراتيجية $\epsilon$-NS بكفاءة (تم إثبات ذلك عبر حجة عدم التمييز بين نموذجي لعبتين).
  • الكفاية: في ظل هذا الافتراض، يستنتجون خوارزمية فعالة من حيث العينات.

• بالنسبة للتغذية المرتدة من نوع "بانديت" (الافتراض 2 - تغطية الإجراء):

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

3.2 حدود تعقيد العينات (Sample Complexity Bounds)

يوفر المؤلفون خوارزميات ذات تعقيد عينات منخفض (تتطلب مجموعات بيانات صغيرة) تحقق نتائج $\epsilon$-NS:

• شبه-المنظمة (Semi-Bandit): يتناسب تعقيد العينات بشكل مثالي مع $\epsilon$ (حتى لو كانت عوامل لوغاريتمية) ومع عدد الوكلاء $n$ والتحالفات $k$ بشكل متعدد الحدود.
  $$M = O\left( \frac{n^2 k}{\epsilon^2} \cdot \text{polylog}(n, k, 1/\delta) \right)$$
• بانديت (Bandit): تعقيد العينات أعلى بسبب نقص البيانات التفصيلية، لكنه لا يزال يحقق ضمانات المثالية حتى مع العوامل اللوغاريتمية تحت الافتراض الأكثر صرامة.
  $$M = O\left( \frac{n^2 k}{\epsilon^2} \cdot \text{polylog}(n, k, 1/\delta) \right)$$
  (ملاحظة: الثوابت والارتباطات المحددة مع $n$ و $k$ تختلف قليلاً بينهما، لكن كلاهما يتجنب الاعتماد الأسي على حجم فضاء الإجراءات كما هو متبع في إعدادات الوكلاء المتعددين العامة).

3.3 الاستراتيجيات النقية مقابل المختلطة

بينما يتعامل الإطار مع الاستراتيجيات المختلطة، يوضح المؤلفون أنه بالنسبة للألعاب المتماثلة، توجد دائماً استراتيجيات مستقرة وفق توازن ناش نقية. يقومون بتكييف الخوارزمية لإخراج استراتيجيات نقية، مما يقلل من عامل تعقيد العينات المتعلق بعدد أحجام التحالفات الممكنة (من $n+1$ إلى ثابت قدره 3).

4. النتائج والتجارب

• التجارب الاصطناعية: قيم المؤلفون الخوارزمية 1 على مجموعات بيانات اصطناعية مع أعداد متفاوتة من الوكلاء ($n$) والتحالفات ($k$).
• التحقق من الافتراضات:
  • عندما تم إنشاء مجموعة البيانات بواسطة سياسة عشوائية منتظمة (التي تستوفي افتراضات التغطية)، تقاربت الخوارزمية باستمرار نحو فجوة مزدوجة منخفضة (استقرار عالٍ وفق توازن ناش) مع زيادة حجم مجموعة البيانات.
  • عندما تم إنشاء مجموعة البيانات بواسطة سياسة منحازة (التي تنتهك افتراضات التغطية، مثل فقدان أحجام تحالف محددة)، فشلت الخوارزمية في التقارب نحو نتيجة مستقرة، مما يؤكد الضرورة النظرية لافتراضات التغطية.
• التوسع (Scaling): تطابقت النتائج التجريبية مع معدل التقارب النظري $1/\sqrt{M}$ والتوسع مع $n$ و $k$.

5. الأهمية والتأثير

1. الربط بين التعلم غير المتصل (Offline RL) ونظرية الألعاب: يعد هذا العمل خطوة مهمة في تطبيق تقنيات التعلم المعزز غير المتصل على نظرية الألعاب التعاونية، وتحديداً في معالجة مشكلة "التغطية" في بيئات الوكلاء المتعددين.
2. القابلية للتطبيق في العالم الحقيقي: نموذج التحالفات المتداخلة والمعلومات الجزئية ذو صلة وثيقة بالسيناريوهات الواقعية مثل شركات الاستشارات، والتعاونات البحثية، واقتصادات العمل الحر (Gig Economies)، حيث يعمل الوكلاء في فرق متعددة وتكون البيانات التاريخية هي المصدر الوحيد لمعلومات التفضيلات.
3. الدقة النظرية: تقدم الورقة أول شروط ضرورية وكافية لتعلم الاستقرار وفق توازن ناش في ألعاب التحالف المتداخلة. وهي تميز بصرامة بين متطلبات المعلومات للتغذية المرتدة شبه-المنظمة وتغذية "بانديت"، موضحة أن البيانات التفصيلية حاسمة لمتطلبات التغطية الأضعف.
4. الكفاءة: من خلال إزالة الاعتماد الأسي على عدد الإجراءات (كما هو الحال غالباً في الألعاب ذات المجموعات غير المتساوية)، توفر الخوارزميات المقترحة مساراً عملياً لإيجاد هياكل تحالف مستقرة في الأنظمة واسعة النطاق دون الحاجة إلى استكشاف نشط ومكلف.

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