الانتقال إلى المحتوى
العودة إلى نتائج البحث

توازن ناش (Nash Equilibrium)

قدّمه
John Nash
السنة
1950
النوع
algorithm
العائلة
Game-theoretic

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

في توازن ناش، تكون استراتيجية كل لاعب هي أفضل استجابة لكل استراتيجية لاعب آخر. تخيل موقفًا يعرف فيه كلا اللاعبين استراتيجية الآخر: لن يرغب أي منهما في التغيير لأن القيام بذلك سيضر بهما فقط. تستغل خوارزمية Lemke-Howson هندسة متعددات الأوجه للألعاب، وتتتبع التسميات (القيود غير المُرضاة) وتتنقل عبر الرؤوس حتى يتم العثور على زوج ذي تسمية كاملة - وهو تكوين لا يملك فيه كلا اللاعبين انحرافات مربحة.

التاريخ

أثبت جون ناش في أطروحته عام 1950 أن كل لعبة محدودة تمتلك على الأقل توازن ناش باستراتيجية مختلطة واحدة. في عام 1964، نشر Lemke و Howson أول خوارزمية بناءة لإيجاد هذه التوازنات، محولين إثبات وجود ناش إلى طريقة حسابية عملية. أصبح عملهما أساسيًا لنظرية الألعاب الحسابية والاقتصاد الخوارزمي.

متى تُستخدم

استخدم تحليل توازن ناش عند دراسة الألعاب ذات لاعبين ومساحات استراتيجية منفصلة، أو عند البحث عن توازنات مختلطة بالكامل. مناسب لنمذجة المنافسة والتفاوض ومشكلات التنسيق حيث يكون التفاعل الاستراتيجي أمرًا بالغ الأهمية. تعمل طريقة Lemke-Howson بشكل أفضل للألعاب ثنائية المصفوفة غير المنحرفة؛ قد تتطلب الحالات المنحرفة حسابًا رمزيًا أو اضطرابًا.

الحدود والاعتبارات

  • محدودة بالألعاب ثنائية اللاعبين (ثنائية المصفوفة)؛ امتداد الألعاب متعددة اللاعبين هو مسألة NP-hard
  • تفشل أو تصبح غير فعالة في الألعاب المنحرفة حيث تكون هناك عدة تحركات دخول ممكنة
  • قد تجد توازنًا واحدًا فقط؛ غالبًا ما توجد توازنات متعددة في الألعاب غير الصفرية
  • لا تتعامل مباشرة مع الألعاب الديناميكية أو الألعاب ذات الشكل الواسع دون إعادة صياغة

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

نقاط القوة

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

التطبيقات

  • الاقتصاد: نمذجة المنافسة الاحتكارية وسلوك تحديد الأسعار في الأسواق
  • المزادات وتصميم الآليات: تحليل استراتيجيات المزايدة في المزادات ذات السعر الأول والمغلقة
  • الأمن السيبراني: التنبؤ بتوازنات المهاجم والمدافع في ألعاب أمن الشبكات
  • علم الأحياء البرية: تحليل الاستراتيجيات المستقرة تطوريًا في تفاعلات المفترس والفريسة

كيف يعمل

كيف يعمل

1

تحويل لعبة ثنائية المصفوفة إلى مشكلتين من مشاكل التكامل الخطي (LCP)، واحدة لكل لاعب، تمثل شروط الاستجابة الأفضل لديهما.

2

تعيين تسميات لحواف ورؤوس متعددات الأوجه للاستراتيجيات بناءً على أي من قيود حوافز اللاعبين يتم انتهاكها.

3

بدءًا من الرأس الذي يتكون من جميع الواحدات (ذو تسمية كاملة)، قم بإجراء تنقلات تشبه السمبلكس للتنقل في متعدد الأوجه، وإزالة وإضافة التسميات حتى يتم اكتشاف زوج ذي تسمية كاملة.

4

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

الأخطاء الشائعة

  • افتراض وجود توازن فريد؛ العديد من الألعاب لها توازنات ناش متعددة ذات آثار مكاسب مختلفة
  • الخلط بين توازنات الاستراتيجية المختلطة (اللعب الاحتمالي) وتوازنات الاستراتيجية النقية، مما يؤدي إلى سوء تفسير سلوك الوكلاء
  • تجاهل التمييز بين الشروط الضرورية والكافية للتوازن؛ الزوج ذو التسمية الكاملة يحقق الأمثلية ولكنه قد لا يتحقق إذا لم يتمكن اللاعبون من التنسيق

الأسئلة الشائعة

هل يمكن أن يكون للعبة توازن ناش غير موجود؟

قد لا توجد توازنات استراتيجية نقية (مثل، حجر-ورقة-مقص)، ولكن كل لعبة محدودة لديها على الأقل توازن استراتيجية مختلطة واحدة حيث يقوم اللاعبون بالعشوائية على الإجراءات باحتمالات محددة.

كيف يختلف توازن الاستراتيجية المختلطة عن توازن الاستراتيجية النقية؟

في توازن الاستراتيجية النقية، يلتزم كل لاعب بإجراء محدد بشكل مؤكد. في توازن الاستراتيجية المختلطة، يستخدم كل لاعب توزيعًا احتماليًا على الإجراءات. غالبًا ما تكون التوازنات المختلطة أكثر عمومية وتوجد عندما لا توجد توازنات نقية.

لماذا تُفضل خوارزمية Lemke-Howson على البحث الشامل؟

تستغل الخوارزمية بنية متعدد الأوجه لمساحات الاستراتيجية، مما يقلل مساحة البحث بشكل أسي ويحقق التقارب في وقت متعدد الحدود للألعاب غير المنحرفة، في حين يصبح التعداد الشامل غير عملي مع نمو مساحة الاستراتيجية.

طرق ذات صلة

المصادر

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    افتح مرجع DOI
    تم النسخ.
  2. Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.

    افتح مرجع DOI
    تم النسخ.