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

📅 آخر تحديث: ٢٠ يوليو ٢٠٢٦
✍️ نُشر في: ٢٠ يوليو ٢٠٢٦
الموسوعة الحرة

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

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

يمكن تناول هذا المجال من منظورين متكاملين:

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

يجب على مصممي الخوارزميات في هذا المجال تلبية المتطلبات الخوارزمية التقليدية (مثل وقت التشغيل متعدد الحدود ونسبة التقريب الجيدة ) مع معالجة قيود الحوافز في الوقت نفسه لضمان تصرف المشاركين وفقًا للتصميم المقصود للنظام.

تاريخ

نيسان-رونين: إطار عمل جديد لدراسة الخوارزميات

في عام 1999، لفتت الورقة البحثية الرائدة لنوام نيسان وأمير رونين [ 1 ] انتباه مجتمع علوم الحاسوب النظرية إلى تصميم خوارزميات للمستخدمين الأنانيين (الاستراتيجيين). كما ذكرا في الملخص:

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

صاغت هذه الورقة البحثية مصطلح تصميم الآلية الخوارزمية ، وقد اعترفت بها لجنة جائزة غودل لعام 2012 كواحدة من "ثلاث أوراق بحثية أرست الأساس للنمو في نظرية الألعاب الخوارزمية". [ 2 ]

ثمن الفوضى

أما الورقتان البحثيتان الأخريان اللتان استُشهد بهما في جائزة غودل لعام 2012 لمساهماتهما الأساسية في نظرية الألعاب الخوارزمية، فقد قدمتا وطورتا مفهوم "ثمن الفوضى". في ورقتهما البحثية المنشورة عام 1999 بعنوان "توازنات أسوأ الحالات" [ 3 ] ، اقترح كوتسوبيا وباباديميتريو مقياسًا جديدًا لتدهور كفاءة النظام نتيجةً للسلوك الأناني لعناصره: وهو نسبة كفاءة النظام عند التكوين الأمثل إلى كفاءته عند أسوأ توازن ناش. (لم يظهر مصطلح "ثمن الفوضى" إلا بعد بضع سنوات. [ 4 ] )

الإنترنت كعامل محفز

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

تدرس نظرية الألعاب حالات التوازن (مثل توازن ناش ). يُعرَّف التوازن عمومًا بأنه حالة لا يكون لدى أي لاعب فيها حافز لتغيير استراتيجيته. توجد حالات التوازن في العديد من المجالات المتعلقة بالإنترنت، مثل التفاعلات المالية وموازنة أحمال الاتصالات . توفر نظرية الألعاب أدوات لتحليل حالات التوازن، ويتمثل أحد المناهج الشائعة في "إيجاد اللعبة" - أي صياغة تفاعلات محددة على الإنترنت كلعبة، واستنباط حالات التوازن المرتبطة بها.

إعادة صياغة المشكلات في سياق الألعاب تُتيح تحليل التفاعلات عبر الإنترنت وبناء آليات لتلبية متطلبات محددة. إذا أمكن إثبات وجود نقاط توازن، فلا بد من الإجابة على سؤال آخر: هل يمكن إيجاد نقطة توازن، وفي وقت معقول؟ يقود هذا إلى تحليل خوارزميات إيجاد نقاط التوازن. وتكتسب فئة التعقيد PPAD أهمية خاصة ، إذ تشمل العديد من المشكلات في نظرية الألعاب الخوارزمية.

مجالات البحث

تصميم الآلية الخوارزمية

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

عدم كفاءة التوازنات

طُرح مفهوما " ثمن الفوضى" و "ثمن الاستقرار" لوصف انخفاض أداء النظام نتيجةً للسلوك الأناني للمشاركين فيه. يُعبّر " ثمن الفوضى" عن أسوأ أداء للنظام عند حالة التوازن مقارنةً بالأداء الأمثل الممكن. [ 5 ] أما "ثمن الاستقرار"، فيُعبّر عن الأداء النسبي لأفضل حالة توازن للنظام. [ 6 ] يُعدّ هذان المفهومان نظيرين لمفهوم " نسبة التقريب" في تصميم الخوارزميات.

تعقيد إيجاد التوازنات

يُثبت وجود توازن في لعبة ما عادةً باستخدام نظريات النقطة الثابتة غير البنّاءة . لا توجد خوارزميات فعّالة معروفة لحساب توازنات ناش . تُعتبر المسألة كاملةً لفئة التعقيد PPAD حتى في الألعاب ثنائية اللاعبين. [ 7 ] في المقابل، يمكن حساب التوازنات المترابطة بكفاءة باستخدام البرمجة الخطية، [ 8 ] وكذلك تعلمها عبر استراتيجيات عدم الندم. [ 9 ]

الاختيار الاجتماعي الحسابي

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

وتشمل المواضيع الأخرى ما يلي:

وتضم المنطقة تطبيقات عملية متنوعة: [ 11 ] [ 12 ]

المجلات والنشرات الإخبارية

غالباً ما يتم نشر أوراق نظرية الألعاب الخوارزمية أيضاً في مجلات نظرية الألعاب مثل GEB ، [ 15 ] ومجلات الاقتصاد مثل Econometrica ، ومجلات علوم الحاسوب مثل SICOMP . [ 16 ]

انظر أيضاً

مراجع

  1. ↑ نيسان، نوام ؛ رونين، أمير (1999)، "تصميم الآليات الخوارزمية"، وقائع الندوة الحادية والثلاثين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC '99) ، الصفحات 129-140 ، doi : 10.1145/301250.301287 ، ISBN  978-1581130676، S2CID 8316937 
  2. ↑ «ACM SIGACT تُقدّم جائزة غودل لبحثٍ سلّط الضوء على آثار الاستخدام الأناني للإنترنت» (بيان صحفي). نيويورك. رابطة آلات الحوسبة. ١٦ مايو ٢٠١٢. مؤرشف من الأصل في ١٨ يوليو ٢٠١٣. تم الاطلاع عليه في ٨ يناير ٢٠١٨ .
  3. ↑ كوتسوباس، إلياس؛ باباديميتريو، كريستوس (مايو 2009). "توازنات أسوأ الحالات" . مجلة علوم الحاسوب . 3 (2): 65-69 . doi : 10.1016/j.cosrev.2009.04.003 . مؤرشف من الأصل في 13 مارس 2016. تم الاطلاع عليه في 8 يناير 2018 .
  4. ↑ باباديميتريو، كريستوس (2001)، "الخوارزميات والألعاب والإنترنت"، وقائع الندوة الثالثة والثلاثين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC '01) ، الصفحات 749-753 ، CiteSeerX 10.1.1.70.8836 ، doi : 10.1145/380752.380883 ، ISBN   978-1581133493، S2CID 207594967 
  5. ↑ تيم رافغاردن (2005). التوجيه الأناني وثمن الفوضى . مطبعة معهد ماساتشوستس للتكنولوجيا . ISBN 0-262-18243-2.
  6. ↑
    • أنشيلفيتش، إليوت؛ داسغوبتا، أنيربان؛ كلاينبيرغ، جون؛ تاردوس، إيفا؛ ويكسلر، توم؛ رافغاردن، تيم (2008). "ثمن الاستقرار لتصميم الشبكات مع التوزيع العادل للتكاليف". مجلة SIAM للحوسبة ، 38 (4): 1602-1623 . doi : 10.1137/070680096 . S2CID 2839399 . 
  7. ↑
  8. ↑ باباديميتريو، كريستوس هـ.؛ رافغاردن، تيم (2008). "حساب التوازنات المترابطة في الألعاب متعددة اللاعبين". مجلة ACM . 55 (3): 14:1–14:29. CiteSeerX 10.1.1.335.2634 . doi : 10.1145/1379759.1379762 . S2CID 53224027 .  
  9. ↑ فوستر، دين ب.؛ فوهرا، راكيش ف. (1996). "التعلم المعاير والتوازن المترابط" . الألعاب والسلوك الاقتصادي .
  10. ↑ فيليكس براندت؛ فينسنت كونيتزر؛ أولي إندريس؛ جيروم لانغ؛ أرييل د. بروكاسيا، محرران (2016)، دليل الاختيار الاجتماعي الحسابي (PDF)
  11. ↑ تيم رافغاردن (2016). عشرون محاضرة في نظرية الألعاب الخوارزمية . مطبعة جامعة كامبريدج . ISBN 9781316624791.
  12. ↑ "EC'19 | | المؤتمر العشرون لجمعية ACM حول الاقتصاد والحوسبة" .
  13. ↑ تياك
  14. ↑ بورصات SIGEcom
  15. ↑ تشاولا، شوتشي ؛ فليشر، ليزا؛ هارتلاين، جيسون؛ تيم رافغاردن (2015)، "مقدمة للعدد الخاص - نظرية الألعاب الخوارزمية - STOC/FOCS/SODA 2011"، الألعاب والسلوك الاقتصادي ، 92 : 228-231 ، doi : 10.1016/j.geb.2015.02.011
  16. ↑ SICOMP
  • gambit.sourceforge.net - مكتبة لبرامج وأدوات نظرية الألعاب لبناء وتحليل الألعاب الاستراتيجية والألعاب ذات النطاق المحدود.
  • gamut.stanford.edu - مجموعة من مولدات الألعاب المصممة لاختبار خوارزميات نظرية الألعاب.