الأسس البديهية والاحتمالية لقيمة شابلي النظرية الهودجية

المعلومات الأساسية

• معرّف الورقة: 2106.15094
• العنوان: الأسس البديهية والاحتمالية لقيمة شابلي النظرية الهودجية
• المؤلف: Tongseok Lim (جامعة بوردو)
• التصنيف: math.OC cs.GT econ.TH
• تاريخ النشر: 14 أكتوبر 2025 (مسودة arXiv)
• رابط الورقة: https://arxiv.org/abs/2106.15094

الملخص

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

السياق البحثي والدافع

خلفية المشكلة

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

الدافع البحثي

1. النقص النظري: على الرغم من إمكانية تطبيق صيغة شابلي على كل لعبة فرعية، فإن هذا النهج يفترض ضمناً أن الائتلاف ينمو فقط نحو الهدف S، مما يفشل في التقاط البنية الكاملة للعبة الأكبر التي تتضمن جميع المشاركين في N.
2. الاحتياجات العملية: تتطلب التطبيقات الحديثة (تقييم البيانات في التعلم الآلي والإسناد المميز وتفسير النماذج الطبية وغيرها) تقييم مساهمات المشاركين في الائتلافات الجزئية.
3. الاكتمال النظري: على الرغم من الابتكار في إطار ستيرن-تيتنهورست، إلا أنه يعاني من مشكلتين حاسمتين:
   • غياب أساس بديهي شامل يميز بشكل فريد قيم جميع الائتلافات الجزئية
   • غياب تفسير احتمالي مشابه لصيغة شابلي

المساهمات الأساسية

1. التوصيف البديهي الشامل: اقتراح خمسة بديهيات (A1-A5) تحدد بشكل فريد توزيع القيمة في جميع حالات الائتلاف، وليس فقط الائتلاف الكبير.
2. نظرية التمثيل الاحتمالي: اشتقاق صيغة احتمالية تستند إلى المسير العشوائي على رسم بياني الائتلاف، تفسر قيمة المشارك كمساهمة هامشية متراكمة متوقعة.
3. التوحيد النظري: إنشاء التكافؤ بين الطريقة البديهية والتفسير الاحتمالي، مما يوفر أساساً نظرياً متيناً لقيمة شابلي النظرية الهودجية.
4. الطرق الحسابية: إثبات أن القيمة المعرفة احتمالياً يمكن حسابها بكفاءة من خلال حل نظام المعادلات الخطية (3.3).

شرح الطريقة

تعريف المهمة

بالنظر إلى لعبة تعاونية v ∈ G_N، قم بتعيين قيمة Φ_i(v,S) لكل ائتلاف S ⊆ N وكل مشارك i ∈ N، بحيث تفي بمعايير العدالة وتتمتع بتفسير احتمالي.

الإطار الأساسي

1. بناء رسم بياني الائتلاف

استخدام رسم بياني فوق المكعب G = (V,E) لتمثيل فضاء الائتلاف:

• مجموعة الرؤوس: V := 2^N = {S | S ⊆ N}
• مجموعة الحواف: E := {(S, S ∪ {i}) ∈ V × V | S ⊆ N \ {i}, i ∈ N}

2. معادلة بواسون

معادلة التوازن المقترحة من قبل ستيرن-تيتنهورست:

Φ_i(v,S) - (1/|N|)∑_{T~S} Φ_i(v,T) = (1/|N|)∑_{T~S} ∂_iv(T,S)

حيث ∂_iv تمثل المساهمة الهامشية للمشارك i.

3. نظام البديهيات الخمسة

• A1 (الكفاءة): v(S) = ∑_{i∈N} Φ_i(v,S)
• A2 (الخطية): Φ_i(αv + α'v', S) = αΦ_i(v,S) + α'Φ_i(v',S)
• A3 (التماثل): Φ_i(v^{ij}, S^{ij}) = Φ_j(v,S)
• A4 (المشارك الصفري): إذا كان ∂iv ≡ 0، فإن Φ_j(v, S∪{i}) = Φ_j(v,S) = Φ_j(v{-i}, S)
• A5 (الاستقلالية): لجميع S ⊆ N{i}، Φ_i(v,S) + Φ_i(v, S∪{i})/2 ثابت

نقاط الابتكار التقني

1. بديهية الاستقلالية (A5)

هذا هو الابتكار الرئيسي، الذي يتطلب أن يكون متوسط قيمة المشارك i في حالات داخل وخارج الائتلاف مستقلاً عن الائتلاف المحدد S. هذا الشرط:

• يكمل أوجه القصور في بديهيات شابلي الكلاسيكية
• يضمن الفرادة على جميع الائتلافات الجزئية
• له تفسير عدالة بديهي

2. نموذج المسير العشوائي

سلسلة ماركوف معرفة على فضاء الائتلاف:

• احتمالية الانتقال: p_{S,T} = 1/|N| إذا كان T ~ S
• تسمح للمشاركين بالانضمام والمغادرة من الائتلاف
• الحالة الأولية: X_0 = ∅

3. تمثيل تكامل المسار

إجمالي المساهمة المتوقعة للمشارك i للوصول إلى الائتلاف S:

Ψ_i(v,S) = E[∑_{t=1}^{τ_S} ∂_iv(X_{t-1}, X_t)]

النتائج النظرية الرئيسية

النظرية 4.1 (التوصيف الفريد)

يوجد تطبيق فريد Φ يرضي البديهيات A1-A5 والشروط الأولية Φ(v,∅) = 0، وهذا التطبيق هو بالضبط حل معادلة بواسون (3.3).

النظرية 5.1 (التكافؤ الاحتمالي)

Φ = Ψ، أي أن القيمة المعرفة بديهياً والقيمة المعرفة بتكامل المسار الاحتمالي متساوية تماماً.

التحقق التجريبي

مثال لعبة القفازات

بالنسبة للعبة القفازات ثلاثية الأشخاص (المشارك 1 لديه قفاز أيسر، والمشاركون 2 و 3 لديهم قفازات يمنى):

• قيمة شابلي الكلاسيكية: ϕ_1(v) = 2/3, ϕ_2(v) = ϕ_3(v) = 1/6
• توفر القيمة النظرية الهودجية جدول قيم كامل لجميع الائتلافات الجزئية

الحساب المباشر للعبة ثنائية الأشخاص

يعرض المؤلف بالتفصيل عملية الحساب المباشر لقيمة Ψ في لعبة ثنائية الأشخاص، مما يتحقق من الاتساق مع حل معادلة بواسون.

الأعمال ذات الصلة

الأسس النظرية الكلاسيكية

• نظام البديهيات الأربعة الأصلي لشابلي (1953)
• التقليد البديهي في نظرية اللعب التعاوني

التوسعات الحديثة

• تطبيق نظرية هودج التوليفية في نظرية اللعب (Candogan وآخرون، 2011)
• التفسير النظري للعبة لمعادلات بواسون على الرسوم البيانية (Jiang وآخرون، 2011)
• العمل الرائد لستيرن-تيتنهورست (2019)

مجالات التطبيق

• الإسناد المميز وتقييم البيانات في التعلم الآلي
• تفسير النماذج الطبية
• توزيع التكاليف في الطاقة المستدامة
• تحليل الشبكات الاجتماعية

الخلاصة والمناقشة

الاستنتاجات الرئيسية

1. التوصيف الشامل: نظام البديهيات الخمسة يحدد بشكل فريد قيمة شابلي النظرية الهودجية
2. التفسير الاحتمالي: نموذج المسير العشوائي يوفر معنى احتمالياً بديهياً
3. التوحيد النظري: إنشاء التكافؤ بين الطريقة البديهية والطريقة الاحتمالية
4. الجدوى الحسابية: حل نظام المعادلات الخطية يوفر طريقة حسابية عملية

الأهمية النظرية

• أول توصيف شامل لحل معادلة بواسون على الرسوم البيانية
• توسيع نظرية شابلي من الائتلاف الكبير إلى شبكة الائتلاف بأكملها
• توحيد مبادئ العدالة مع تفسير العمليات العشوائية

القيود

1. التعقيد الحسابي: قد يواجه حل نظام المعادلات الخطية تحديات حسابية للألعاب الكبيرة
2. افتراضات النموذج: قد لا تكون احتمالات الانتقال المنتظمة مناسبة لجميع السيناريوهات العملية
3. التحقق التطبيقي: يتطلب المزيد من التحقق من التطبيقات العملية لفعالية الإطار النظري

الاتجاهات المستقبلية

1. تطوير خوارزميات حسابية فعالة للألعاب الكبيرة الحجم
2. تطبيق الإطار على مشاكل عملية (الاقتصاد والعلوم السياسية والتعلم الآلي)
3. دراسة التوسعات مع احتمالات انتقال غير منتظمة
4. استكشاف نظريات مماثلة على هياكل رسوم بيانية أخرى

التقييم المتعمق

المزايا

1. الاكتمال النظري: توفير الأساس النظري الشامل الذي يفتقده إطار ستيرن-تيتنهورست
2. ابتكار الطريقة: بديهية الاستقلالية A5 هي ابتكار رئيسي ذو أهمية نظرية عميقة
3. المنظور المزدوج: توحيد الطريقة البديهية والاحتمالية يعزز قوة الإقناع النظري
4. الإثبات الصارم: استخدام أدوات نظرية هودج التوليفية للإثبات الرياضي الصارم

أوجه القصور

1. التحقق العملي: غياب التحقق من التطبيقات الفعلية الكبيرة الحجم
2. الكفاءة الحسابية: عدم مناقشة كافية للتعقيد الحسابي في الحالات الكبيرة
3. قيود النموذج: افتراض المسير العشوائي المنتظم قد يكون مبسطاً بشكل مفرط

التأثير

1. المساهمة النظرية: توفير توسيع نظري مهم لنظرية اللعب التعاوني
2. القيمة متعددة التخصصات: إمكانية تطبيق واسعة في التعلم الآلي والاقتصاد وغيرها
3. الأهمية المنهجية: توضيح كيفية تطبيق الأدوات الرياضية المجردة على مشاكل نظرية اللعب

السيناريوهات المناسبة

• ألعاب تعاونية تتطلب تقييم مساهمات الائتلافات الجزئية
• الإسناد المميز وتفسير النماذج في التعلم الآلي
• تقييم أهمية العقد في تحليل الشبكات
• مشاكل توزيع التكاليف والفوائد في الاقتصاد

المراجع

• Shapley, L. S. (1953). قيمة لألعاب n-شخص.
• Stern, A. & Tettenhorst, A. (2019). تحلل هودج وقيمة شابلي للعبة تعاونية. Games and Economic Behavior.
• Candogan, O. وآخرون (2011). التدفقات والتحللات للألعاب: الألعاب التوافقية والمحتملة. Mathematics of Operations Research.

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