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

خوارزمية غيل-شابلي

قدّمه
David Gale, Lloyd Shapley
السنة
1962
النوع
algorithm
العائلة
Game-theoretic

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

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

متى تُستخدم

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

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

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

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

نقاط القوة

  • استقرار مضمون: لا توجد أزواج محظورة في المطابقة النهائية
  • زمن كثير الحدود: تعقيد O(n^2)، مما يجعلها فعالة للمجموعات السكانية الكبيرة
  • تنفيذ بسيط: سهل التطبيق عمليًا مع جمع تفضيلات شفاف
  • حوافز استراتيجية: يتمتع الجانب المقترح بميزة استراتيجية، ويفضل المقترحات المبكرة على المتأخرة
  • قابلية تطبيق عالمية: تعمل مع أي ملفات تعريف تفضيلات دون افتراض التقريب أو التعدي

التطبيقات

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

كيف يعمل

كيف يعمل

1

إنشاء قوائم تفضيلات لجميع الأفراد في كلتا المجموعتين، تمثل ترتيبهم للطرف الآخر.

2

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

3

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

4

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

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

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

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

لماذا الاستقرار مهم في المطابقة؟

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

هل تنتج خوارزمية غيل-شابلي دائمًا نفس المطابقة؟

لا. يمكن أن تؤدي قوائم التفضيلات المختلفة أو ترتيبات الاقتراح المختلفة إلى مطابقات مستقرة مختلفة. ومع ذلك، هناك دائمًا مطابقة مستقرة 'مثلى للرجال' (الأفضل لجميع المقترحين) ومطابقة مستقرة 'مثلى للنساء' (الأفضل لجميع المستجيبين).

كيف تتعامل خوارزمية غيل-شابلي مع التفضيلات على المجموعات (مثل الأزواج)؟

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

طرق ذات صلة

المصادر

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.

    افتح مرجع DOI
    تم النسخ.
  2. Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.

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