الدورانات الفوقية وهيكل المطابقات المستقرة في مشكلة تخصيص مشاريع الطلاب

المعلومات الأساسية

• معرّف الورقة: 2505.13428
• العنوان: مجموعة الدورانات الفوقية لتخصيص الطلاب والمشاريع
• المؤلفون: Peace Ayegba, Sofiat Olaosebikan (جامعة غلاسكو)
• التصنيف: cs.GT (علوم الحاسوب - نظرية الألعاب)
• تاريخ النشر: 10 أكتوبر 2025 (arXiv v2)
• رابط الورقة: https://arxiv.org/abs/2505.13428v2

الملخص

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

طور المؤلفون نتائج هيكلية جديدة لـ SPA-S من خلال تطوير نظرية الدورانات الفوقية (meta-rotations)، وهي تعميم لمفهوم الدورانات في مشكلة الزواج المستقر. تتوافق كل دورة فوقية مع مجموعة التغييرات الدنيا التي تحول مطابقة مستقرة إلى أخرى في شبكة المطابقات المستقرة. تُرتب مجموعة الدورانات الفوقية حسب علاقات الأولوية، مما يشكل مجموعة مرتبة جزئياً من الدورانات الفوقية. أثبت المؤلفون وجود تطابق واحد لواحد بين مجموعة المطابقات المستقرة والمجموعات المغلقة لمجموعة الدورانات الفوقية المرتبة جزئياً.

الخلفية البحثية والدافع

خلفية المشكلة

مشكلة تخصيص مشاريع الطلاب (SPA-S) هي مشكلة مهمة في نظرية المطابقة، وتتميز بالخصائص التالية:

1. الهيكل ثلاثي الطبقات: ثلاث مستويات - الطلاب والمشاريع والمحاضرون، حيث تكون المشاريع وسيطة بين الطلاب والمحاضرين
2. قيود السعة: لكل مشروع ومحاضر حد أقصى للسعة
3. التعبير عن التفضيلات: الطلاب لديهم تفضيلات تجاه المشاريع، والمحاضرون لديهم تفضيلات تجاه الطلاب
4. متطلبات الاستقرار: يجب أن تفي المطابقة بشروط الاستقرار، أي عدم وجود أزواج محظورة

دافع البحث

1. الفجوة النظرية: على الرغم من تأسيس الخوارزميات الأساسية لـ SPA-S، لا يزال هناك نقص في الفهم العميق لهيكل المطابقات المستقرة
2. الاحتياجات الخوارزمية: الحاجة إلى خوارزميات فعالة لتعداد وحساب المطابقات المستقرة، وحساب المطابقات المستقرة تحت أهداف تحسين أخرى
3. تعقيد الهيكل: الهيكل ثلاثي الطبقات لـ SPA-S يجعل من المستحيل تطبيق نظرية الدورانات الكلاسيكية مباشرة، مما يتطلب إطار نظري جديد
4. التطبيقات العملية: الحاجة إلى خطط مطابقة أكثر مرونة في السيناريوهات العملية مثل تخصيص المشاريع الجامعية وتخصيص الموارد

قيود الطرق الموجودة

1. صعوبة التوسيع المباشر: لا يمكن تطبيق تعريف الدورانات الفوقية لمشكلة الإقامة الطبية (HR) مباشرة على SPA-S
2. الاختلافات الهيكلية: في SPA-S، قد يتم تخصيص المشاريع لأعداد مختلفة من الطلاب في مطابقات مستقرة مختلفة، مما ينتهك نظرية المستشفى الريفي لـ HR
3. كفاءة الخوارزمية: نقص الطرق الهيكلية الفعالة لاستكشاف فضاء المطابقات المستقرة

المساهمات الأساسية

1. توسيع نظرية الدورانات الفوقية: تطوير نظرية الدورانات الفوقية لـ SPA-S، مع تعريف مفهوم الدورانات الفوقية المناسب للهيكل ثلاثي الطبقات
2. نظريات هيكلية: إثبات تطابق واحد لواحد بين مجموعة المطابقات المستقرة والمجموعات المغلقة لمجموعة الدورانات الفوقية المرتبة جزئياً
3. أساس خوارزمي: توفير أساس نظري لتعداد وحساب المطابقات المستقرة وحساب المطابقات المستقرة المثلى
4. الليمات والنظريات الجديدة: إنشاء عدة ليمات ونظريات مهمة حول هيكل المطابقات المستقرة في SPA-S
5. طرق بناءة: توفير خوارزميات محددة لتحديد وحذف الدورانات الفوقية

شرح الطريقة

تعريف المهمة

تعريف مشكلة SPA-S:

• مجموعة الطلاب $S = \{s_1, \ldots, s_{n_1}\}$
• مجموعة المشاريع $P = \{p_1, \ldots, p_{n_2}\}$
• مجموعة المحاضرين $L = \{l_1, \ldots, l_{n_3}\}$
• كل مشروع يقدمه محاضر واحد: $P_k \subseteq P$ هي مجموعة المشاريع التي يقدمها المحاضر $l_k$
• قيود السعة: سعة المشروع $c_j$، سعة المحاضر $d_k$
• التفضيلات: الطلاب لديهم تفضيلات صارمة تجاه المشاريع، والمحاضرون لديهم تفضيلات صارمة تجاه الطلاب

تعريف الاستقرار: المطابقة $M$ مستقرة إذا وفقط إذا لم يكن هناك زوج محظور $(s_i, p_j)$ حيث:

• $s_i$ غير مخصص أو يفضل $p_j$ على $M(s_i)$
• يستوفي أحد الشروط التالية:
  • $p_j$ و $l_k$ كلاهما غير ممتلئ
  • $p_j$ غير ممتلئ، $l_k$ ممتلئ، و $l_k$ يفضل $s_i$ على أسوأ طالب في $M(l_k)$
  • $p_j$ ممتلئ و $l_k$ يفضل $s_i$ على أسوأ طالب في $M(p_j)$

بناء النظرية الأساسية

1. تعريف المشروع التالي

بالنسبة للطالب $s_i$، مشروعه التالي $s_M(s_i)$ هو أول مشروع $p$ في قائمة تفضيلاته يستوفي الشروط التالية:

• الشرط (i): $p$ ممتلئ في $M$ والمحاضر $l$ يفضل $s_i$ على $w_M(p)$ (أسوأ طالب في $p$)
• الشرط (ii): $p$ غير ممتلئ في $M$، $l$ ممتلئ، و $l$ يفضل $s_i$ على $w_M(l)$ (أسوأ طالب لدى $l$)

2. تعريف الدورة الفوقية المكشوفة

الدورة الفوقية $\rho = \{(s_0, p_0), (s_1, p_1), \ldots, (s_{r-1}, p_{r-1})\}$ مكشوفة في المطابقة $M$ إذا وفقط إذا:

• كل $(s_t, p_t) \in M$
• $s_t$ هو أسوأ طالب في $p_t$ في $M$
• $s_{t+1} = \text{next}_M(s_t)$ (الفهرس بمودولو $r$)

3. حذف الدورة الفوقية

بالنظر إلى المطابقة المستقرة $M$ والدورة الفوقية المكشوفة $\rho$، يتم حذف $\rho$ للحصول على المطابقة الجديدة $M/\rho$:

• كل طالب $s$ في $\rho$ يتم تخصيصه إلى $s_M(s)$
• الطلاب الآخرون يحتفظون بتخصيصهم الأصلي

الليمات والنظريات الرئيسية

الليمات 1-3: الخصائص الهيكلية تحت علاقة الهيمنة

عندما تهيمن $M$ على $M'$ والطالب $s_i$ مخصص لمشاريع مختلفة في المطابقتين:

• إذا تم تخصيص $s_i$ إلى مشروع ممتلئ $p_j$ في $M'$، فإن أسوأ طالب في $M(p_j)$ ليس في $M'(p_j)$
• إذا تم تخصيص $s_i$ إلى مشروع غير ممتلئ $p_j$ في $M'$، فيجب أن يكون المحاضر ممتلئاً في $M$

الليمة 6: عدم إمكانية الوصول للمشروع

في الدورة الفوقية، لا يمكن للمشاريع الموجودة بين المشروع الحالي والمشروع التالي في قائمة تفضيلات الطالب أن تشكل أزواجاً مستقرة.

الليمة 7: وجود الدورة الفوقية

أي مطابقة مستقرة غير محسّنة للمحاضر تحتوي على دورة فوقية مكشوفة واحدة على الأقل.

الليمة 9: الاستقرار بعد الحذف

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

الليمة 10: الاتساق

إذا كان طالب معين في الدورة الفوقية يفضل المطابقة الأصلية، فإن جميع الطلاب ذوي الصلة يفضلون المطابقة الأصلية.

النظرية 2: النتيجة الرئيسية

يوجد تطابق واحد لواحد بين مجموعة المطابقات المستقرة والمجموعات المغلقة لمجموعة الدورانات الفوقية المرتبة جزئياً.

إعداد التجارب

تحليل الأمثلة

توضح الورقة تطبيق النظرية من خلال أمثلة محددة:

المثال $I_1$:

• 9 طلاب، 8 مشاريع، 2 محاضر
• سعات المشاريع: $c_1 = c_3 = 2$، سعات المشاريع الأخرى = 1
• سعات المحاضرين: $d_1 = 4, d_2 = 5$
• إجمالي 7 مطابقات مستقرة

عملية تحديد الدورة الفوقية

1. بناء الرسم البياني الموجه $H(M)$: الرؤوس هي الطلاب المخصصون لمشاريع مختلفة في $M$ و $M_L$
2. تتبع المسار: البدء من أي رأس، والمتابعة على طول الحافة الخارجة حتى إعادة زيارة رأس ما
3. استخراج الحلقة: المسار بين الرأس المكرر يشكل دورة فوقية

التحقق من الخوارزمية

التحقق من صحة النظرية من خلال حذف الدورات الفوقية بشكل تدريجي:

• $M_1 \xrightarrow{\rho_1} M_2 \xrightarrow{\rho_2} M_3$
• كل خطوة حذف تنتج مطابقة مستقرة جديدة
• يمكن الوصول في النهاية إلى المطابقة المثلى للمحاضر

نتائج التجارب

التحقق النظري

1. تحديد الدورة الفوقية: تم تحديد جميع الدورات الفوقية الأربع في المثال بنجاح
2. تحويل المطابقة: تم التحقق من صحة حذف الدورة الفوقية
3. التطابق الواحد لواحد: تم تأكيد العلاقة بين المطابقات والمجموعات المغلقة

الاكتشافات الهيكلية

1. الدورات الفوقية المكشوفة المتكررة: يمكن كشف نفس الدورة الفوقية في مطابقات مستقرة متعددة
2. التعايش متعدد الدورات: قد تحتوي مطابقة مستقرة واحدة على دورات فوقية مكشوفة متعددة
3. تفرد المسار: المسار الذي يبدأ من أي طالب يحدد الدورة الفوقية بشكل فريد

كفاءة الخوارزمية

• البناء في الوقت متعدد الحدود: يمكن بناء مجموعة الدورانات الفوقية المرتبة جزئياً في الوقت متعدد الحدود
• التمثيل المضغوط: على الرغم من أن عدد المطابقات المستقرة قد يكون أسياً، توفر المجموعة المرتبة جزئياً تمثيلاً مضغوطاً

الأعمال ذات الصلة

تطور نظرية المطابقة المستقرة

1. خوارزمية Gale-Shapley: وضعت الأساس لنظرية المطابقة المستقرة
2. نظرية الدورانات: طور Gusfield و Irving مجموعة الدورانات المرتبة جزئياً لمشكلة الزواج المستقر
3. التوسيع متعدد لمتعدد: وسّع Bansal مفهوم الدورانات إلى إعدادات متعددة لمتعددة

الأبحاث ذات الصلة بـ SPA-S

1. Abraham وآخرون: وضعوا الخوارزميات الأساسية لـ SPA-S ونظرية المشاريع غير المرغوبة
2. دراسات الخصائص الهيكلية: ركزت الأعمال السابقة بشكل أساسي على الخصائص الأساسية، مع نقص في تحليل الهيكل العميق

تطور الدورانات الفوقية

1. مشكلة HR: طور Cheng نظرية الدورانات الفوقية لمشكلة الإقامة الطبية
2. الحالات مع التعادل: درس Scott وآخرون المطابقات الفائقة المستقرة مع تفضيلات متعادلة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

1. الاكتمال النظري: إنشاء إطار نظري كامل للدورانات الفوقية لـ SPA-S
2. توصيف الهيكل: توفير تمثيل هيكلي مضغوط لمجموعة المطابقات المستقرة
3. الأساس الخوارزمي: توفير أساس نظري لمختلف مشاكل التحسين

القيود

1. تحليل التعقيد: لم يتم توفير تحليل تفصيلي لتعقيد الوقت
2. التطبيقات العملية: نقص التحقق على بيانات حقيقية واسعة النطاق
3. قيود التوسيع: تنطبق النظرية بشكل أساسي على حالات التفضيلات الصارمة

الاتجاهات المستقبلية

1. توصيف متعدد الأوجه: تطوير تمثيل متعدد الأوجه لمجموعة المطابقات المستقرة
2. التوسيع مع التعادل: توسيع النظرية لتشمل حالات التفضيلات المتعادلة
3. تحسين الخوارزمية: تطوير خوارزميات أكثر كفاءة لتحديد وحذف الدورات الفوقية
4. البحث التطبيقي: التحقق من القيمة النظرية في سيناريوهات تخصيص المشاريع الفعلية

التقييم المتعمق

المميزات

1. الابتكار النظري: توسيع ناجح لنظرية الدورانات إلى هيكل ثلاثي الطبقات أكثر تعقيداً
2. الإثباتات الصارمة: توفير إثباتات رياضية كاملة وصارمة
3. القيمة العملية: توفير أساس نظري متين لتصميم الخوارزميات العملية
4. الوضوح في التعبير: هيكل الورقة واضح والتعبير الرياضي دقيق

النقاط التقنية البارزة

1. دقة التعريف: يلتقط تعريف الدورة الفوقية بدقة الخصائص الهيكلية لـ SPA-S
2. الطرق البناءة: توفير طرق عملية قابلة للتطبيق لتحديد الدورات الفوقية
3. إثبات الاكتمال: إنشاء علاقة تطابق واحد لواحد كاملة

أوجه القصور

1. تعقيد الحساب: لم يتم تحليل تعقيد الخوارزمية بعمق
2. حجم التجارب: الأمثلة صغيرة الحجم، مع نقص التحقق واسع النطاق
3. تحليل المقارنة: المقارنة مع الطرق الأخرى غير كافية

تقييم التأثير

1. المساهمة النظرية: توفير رؤى هيكلية مهمة لنظرية المطابقة
2. الأهمية الخوارزمية: توفير أفكار حل جديدة لمشاكل خوارزمية ذات صلة
3. الإمكانات التطبيقية: قيمة تطبيقية عملية في مجالات مثل تخصيص الموارد التعليمية

السيناريوهات المعمول بها

1. تخصيص مشاريع الجامعة: قابل للتطبيق المباشر على سيناريوهات تخصيص مشاريع الطلاب
2. تخصيص الموارد: قابل للتطبيق على مشاكل تخصيص الموارد ذات الهيكل الوسيط
3. تحسين المطابقة: توفير أدوات نظرية لمختلف مشاكل تحسين المطابقة

المراجع

تستشهد الورقة بالأدبيات المهمة في مجال نظرية المطابقة، بما في ذلك:

• Gale & Shapley (1962): العمل الرائد في مشكلة الزواج المستقر
• Abraham وآخرون (2007): الخوارزميات الأساسية لمشكلة SPA-S
• Gusfield & Irving (1989): الهيكل والخوارزميات لمشكلة الزواج المستقر
• Bansal (2007): خوارزمية الوقت متعدد الحدود للتخصيص المستقر متعدد لمتعدد

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