2025-11-18T20:31:13.847843

Fair Assignment of Indivisible Chores to Asymmetric Agents

Seddighin, Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share value (\MMS) context. While constant-\MMS\ allocations/assignments are guaranteed to exist for both goods and chores in the symmetric setting, the situation becomes much more complex when agents have different entitlements. For the allocation of indivisible goods, it has been proven that an $n$-\WMMS\ (weighted \MMS) guarantee is the best one can hope for. For indivisible chores, however, it was recently discovered that an $O(\log n)$-\WMMS\ assignment is guaranteed to exist. In this work, we improve this upper bound to a constant-\WMMS\ guarantee.\footnote{We prove the existence of a 20-\WMMS\ assignment, but we did not attempt to optimize the constant factor. We believe our methods already yield a slightly better bound with a tighter analysis.}
academic

التوزيع العادل للمهام غير القابلة للتقسيم على الوكلاء غير المتماثلين

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

  • معرّف الورقة: 2510.10698
  • العنوان: التوزيع العادل للمهام غير القابلة للتقسيم على الوكلاء غير المتماثلين
  • المؤلفون: Masoud Seddighin, Saeed Seddighin
  • التصنيف: cs.GT (علوم الحاسوب - نظرية الألعاب)
  • تاريخ النشر: 12 أكتوبر 2025 (نسخة أولية على arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.10698v1

الملخص

تدرس هذه الورقة مشكلة التوزيع العادل للمهام غير القابلة للتقسيم على وكلاء يتمتعون بحقوق مختلفة ضمن إطار عمل القيمة الأدنى الأقصى (MMS). بينما يُضمن وجود توزيعات ثابتة-MMS للسلع والمهام في الإعدادات المتماثلة، يصبح الوضع أكثر تعقيداً عندما يمتلك الوكلاء حقوقاً مختلفة. بالنسبة لتوزيع السلع غير القابلة للتقسيم، ثبت أن ضمان n-WMMS (القيمة الأدنى الأقصى المرجحة) هو الأمثل. ومع ذلك، بالنسبة للمهام غير القابلة للتقسيم، تم اكتشاف مؤخراً وجود ضمان توزيع O(log n)-WMMS. تحسّن هذه الورقة هذا الحد الأعلى إلى ضمان ثابت-WMMS، حيث تثبت وجود توزيع 20-WMMS.

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

  1. المشكلة الأساسية: تدرس هذه الورقة مشكلة التوزيع العادل للمهام غير القابلة للتقسيم بين وكلاء غير متماثلين. بخلاف مشكلة "تقسيم الكعكة" الكلاسيكية، يتعامل هنا مع مهام منفصلة وغير قابلة للتقسيم (chores)، وللوكلاء حقوق مختلفة (entitlements).
  2. أهمية المشكلة:
    • في العالم الحقيقي، تحدث حالات الحقوق غير المتساوية بشكل متكرر، مثل قوانين الوراثة في مختلف الثقافات والأديان التي تحدد عادة توزيعات غير متساوية
    • يعتمد توزيع الموارد الطبيعية (مثل النفط والثروة السمكية) عادة على اعتبارات جغرافية واقتصادية وسياسية
    • تبرز هذه الاحتياجات العملية أهمية دراسة التوزيع العادل في ظل الحقوق غير المتساوية
  3. قيود الطرق الموجودة:
    • لا تنطبق ضمانات التقريب الثابت من الإعدادات المتماثلة بشكل مباشر، لكن الحالات غير المتماثلة أكثر تحدياً
    • بالنسبة لتوزيع السلع، ثبت أن n-WMMS هو الضمان الأمثل
    • بالنسبة لتوزيع المهام، كان أفضل نتيجة سابقة هي ضمان O(log n)-WMMS
  4. دافع البحث: تحسين نسبة التقريب لتوزيع المهام من المستوى اللوغاريتمي إلى المستوى الثابت، وهو اختراق نظري كبير.

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

  1. المساهمة النظرية الرئيسية: إثبات وجود توزيع 20-WMMS لمشكلة التوزيع غير المتماثل، وهو أول ضمان ثابت-WMMS
  2. الابتكار الخوارزمي: اقتراح خوارزمية السكين المتحركة الطبقية (Layered Moving Knife Algorithm) الجديدة، التي تمد طريقة السكين المتحركة إلى الإعدادات غير المتماثلة
  3. تحسين الحالات الصغيرة: توفير حدود أفضل من log n+1 للحالات n=3 و n=4
  4. التحليل المستقل عن المهام: تطوير تقنيات تحليل مستقلة عن المهام، مما يحسّن الحدود لأعداد صغيرة من الوكلاء

شرح الطريقة

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

المدخلات:

  • N = {a₁, a₂, ..., aₙ}: n وكيل
  • M = {b₁, b₂, ..., bₘ}: m مهمة
  • Vᵢ: دالة التكلفة الإضافية للوكيل aᵢ
  • wᵢ: حق الوكيل aᵢ، حيث ∑wᵢ = 1

المخرجات: توزيع المهام على الوكلاء بحيث تحقق حزمة المهام Sᵢ التي يحصل عليها الوكيل aᵢ: Vᵢ(Sᵢ) ≤ α·WMMSᵢ

التعاريف الرئيسية:

  • القيمة الأدنى الأقصى المرجحة: WMMSᵢ = min⟨A₁,...,Aₙ⟩∈Π(M) maxⱼ∈N Vᵢ(Aⱼ)·(wᵢ/wⱼ)
  • توزيع α-WMMS: لا تتجاوز تكاليف جميع الوكلاء α أضعاف قيمة WMMS الخاصة بهم

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

1. مرحلة المعالجة المسبقة

الليما 4.1 (اختزال إعداد المهام المرتبة): إذا كان هناك ضمان لوجود توزيع α-WMMS في إعداد المهام المرتبة، فإنه يوجد أيضاً في الحالة العامة.

الليما 4.2 (اختزال قابلية تقسيم الحقوق): إذا كان هناك ضمان لوجود توزيع α-WMMS في إعداد الحقوق القابلة للتقسيم، فإنه يوجد توزيع 2α-WMMS في الحالة العامة.

2. خوارزمية السكين المتحركة الطبقية

تحافظ الخوارزمية على ثلاث مجموعات من الوكلاء:

  • الوكلاء الميتون (D): الوكلاء الذين اكتملت تخصيصاتهم
  • الوكلاء قيد المعالجة (P): الوكلاء المشاركون في جولة التخصيص الحالية
  • وكلاء الانتظار (Q): الوكلاء في انتظار التخصيص

تدابير السلامة:

  • ∑aᵢ∈P wᵢ ≥ ∑aᵢ∈D wᵢ
  • m - s ≥ ∑ᵢ>minp wᵢ/wminp (حيث minp هو الوكيل ذو الفهرس الأصغر في P)

التدفق الأساسي:

  1. تخصيص المهام من bₘ إلى b₁ بالتتابع
  2. إنشاء 2wᵢ/wminp نسخة لكل وكيل aᵢ في P لتكوين P'
  3. استخدام فترة السكين (ℓ,r)، توسيع الفترة قدر الإمكان حتى لا يكون لأي وكيل تكلفة ≤ 5wminp
  4. تخصيص جميع المهام داخل الفترة لنسخة وكيل واحدة تحقق الشروط
  5. عند تفريغ P'، تحديث مجموعات D و P و Q

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

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

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

إعداد التحليل النظري

تركز هذه الورقة بشكل أساسي على التحليل النظري، مع تركيز الجزء التجريبي على:

  1. تحليل الحالات الصغيرة: تحليل الحدود الدقيقة لـ n=3,4
  2. التحقق التجريبي: التحقق من خلال أخذ عينات عشوائية من مليار مجموعة إعدادات حقوق لـ 3≤n≤10
  3. المعايير المقارنة: المقارنة مع الحد الأعلى السابق log n+1

مؤشرات التقييم

  • نسبة التقريب: عامل مضاعف ضمان WMMS
  • نطاق التطبيق: نطاق عدد الوكلاء الذي تنطبق عليه الخوارزمية
  • الضمان النظري: الأداء المضمون في أسوأ الحالات

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

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

الإعدادالأعمال السابقةنتائج هذه الورقة
n عامlog n+120
n=2(√3+1)/2-
n=3-≈2.1122
n=4-≈2.5404

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

النظرية 4.5: يوجد توزيع 20-WMMS لمشكلة التوزيع غير المتماثل.

النظرية 5.4: بالنسبة لثلاثة وكلاء، يوجد دائماً توزيع 2.1122-WMMS تقريباً.

النظرية 5.5: بالنسبة لأربعة وكلاء، يوجد دائماً توزيع 2.5404-WMMS تقريباً.

الاكتشافات التجريبية

  1. الاختراق النظري: تحسين الحد الأعلى من O(log n) إلى ثابت للمرة الأولى
  2. تحسين الحالات الصغيرة: بالنسبة لـ n≤10، توفر تقنية المستقلة عن المهام حدود أفضل
  3. الحد العملي: الحد الثابت يتفوق على الحد اللوغاريتمي فقط عندما n>2¹⁹=524288

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

الاتجاهات البحثية الرئيسية

  1. التقسيم العادل الكلاسيكي: يبدأ من مشكلة تقسيم الكعكة لـ Steinhaus عام 1948
  2. توزيع السلع غير القابلة للتقسيم: الانتقال من الموارد المستمرة إلى توزيع السلع المنفصلة
  3. مفهوم MMS: القيمة الأدنى الأقصى التي اقترحها Budish كمقياس للعدالة

علاقة هذه الورقة بالأعمال ذات الصلة

  • Aziz وآخرون 4: أول دراسة لتوزيع المهام تحت الحقوق غير المتساوية
  • Wang وآخرون 27: تأسيس الحد الأعلى O(log n)-WMMS
  • Huang وآخرون 21: توفير حدود محددة للحالات الصغيرة

المزايا التقنية

مقارنة بالأعمال الموجودة، تتمتع هذه الورقة بالمزايا التالية:

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

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

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

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

القيود

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

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

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

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

المزايا

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

أوجه القصور

  1. قيود الجدوى العملية: الثابت 20 كبير نسبياً، التحسن العملي محدود
  2. نطاق التطبيق: يتمتع بميزة فقط في الحالات الضخمة جداً
  3. تعقيد الخوارزمية: التنفيذ معقد نسبياً، قد يؤثر على التطبيق العملي

التأثير

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

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

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

المراجع

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

  1. Budish (2011): اقتراح مفهوم MMS
  2. Aziz وآخرون (2019): العمل الرائد في توزيع المهام غير المتماثل
  3. Wang وآخرون (2024): أفضل نتيجة سابقة O(log n)
  4. Huang وآخرون (2023): تحليل الحدود للحالات الصغيرة

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