ملتقى التوقعات: كيف تجمع الخوارزميات بين الأزواج بتأخير مثالي ✛ ✎

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

النموذج الرياضي لهذا الملتقى يُسمى 'المطابقة التامة ذات التكلفة الدنيا مع تأخير' (Min-Cost Perfect Matching with Delay - MPMD). يُستبدل فضاء حلبة الرقص بفضاء متري (metric space) — مجرد مجموعة نقاط ذات مسافات معروفة. يظهر كل طلب جديد في نقطة عشوائية، وعلى المنظم أن يقرر: هل يصله بأحد المنتظرين، دافعًا تكلفةً تساوي المسافة بينهما، أم يسمح له بالانتظار، مراكمًا غرامة التأخير. المقياس الرئيسي للنجاح هو التحليل التنافسي (competitive analysis) (مقارنة بالحل المثالي بعد وقوع الحدث)، وهي فكرة طرحها جون فون نيومان في نظرية الألعاب. تتنافس الخوارزمية مع خصم وهمي يعرف المستقبل ويتخذ دائمًا القرار الأمثل.

لكن بمجرد تغيير طبيعة نفاد الصبر — يتحول الملتقى. فبدل أن تنمو الغرامة تناسبًا مع طول الطابور (التأخير القياسي)، يمكننا أن نأخذ في الاعتبار الاستياء الفردي الذي يتصاعد بشكل غير متناسب: دقيقة الانتظار محتملة، لكن الدقيقة الثانية تثير الغضب أكثر بكثير. يوصف هذا السلوك بدالة محدبة (convex function) (ذات تسارع في النمو)، مثلًا f(t)=$t^k$/k + t. أثبت الباحثون: إذا كانت مشتقة هذه الدالة عند الصفر موجبة، أي أنه حتى في اللحظة الأولى يسبب التأخير ألمًا ملموسًا، فإن المسألة تُحل بكفاءة ثابتة. يكفي تطبيق خوارزمية 'عديمة الصبر'، تصل إجباريًا بين الطلبات التي انتظرت أكثر من عتبة 4δ.

كشف العمل عن انتقال طوري غير متوقع: أدنى تغيير في السلوك المحلي للدالة عند الصفر يقلب تعقيد المسألة. وهذا يذكر بـنظام ديناميكي، حيث يغير نابض خفي نمط التذبذب بأكمله. بالنسبة للتأخيرات القياسية، يبلغ معامل التنافسية (competitive ratio) الحتمي O($2^n$) — نمو أسي مع أبعاد المترية، وهو مع ذلك أفضل من التقدير السابق المعتمد على عدد الطلبات الذي قد يكون كبيرًا جدًا. أما الخوارزمية العشوائية، فتعطي، كمنظم يرمي قطعة نقد، O(n²). يصبح التباين واضحًا بشكل خاص في الحالة المحدبة ذات المشتقة الموجبة: 13·$2^{k+1}$((4δ)^{k-1}+1) — ثابت لا يعتمد على عدد الضيوف.

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