تتقصى هذه الورقة البحثية التخصيص العادل للسلع غير القابلة للتجزئة حيث يمكن للوكلاء اختيار بيع العناصر بأسعار السوق، مع تكييف مفاهيم العدالة القياسية مثل MMS وEFX لتناسب هذا الإطار الهجين، وإرساء ضمانات الوجود وحدود التقريب للتخصيصات التي توازن بين توزيع السلع والعائدات.
تعد التقسيم العادل مجالاً في الرياضيات والاقتصاد مخصصاً لحل مشكلة قديمة قدم التعاون البشري: كيف يتم تقسيم الموارد بحيث يشعر الجميع أنهم حصلوا على حصة عادلة. لعقود من الزمن، درس الباحثون كيفية تقسيم الأشياء التي لا يمكن قطعها، مثل منزل أو سيارة أو مجموعة من الكتب النادرة. في هذه السيناريوهات، يتمثل الهدف في إيجاد ترتيب لا يشعر فيه أي شخص بالحسد تجاه ما حصل عليه شخص آخر، أو حيث يُضمن لكل فرد حد أدنى من الرضا بناءً على تفضيلاته الشخصية. ومع ذلك، تفترض هذه النماذج الكلاسيكية أن العناصر المعنية ثابتة في شكلها الحالي، وهي تتجاهل خياراً شائعاً جداً في العالم الحقيقي: القدرة على بيع عنصر مقابل نقد. ففي حالات الطلاق، على سبيل المثال، قد يقرر الزوجان أن بيع منزل الأسرة وتقسيم المال هو حل أفضل من احتفاظ أحد الطرفين بالمنزل وحصول الآخر على لا شيء. هذا الخيار البسيط المتمثل في البيع يغير المشهد الكامل لما هو ممكن، ولكنه يفرض أيضاً تعقيدات جديدة لم تعالجها النظريات السابقة.
لقد خطى أورييل فيجي ويوتام غافني من معهد ويزمان للعلوم هذه الخطوة لسد هذه الفجوة، وذلك باستكشاف ما يحدث عندما يمكن للوكلاء اختيار بيع السلع بأسعار السوق قبل تقسيم العناصر المتبقية والنقد الناتج عنها. يتساءل عملهما سؤالاً جوهرياً: إذا كان بإمكان الناس بيع العناصر، فهل يصبح من الأسهل أم الأصعب ضمان نتيجة عادلة؟ لقد وجدا أنه بينما يفتح البيع آفاقاً أكثر، فإنه يجعل من الصعب في الواقع ضمان أنواع معينة من العدالة مقارنة بالإطار التقليدي الذي يكون فيه البيع محظوراً. طور الباحثان طرقاً جديدة لقياس العدالة تأخذ في الاعتبار كلاً من قيمة العناصر التي يحتفظ بها الأشخاص والمال الذي يتلقونه من المبيعات. وقد أثبتا أنه بالنسبة لشخصين، من الممكن دائماً إيجاد تقسيم يستوفي أقوى معايير العدالة الممكنة، مما يضمن عدم حسد أي شخص لحزمة الآخر حتى بعد مراعاة خيار البيع. ومع ذلك، مع زيادة عدد الأشخاص، تصبح الضمانات أضعف قليلاً. فبالنسبة لثلاثة أشخاص، أظهرا أنه من المستحيل ضمان حصول الجميع على أقصى حصة عادلة ممكنة لهم؛ وفي بعض الحالات، فإن أفضل ما يمكن لأي شخص أن يأمله هو جزء محدد من تلك الحصة المثالية.
كما استقصى الباحثان مدى إمكانية تقريب هذه الحصص العادلة للمجموعات الأكبر. وأثبتا أنه لأي عدد من الأشخاص، توجد دائماً طريقة لتقسيم السلع والمال بحيث يحصل كل فرد على ثلثي الحد الأددد الأدنى المضمون له على الأقل. وهذه نتيجة مهمة لأنها تظهر أنه حتى مع تعقيد البيع المضاف، لا يزال من الممكن تحقيق مستوى عالٍ جداً من العدالة. علاوة على ذلك، وجدا أنه من الممكن الجمع بين هذه العدالة القائمة على الحصة وبين الشعور القوي بخلو النفس من الحسد، مما يعني أن لا أحد يفضل استبدال حزمته الكاملة من السلع والنقد بحزمة شخص آخر. وقد حققا ذلك من خلال تكييف خوارزمية تُعرف باسم طريقة "المقسم المنفرد" (Lone Divider)، والتي تتضمن اقتراح شخص ما لتقسيم، ثم يختار الآخرون أجزاءهم المفضلة. وفي الإطار الجديد المرتبط بالبيع، كان عليهما تعديل هذا النهج بعناية، وضمان اختيار الشخص الذي يقترح التقسيم بحكمة وهيكلة الحزم بطريقة محددة لمنع بيع العناصر من الإضرار بشكل غير عادل بالمشاركين الآخرين.
أحد النتائج الأكثر لفتاً للنظر في الورقة البحثية هو الفرق بين الإطار الذي يتضمن البيع والإطار الذي لا يتضمنه. فقد صاغ المؤلفان مثالاً محدداً يتضمن ثلاثة أشخاص وثمانية عناصر حيث، إذا كان البيع مسموحاً به، سيكون من المستحيل ضمان حصول الجميع على أكثر من أحد عشر جزءاً من اثني عشر جزءاً من حصتهم المثالية. وفي الإطار التقليدي حيث لا يمكن بيع العناصر، يكون أفضل حد معروف لهذا السيناريو نفسه أعلى بكثير، مما يعني أن القدرة على البيع تخلق في الواقع فجوة أوسع بين ما هو ممكن نظرياً وما يمكن ضمانه في الممارسة العملية. تشير هذه النتيجة المنافية للحدس إلى أنه بينما يوفر البيع المرونة، فإنه يفرض أيضاً نوعاً جديداً من المخاطر حيث قد تُباع عناصر عالية القيمة بسعر منخفض، مما يترك العناصر المتبقية غير كافية لتلبية احتياجات الجميع. كما استكشف الباحثون سيناريو ذا صلة يتعلق بالأعمال المنزلية أو المهام التي يكرهها الناس، حيث يلعب خيار الاستعانة بمصادر خارجية للعمل مقابل رسوم نفس دور بيع السلع. ووجدوا أنماطاً مماثلة، مظهرين أن القدرة على دفع مبلغ لشخص آخر للقيام بمهمة ما تجعل من الصعب ضمان توزيع عادل تماماً للعمل المتبقي.
كما تتناول الورقة الجانب العملي لهذه البراهين الرياضية، متسائلة عما إذا كان يمكن للحاسوب حساب هذه التخصيصات العادلة بكفاءة. أظهر المؤلفون أنه في الحالة الخاصة لشخصين، يمكن العثور على تقسيم عادل في وقت معقول. وبالنسبة للمجموعات الأكبر، طوروا خوارزميات يمكنها الاقتراب من الحصة العادلة المثالية بشكل تعسفي، مما يعني أنه مع قدرة حوسبية كافية، يمكن للمرء إيجاد حل يكاد يكون في أفضل حالاته النظرية. كما أثبتا أن نوعاً معيناً من ضمان العدالة، القائم على الحصة النسبية المقتطعة، يمكن حسابه بسرعة ودمجه مع شروط خلو النفس من الحسد. يوفر هذا العمل إطاراً قولاً لفهم كيفية تفاعل الأسواق والتفضيلات الشخصية في مشكلات التقسيم العادل، ويقدم أدوات جديدة لمواقف تتراوح من تسويات الطلاق إلى تقسيم الأصول الموروثة. ومن خلال التعريف الدقيق لما هو ممكن عندما يكون البيع خياراً متاحاً، أوضح الباحثون حدود العدالة في عالم يمكن فيه تحويل الموارد إلى مال، مما يضمن معرفة الضمانات التي يمكننا الاعتماد عليها بدقة عندما تكون المخاطر عالية.
ملخص تقني: التخصيص العادل مع خيار البيع الاختياري
تعريف المشكلة
تتناول هذه الورقة مشكلة التخصيص العادل للسلع غير القابلة للتجزئة في سياق يمتلك فيه الوكلاء دوال تقييم ذاتية للسلع، ولكن هذه السلع تمتلك أيضاً أسعار سوق خارجية. على خلاف نماذج التقسيم العادل التقليدية حيث تكون السلع غير قابلة للتجزئة بشكل صارم، يقدم هذا السياق "خياراً خارجياً": يمكن للوكلاء اختيار بيع السلع بأسعار السوق الخاصة بها. وتكون عوائد هذه المبيعات قابلة للتجزئة ولها قيمة مضافة موحدة لجميع الوكلاء.
يكمن التحدي الجوهري في تصميم آلية تخصيص تقرر في آن واحد:
أي مجموعة فرعية من السلعة يجب بيعها.
كيفية تخصيص السلع المتبقية غير المباعة.
كيفية توزيع العوائد النقدية من السلع المباعة.
الهدف هو تلبية مفاهيم العدالة التي تكيف الضمانات القياسية القائمة على الحصص (share-based) والضمانات القائمة على الحسد (envy-based) لتناسب هذه البيئة الهجينة. يفترض المؤلفون وجود تقييمات جمعية (additive) لكل من السلع والمال.
مفاهيم العدالة
تكيف الورقة فئتين من تعريفات العدالة:
المفاهيم القائمة على الحصة (Share-Based Notions):
الحصة القصوى (Maximin Share - MMS): تُعرف بأنها القيمة القصوى التي يمكن للوكيل أن يضمنها لنفسه عن طريق اتخاذ القرار الأمثل بشأن أي السلع سيبيع، ثم تقسيم السلع المتبقية والعوائد إلى n من الحزم، بحيث يحصل على الحزمة الأقل قيمة. وخلافاً لـ MMS القياسي، يقوم الوكيل بتحسين كل من قرار البيع والتقسيم.
الحصة النسبية المبتورة (Truncated Proportional Share - TPS): هي امتداد لمفهوم TPS من سياقات السلع غير القابلة للتجزئة، وتُعرف بأنها أكبر قيمة t بحيث يكون مجموع max{p(g),min{v(g),t}} لكل سلعة، مقسوماً على n، يساوي t.
المفاهيم القائمة على الحسد (Envy-Based Notions):
SEF1 و SEFX (الخلو من الحسد القابل للبيع - Strong/Sellable Envy-Free): هذه هي تعديلات على EF1 و EFX. يكون التخصيص SEFX إذا كان أي وكيل i لا يحسد حزمة الوكيل j حتى لو قام j ببيع إحدى سلعهم (وتلقي سعر السوق) بدلاً من الاحتفاظ بها. رسمياً، vˉi(Ai)+Pi≥vˉi(Aj∖{g})+p(g) لكل سلعة g∈Aj، حيث vˉi(g)=max{vi(g),p(g)}.
المنهجية والخوارزميات
يستخدم المؤلفون مجموعة متنوعة من التقنيات الخوارزمية، بما في ذلك تنويعات من نماذج "القطع والاختيار" (Cut & Choose)، و"ملء الحقيبة" (Bag-Filling)، و"المقسم الوحيد" (Lone Divider)، والتي تم تعديلها للتعامل مع التعقيد الناتج عن البيع الاختياري.
القطع والإعطاء (n=2): بالنسبة لوكيلين، يقدم المؤلفون بروتوكول "القطع والإعطاء" (Cut & Give). يقترح أحد الوكلاء (القاطع - Cutter) تقسيماً بناءً على الـ MMS الخاص به. إذا وجد الوكيل الآخر (المعطي - Giver) الحزمة مقبولة، فإنه يأخذها. إذا لم يكن الأمر كذلك، يقوم المعطي بتعديل التقسيم عن طريق بيع سلعة من مقاصده وإلغاء عملية بيع القاطع، مما يخلق حزمة جديدة تحقق كلاً من MMS و SEFX.
ملء الحقيبة مع السلع الافتراضية (TPS): لتحقيق n/(2n−1)-TPS، تستخدم الخوارزمية نهج "السكين المتحركة". يتم بيع السلع ذات أسعار السوق المرتفعة فوراً لتلبية الحد الأدنى من متطلبات حصص الوكلاء. وتُعامل العوائد المتبقية كـ "سلع افتراضية". ثم تقوم إجراءات ملء الحقيبة بتخصيص الحزم حتى يصل الوكيل إلى القيمة المطلوبة.
التقسيمات القانونية (Lone Divider لـ MMS): بالنسبة لـ n عامة، يكيف المؤلفون طريقة "المقسم الوحيد". ويتمثل الابتكار الرئيسي في بناء "تقسيمات قانونية" يقترحها الوكيل صاحب أعلى MMS. تتكون هذه التقسيمات من "حزم نقية" (بدون مال)، و"حزم فردية" (سلعة واحدة بالإضافة إلى عوائد من سلعة واحدة أخرى مباعة على الأكثر)، وحزمة واحدة من "المتبقيات". هذا الهيكل يحد من الخسارة المحتملة التي قد يتكبدها الوكيل إذا تم تخصيص حزمة رفضها لشخص آخر، وتحديداً عبر الحد من الخسارة الناجمة عن البيع القسري.
التعامل مع العناصر عالية القيمة: تتضمن الخوارزميات مراحل أولية للتعامل مع السلع التي تتجاوز قيمتها بشكل كبير عتبة MMS، إما ببيعها لتلبية احتياجات وكلاء محددين أو تخصيصها مباشرة، مما يضمن ملاءمة المشكلة المتبقية لإطار التقريب.
النتائج الرئيسية
1. ضمانات الحصة والحسد المشتركة
وكيلان (n=2): يوجد دائماً تخصيص يحقق في آن واحد MMS و SEFX. هذه نتيجة قوية، حيث إن تحقيق MMS كامل مستحيل عموماً لـ n≥3 في الإعدادات القياسية، وهنا يتم تحقيقه جنباً إلى جنب مع مفهوم قوي للخلو من الحسد.
وكلاء عامون (n≥2): يوجد تخصيص يحقق في آن واحد n/(2n−1)-TPS و SEFX. وقد ثبت أن النسبة n/(2n−1) هي أفضل تقريب ممكن لـ TPS حتى بدون شرط SEFX.
2. حدود تقريب MMS
ثلاثة وكلاء (n=3): تحدد الورقة فجوة كمية بين الإعدادات مع وبدون البيع. بينما يتم ضمان MMS كامل لـ n=3 مع m=8 من العناصر في الإعداد القياسي للسلع غير القابلة للتجزيم (حيث كان أفضل حد معروف بدون البيع هو 39/40)، فإنه في إعداد البيع، توجد حالات لا يضمن فيها أي تخصيص أكثر من 11/12-MMS.
وكلاء عامون (n≥4): يقدم المؤلفون تخصيص 2/3-MMS. وهذا يطابق أفضل نسبة تقريب معروفة لإعداد MMS في حالة السلع غير القابلة للتجزئة (بدون حد الـ O(1/n) المضاف الموجود في بعض الأعمال السابقة).
حالة خاصة (n=3): من خلال دمج نهج n العام مع خوارزمية الـ MMS الكامل لـ n=2، يحقق المؤلفون تخصيص 3/4-MMS لثلاثة وكلاء.
3. التعقيد الحسابي
حساب MMS: حساب قيمة MMS الدقيقة هو مسألة صعبة (weakly NP-hard) لـ n=2 وصعبة بقوة (strongly NP-hard) لـ n عامة. ومع ذلك، تقدم الورقة:
خوارزمية ذات وقت شبه متعدد الحدود (pseudo-polynomial time) لـ n ثابتة.
مخطط تقريب في وقت متعدد الحدود (PTAS) لحساب قيم وتقسيمات MMS.
حساب TPS: يمكن حساب TPS بكفاءة في وقت متعدد الحدود.
الضمانات المشتركة: يوجد FPTAS لتخصيصات تكون n/(2n−1)-TPS و ϵ-SEFX.
4. التوسعات
تساوي العوائد: تحلل الورقة إعداداً مقيداً حيث يجب توزيع عوائد البيع بالتساوي بين جميع الوكلاء. في هذه الحالة، تنخفض ضمانة التقريب إلى 1/n-TPS، ويمكن أن تكون ضمانة MMS أضعف بكثير من الحالة غير المقيدة.
الأعباء (Chores) مع التعهيد من الخارج: يتم توسيع النموذج ليشمل الأعباء (قيم سالبة) حيث يمكن للوكلاء "التعهيد من الخارج" للمهام بتكلفة سوقية. تعكس النتائج نتائج إعداد السلع: يمكن تحقيق تقريب 2-MMS، لكن فجوة التقريب أوسع مما هي عليه في إعداد الأعباء القياسي للسلع غير القابلة للتجزئة.
الأهمية والادعاءات
تدعي الورقة تقديم إطار عمل "أفضل ما في العالمين" للتقسيم العادل عندما تكون خيارات السوق متاحة. وتتمثل مساهماتها الرئيسية في:
تحديد الفجوة النظرية: توضح أن إدخال خيارات البيع، رغم أنه يوسع مجموعة النتائج الممكنة، يمكن أن يجعل تقريب ضمانات معينة للعدالة (تحديداً MMS لـ n=3) أصعب بشكل متناقض مقارنة بإعداد السلع غير القابلة للتجزئة الصرف.
خوارزميات قوية: تطور تقنيات خوارزمية مبتكرة (التقسيمات القانونية، والمقسم الوحيد المعدل) التي تنجح في استعادة أفضل نسب التقريب المعروفة لـ MMS في وجود البيع، رغم التعقيد المضاف المتمثل في تحسين قرارات البيع.
عدالة موحدة: تنجح في دمج الضمانات القائمة على الحصة (MMS/TPS) مع مفاهيم قوية للخلو من الحسد (SEFX) في تخصيص واحد، مما يظهر أن تقريبات الحصة عالية الجودة لا تمنع بالضرورة الخلو من الحسد القوي في هذا السياكن.
يؤكد المؤلفون أن نتائجهم دقيقة في عدة حالات (مثل حد n/(2n−1) لـ TPS)، وأن النتائج السلبية (مثل فجوة 11/12 لـ n=3) هي قيود مثبتة للنموذج، وليست مجرد نتاج لمحدودية الخوارزميات الحالية.