الدرس 1 من 2 · نظرية الألعاب
الألعاب الاستراتيجية وتوازن ناش Strategic Games and Nash Equilibrium
في اللعبة الاستراتيجية يعتمد عائد كل لاعب على اختيارات الآخرين؛ وتوازن ناش حالة لا يستفيد فيها أي لاعب من تغيير استراتيجيته منفرداً، وقد يكون خالصاً أو مختلطاً، ولكل لعبة منتهية توازن مختلط واحد على الأقل.
محتويات الدرس
1 مقدمة
عندما يدرب فريقان نموذجين يتنافسان، أو يتفاوض وكيلان ذكيان على سعر، أو تتنافس سيارتان ذاتيتا القيادة على المسار نفسه، فإن أفضل قرار لكل طرف يعتمد على قرار الآخر. نظرية الألعاب تعطينا لغة دقيقة لتحليل هذه المواقف.
الأهداف التعليمية
- تمثيل لعبة ثنائية بمصفوفتي عوائد
- إيجاد أفضل الاستجابات وتوازنات ناش الخالصة
- حساب التوازن المختلط في ألعاب 2×2 بمبدأ عدم الاكتراث
- التمييز بين التوازن والأمثلية الجماعية (معضلة السجينين)
2 لماذا ندرس هذا الموضوع؟
الأنظمة متعددة الوكلاء والتعلم المعزز متعدد الوكلاء تقوم على مفاهيم التوازن، والشبكات التوليدية التنافسية لعبة بين مولّد ومميّز، وتفسير قرارات النماذج بقيم شابلي (SHAP) مستمد من نظرية الألعاب التعاونية. فهم توازن ناش هو نقطة البداية.
3 الشرح النظري
اللعبة في شكلها الاستراتيجي
لاعبان، لكل منهما مجموعة استراتيجيات. المصفوفة A تعطي عوائد اللاعب الأول (الصف) والمصفوفة B عوائد الثاني (العمود). في معضلة السجينين (العوائد سنوات سجن بإشارة سالبة):
| تعاون | خيانة | |
|---|---|---|
| تعاون | (−1، −1) | (−3، 0) |
| خيانة | (0، −3) | (−2، −2) |
أفضل استجابة وتوازن ناش
أفضل استجابة لاعب هي الاستراتيجية التي تعظم عائده بمعلومية استراتيجية الآخر. والزوج \((i^*, j^*)\) توازن ناش إذا كانت كل استراتيجية أفضل استجابة للأخرى:
\[A_{i^*j^*} \ge A_{ij^*}\;\forall i,\qquad B_{i^*j^*} \ge B_{i^*j}\;\forall j\]
في معضلة السجينين «الخيانة» أفضل لكل لاعب أياً كان اختيار الآخر، فالتوازن الوحيد (خيانة، خيانة) بعائد \((-2, -2)\)، مع أن (تعاون، تعاون) أفضل لكليهما. التوازن ليس بالضرورة أمثلاً جماعياً.
التوازن المختلط
في «مطابقة العملات» لا يوجد توازن خالص. الحل أن يختار كل لاعب عشوائياً باحتمالات محددة. مبدأ عدم الاكتراث: في التوازن المختلط يجعل كل لاعب خصمه غير مكترث بين استراتيجيتيه. في لعبة 2×2، إذا لعب الثاني العمود الأول باحتمال q:
\[q A_{11} + (1-q)A_{12} = q A_{21} + (1-q)A_{22} \Rightarrow q^* = \frac{A_{22} - A_{12}}{A_{11} - A_{12} - A_{21} + A_{22}}\]
وبالمثل \(p^*\) من مصفوفة B. في «معركة الجنسين» \(A = \begin{bmatrix}2&0\\0&1\end{bmatrix}\) و\(B = \begin{bmatrix}1&0\\0&2\end{bmatrix}\): توازنان خالصان، وتوازن مختلط \(p^* = 2/3\) و\(q^* = 1/3\).
مبرهنة ناش
لكل لعبة منتهية (عدد منته من اللاعبين والاستراتيجيات) توازن ناش واحد على الأقل باستراتيجيات مختلطة (ناش، 1950). لكن إيجاده في الألعاب الكبيرة صعب حسابياً، ولذلك تُدرس ديناميكيات التعلم التي قد تتقارب إليه أو لا.
4 التعريفات الرياضية
- توازن ناش
- ملف استراتيجيات لا يستطيع فيه أي لاعب زيادة عائده بتغيير استراتيجيته منفرداً.
- أفضل استجابة
- الاستراتيجية التي تعظم عائد اللاعب بمعلومية استراتيجيات الآخرين.
- الاستراتيجية المختلطة
- توزيع احتمالي على الاستراتيجيات الخالصة.
- الاستراتيجية المهيمنة
- استراتيجية أفضل من غيرها أياً كان ما يفعله الآخرون.
- توازن ناش (Nash Equilibrium)
- ملف استراتيجيات لا يستفيد فيه أي لاعب من الانحراف منفرداً.\[A_{i^*j^*}\ge A_{ij^*},\;B_{i^*j^*}\ge B_{i^*j}\]
- الاستراتيجية المختلطة (Mixed Strategy)
- توزيع احتمالي على الاستراتيجيات الخالصة، ويُحسب في التوازن بمبدأ عدم الاكتراث.\[q^*=\frac{A_{22}-A_{12}}{A_{11}-A_{12}-A_{21}+A_{22}}\]
- أفضل استجابة (Best Response)
- الاستراتيجية التي تعظم عائد اللاعب بمعلومية استراتيجيات الآخرين.\[\arg\max_i A_{ij}\]
5 المعادلات
6 مثال محلول خطوة بخطوة
معضلة السجينين
المسألة: أوجد توازن ناش في معضلة السجينين.
- إذا تعاون الآخر: الخيانة تعطي 0 مقابل −1.
- إذا خان الآخر: الخيانة تعطي −2 مقابل −3.
- الخيانة مهيمنة للاعبين.
النتيجة: (خيانة، خيانة) بعائد (−2، −2)
توازن مختلط
المسألة: أوجد التوازن المختلط لمعركة الجنسين.
- \(q^* = (1 - 0)/(2 - 0 - 0 + 1) = 1/3\).
- \(p^* = (2 - 0)/(1 - 0 - 0 + 2) = 2/3\).
النتيجة: \(p^* = 2/3\)، \(q^* = 1/3\)، والعائد المتوقع للأول \(0.6667\)
لا توازن خالص
المسألة: أثبت أن مطابقة العملات لا توازن خالصاً لها.
- في كل خانة يكسب أحدهما 1 ويخسر الآخر 1.
- الخاسر يستفيد دائماً من تغيير اختياره.
النتيجة: التوازن الوحيد مختلط \((1/2, 1/2)\)
7 تطبيق عملي في الذكاء الاصطناعي
- الأنظمة متعددة الوكلاء: وكلاء التعلم المعزز في بيئة مشتركة يتقاربون أحياناً إلى توازن، وأحياناً يدورون حوله.
- تصميم الآليات والمزادات: تُصمم قواعد المزادات الإعلانية بحيث يكون الصدق في المزايدة توازناً.
- قيم شابلي: مقياس SHAP لتفسير النماذج مستمد من توزيع العائد العادل في الألعاب التعاونية.
8 مختبر تفاعلي مرتبط بالدرس
ألعاب ثنائية بمصفوفتي عوائد مع توازنات ناش الخالصة والمختلطة ودالتي أفضل استجابة، والألعاب الصفرية ومبرهنة Minimax، وديناميكيات التعلم: الانحدار-الصعود التدرجي المتزامن والمتناوب واللعب الوهمي.
افتح مختبر نظرية الألعاب9 تمارين تدريبية
أسئلة مراجعة للتفكير
- لماذا لا يكون (تعاون، تعاون) توازناً في معضلة السجينين؟
- لماذا يُحسب \(q^*\) من مصفوفة اللاعب الأول لا الثاني؟
أخطاء شائعة
- الخلط بين توازن ناش والنتيجة الأفضل للجميع.
- البحث عن أفضل استجابة لاعب في مصفوفة الآخر.
- افتراض أن لكل لعبة توازناً خالصاً.
- تفسير الاستراتيجية المختلطة على أنها تردد أو جهل؛ هي اختيار عشوائي مقصود يمنع الاستغلال.
10 ملخص الدرس
- توازن ناش: لا أحد يستفيد من الانحراف منفرداً.
- قد يكون التوازن أسوأ للجميع من بديل آخر.
- التوازن المختلط يُحسب بمبدأ عدم الاكتراث.
- كل لعبة منتهية لها توازن مختلط.
11 اختبار قصير
5 أسئلة · 10 دقائق · النجاح من 60% — اجتيازه يُكمل الدرس.
