مقدمة في نظرية الألعاب

• نظرية الألعاب: دراسة النماذج الرياضية للتفاعلات الاستراتيجية بين الوكلاء العقلانيين.

جون ناش

• طالب دراسات عليا في جامعة برينستون.
• أطروحة الدكتوراه: الألعاب غير التعاونية (1950).
• جائزة نوبل في الاقتصاد (1994).
• مصدر إلهام لفيلم "A Beautiful Mind".

التفاعل الاستراتيجي

• يعتمد نفع كل وكيل ليس فقط على أفعاله، بل أيضًا على أفعال الوكلاء الآخرين.

العقلانية

• يتصرف كل وكيل لتعظيم نفعه الشخصي.

الأنانية مقابل الإيثار

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

أمثلة

• المزادات
• المفاوضات
• ألعاب الازدحام
• توجيه الشبكة
• تبادل الكلى
• الشبكات الاجتماعية
• ألعاب الأمن

نظرية الألعاب الخوارزمية

• مجال متعدد التخصصات يقع عند تقاطع نظرية الألعاب وعلوم الكمبيوتر.

الحساب (Computation)

• كيف يتم حساب مفاهيم الحل في الألعاب؟
• ما هي التعقيدات الحسابية؟
• هل يمكننا تصميم خوارزميات فعالة؟

التصميم

• كيف يمكننا تصميم الألعاب لتحقيق نتائج مرغوبة؟
• ما هي الحوافز الصحيحة لمواءمة الأهداف الفردية والاجتماعية؟

عناصر مهمة في هذه الدورة التدريبية

• تصميم الآلية
• الاختيار الاجتماعي
• التقسيم العادل
• ثمن الفوضى

الوكلاء المهتمون بأنفسهم

مثال: لعبة التوجيه

• $n$ من الوكلاء يريدون السفر من S إلى T.
• يختار كل وكيل مسارًا.
• تكلفة المسار هي مجموع تكاليف الحواف على المسار.
• يريد كل وكيل تقليل تكلفته الخاصة.

النتيجة المثالية اجتماعيًا

• تقليل التكلفة الإجمالية لجميع الوكلاء.

النتيجة الأنانية

• يختار كل وكيل مسارًا يقلل من تكلفته الخاصة, بالنظر إلى اختيارات الوكلاء الآخرين.

المصطلحات

• اللاعبون / الوكلاء: الأفراد الذين يتخذون القرارات.
• الاستراتيجيات: الخيارات الممكنة المتاحة لكل لاعب.
• المنافع / العوائد: القيمة العددية التي تمثل النتيجة لكل لاعب بناءً على الاستراتيجيات التي اختارها جميع اللاعبين.
• ملف تعريف الاستراتيجية: مجموعة من الاستراتيجيات، واحدة لكل لاعب.
• الرفاهية الاجتماعية: مجموع منافع جميع اللاعبين.
• التكلفة: فائدة سلبية.

مثال: معضلة السجين

• تم القبض على متهمين لارتكاب جريمة. يتم احتجازهما في زنزانات منفصلة ولا يمكنهما التواصل. تعرض الشرطة على كل مشتبه به الصفقة التالية:
  • إذا اعترفت ولم يعترف شريكك، فسيتم إطلاق سراحك، ويحصل شريكك على 10 سنوات.
  • إذا اعترفتما كلاكما، فستحصلان على 5 سنوات لكل منكما.
  • إذا لم تعترف واعترف شريكك، فستحصل على 10 سنوات، ويتم إطلاق سراح شريكك.
  • إذا لم يعترف أي منكما، فستحصلان على سنة واحدة لكل منكما.

مصفوفة العوائد

• توضح نتائج الحالات المختلفة للاعتراف و الصمت لكلا المتهمين.

تحليل

• الاستراتيجية المهيمنة لكل لاعب هي الاعتراف.
• توازن ناش هو أن يعترف كلا اللاعبين.
• النتيجة المثالية اجتماعيًا هي أن يبقى كلا اللاعبين صامتين.

توازن ناش

تعريف

• عبارة عن مجموعة من الاستراتيجيات حيث لا يمكن لأي لاعب تحسين نفعه عن طريق تغيير استراتيجيته من جانب واحد، بافتراض أن استراتيجيات اللاعبين الآخرين تظل ثابتة.

الترميز

• $n$ لاعبًا ${1, 2,..., n}$
• $S_i$ هي مجموعة الاستراتيجيات للاعب $i$
• $s_i \in S_i$ هي استراتيجية للاعب $i$
• $s = (s_1, s_2,..., s_n)$ هو ملف تعريف الاستراتيجية
• $s_{-i} = (s_1,..., s_{i-1}, s_{i+1},..., s_n)$ هو ملف تعريف استراتيجية بدون استراتيجية اللاعب $i$
• $u_i(s)$ هو نفع اللاعب $i$ في ملف تعريف الاستراتيجية $s$

التعريف الرسمي

• ملف تعريف الاستراتيجية $s = (s_1, s_2,..., s_n)$ هو توازن ناش إذا كان لكل لاعب $i$ ولكل استراتيجية $s_i' \in S_i$: $u_i(s_i, s_{-i}) \ge u_i(s_i', s_{-i})$

تعريف بديل

• ملف تعريف الاستراتيجية $s = (s_1, s_2,..., s_n)$ هو توازن ناش إذا كان لكل لاعب $i$: $s_i \in \argmax_{s_i' \in S_i} u_i(s_i', s_{-i})$

أمثلة

• معضلة السجين: (اعترف، اعترف) هو توازن ناش.
• لعبة التوجيه: ملف تعريف استراتيجية حيث يختار كل وكيل أقصر مسار نظرًا للازدحام الناجم عن الوكلاء الآخرين هو توازن ناش.

وجود توازن ناش

نظرية (ناش، 1950)

• كل لعبة بها عدد محدود من اللاعبين وعدد محدود من الاستراتيجيات لديها توازن ناش واحد على الأقل (ربما في استراتيجيات مختلطة).

استراتيجية مختلطة

• توزيع احتمالي على مجموعة الاستراتيجيات النقية.

مثال: لعبة مطابقة العملات المعدنية

• يختار لاعبان في وقت واحد إظهار صورة (H) أو كتابة (T). إذا تطابقت الخيارات، يفوز اللاعب 1. إذا اختلفت الخيارات، يفوز اللاعب 2.

مصفوفة العوائد

• توضح نتائج الحالات المختلفة لاختيارات اللاعبين.

تحليل

• لا يوجد توازن ناش للاستراتيجية النقية.
• توازن ناش للاستراتيجية المختلطة هو أن يختار كل لاعب H باحتمال 1/2 و T باحتمال 1/2.

المرة القادمة

• سعر الفوضى
• تصميم الآلية (Mechanism Design)