نظرية الألعاب الحسابية

• تهدف نظرية الألعاب الحسابية إلى تصميم خوارزميات فعالة للأنظمة التي تشمل عدة وكلاء استراتيجيين من منظور علوم الحاسوب.
• تهدف نظرية الألعاب الحسابية إلى استخدام التعقيد الحسابي لفهم جدوى مفاهيم الحل المختلفة في نظرية الألعاب من منظور نظرية الألعاب.

أمثلة

• مزادات البحث المدفوع: تبيع محركات البحث مثل محرك بحث جوجل خانات الإعلانات عبر المزادات.
• توجيه الشبكة: تريد شركات تزويد خدمات الإنترنت توجيه حركة المرور بكفاءة.
• تبادل الكلى: تريد المستشفيات إيجاد أفضل طريقة لمطابقة المرضى مع المتبرعين المتوافقين.

التوجيه الأناني

• توجد شبكة من $n$ من اللاعبين الذين يرغبون في توجيه حركة المرور من المصدر إلى الوجهة.
• لكل حافة $e$ دالة تكلفة $c_e(x)$ تعتمد على كمية حركة المرور على الحافة.
• توازن واردوب هو تدفق لا يستطيع فيه أي لاعب تحسين تكلفته بتغيير مساره من جانب واحد.
• يتمثل سعر الفوضى في نسبة التكلفة بين أسوأ توازن في واردوب وتكلفة التدفق الأمثل.

$$ PoA = \frac{\text{تكلفة أسوأ توازن في واردوب}}{\text{تكلفة التدفق الأمثل}} $$

مفارقة برايس

• يمكن لإضافة حافة إلى الشبكة أن تزيد من تكلفة جميع اللاعبين في حالة التوازن.
• المثال: وحدة واحدة من حركة المرور تريد السفر من A إلى B.
• بدون الحافة المتقطعة، تكون التكلفة 1.
• مع الحافة المتقطعة، تكون التكلفة $\frac{3}{2}$.

الشبكة بدون الحافة المتقطعة

• الحافة من A إلى C: $c(x) = x$.
• الحافة من A إلى D: $c(x) = 1$.
• الحافة من C إلى B: $c(x) = 1$.
• الحافة من D إلى B: $c(x) = x$.

الشبكة مع الحافة المتقطعة

• الحافة من A إلى C: $c(x) = x$.
• الحافة من A إلى D: $c(x) = 1$.
• الحافة من C إلى B: $c(x) = 1$.
• الحافة من D إلى B: $c(x) = x$.
• الحافة من C إلى D: $c(x) = 0$.
• سعر الفوضى في الشبكة ذات دوال التكلفة الخطية هو $\frac{4}{3}$ على الأكثر.