2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
academic

التوزيع العادل والفعال للمن المختلط غير القابل للتقسيم

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

  • معرّف الورقة البحثية: 2507.03946
  • العنوان: التوزيع العادل والفعال للمن المختلط غير القابل للتقسيم
  • المؤلفون: Siddharth Barman (معهد العلوم الهندي)، Vishwa Prakash HV (معهد تشيناي للرياضيات)، Aditi Sethia (معهد العلوم الهندي)، Mashbat Suzuki (جامعة نيو ساوث ويلز)
  • التصنيف: cs.GT (علوم الحاسوب - نظرية الألعاب)
  • تاريخ النشر: 15 أكتوبر 2025 (النسخة الثانية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2507.03946v2

الملخص

تدرس هذه الورقة البحثية مشكلة التوزيع العادل للمن المختلط غير القابل للتقسيم (mixed manna) بين الوكلاء ذوي التقييمات الإضافية. يشير المن المختلط إلى السلع التي قد تكون قيمتها موجبة أو سالبة أو صفرية. تؤسس الورقة ضمانات نظرية تثبت أن العدالة (بناءً على استرخاء مفهوم الخلو من الحسد) وكفاءة باريتو يمكن تحقيقهما معاً. بشكل محدد، تستند الضمانات العادلة إلى مفهوم "الخلو من الحسد مع إعادة توزيع k عنصر" (EFR-k): يقال إن التوزيع A هو EFR-k إذا كان هناك مجموعة جزئية R تحتوي على عناصر بحد أقصى k بحيث يمكن الحصول على توزيع خالٍ من الحسد تجاه كل وكيل i من خلال إعادة توزيع العناصر في R.

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

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

التوزيع العادل مشكلة متكررة في سيناريوهات واقعية متعددة مثل تقسيم الممتلكات وتخصيص المهام والنزاعات الحدودية وتوزيع الديون. عندما يمتلك الوكلاء المشاركون تفضيلات شخصية، فإن سؤال "من يحصل على ماذا" يتمتع بأهمية عملية وثراء نظري.

التحديات البحثية

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

الدافع البحثي

تهدف الورقة إلى توفير ضمانات نظرية للتوزيع العادل والفعال للمن المختلط من خلال إدخال مفهوم EFR-k وتطوير خوارزميات حسابية فعالة.

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

  1. ضمانات الوجود النظري: تثبت أنه بالنسبة لتوزيع المن المختلط بين n وكيل بتقييمات إضافية، يوجد دائماً توزيع يكون EFR-(n-1) وباريتو أمثل.
  2. القابلية الحسابية للخوارزمية: عندما يكون عدد الوكلاء n ثابتاً، يمكن حساب توزيع EFR-(n-1) وباريتو أمثل في وقت متعدد الحدود.
  3. نتائج EFR المستقلة:
    • يمكن حساب توزيع المن المختلط EFR-(n-1) في وقت متعدد الحدود
    • عندما تكون جميع العناصر سلعاً، يوجد توزيع EFR-⌊n/2⌋ ويمكن حسابه بكفاءة
  4. نتائج الإحكام:
    • بالنسبة للأعمال المنزلية، الحد (n-1) محكم
    • بالنسبة للسلع، الحد ⌊n/2⌋ محكم
  5. الابتكار التقني: تطبيق نظرية Knaster-Kuratowski-Mazurkiewicz (KKM) لأول مرة في التوزيع العادل المنفصل.

شرح الطريقة

تعريف المهمة

المدخلات:

  • n وكيل، يُرمز لهم بـ n = {1,...,n}
  • m عنصر غير قابل للتقسيم، يُرمز لها بـ m = {1,...,m}
  • دوال تقييم إضافية {vi}i∈n، حيث vi(t) ∈ ℝ تمثل تقييم الوكيل i للعنصر t

المخرجات: توزيع A = (A1,...,An)، حيث Ai ⊆ m هي مجموعة العناصر المخصصة للوكيل i

الهدف: إيجاد توزيع يرضي في نفس الوقت EFR-k وباريتو الأمثل

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

تعريف EFR-k

يقال إن التوزيع A هو EFR-k إذا وفقط إذا كانت هناك مجموعة جزئية R ⊆ m بحجم لا يتجاوز k، بحيث يمكن الحصول على توزيع خالٍ من الحسد تجاه كل وكيل i من خلال إعادة توزيع العناصر في R.

المكونات التقنية الرئيسية

  1. اضطراب التقييم: للحصول على شروط غير متحللة، يتم إضافة اضطراب إضافي صغير كافٍ إلى التقييمات المعطاة:
    v̄i(t) = vi(t) - εi,t

    حيث يتم سحب εi,t بشكل عشوائي منتظم من (0,ε).
  2. إزاحة الأوزان: لكل متجه وزن w ∈ Δn-1، يتم إزاحة كل مكون بمعامل η > 0:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. غطاء KKM: لكل وكيل i، يتم تعريف المجموعة
    Ci := {w ∈ Δn-1 : يوجد توزيع Xi ∈ Oη(w) بحيث i خالٍ من الحسد تحت Xi}

إطار الخوارزمية الرئيسي

خطوط إثبات النظرية 3.1

  1. بناء التقييمات المضطربة: ضمان خصائص عدم التحلل
  2. تعريف غطاء KKM: بناء عائلة مجموعات مغلقة {Ci} تحقق شروط KKM
  3. تطبيق نظرية KKM: الحصول على التقاطع w* ∈ ∩i Ci
  4. حجة العد: إثبات أن حجم مجموعة إعادة التوزيع R لا يتجاوز n-1

الخوارزمية 1: تسلسل الاختيار الواعي للنزاع للسلع

بالنسبة لحالة السلع البحتة، تم تصميم خوارزمية قائمة على الجولات:

  • مرحلة حل النزاع: تحديد العناصر التي يفضلها عدة وكلاء بشكل متساوٍ، إضافتها إلى مجموعة إعادة التوزيع R
  • مرحلة الاختيار: الوكلاء النشطون يختارون العنصر الأفضل لديهم بترتيب معجمي

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

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

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

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

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

  1. إثبات الوجود: استخدام نظرية KKM لإثبات وجود توزيع EFR-(n-1) وباريتو أمثل
  2. تحليل الإحكام: بناء أمثلة مضادة لإثبات إحكام الحدود
  3. تعقيد الخوارزمية: تحليل التعقيد الزمني للخوارزمية

تحليل التعقيد

  • عدد الوكلاء الثابت: يمكن حساب توزيع EFR-(n-1) وباريتو أمثل في وقت m^poly(n)
  • الحالة العامة: يمكن حساب توزيع EFR-(n-1) في وقت متعدد الحدود
  • حالة السلع: يمكن حساب توزيع EFR-⌊n/2⌋ في وقت متعدد الحدود

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

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

النظرية 3.1 (نتيجة الوجود الرئيسية)

كل مثيل توزيع عادل للمن المختلط غير القابل للتقسيم بتقييمات إضافية يمتلك توزيع EFR-(n-1) وباريتو أمثل.

النظرية 4.1 (نتيجة القابلية الحسابية)

بالنسبة لمثيل توزيع المن المختلط بعدد ثابت من الوكلاء، يمكن حساب توزيع EFR-(n-1) وباريتو أمثل في وقت متعدد الحدود.

النظرية 5.1 (نتيجة EFR المستقلة)

بالنسبة لمثيل التوزيع العادل للمن المختلط بتقييمات إضافية، يوجد دائماً توزيع يكون في نفس الوقت EFR-(n-1) و EF1، ويمكن حسابه في وقت متعدد الحدود.

النظرية 5.4 (حد محسّن للسلع)

بالنسبة لمثيل التوزيع العادل للسلع البحتة، تحسب الخوارزمية 1 توزيع EFR-⌊n/2⌋ في وقت متعدد الحدود.

نتائج الإحكام

النظرية 5.2 (إحكام الأعمال المنزلية)

يوجد مثيل توزيع أعمال منزلية لا يمتلك توزيع EFR-(n-2)، مما يثبت أن الحد (n-1) محكم.

النظرية 5.5 (إحكام السلع)

يوجد مثيل توزيع سلع لا يمتلك توزيع EFR-(⌊n/2⌋-1)، مما يثبت أن الحد ⌊n/2⌋ محكم.

نتائج التعقيد الحسابي

النظرية A.1 (تعقيد مشكلة القرار)

بالنظر إلى توزيع A وعدد صحيح موجب k < n-2، فإن تحديد ما إذا كان A هو EFR-k هو NP-كامل.

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

النظرية الكلاسيكية للتوزيع العادل

  • الحالة القابلة للتقسيم: تثبت النتائج الكلاسيكية لـ Varian و Weller أن الخلو من الحسد والكفاءة يمكن تحقيقهما معاً
  • السلع غير القابلة للتقسيم: تم تطوير نظرية ناضجة لتحقيق EF1 وباريتو الأمثل معاً (تعظيم الرفاهية الاجتماعية لـ Nash)

تحديات الأعمال المنزلية والمن المختلط

  • توزيع الأعمال المنزلية: لا تزال مسألة وجود EF1+PO غير محلولة حتى لأربعة وكلاء
  • المن المختلط: لا تزال مسألة وجود EF1+PO لثلاثة وكلاء مفتوحة
  • الاختلاف المنهجي: لا توجد دالة مشابهة لرفاهية Nash الاجتماعية تضمن EF1 للأعمال المنزلية

مفاهيم الاسترخاء ذات الصلة

  • EF1: القضاء على الحسد بإزالة عنصر واحد
  • EFX: القضاء على الحسد بإزالة أي عنصر
  • التوزيع الكسري: الخلو من الحسد مع توزيع كسري لعناصر بحد أقصى (n-1)

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

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

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

القيود

  1. الحدود: حد EFR-(n-1) نسبياً كبير، حيث يتطلب إعادة توزيع حوالي عنصرين لكل وكيل في المتوسط
  2. افتراض الوكلاء الثابتين: تتطلب خوارزمية الوقت متعدد الحدود أن يكون عدد الوكلاء ثابتاً
  3. قيود التقييم الإضافي: تنطبق النتائج فقط على دوال التقييم الإضافية

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

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

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

المزايا

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

أوجه القصور

  1. قابلية عملية محدودة: قد يكون حد EFR-(n-1) كبيراً جداً في التطبيقات العملية
  2. غياب التقييم التجريبي: كورقة نظرية، تفتقر إلى تقييم الأداء على البيانات الحقيقية
  3. كفاءة الخوارزمية: قد يكون التعقيد m^poly(n) عند ثبات عدد الوكلاء مرتفعاً في الممارسة العملية

الأثر

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

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

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

المراجع

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

  • Budish (2011): إدخال مفهوم EF1
  • Caragiannis et al. (2019): العلاقة بين رفاهية Nash الاجتماعية و EF1+PO
  • Aziz et al. (2022): وجود EF1 للمن المختلط
  • Sandomirskiy & Segal-Halevi (2022): النتائج ذات الصلة بالتوزيع الكسري

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