نتائج هيكلية وخوارزمية للدورات المستقرة والتقسيمات في مشكلة زملاء الغرفة

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