Asymptotic Equivalence of Immediate and Deferred Acceptance

تخيل أنك عمدة مدينة صاخبة، حيث يحتاج كل طفل إلى مقعد في مدرسة، وهناك بالضبط عدد من المقاعد يساوي عدد الطلاب. المشكلة ليست فقط في إيجاد أي مقعد، بل في إيجاد المقعد المناسب. فكل عائلة لديها قائمة بالمدارس التي تحبها، بدءاً من "مدرسة أحلامي" وصولاً إلى "المدرسة التي سأذهب إليها إذا اضطررت لذلك". والمدينة أيضاً لديها قواعد؛ فربما تعطي مدرسة ما الأولوية للأطفال الذين يعيشون بالقرب منها أو الذين لد الله لديهم إخوة مسجلون فيها بالفعل. السؤال الكبير الذي يواجه المسؤولين هو: كيف نربط الأطفال بالمدارس بحيث يكون الجميع سعيدين قدر الإمكان؟

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

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

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

---

سباق المدارس العظيم: حكاية آليتين

قرر جوسوي أورتيجا، الباحث من جامعة كوينز بلفاست، حسم هذا الجدل من خلال إجراء تجربة ذهنية ضخمة. لم ينظر إلى مدن حقيقية بتاريخها وسياساتها المعقدة، بل تخيل "سوقاً عشوائياً" – عالماً حيث يتم رسم قائمة المدارس المفضلة لكل طالب بشكل عشوائي تماماً، مثل سحب أسماء من قبعة. في هذا العالم، هناك $n$ من الطلاب و $n$ من المدارس.

أراد أورتيجا قياس "متوسط الترتيب". تخيل لو حصل كل طالب على درجة بناءً على مدى ارتفاع المدرسة المخصصة له في قائمته. إذا حصلت على خيارك رقم 1، فإن ترتيبك هو 1. إذا حصلت على خيارك رقم 100، فإن ترتيبك هو 100. الهدف هو إبقاء هذا الرقم منخفضاً قدر الإمكان.

لفترة طويلة، كنا نعرف الإجابة بالنسبة للرقصة البطيئة والحذرة (DA). ففي السبعينيات، اكتشف علماء الرياضيات أنه في السوق العشوائي، ينتهي الأمر بالمتوسط للطلاب في مدرسة ذات ترتيب تقريبي يبلغ $\log n$ (لوغاريتم $n$). إذا كان لديك 1,000 طالب، فإن متوسط الترتيب هو 7 تقريباً. وإذا كان لديك 100,000 طالب، فهو حوالي 11. الرقم ينمو، ولكن ببطء شديد.

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

سر "جامع الكوبونات"

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

تخيل أنك تحاول جمع مجموعة كاملة من $n$ من بطاقات التداول المختلفة. في كل مرة تشتري فيها علبة حبوب إفطار، تحصل على بطاقة عشوائية واحدة. كم عدد العلب التي تحتاج إلى شرائها للحصول على كل بطاقة على الأقل مرة واحدة؟
الإجابة هي تقريباً $n \times \log n$. أنت تقضي وقتاً طويلاً في شراء العلب فقط لتجد آخر بضع بطاقات نادرة تنقصك.

أظهر أورتيجا أن القبول المؤجل يشبه هذا تماماً. يستمر الطلاب في التقديم للمدارس حتى تتلقى كل مدرسة طلباً واحداً على الأقل. إجمالي الطلبات المقدمة من الجميع هو تقريباً نفس عدد علب الحبوب التي قد تحتاج لشرائها لجمع كل الكوبونات. وبما أن متوسط عدد الطلبات التي يقدمها الطالب هو حوالي $\log n$، فإن ترتيب مدرستهم النهائي هو أيضاً حوالي $\log n$.

ثم وجه أورتيجا نظره نحو القبول الفوري. في البداية، بدا الأمر مختلفاً لأن الطلاب لا يمكنهم الاستمرار في التقديم فوراً؛ بل عليهم الانتظار حتى تنتهي "جولة" قبل المحاولة مرة أخرى. لكن أدرك أورتيجا أنه إذا نظرت إلى العملية بطريقة معينة، فهي أيضاً تشبه "جامع الكوبونات".

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

الكشف الكبير

إليك النتيجة الصادمة: الفرق بين الطريقتين صغير بشكل مفاجئ.

أثبت أورتيجا رياضياً أنه مع ازدياد حجم السوق (عندما يصبح $n$ كبيراً جداً)، فإن متوسط ترتيب الطلاب في نظام القبول الفوري (IA) هو أيضاً تقريباً $\log n$.

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

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

لماذا يهم هذا؟

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

لقد وسّع أورتيجا هذا الاكتشاف ليشمل متغيرات أخرى أيضاً. سواء كانت المدارس تمتلك مقاعد متعددة (مطابقة من كثير إلى واحد) أو ما إذا كان يُسمح للطلاب بتجاوز المدارس الممتلئة (وهو تنويع يسمى "القبول الفوري مع التجاوز")، فإن النتيجة تظل ثابتة: متوسط الترتيب يبقى حول $\log n$.

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