مشكلة المطابقة المستقرة

في الرياضيات والاقتصاد وعلوم الحاسوب ، تُعرف مسألة التوفيق المستقر ^{[ 1 ] [ 2 ] [ 3 ]} بأنها إيجاد توفيق مستقر بين مجموعتين متساويتين في الحجم من العناصر ، مع مراعاة ترتيب تفضيلات كل عنصر. التوفيق هو تقابل بين عناصر إحدى المجموعتين وعناصر المجموعة الأخرى. لا يكون التوفيق مستقرًا إذا:

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

وقد تم تحديد مشكلة الزواج المستقر على النحو التالي:

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

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

تُستخدم خوارزميات إيجاد حلول لمشكلة الزواج المستقر في العديد من المواقف الواقعية، ولعلّ أشهرها هو تعيين طلاب الطب المتخرجين في أولى وظائفهم بالمستشفيات. ^{[ 4 ]} في عام 2012، مُنحت جائزة نوبل التذكارية في العلوم الاقتصادية للويد إس. شابلي وألفين إي. روث "لإسهاماتهما في نظرية التخصيصات المستقرة وتطبيق تصميم السوق". ^{[ 5 ]}

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

تُستخدم خوارزمية غيل-شابلي للمطابقة المستقرة لتعيين الحاخامات الذين تخرجوا من كلية الاتحاد العبري للجماعات اليهودية. ^{[ 7 ]}

بشكل عام، قد يكون هناك العديد من التوافقات المستقرة المختلفة. على سبيل المثال، لنفترض أن هناك ثلاثة رجال (أ، ب، ج) وثلاث نساء (س، ص، ع) لديهم تفضيلات كالتالي:

أ: YXZ  ب: ZYX  ج: XZY 

X: BAC  Y: CBA  Z: ACB

توجد ثلاثة حلول مستقرة لهذا الترتيب المتطابق:

• يحصل الرجال على خيارهم الأول والنساء على خيارهم الثالث - (AY، BZ، CX)؛
• يحصل جميع المشاركين على خيارهم الثاني - (AX، BY، CZ)؛
• تحصل النساء على خيارهن الأول والرجال على خيارهم الثالث - (AZ، BX، CY).

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

في حالة عشوائية منتظمة لمسألة الزواج المستقر مع n من الرجال و n من النساء، يكون متوسط ​​عدد التوافقات المستقرة مقاربًا${\displaystyle e^{-1}n\ln n}$[ ^{9 ]} في حالة زواج مستقر يتم اختيارها لزيادة عدد التوافقات المستقرة المختلفة إلى أقصى حد، يكون هذا العدد ^دالة أسية لـ n . ^{[ 10 ]} يُعد حساب عدد التوافقات المستقرة في حالة معينة مسألة كاملة من النوع P. ^{[ 11 ]}

في عام 1962، أثبت ديفيد غيل ولويد شابلي أنه لأي عدد متساوٍ في مجموعات مختلفة، في سياق القبول الجامعي والأفراد الراغبين في الزواج، من الممكن دائمًا حل المسألة كأزواج متطابقة لجعل جميع الأزواج الناتجة / العوامل المتطابقة مستقرة. وقد قدما خوارزمية للقيام بذلك. ^{[ 12 ] [ 13 ]}

تتضمن خوارزمية غيل-شابلي (المعروفة أيضًا باسم خوارزمية القبول المؤجل) عددًا من "الجولات" (أو " التكرارات "):

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

تضمن هذه الخوارزمية إنتاج زواج مستقر لجميع المشاركين مع مرور الوقت${\displaystyle O(n^{2})}$أين${\displaystyle n}$هو عدد الرجال أو النساء. ^{[ 14 ]}

من بين جميع التوافقات المستقرة المختلفة الممكنة، ينتج عنها دائمًا التوافق الأفضل لجميع الرجال من بين جميع التوافقات المستقرة، والأسوأ لجميع النساء. ^{[ 15 ]}

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

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

تتعلق نظرية المستشفيات الريفية بصيغة أكثر عمومية لمشكلة التوفيق المستقر، مثل تلك التي تنطبق على مشكلة مطابقة الأطباء مع الوظائف في المستشفيات، وتختلف بالطرق التالية عن الشكل الأساسي n- إلى- n لمشكلة الزواج المستقر:

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

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

بالنسبة لهذا النوع من مشاكل المطابقة المستقرة، تنص نظرية المستشفيات الريفية على ما يلي:

• مجموعة الأطباء المعينين، وعدد الوظائف المشغولة في كل مستشفى، هي نفسها في جميع عمليات المطابقة المستقرة.
• أي مستشفى لديه بعض الوظائف الشاغرة في عملية مطابقة مستقرة، يتلقى نفس مجموعة الأطباء بالضبط في جميع عمليات المطابقة المستقرة.

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

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

تختلف مشكلة المستشفيات/المقيمين - المعروفة أيضًا بمشكلة قبول الطلاب في الجامعات - عن مشكلة الزواج المستقر في أن المستشفى يمكنه قبول أكثر من مقيم، أو أن الجامعة يمكنها قبول دفعة جديدة تضم أكثر من طالب. يمكن أن تكون الخوارزميات المستخدمة لحل مشكلة المستشفيات/المقيمين موجهة نحو المستشفى (كما كان الحال مع برنامج التوفيق الوطني للإقامة الطبية قبل عام ١٩٩٥) ^{[ ١٩ ]} أو موجهة نحو المقيم . وقد تم حل هذه المشكلة، باستخدام خوارزمية، في نفس الورقة البحثية الأصلية التي نشرها غيل وشابلي، والتي حلت فيها مشكلة الزواج المستقر. ^{[ ١٢ ]}

تتيح مسألة المستشفيات /المقيمين مع الأزواج إمكانية إدراج الأزواج ضمن مجموعة المقيمين، حيث يجب تخصيصهم معًا إما لنفس المستشفى أو لزوج محدد من المستشفيات يختاره الزوجان (على سبيل المثال، يرغب الزوجان في ضمان بقائهما معًا وعدم حصرهما في برامج بعيدة عن بعضهما). إن إضافة الأزواج إلى مسألة المستشفيات/المقيمين تجعل المسألة من فئة NP-complete . ^{[ 20 ]}

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

تُعدّ مسألة التوفيق مع العقود تعميمًا لمسألة التوفيق، حيث يمكن التوفيق بين المشاركين بشروط عقود مختلفة. ^{[ 21 ]} ومن الحالات الخاصة المهمة للعقود التوفيق مع الأجور المرنة. ^{[ 22 ]}

تسعى مسألة المطابقة الشائعة إلى إيجاد تطابق${\displaystyle M^{*}}$بحيث لا يوجد تطابق آخر${\displaystyle M}$يوجد عدد أكبر من الأشخاص الأكثر سعادة بـ${\displaystyle M}$أكثر من مع${\displaystyle M^{*}}$بالنسبة للمدخلات غير الثنائية، فإن تحديد ما إذا كان هناك تطابق شائع هو مسألة NP-كاملة . ^{[ 23 ]}

• المطابقة (نظرية الرسم البياني) - المطابقة بين رؤوس مختلفة من الرسم البياني؛ عادة لا علاقة لها بترتيب التفضيلات.
• المطابقة الخالية من الحسد – تخفيف لمفهوم المطابقة المستقرة لمشاكل المطابقة من متعدد إلى واحد
• مطابقة قوس قزح للرسوم البيانية ذات الحواف الملونة
• متعدد السطوح المتطابق المستقر
• مشكلة السكرتيرة (وتسمى أيضاً مشكلة الزواج ) – تحديد الوقت المناسب للتوقف للحصول على أفضل مكافأة في سلسلة من الخيارات

• كلاينبرغ، ج.، وتاردوس، إ. (2005) تصميم الخوارزميات ، الفصل 1، الصفحات 1-12. انظر الموقع الإلكتروني المصاحب للنصتمت أرشفة هذه الصفحة بتاريخ 14 مايو 2011 في موقع Wayback Machine .
• كنوت، دي إي (1996). الزواج المستقر وعلاقته بمسائل التوافقية الأخرى: مقدمة في التحليل الرياضي للخوارزميات . وقائع ومحاضرات مركز الرياضيات التطبيقية. ترجمة إنجليزية. الجمعية الرياضية الأمريكية.
• بيتيل، ب. (1992). "حول الحلول المحتملة لمسألة الزواج المستقر" . حوليات الاحتمالات التطبيقية . 2 (2): 358-401 . doi : 10.1214/aoap/1177005708 . JSTOR 2959755 . 
• روث، أ. إي. (1984). "تطور سوق العمل للأطباء المتدربين والمقيمين: دراسة حالة في نظرية الألعاب" (ملف PDF) . مجلة الاقتصاد السياسي . 92 (6): 991-1016 . doi : 10.1086/261272 . S2CID 1360205 . 
• روث، أ. إي.؛ سوتومايور، م. أ. أو. (1990). المطابقة الثنائية: دراسة في نمذجة وتحليل نظرية الألعاب . مطبعة جامعة كامبريدج .
• شوهام، يواف؛ ليتون-براون، كيفن (2009). أنظمة متعددة الوكلاء: الأسس الخوارزمية، ونظرية الألعاب، والمنطقية . نيويورك: مطبعة جامعة كامبريدج . ISBN 978-0-521-89943-7.انظر القسم 10.6.4؛ يمكن تنزيله مجاناً عبر الإنترنت .
• شومر، J.؛ فوهرا، RV (2007). "تصميم الآلية بدون مال" (PDF) . وفي نيسان نوعام؛ خشن ، تيم. تاردوس، إيفا؛ فازيراني، فيجاي (محرران). نظرية اللعبة الخوارزمية . ص 255 – 262. ISBN  978-0521872829.
• غوسفيلد، د.؛ إيرفينغ، ر. و. (1989). مشكلة الزواج المستقر: البنية والخوارزميات . مطبعة معهد ماساتشوستس للتكنولوجيا . ISBN 0-262-07118-5.

• عرض توضيحي تفاعلي بتقنية الفلاش لمشكلة الزواج المستقر
• https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• ملاحظات محاضرة حول مشاكل الزواج المستقر