2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.
We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $α$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.
academic

تخصيص MMS عبر الإنترنت للمهام المنزلية

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

  • معرّف الورقة: 2507.14039
  • العنوان: Online MMS Allocation for Chores
  • المؤلفون: Jiaxin Song (جامعة إلينوي أوربانا-شامبين)، Biaoshuai Tao (جامعة شنغهاي جياو تونغ)، Wenqian Wang (جامعة شنغهاي جياو تونغ)، Yuhao Zhang (جامعة شنغهاي جياو تونغ)
  • التصنيف: cs.GT (علوم الحاسوب - نظرية الألعاب)
  • تاريخ النشر: 11 أكتوبر 2025 (arXiv v2)
  • رابط الورقة: https://arxiv.org/abs/2507.14039

الملخص

تدرس هذه الورقة مشكلة التخصيص العادل للمهام المنزلية غير القابلة للتقسيم بين n من الوكلاء في بيئة عبر الإنترنت. في هذا الإعداد، تصل العناصر بالتسلسل ويجب تخصيصها بشكل لا رجعة فيه لأحد الوكلاء عند وصولها، والهدف هو إنتاج تخصيص α-MMS في النهاية. على الرغم من أن الأعمال الحديثة حققت تقدماً تحت افتراضات مقيدة، فإن أفضل ضمان معروف للحالة العامة لا يزال تافهاً n-MMS، والحد الأدنى الأقوى هو 2 فقط. تغلق هذه الورقة الفجوة في النتائج السلبية بإثبات أنه بالنسبة لأي n ثابت و ε، لا توجد خوارزمية يمكنها ضمان تخصيص (n-ε)-MMS. في الوقت نفسه، تقترح الورقة خوارزمية عبر الإنترنت تضمن تخصيص min{n, O(k), O(log D)}-MMS، حيث k هو الحد الأقصى لعدد قيم المنفعة السالبة المختلفة بين جميع الوكلاء، و D هي أقصى نسبة بين أقصى وأدنى منفعة سالبة لأي وكيل.

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

1. تعريف المشكلة

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

2. أهمية البحث

تتمتع هذه المشكلة بتطبيقات واسعة في الواقع، مثل:

  • تخصيص مهام العمل للموظفين على منصات الخدمات عبر الإنترنت
  • مشاكل موازنة حمل النظام
  • ضمانات العدالة في جدولة الموارد

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

يعاني البحث الموجود من القيود التالية:

  • تحقيق نتائج غير تافهة فقط تحت افتراضات مقيدة جداً (مثل حالة وكيلين بقيمتين)
  • الحاجة إلى معرفة مسبقة بإجمالي المنفعة السالبة لكل وكيل
  • بالنسبة للحالة العامة، يمكن للخوارزمية الأفضل المعروفة فقط ضمان n-MMS التافه

4. دافع البحث

تهدف هذه الورقة إلى:

  • تحديد الحدود النظرية لمشكلة تخصيص MMS عبر الإنترنت
  • تصميم خوارزميات عملية تنطبق على الحالة العامة
  • توفير ضمانات أداء أفضل تحت قيود المعاملات الفعلية

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

  1. التوصيف الدقيق للحد الأدنى النظري: إثبات أنه بالنسبة لأي n ثابت و ε > 0، لا توجد خوارزمية يمكنها ضمان تخصيص (n-ε)-MMS، مما يغلق الفجوة النظرية بالكامل
  2. خوارزمية عبر الإنترنت عامة: تقديم خوارزمية تنطبق على الحالة العامة وتضمن تخصيص min{n, O(k), O(log D)}-MMS
  3. تحليل معاملي: عندما يكون k (عدد قيم المنفعة السالبة المختلفة) ثابتاً، يمكن للخوارزمية تحقيق ضمان O(1)-MMS
  4. حالة القيمتين المحسّنة: توفير ضمان محسّن (2+√3) ≈ 3.7-MMS لحالة القيمتين الشخصية
  5. تقنيات تحليل جديدة: إدخال إطار عمل "Stacking Game" الذي يحول المشكلة إلى مشكلة تقليل الفروقات الخاصة

شرح الطريقة

تعريف المهمة

  • الإدخال: n من الوكلاء، m من المهام المنزلية التي تصل بالتسلسل
  • القيود: لكل مهمة j منفعة سالبة شخصية di(j) للوكيل i، دوال المنفعة السالبة قابلة للإضافة
  • الإخراج: تخصيص A = (A1, ..., An)، حيث Ai هي مجموعة المهام المخصصة للوكيل i
  • الهدف: تحقيق تخصيص α-MMS، أي بالنسبة لجميع i، di(Ai) ≤ α · MMSi

معمارية النموذج

1. إطار خوارزمية الجولة العامة

تستند الخوارزمية إلى امتداد فكرة الجولة (round-robin):

  • الحفاظ على معامل الضغط Hθi لكل نوع منفعة سالبة θ لكل وكيل i
  • يقيس معامل الضغط درجة "الحمل الزائد" للوكيل بالنسبة للتخصيص المثالي
  • الاستراتيجية الجشعة: تخصيص المهمة الجديدة الواصلة للوكيل ذي أقل ضغط للنوع المقابل

2. تقنية تقريب القيم

  • تقريب المنفعة السالبة لكل مهمة واصلة إلى أقرب قوة للعدد 2
  • تقليل عدد أنواع المنفعة السالبة المختلفة
  • تحسين النسبة التنافسية من O(k²) إلى O(k)

3. آلية تحديث الضغط

عند وصول المهمة j:

  • إذا تلقى الوكيل i المهمة j (من النوع θ)، فإن Hθi يزداد بمقدار 1
  • ينخفض معامل الضغط المقابل للوكلاء الآخرين i' بمقدار 1/(n-1)

نقاط الابتكار التقني

1. تجريد Stacking Game

تجريد مشكلة التخصيص عبر الإنترنت إلى "لعبة الترص" المتماثلة المستمرة:

  • الحفاظ على دالة غير متناقصة على الفترة (-1/2, 1/2]
  • يختار الخصم اتحاد فترات بقياس إجمالي 1/k
  • تقوم الخوارزمية بجشع برفع الأجزاء المنخفضة وخفض الأجزاء العالية
  • إثبات أن الخصم لا يمكنه جعل قيمة الدالة تتجاوز O(k)

2. إثبات الحد الأدنى بالبناء العودي

تصميم بناء عودي للحالات الصعبة:

  • تعريف T(n', ε) كعدد الجولات المطلوبة لتحقيق (n-ε)-MMS لـ n' وكيل
  • بناء حالة صعبة لـ T(n'+1) من T(n')
  • آلية "تنظيف" ذكية تجعل التخصيصات السابقة مهملة

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

هذه الورقة عمل نظري بشكل أساسي، بدون تقييم تجريبي بالمعنى التقليدي، بل يتم التحقق من النتائج النظرية من خلال البراهين الرياضية.

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

  1. الإثبات البنائي: إثبات الحدود الدنيا من خلال بناء حالات صعبة محددة
  2. الإثبات بالاستقراء: استخدام الاستقراء الرياضي لإثبات ضمانات أداء الخوارزمية
  3. التحليل الثنائي: تحليل أداء الخوارزمية من خلال المشكلة الثنائية لـ Stacking Game

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

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

1. نتائج الاستحالة الدقيقة

النظرية 5: بالنسبة لأي n و ε > 0، لا توجد خوارزمية عبر الإنترنت يمكنها ضمان تخصيص (n-ε)-MMS.

هذه النتيجة دقيقة، بدون ثوابت مخفية في رموز O الكبيرة، وتطابق تماماً الحد الأعلى التافه.

2. أداء الخوارزمية العامة

النظرية 1: تضمن الخوارزمية 1 تخصيص min{n, O(k), O(log D)}-MMS، حيث:

  • k هو الحد الأقصى لعدد قيم المنفعة السالبة المختلفة بين جميع الوكلاء
  • D هي أقصى نسبة بين أقصى وأدنى منفعة سالبة لأي وكيل

3. تحسين حالة القيمتين

النظرية 6: بالنسبة لحالة القيمتين الشخصية، توجد خوارزمية تضمن تخصيص min{n, 2+√3}-MMS، حيث 2+√3 ≈ 3.7.

نتائج التحليل التقني

1. حدود Stacking Game

النظرية 3: في لعبة Stacking Game، لا يمكن للخصم الحصول على ربح يتجاوز 2k.

هذه النتيجة هي جوهر تحليل الخوارزمية، وتؤدي مباشرة إلى النسبة التنافسية O(k).

2. التحكم في معاملات الضغط

من خلال تحليل Stacking Game، يتم إثبات أن جميع معاملات الضغط Hθi يمكن الحفاظ عليها ضمن نطاق O(k)، مما يضمن أداء الخوارزمية.

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

1. موازنة الحمل عبر الإنترنت

ترتبط مشكلة تخصيص MMS عبر الإنترنت ارتباطاً وثيقاً بمشكلة موازنة الحمل عبر الإنترنت الكلاسيكية:

  • العمل الرائد لـ Graham (1969)
  • أفضل نسبة تنافسية حالية في 1.88, 1.92

2. تخصيص MMS غير المتصل بالإنترنت

البحث في تخصيص MMS في الحالة غير المتصلة بالإنترنت:

  • أفضل حد أعلى: 15/13 (Garg et al., 2025)
  • أفضل حد أدنى: 44/43 (Feige et al., 2021)

3. التخصيص العادل عبر الإنترنت

أعمال أخرى في التخصيص العادل عبر الإنترنت:

  • مفاهيم العدالة القائمة على الحسد
  • نموذج وصول الوكلاء عبر الإنترنت
  • التخصيص عبر الإنترنت للسلع

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

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

  1. التوصيف الكامل للحدود النظرية: إثبات أن n-MMS هو الحد النظري الدقيق لمشكلة تخصيص المهام المنزلية عبر الإنترنت
  2. تصميم خوارزميات عملية: توفير خوارزمية عامة ذات أداء جيدة تحت قيود المعاملات
  3. مساهمة منهجية تقنية: يوفر إطار عمل Stacking Game أداة تحليل جديدة لهذه الفئة من المشاكل

القيود

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

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

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

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

المزايا

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

أوجه القصور

  1. غياب التحقق التجريبي: كعمل نظري بحت، يفتقر إلى التحقق على بيانات فعلية
  2. اعتماد المعاملات: تعتمد أداء الخوارزمية بشكل كبير على قيم k و D
  3. تحليل التعقيد: لم يتم تحليل تعقيد الوقت والمساحة للخوارزمية بالتفصيل

التأثير

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

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

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

المراجع

تستشهد الورقة بأعمال ذات صلة غنية، بما في ذلك:

  • Budish (2010): تقديم مفهوم MMS
  • Zhou et al. (2023): الأعمال المبكرة في تخصيص MMS عبر الإنترنت
  • Wang and Wei (2025): النتائج في حالة وكيلين بقيمتين
  • Garg et al. (2025): أحدث التطورات في تخصيص MMS غير المتصل بالإنترنت

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