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

في الرياضيات والاقتصاد وعلوم الكمبيوتر خوارزمية جيل-شابلي (Gale–Shapley algorithm)، المعروفة أيضًا بأسماء: خوارزمية القبول المؤجل (deferred acceptance algorithm propose)، أو خوارزمية الاقتراح والرفض (propose-and-reject algorithm)،أو خوارزمية بوسطن بول ( Boston Pool algorithm) هي خوارزمية لإيجاد حل لمشكلة الإقران المتكافئ. تم تسميتها على اسم ديفيد جيل و لويد شابلي، اللذين نشراها لأول مرة في عام 1962، على الرغم من أنها كانت تستخدم في برنامج مطابقة المقيمين الوطني منذ أوائل الخمسينيات. فاز شابلي وألفين إي روث الذي أشار إلى تطبيقها سابقا،بجائزة نوبل في الاقتصاد لعام 2012 .

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

إن مشكلة الإقتران المتكافيء و خوارزمية جيل-شابلي التي تحلها، لها تطبيقات واسعة النطاق في العالم الحقيقي، بما في ذلك مطابقة طلاب الطب الأميركيين مع برامج الإقامة، ومقدمي الطلبات للجامعات الفرنسية مع المدارس. لمزيد من المعلومات، راجع مشكلة الإقران المتكافئ § Applications

الخلفية

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

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

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

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

الحل

رسوم متحركة توضح مثالاً لخوارزمية جيل-شابلي

في عام 1962، أثبت ديفيد جيل و لويد شابلي أنه بالنسبة لأي عدد متساوٍ من المشاركين من كل نوع، من الممكن دائمًا العثور على تطابق تكون فيه جميع الأزواج مستقرة. وقد قدموا خوارزمية للقيام بذلك. ^[4][5] في عام 1984، لاحظ ألفين إي. روث أن نفس الخوارزمية كانت مستخدمة عمليًا منذ أوائل الخمسينيات، مثل "خوارزمية مجموعة بوسطن" التي يستخدمها برنامج المطابقة الوطنية للمقيمين . ^[6][7]

تتضمن خوارزمية جيل-شابلي عددًا من "الجولات" (أو " التكرارات "). و من حيث المتقدمين للوظائف وأصحاب العمل يمكن التعبير عن ذلك على النحو التالي: ^[8]

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

تفاصيل التنفيذ و تحليل الوقت

لتنفيذ الخوارزمية بكفاءة، يجب أن يكون كل صاحب عمل قادرًا على العثور على المتقدم التالي بسرعة، ويجب أن يكون كل متقدم قادرًا على مقارنة أصحاب العمل بسرعة. إحدى الطرق للقيام بذلك هي ترقيم كل متقدم و كل صاحب عمل من 1 إلى ${\displaystyle n}$ ، فيكون ${\displaystyle n}$ هو عدد أصحاب العمل و المتقدمين، و تخزين هياكل البيانات التالية: ^[9]

• مجموعة من أصحاب العمل الذين لديهم وظائف شاغرة
• مصفوفة أحادية البعد مفهرسة من قبل أصحاب العمل، تحدد مؤشر التفضيل للمتقدم التالي الذي سيرسل إليه عرضًا، في البداية 1 لكل صاحب عمل
• مصفوفة أحادية البعد مفهرسة حسب المتقدمين، تحدد صاحب العمل الحالي، في البداية قيمة مراقبة مثل 0 تشير إلى أنهم عاطلون عن العمل
• مصفوفة ثنائية الأبعاد مفهرسة بواسطة مقدم الطلب وصاحب العمل، تحدد موضع صاحب العمل في قائمة تفضيلات مقدم الطلب
• مصفوفة ثنائية الأبعاد مفهرسة بواسطة صاحب العمل وعدد ${\displaystyle i}$ من 1 الى ${\displaystyle n}$ ، تسمية مقدم الطلب الذي يمثل كل صاحب عمل ${\displaystyle i}$th

يستغرق إعداد هياكل البيانات هذه ${\displaystyle O(n^{2})}$ وقت طويلا. باستخدام هذه الهياكل، من الممكن العثور على صاحب عمل لديه منصب شاغر، و تقديم عرض من نفس صاحب العمل إلى المتقدم التالي، وتحديد ما إذا كان العرض مقبولاً، و تحديث جميع هياكل البيانات لتعكس نتائج هذه الخطوات في وقت ثابت لكل عرض. و بمجرد انتهاء الخوارزمية، يمكن قراءة المطابقة الناتجة من مجموعة أصحاب العمل لكل متقدم. يمكن أن يكون هناك ${\displaystyle O(n^{2})}$ العروض قبل أن ينفد كل صاحب عمل من العروض التي يجب تقديمها، وبالتالي فإن الوقت الإجمالي هو ${\displaystyle O(n^{2})}$ ^[9] .

على الرغم من أن هذا الحد الزمني تربيعي في عدد المشاركين، إلا أنه يمكن اعتباره وقتًا خطيًا عند قياسه من حيث حجم المدخلات و مصفوفتين من التفضيلات للحجم ${\displaystyle O(n^{2})}$ ^[10] .

ضمانات الصحة

تضمن هذه الخوارزمية ما يلي:

الجميع يتم إقرانهم

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

المباريات مستقرة

لا يمكن لأي متقدم X وصاحب العمل Y تفضيل بعضهما البعض على نظيرهما النهائي. إذا قدم Y عرضًا إلى X ، فلن يرفض X Y إلا بعد تلقي عرض أفضل، وبالتالي لا يمكن لـ X تفضيل Y على نظيرهما النهائي. وإذا توقف Y عن تقديم العروض قبل الوصول إلى X في قائمة تفضيلاته، فلا يمكن لـ Y تفضيل X على نظيرهما النهائي. في كلتا الحالتين، لا يشكل X و Y زوجًا غير متكافيء. ^[8]

الحل الأمثل

قد يكون هناك العديد من الأقران المتكافئة لنفس نظام التفضيلات. وهذا يثير السؤال: ما هي المطابقة التي تم إرجاعها بواسطة خوارزمية جيل-شابلي؟ هل هو المطابقة الأفضل للمتقدمين، أم لأصحاب العمل، أم وسيط؟ وكما اتضح، فإن خوارزمية جيل-شابلي التي يقدم أصحاب العمل من خلالها عروضاً للمتقدمين تسفر دائماً عن نفس المطابقة المتكافئة (بغض النظر عن الترتيب الذي تُقدم به عروض العمل)، واختيارها هو الأفضل لجميع أصحاب العمل و الأسوأ لجميع المتقدمين في هذه العملية. ^[8]

في الشكل المعكوس للخوارزمية، تتكون كل جولة من قيام المتقدمين العاطلين عن العمل بكتابة طلب وظيفة واحد إلى صاحب العمل المفضل لديهم، ويقوم صاحب العمل إما بقبول الطلب (ربما فصل موظف موجود للقيام بذلك) أو رفضه. و يؤدي هذا إلى تكافيء أفضل لجميع المتقدمين وأسوأ لجميع أصحاب العمل في هذه العملية. مما يعني أن هذان المتطابقان هما العنصران العلوي و السفلي لشبكة الم الاقتران المتكافيء . ^[11]

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

الاعتبارات الاستراتيجية

إن خوارزمية جيل-شابلي هي آلية صادقة من وجهة نظر الجانب المقترح. وهذا يعني أنه لا يمكن لأي مقترح أن يحصل على تكافيء أفضل من خلال تحريف تفضيلاته. علاوة على ذلك، فإن خوارزمية جيل-شابلي هي دليل على استراتيجية المجموعة بالنسبة للمقترحين أيضا، أي أنه لا يمكن لأي تحالف من المقترحين تنسيق التمثيل الخاطئ لتفضيلاتهم بحيث يكون جميع المقترحين في التحالف أفضل حالًا بشكل صارم. ^[12] ومع ذلك، فمن الممكن أن تسيء بعض التحالفات تمثيل تفضيلاتها بحيث يصبح بعض المقترحين أفضل حالاً، بينما يحتفظ الآخرون بنفس الشريك. ^[13]

تعتبر خوارزمية جيل-شابلي غير صادقة بالنسبة للمشاركين غير المقترحين.ببساطة لأنه، كل شخص قادرًا على تحريف تفضيلاته و الحصول على تطابق أفضل. ^[14] إضافة إلى ذلك، فهناك شكل خاص من أشكال التلاعب وهو الاختصار : تقديم البدائل الأعلى فقط، مما يعني أن البدائل الأدنى غير مقبولة على الإطلاق. في ظل المعلومات الكاملة، يكفي النظر في التحريفات التي تبدو على شكل استراتيجيات الاختصار. و مع ذلك، يتطلب التمثيل الخاطئ الناجح معرفة تفضيلات الوكلاء الآخرين؛ وبدون هذه المعرفة، يمكن للتحريف أن يعطي الوكيل مهمة أسوأ. علاوة على ذلك، حتى بعد أن يرى العميل الإقتران النهائية، فإنه لا يستطيع استنتاج استراتيجية من شأنها ضمان نتيجة أفضل في وقت لاحق. وهذا يجعل خوارزمية جيل-شابلي <i id="mwqQ">آلية لقول الحقيقة خالية من الندم</i> . و علاوة على ذلك، في خوارزمية جيل-شابلي، فإن قول الحقيقة هو الاستراتيجية الوحيدة التي تضمن عدم الشعور بالندم. خوارزمية جيل-شابلي هي الآلية الوحيدة الخالية من الندم في فئة خوارزميات المكافئة. ^[15]

التعميمات

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

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

التقدير

وقد حصل شابلي وروث على جائزة نوبل التذكارية في العلوم الاقتصادية لعام 2012 "لنظرية التخصيصات المستقرة وممارسة تصميم السوق ". توفي جيل في عام 2008، مما جعله غير مؤهل للحصول على الجائزة. ^[18]

انظر أيضا

• مزاد القبول المؤجل
• مشكلة زملاء السكن المستقرين

مراجع

1. Gusfield، Dan؛ Irving، Robert W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. ص. 6. ISBN:9780262515528.
2. Wagner، Roy (أبريل 2009). "Mathematical marriages: Intercourse between mathematics and semiotic choice". Social Studies of Science. ج. 39 ع. 2: 289–308. DOI:10.1177/0306312708099443. hdl:20.500.11850/121579.
3. Giagkousi، Kyriaki (مارس 2021). Gender and Computing Algorithms: The case of Stable Matching (PDF) (Master's thesis). National and Kapodistrian University of Athens, Department of History and Philosophy of Science and Department of Informatics and Telecommunications. مؤرشف من الأصل (PDF) في 2024-04-22. اطلع عليه بتاريخ 2023-12-20.
4. Gale، D.؛ Shapley، L. S. (1962). "College admissions and the stability of marriage". الرياضيات الأمريكية الشهرية. ج. 69 ع. 1: 9–14. DOI:10.2307/2312726. JSTOR:2312726. مؤرشف من الأصل في 2017-09-25. اطلع عليه بتاريخ 2019-11-20.
5. Mairson، Harry (1992). "The stable marriage problem". The Brandeis Review. ج. 12. مؤرشف من الأصل في 2012-08-05.
6. Roth، Alvin E. (فبراير 2003). "The origins, history, and design of the resident match". دورية الجمعية الطبية الأمريكية. ج. 289 ع. 7: 909–912. DOI:10.1001/jama.289.7.909.
7. Bergstrom، Theodore C. (يونيو 1992). "Review of Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by A. E. Roth and M. A. O. Sotomayor". مجلة الأدب الاقتصادي. ج. 30 ع. 2: 896–898. JSTOR:2727713.
8. Erickson، Jeff (يونيو 2019). "4.5 Stable matching" (PDF). Algorithms. University of Illinois. ص. 170–176. اطلع عليه بتاريخ 2023-12-19.
9. Kleinberg، Jon؛ Tardos، Éva (2006). "2.3 Implementing the stable matching algorithm using lists and arrays". Algorithm Design. Addison-Wesley. ص. 42–47.
10. Gusfield & Irving (1989), p. 182.
11. Knuth, Donald E. (1976). Mariages stables et leurs relations avec d'autres problèmes combinatoires (PDF) (بالفرنسية). Montréal, Quebec: Les Presses de l'Université de Montréal. ISBN:0-8405-0342-3. MR:0488980. Archived from the original (PDF) on 2024-02-05. See in particular Problem 6, pp. 87–94.
12. Dubins، L. E.؛ Freedman، D. A. (1981). "Machiavelli and the Gale–Shapley algorithm". الرياضيات الأمريكية الشهرية. ج. 88 ع. 7: 485–494. DOI:10.2307/2321753. JSTOR:2321753. MR:0628016.
13. Huang، Chien-Chung (2006). "Cheating by men in the Gale-Shapley stable matching algorithm". في Azar، Yossi؛ Erlebach، Thomas (المحررون). Algorithms – ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11–13, 2006, Proceedings. Lecture Notes in Computer Science. Springer. ج. 4168. ص. 418–431. DOI:10.1007/11841036_39. MR:2347162.
14. Gonczarowski، Yannai A.؛ Friedgut، Ehud (أبريل 2013). "Sisterhood in the Gale–Shapley matching algorithm". Electronic Journal of Combinatorics. ج. 20 ع. 2: P12:1–P12:18. arXiv:1104.2217. DOI:10.37236/3267.
15. Fernandez، Marcelo Ariel (31 يوليو 2020). "Deferred acceptance and regret-free truth-telling" (Working paper). Johns Hopkins University Department of Economics. مؤرشف من الأصل في 2023-12-24.
16. Mathieu، Claire (2018). "College admission algorithms in the real world" (Invited lecture at the European Symposium of Algorithms). Aalto University.
17. Floréen، Patrik؛ Kaski، Petteri؛ Polishchuk، Valentin؛ Suomela، Jukka (أغسطس 2009). "Almost stable matchings by truncating the Gale–Shapley algorithm". Algorithmica. ج. 58 ع. 1: 102–118. arXiv:0812.4893. DOI:10.1007/s00453-009-9353-9.
18. Bhattacharjee، Yudhijit (15 أكتوبر 2012). "Economics Nobel honors matchmaking finesse". Science. ج. 338 ع. 6105: 314. DOI:10.1126/science.338.6105.314. PMID:23087221.

المرجع "carter-price" المذكور في <references> غير مستخدم في نص الصفحة.

• بوابة رياضيات
• بوابة علم الحاسوب