خوارزمية جيل-شابلي
المحتويات
قبل الخوض في التفاصيل، في الرياضيات والاقتصاد وعلوم الكمبيوتر خوارزمية جيل-شابلي (Gale–Shapley algorithm)، المعروفة كذلك بأسماء: خوارزمية القبول المؤجل (deferred acceptance algorithm)، أو خوارزمية الاقتراح والرفض (propose-and-reject algorithm)،أو خوارزمية مجموعة بوسطن ( Boston Pool algorithm) هي خوارزمية لإيجاد حل لمشكلة الإقران المتكافئ. تم تسميتها على اسم ديفيد جيل و لويد شابلي، اللذين نشراها لأول مرة في عام 1962، على الرغم من أنها كانت تستعمل في برنامج مطابقة المقيمين الوطني منذ أوائل الخمسينيات. فاز شابلي وألفين إي روث الذي أشار إلى تطبيقها سابقا، بجائزة نوبل التذكارية في العلوم الاقتصادية لعام 2012 . وفيما يلي تفاصيل أوسع عن ذلك.
وعلى صعيد آخر، إن مشكلة الإقتران المتكافيء و خوارزمية جيل-شابلي التي تحلها، لها تطبيقات واسعة النطاق في العالم الحقيقي، بما في ذلك مطابقة طلاب الطب الأميركيين مع برامج الإقامة، ومقدمي الطلبات للجامعات الفرنسية مع المدارس. لمزيد من المعلومات، راجع
ومن ناحية أخرى، تسعى مشكلة الإقتران المتكافيء إلى إقران عدد متساوٍ من المشاركين من نوعين، وذلك باستخدام تفضيلات كل مشارك. يجب أن يكون هذا الاقتران مستقرًا: لا ينبغي لأي زوج من المشاركين تفضيل بعضهما البعض على المباراة المخصصة لهم. في كل جولة من خوارزمية جيل-شابلي، يقترح المشاركون غير المتطابقين من نوع واحد تطابقًا مع المشارك التالي في قائمة تفضيلاتهم. يتم قبول كل اقتراح إذا كان المتلقي يفضله على نظيره الحالي. إن الإجراء الناتج هو آلية صادقة من وجهة نظر المشاركين المقترحين، الذين يحصلون على الزوج المفضل لديهم بما يتفق مع الاستقرار. في المقابل، يحصل متلقي المقترحات على الزوج الأقل تفضيلاً بالنسبة لهم. يمكن تنفيذ الخوارزمية لتعمل في وقت متكافئ في عدد المشاركين، وخطي في حجم المدخلات إلى الخوارزمية.
الحل
علاوةً على ذلك، يتم تكرار هذه العملية حتى يقوم جميع أصحاب العمل بشغل الوظائف لديهم أو استنفاد قوائم المتقدمين لديهم.
وفي هذا السياق، في عام 1962، أثبت ديفيد جيل و لويد شابلي أنه بالنسبة لأي عدد متساوٍ من المشاركين من كل نوع، من الممكن دائمًا العثور على تطابق تكون فيه جميع الأزواج مستقرة. وقد قدموا خوارزمية للقيام بذلك. في عام 1984، لاحظ ألفين إي. روث أن نفس الخوارزمية كانت مستعملة عمليًا منذ أوائل الخمسينيات، مثل "خوارزمية مجموعة بوسطن" التي يستعملها برنامج المطابقة الوطنية للمقيمين .
من جهة ثانية، يقوم كل متقدم حصل على عرض بتقييمه مقارنة بمنصبه الحالي (إذا كان لديه واحد). إذا لم يكن المتقدم قد حصل على وظيفة بعد، أو إذا تلقى عرضًا من صاحب عمل يفضله عن صاحب عمله الحالي، فإنه يقبل العرض الأفضل الجديد و يصبح متوافقا مع صاحب العمل الجديد (ربما يترك صاحب العمل السابق بمنصب شاغر). و إلا فإنهم يرفضون العرض الجديد.
من جانب آخر، في كل جولة، يقوم واحد أو أكثر من أصحاب العمل الذين لديهم وظائف شاغرة بتقديم عرض وظيفة للمتقدم الذي يفضلونه، من بين أولئك الذين لم يقدموا لهم عرضًا بعد.
وفي هذا الصدد، تتضمن خوارزمية جيل-شابلي عددًا من "الجولات" (أو " التكرارات "). و من حيث المتقدمين للوظائف وأصحاب العمل يمكن التعبير عن ذلك على النحو التالي:
التعميمات
إضافةً إلى ذلك، تم استخدام شكل من أشكال خوارزمية جيل-شابلي، التي يتم تنفيذها من خلال بروتوكول في العالم الحقيقي بدلاً من حسابها على أجهزة الكمبيوتر، لتنسيق القبول في التعليم العالي في فرنسا منذ عام 2018، من خلال نظام باركورسوب . في هذه العملية، على مدار الصيف الذي يسبق بدء الدراسة، يتلقى المتقدمون عروض القبول، ويجب عليهم الاختيار في كل جولة من العملية ما إذا كانوا سيقبلون أي عرض جديد (وإذا كان الأمر كذلك، فيجب عليهم رفض أي عرض سابق قبلوه). إن الطريقة معقدة بسبب القيود الإضافية التي تجعل المشكلة التي تحلها ليست بالضبط مشكلة الإقران الأمثل. إن الميزة التي تتمتع بها هذه الخوارزمية هي أن الطلاب لا يحتاجون إلى الالتزام بتفضيلاتهم في بداية العملية، بل يمكنهم تحديد تفضيلاتهم الخاصة مع تقدم الخوارزمية، على أساس المقارنات المباشرة بين العروض التي تلقوها. من المهم أن تتم هذه العملية بعدد صغير من جولات المقترحات، بحيث تنتهي قبل تاريخ بدء المدارس، ولكن على الرغم من إمكانية حدوث عدد كبير من الجولات من الناحية النظرية، إلا أنها لا تحدث في الممارسة العملية. لقد ثبت نظريًا أنه إذا كان من الضروري إنهاء خوارزمية جيل-شابلي مبكرًا، بعد عدد صغير من الجولات التي يقدم فيها كل منصب شاغر عرضًا جديدًا، فإنها مع ذلك تنتج مشاركين أقران لديهم نسبة عالية من الاستقرار مقارنة بنسب الأزواج غير المستقرة.
ومن جهة أخرى، في عملهم الأصلي حول المشكلة، فكر جيل وشابلي في شكل أكثر عمومية لمشكلة الاقتران الأمثل، وهو مناسب للقبول في الجامعات والكليات . في هذه المشكلة، قد يكون لكل جامعة أو كلية حصصها الخاصة، وعدد مستهدف من الطلاب للقبول، وقد يختلف عدد الطلاب المتقدمين للقبول عن مجموع الحصص، مما يؤدي بالضرورة إلى بقاء بعض الطلاب غير مقترنين أو بقاء بعض الحصص شاغرة. علاوةً على ذلك، قد تكون قوائم التفضيلات غير مكتملة: إذا أسقطت جامعة طالبًا من قائمتها، فهذا يعني أنها تفضل ترك حصتها غير مكتملة بدلاً من قبول هذا الطالب، وإذا أسقط طالب جامعة من قائمته، فهذا يعني أنه يفضل البقاء غير مقبول بدلاً من الذهاب إلى تلك الجامعة. ومع ذلك، فمن الممكن تحديد مطابقات أفضل لهذه المشكلة الأكثر عمومية، لإثبات أن هذه النظرية موجودة دائمًا، وتطبيق نفس الخوارزمية للعثور على واحدة.
ضمانات الصحة
تضمن هذه الخوارزمية ما يلي:
المباريات مستقرة
وفي هذا السياق، لا يمكن لأي متقدم X وصاحب العمل Y تفضيل بعضهما البعض على نظيرهما النهائي. إذا قدم Y عرضًا إلى X ، فلن يرفض X Y إلا بعد تلقي عرض أفضل، وبالتالي لا يمكن لـ X تفضيل Y على نظيرهما النهائي. وإذا توقف Y عن تقديم العروض قبل الوصول إلى X في قائمة تفضيلاته، فلا يمكن لـ Y تفضيل X على نظيرهما النهائي. في كلتا الحالتين، لا يشكل X و Y زوجًا غير متكافيء.
تفاصيل التنفيذ و تحليل الوقت
وفي هذا السياق، مصفوفة ثنائية الأبعاد مفهرسة بواسطة مقدم الطلب وصاحب العمل، تحدد موضع صاحب العمل في قائمة تفضيلات مقدم الطلب
ومن ناحية أخرى، مصفوفة أحادية البعد مفهرسة من قبل أصحاب العمل، تحدد مؤشر التفضيل للمتقدم التالي الذي سيرسل إليه عرضًا، في البداية 1 لكل صاحب عمل
ومن ناحية أخرى، مصفوفة أحادية البعد مفهرسة حسب المتقدمين، تحدد صاحب العمل الحالي، في البداية قيمة مراقبة مثل 0 تشير إلى أنهم عاطلون عن العمل
مجموعة من أصحاب العمل الذين لديهم وظائف شاغرة
ومن جهة أخرى، مصفوفة ثنائية الأبعاد مفهرسة بواسطة صاحب العمل وعدد من 1 الى ، تسمية مقدم الطلب الذي يمثل كل صاحب عمل
وفي هذا الصدد، لتنفيذ الخوارزمية بكفاءة، يجب أن يكون كل صاحب عمل قادرًا على العثور على المتقدم التالي بسرعة، ويجب أن يكون كل متقدم قادرًا على مقارنة أصحاب العمل بسرعة. إحدى الطرق للقيام بذلك هي ترقيم كل متقدم و كل صاحب عمل من 1 إلى ، فيكون هو عدد أصحاب العمل و المتقدمين، و تخزين هياكل البيانات التالية:
ومن ناحية أخرى، يستغرق إعداد هياكل البيانات هذه وقت طويلا. باستخدام هذه الهياكل، من الممكن العثور على صاحب عمل لديه منصب شاغر، و تقديم عرض من نفس صاحب العمل إلى المتقدم التالي، وتحديد ما إذا كان العرض مقبولاً، و تحديث جميع هياكل البيانات لتعكس نتائج هذه الخطوات في وقت ثابت لكل عرض. و بمجرد انتهاء الخوارزمية، يمكن قراءة المطابقة الناتجة من مجموعة أصحاب العمل لكل متقدم. يمكن أن يكون هناك العروض قبل أن ينفد كل صاحب عمل من العروض التي يجب تقديمها، وبالتالي فإن الوقت الإجمالي هو .
كذلك، على الرغم من أن هذا الحد الزمني تربيعي في عدد المشاركين، إلا أنه يمكن اعتباره وقتًا خطيًا عند قياسه من حيث حجم المدخلات و مصفوفتين من التفضيلات للحجم .
الحل الأمثل
من جهة ثانية، في الشكل المعكوس للخوارزمية، تتكون كل جولة من قيام المتقدمين العاطلين عن العمل بكتابة طلب وظيفة واحد إلى صاحب العمل المفضل لديهم، ويقوم صاحب العمل إما بقبول الطلب (ربما فصل موظف موجود للقيام بذلك) أو رفضه. و يؤدي هذا إلى تكافيء أفضل لجميع المتقدمين وأسوأ لجميع أصحاب العمل في هذه العملية. مما يعني أن هذان المتطابقان هما العنصران العلوي و السفلي لشبكة الاقتران المتكافئ .
من جهة ثانية، قد يكون هناك الكثير من الأقران المتكافئة لنفس نظام التفضيلات. وهذا يثير السؤال: ما هي المطابقة التي تم إرجاعها بواسطة خوارزمية جيل-شابلي؟ هل هو المطابقة الأفضل للمتقدمين، أم لأصحاب العمل، أم وسيط؟ وكما اتضح، فإن خوارزمية جيل-شابلي التي يقدم أصحاب العمل من خلالها عروضاً للمتقدمين تسفر دائماً عن نفس المطابقة المتكافئة (بغض النظر عن الترتيب الذي تُقدم به عروض العمل)، واختيارها هو الأفضل لجميع أصحاب العمل و الأسوأ لجميع المتقدمين في هذه العملية.
وعلى صعيد آخر، في كلا شكلي الخوارزمية، تقترح مجموعة واحدة من المشاركين متطابقات، و تقرر المجموعة الأخرى ما إذا كانت ستقبل أو ترفض كل اقتراح. نتيجة لذلك، إن الإقتران يكون دائمًا الأفضل للمجموعة التي تقدم المقترحات، و الأسوأ للمجموعة التي تقرر كيفية التعامل مع كل مقترح.
التقدير
من جهة ثانية، وقد حصل شابلي وروث على جائزة نوبل التذكارية في العلوم الاقتصادية لعام 2012 "لنظرية التخصيصات المستقرة وممارسة تصميم السوق ". توفي جيل في عام 2008، مما جعله غير مؤهل للحصول على الجائزة.
- انظر كذلك
- مزاد القبول المؤجل
- مشكلة زملاء السكن المستقرين
الاعتبارات الاستراتيجية
من جهة ثانية، تعتبر خوارزمية جيل-شابلي غير صادقة بالنسبة للمشاركين غير المقترحين.ببساطة لأنه، كل شخص قادرًا على تحريف تفضيلاته و الحصول على تطابق أفضل. إضافة إلى ذلك، فهناك شكل خاص من أشكال التلاعب وهو الاختصار : تقديم البدائل الأعلى فقط، مما يعني أن البدائل الأدنى غير مقبولة على الإطلاق. في ظل المعلومات الكاملة، يكفي النظر في التحريفات التي تبدو على شكل استراتيجيات الاختصار. و مع ذلك، يتطلب التمثيل الخاطئ الناجح معرفة تفضيلات الوكلاء الآخرين؛ وبدون هذه المعرفة، يمكن للتحريف أن يعطي الوكيل مهمة أسوأ. علاوة على ذلك، حتى بعد أن يرى العميل الإقتران النهائية، فإنه لا يستطيع استنتاج استراتيجية من شأنها ضمان نتيجة أفضل في وقت لاحق. وهذا يجعل خوارزمية جيل-شابلي آلية لقول الحقيقة خالية من الندم . و علاوة على ذلك، في خوارزمية جيل-شابلي، فإن قول الحقيقة هو الاستراتيجية الوحيدة التي تضمن عدم الشعور بالندم. خوارزمية جيل-شابلي هي الآلية الوحيدة الخالية من الندم في فئة خوارزميات المكافئة.
ومن جهة أخرى، إن خوارزمية جيل-شابلي هي آلية صادقة من وجهة نظر الجانب المقترح. وهذا يعني أنه لا يمكن لأي مقترح أن يحصل على تكافيء أفضل من خلال تحريف تفضيلاته. علاوة على ذلك، فإن خوارزمية جيل-شابلي هي دليل على استراتيجية المجموعة بالنسبة للمقترحين كذلك، أي أنه لا يمكن لأي تحالف من المقترحين تنسيق التمثيل الخاطئ لتفضيلاتهم بحيث يكون جميع المقترحين في التحالف أفضل حالًا بشكل صارم. ومع ذلك، فمن الممكن أن تسيء بعض التحالفات تمثيل تفضيلاتها بحيث يصبح بعض المقترحين أفضل حالاً، بينما يحتفظ الآخرون بنفس الشريك.
الجميع يتم إقرانهم
من جانب آخر، في النهاية، لا يمكن أن يكون هناك متقدم وصاحب عمل غير متوافقين أو متكافئين. يجب أن يكون صاحب العمل الذي لم يتم إقرانه في نهاية العملية قد قدم عرضًا لجميع المتقدمين. لكن المتقدم الذي يتلقى عرضًا يظل موظفًا لبقية العملية، وبالتالي لا يمكن أن يكون هناك متقدمون عاطلون عن العمل. نظرًا لأن أعداد المتقدمين وفرص العمل متساوية، فلا يمكن كذلك أن تكون هناك وظائف شاغرة متبقية.
الخلفية
ومن جهة أخرى، بعبارة أخرى، يكون التطابق متكافئا عندما لا يكون هناك زوج ( أ ، ب ) حيث يفضل كلا المشاركين بعضهما البعض على شركائهما المتطابقين. إذا كان مثل هذا الزوج موجودًا، فإن المطابقة ليست متكافئة كما تبدو عليه، بمعنى أن أعضاء هذا الزوج يفضلون مغادرة النظام و التوافق مع بعضهم البعض، مما قد يترك المشاركين الآخرين غير متوافقين. ببساطة، لأنه يوجد دائمًا قرين متكافئ، فالمشكلة الخوارزمية يتم حلها بواسطة خوارزمية جيل-شابلي و هي العثور على واحد.
ومن جهة أخرى، كان هناك عنصر أ من المجموعة الإقتران الأولى يفضل بعض العناصر المعينة ب من المجموعة الإقتران الثانية على العنصر الذي تمت تفضيله أ معه بالفعل، ويفضل ب كذلك أ على العنصر الذي تم اقران ب معه بالفعل. من أصحاب العمل، مثلًا)، و ترتيبًا لكل مشارك يعطي تفضيلاته بشأن من يتم مطابقته معه من بين المشاركين من النوع الآخر. يقوم الأزواج المتطابقون بمطابقة كل مشارك من نوع واحد مع مشارك من النوع الآخر. المطابقة ليست مستقرة إذا: يفضل ب كذلك أ على العنصر الذي يتطابق معه ب بالفعل.
كذلك، تأخذ مشكلة الاقتران الأمثل، في أبسط أشكالها، كمدخلات أعدادًا متساوية من نوعين من المشاركين (n متقدم للوظائف وn من أرباب العمل، مثلًا)، وترتيبًا لكل مشارك يعطي تفضيله لمن يتم مطابقته بين المشاركين من النوع الآخر. يقرن المكافيء أ كل مشارك من نوع واحد مع مشارك من النوع الآخر. المطابقة أ ليست الأمثل إذا:
وفي السياق ذاته، تمت مقارنة مشكلة الإقتران الأمثل أو المتكافيء كذلك بمشكلة الزواج المستقر ، وذلك باستعارة المصطلح ليتناسب مع الإقتران أو الزواج بين الرجل والمرأة، حيث تصف الكثير من مصادر خوارزمية جيل-شابلي أنه يمثل عروض الزواج بينهما. ومع ذلك، فقد تعرضت هذه الاستعارة لانتقادات لكونها تعتمد على جنس المقترن و غير واقعية: فخطواتها لا تعكس بدقة مطلقا السلوك البشري النموذجي أو حتى النمطي.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟