إجراء واحد كثير جداً: عدم قابلية التقريب للعقود التوليفية ذات الميزانية

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

• معرّف الورقة: 2511.20110
• العنوان: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
• المؤلفون: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (جامعة تل أبيب)
• التصنيف: cs.GT (نظرية الألعاب)
• وقت النشر/المؤتمر: ITCS 2026 (نسخة ما قبل الطباعة: 26 نوفمبر 2025)
• رابط الورقة: https://arxiv.org/abs/2511.20110

الملخص

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

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

1. مشكلة البحث

تدرس هذه الورقة مشكلة تصميم العقود للإجراءات التوليفية متعددة الوكلاء، والتحدي الأساسي هو: عندما يواجه الموكل (principal) قيود الميزانية، كيف يمكن تصميم عقود حافزة لجعل عدة وكلاء (agents) يختارون مجموعات إجراءات مناسبة لتحسين هدف الموكل (الربح أو المكافآت أو الرفاهية)؟

2. أهمية المشكلة

• الأهمية النظرية: نظرية العقود هي مجال أساسي في الاقتصاد الجزئي، حيث منحت جائزة نوبل للاقتصاد عام 2016 لـ Hart و Hölmstrom تأكيداً على أهميتها
• القيمة العملية: تطبيقات واسعة في الأسواق الحسابية الحديثة، مثل:
  • تحفيز فريق المهندسين في الشركات الناشئة من خلال حقوق الملكية
  • تصميم آليات مكافآت المهام في منصات التمويل الجماعي
  • تصميم العقود في الاستعانة بالعمل من الخارج

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

توجد فئتان من النتائج الإيجابية في الأدبيات:

• (i) بدون قيود الميزانية + الإجراءات التوليفية: DEFK25 يعطي تقريب عامل ثابت للدوال شبه المعيارية
• (ii) مع قيود الميزانية + الإجراءات الثنائية: FGPS25, AHT25 يعطي تقريب عامل ثابت للدوال شبه المعيارية

لكن الجمع بين الاثنين (قيود الميزانية + الإجراءات التوليفية) لم تُعرف قابليته للتقريب.

4. دافع البحث

الملاحظة الرئيسية: أحادية الاستجابة الأفضل (best-response monotonicity) في إعداد الإجراءات الثنائية تفشل في الإجراءات التوليفية. عندما يمكن للوكيل اختيار مجموعة فرعية من الإجراءات، قد يؤدي تقليل الوكلاء الآخرين لإجراءاتهم إلى تقليل هذا الوكيل لإجراءاته أيضاً، وهذه اللاأحادية هي مصدر التعقيد.

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

1. نظرية عدم القابلية للتقريب (Theorem 3.1):
   • بالنسبة لوظائف المكافآت شبه المعيارية، تحت أي ميزانية B ∈ (0,1)، لا يمكن لأي خوارزمية احتمالية متعددة الحدود (حتى مع وصول أوراكل الطلب) تقريب هدف BEST بأي عامل محدود
   • نتيجة الصعوبة مشدودة: حتى مع n-1 وكيل لديهم إجراءات ثنائية فقط، والوكيل المتبقي لديه إجراء إضافي واحد فقط
2. تقريب عامل ثابت لوظائف البديل الإجمالي (Theorem 4.1 & Corollary 4.2):
   • بالنسبة لوظائف المكافآت البديلة الإجمالية، توجد خوارزمية حتمية متعددة الحدود بتقريب O(1)
   • تتطلب فقط استعلامات القيمة (لا تحتاج إلى أوراكل الطلب)
   • تنطبق على أي ميزانية وجميع أهداف BEST
3. FPTAS للوظائف الإضافية (Theorem 5.1):
   • بالنسبة لوظائف المكافآت الإضافية، توجد FPTAS لأهداف الربح والمكافآت والرفاهية
   • هذا هو أول FPTAS في إعداد الإجراءات التوليفية متعددة الوكلاء (حتى بدون قيود الميزانية)
4. الفصل النظري:
   • أول فصل واضح بين إعدادات الميزانية وغير الميزانية في التعقيد في العقود التوليفية
   • أول فصل بين الدوال شبه المعيارية والدوال البديلة الإجمالية في قابلية التقريب للعقود ذات الميزانية

شرح الطريقة

تعريف المهمة

المثيل: ⟨A, {Ti}i∈A, f, c⟩

• A: مجموعة n من الوكلاء
• Ti: مجموعة الإجراءات المتاحة للوكيل i، يمكن للوكيل اختيار أي مجموعة فرعية Si ⊆ Ti
• f: 2^T → 0,1: دالة المكافآت، تعيين مجموعات الإجراءات إلى احتمالية النجاح
• c = {cj}j∈T: متجه تكاليف الإجراءات

العقد: α = (α1,...,αn) ∈ 0,1^n، حيث αi هي نسبة ما يتم دفعه للوكيل i عند نجاح المشروع

قيد الميزانية: ∑i∈A αi ≤ B

الهدف: إيجاد عقد α ممكن للميزانية وتوازن ناش S، لتعظيم دالة الهدف φ(α,S)، حيث φ تنتمي إلى فئة أهداف BEST:

• الربح: uP(α,S) = (1 - ∑αi)f(S)
• المكافآت: f(S)
• الرفاهية: f(S) - c(S)

بناء عدم القابلية للتقريب (Section 3)

الفكرة الأساسية

بناء عائلة معاملة من المثيلات I(A')، حيث A' ⊆ n و |A'| = n/2:

إعداد الوكلاء:

• n وكيل بإجراءات ثنائية (الإجراء i أو عدم الإجراء)
• وكيل خاص (n+1) لديه إجراءان: G ("جيد") و B ("سيء")

تصميم دالة المكافآت: f^(A')(S) = f1(S) + f2(S) - f3(S,A')، حيث:

f1(S) = max(1/2 · 1[G∈S], ε · 1[B∈S])
f2(S) = ε · min(|S\{G}|, n/2+1)
f3(S,A') = (ε/2) · 1[S = {B}∪A']

اختيار المعاملات: ε < min((1-B)/(K(n)·(n+4)), 4n/B)

الخصائص الرئيسية

1. f^(A') شبه معيارية (Lemma 3.4): من خلال التحقق من الرتابة والخاصية شبه المعيارية
2. محاكاة استعلامات الطلب باستعلامات القيمة (Lemma 3.5): أي استعلام طلب يمكن محاكاته بـ 12 استعلام قيمة
3. وجود توازن جيد (Lemma 3.6): يوجد عقد ممكن للميزانية يحفز A'∪{G}، مع مكافآت ≥ 1/2
4. توازنات أخرى ذات مكافآت منخفضة (Lemma 3.7): لأي توازن ممكن للميزانية S ≠ A'∪{G}، f(S) ≤ (n/2+2)ε

استراتيجية الإثبات

الخطوة 1: إثبات أن الحصول على تقريب جيد يتطلب حفز G

• المجموعات التي تحتوي على G: f(S) ≥ 1/2
• المجموعات التي لا تحتوي على G: f(S) ≤ (n/2+2)ε ≈ 0

الخطوة 2: إثبات أن حفز G يتطلب حفز A' بالضبط في نفس الوقت

• من خلال حد f3، تنخفض المكافآت الهامشية لـ B عندما S-{n+1} = A'
• قيد الميزانية يعني أن حفز عدد صحيح من الوكلاء فقط يمكنه حفز G

الخطوة 3: حد نظري المعلومات

• هناك (n choose n/2) = 2^Ω(n) مجموعة مرشحة A'
• استعلامات متعددة الحدود لا يمكنها تحديد A' باحتمالية غير مهملة
• استخدام مبدأ Yao: لأي توزيع موحد على A'، أي خوارزمية حتمية لها أداء متوقعة سيئة

النتائج الإيجابية لوظائف البديل الإجمالي (Section 4)

الخصائص الرئيسية: أحادية الاستجابة الأفضل

Lemma 4.3 (أحادية الاستجابة الأفضل): بالنسبة لوظائف البديل الإجمالي f، إذا كانت S توازن للعقد α، فبالنسبة لأي وكيل i و S'{-i} ⊆ S{-i}، يوجد S'_i ⊇ S_i بحيث تكون S'i أفضل استجابة لـ i لـ S'{-i}.

فكرة الإثبات:

1. تحويل مشكلة الاستجابة الأفضل إلى مشكلة حزمة الطلب
2. تعريف متجهات السعر p و q بحيث:
   • S_i هي أفضل استجابة لـ S_{-i} ⟺ S هي حزمة طلب بشأن p
   • S'i هي أفضل استجابة لـ S'{-i} ⟺ S' هي حزمة طلب بشأن q
3. بما أن S'{-i} ⊆ S{-i}، لدينا p ≤ q (على مستوى الإحداثيات)
4. تطبيق خاصية البديل الإجمالي: يوجد حزمة طلب S' ⊇ S و S'{-i} = S'{-i}

Lemma تقليل الأبعاد (Lemma 4.5)

بالنظر إلى (α,S) ∈ C(B) والمعامل M ≥ 3، يمكن إيجاد (α',S') ∈ C(B) في وقت متعدد الحدود بحيث:

• f(S') ≥ f(S)/(2M-2)
• ∑α'_i ≤ (5/M)∑αi أو يوجد i بحيث α' = α|_i

الخوارزمية (Algorithm 2):

1. تحديد مجموعة الوكلاء ذوي الدفع العالي Z = {i: αi > p/M}
2. إذا ساهم بعض i∈Z بشكل كبير بمفرده، أرجع عقد وكيل واحد
3. بخلاف ذلك، قسّم الوكلاء المتبقين إلى مجموعات، كل مجموعة بإجمالي دفع ≤ p/M
4. ابحث عن مجموعة U بمكافآت كافية
5. طبّق Lemma المضاعفة (Lemma 2.2) لبناء عقد جديد

نظرية التكافؤ (Theorem 4.1)

Lemma التحليل (Lemma 4.8):

Max-φ(B) ≤ 2·Max-Reward-Bounded(B) + max_i Best-Single_i-φ(B)

سلسلة الاختزال:

1. Max-φ(B) → Max-Reward-Bounded(B) (Lemma 4.10)
2. Max-Reward-Bounded(B) → Max-φ(B') (Lemma 4.11)
3. مشاكل الوكيل الواحد يمكن حلها بدقة (Lemma 4.9)

FPTAS للوظائف الإضافية (Section 5)

طريقة البرمجة الديناميكية

التقسيم:

• اضبط δ = ε/|T|
• عرّف f̃(S) = ∑_{a∈S} ⌊f({a})/(δb)⌋(δb)

تعريف جدول DP:

A^(φ)(j,x) = min_{S,α} {∑αi | f̃(S) ≥ x, S ∈ NE(α), S ⊆ T1∪...∪Tj}

الملاحظة الرئيسية (الوظائف الإضافية):

• أفضل استجابة للوكيل i هي بادئة: تتضمن جميع الإجراءات التي تحقق c_a ≤ αi·f({a})
• انتقال DP: A^(φ)(j,x) = min_{ℓ} {A(j-1, x-f̃({a1,...,aℓ})) + c_{aℓ}/f({aℓ})}

ضمان التقريب:

f̃(S*) ≥ (1-ε)f(S*)

لذلك العقد المُرجع يحقق تقريب (1-ε).

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

هذه ورقة نظرية بحتة ولا تتضمن جزء تجريبي. جميع النتائج هي إثباتات رياضية.

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

1. الإثباتات البنائية: إثبات عدم القابلية للتقريب من خلال بناء مثيلات صعبة بشكل صريح
2. تصميم الخوارزميات: توفير خوارزميات محددة (Algorithm 1, 2) وإثبات ضمانات الأداء
3. تحليل التعقيد: تحليل التعقيد الزمني وتعقيد الاستعلام للخوارزميات

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

غير قابل للتطبيق (عمل نظري بحت)

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

1. العقود التوليفية (Combinatorial Contracts)

نموذج الإجراءات الثنائية:

• BFN06a, BFNW12: تقديم نموذج الوكلاء التوليفيين
• DEFK23: تقريب عامل ثابت لوظائف XOS
• FGPS25, AHT25: الإجراءات الثنائية تحت قيود الميزانية

نموذج الإجراءات التوليفية:

• DEFK21: إجراءات توليفية لوكيل واحد، وظائف البديل الإجمالي قابلة للمعالجة
• DEFK25: إجراءات توليفية متعددة الوكلاء، تقريب O(1) للوظائف شبه المعيارية (بدون ميزانية)

2. العقود الخطية (Linear Contracts)

• Car15: متانة العقود الخطية
• DRT19: ضمانات التقريب للعقود الخطية
• DFPS24: إثبات الغموض

3. العقود تحت قيود الميزانية

• HG24: قيود الميزانية للمهام المستقلة
• DASSTC25: قيود ميزانية الوكلاء
• FGPS25: تكافؤ أهداف BEST

4. الميزة النسبية لهذه الورقة

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

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

1. عقبة ثلاثية الأبعاد: عدم القابلية للتقريب يظهر فقط عندما تكون ثلاث خصائص موجودة في نفس الوقت:
   • وظائف مكافآت شبه معيارية
   • قيود الميزانية
   • الإجراءات التوليفية أي مزيج من خاصيتين يسمح بتقريب عامل ثابت (Figure 1)
2. حد البديل الإجمالي: خاصية البديل الإجمالي هي حد قابل للمعالجة للعقود التوليفية ذات الميزانية
3. خصوصية الوظائف الإضافية: يوجد مخطط تقريب متعدد الحدود الكامل

القيود

1. إحكام عدم القابلية للتقريب:
   • يتطلب فقط n-1 وكيل بإجراءات ثنائية + وكيل واحد بـ 3 إجراءات
   • لكن البناء مصطنع للغاية، قد لا يكون شائعاً في التطبيقات العملية
2. افتراض البديل الإجمالي:
   • افتراض أقوى من شبه المعياري
   • قد لا تحقق العديد من التطبيقات العملية
3. قيود أهداف BEST:
   • FPTAS ينطبق فقط على أهداف الربح والمكافآت والرفاهية
   • لا ينطبق على جميع أهداف BEST
4. ميزانية واحدة:
   • يعتبر فقط قيد الميزانية الإجمالية
   • لا يعتبر قيود الميزانية الفردية

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

1. التعقيد الحسابي:
   • هل توجد PTAS/FPTAS تحت وظائف البديل الإجمالي؟
   • التعقيد الدقيق لمشاكل الوكيل الواحد
2. نماذج أكثر ثراءً:
   • إعدادات متعددة المشاريع ACC+25
   • قيود العدالة CCL25b
   • المعلومات الخاصة ADT21
3. منظور التعلم:
   • تصميم العقود عبر الإنترنت ZBY+23
   • تعقيد العينة DFPS25
4. البحث التجريبي:
   • خصائص فئة الوظائف في التطبيقات الفعلية
   • أداء الخوارزميات الاستكشافية

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

المميزات

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

أوجه القصور

1. الاعتبارات العملية:
   • بناء الصعوبة مصطنع للغاية
   • لم يتم مناقشة قابلية تطبيق افتراض البديل الإجمالي في الممارسة
   • غياب تحليل حالات التطبيق الفعلي
2. القيود التقنية:
   • FPTAS ينطبق فقط على جزء من أهداف BEST
   • لم تُعطَ الثوابت المحددة لتقريب العامل الثابت
   • FPTAS لوكيل واحد يتطلب أوراكل الطلب
3. الفراغات النظرية:
   • فئات وسيطة بين البديل الإجمالي وشبه المعياري؟
   • تعقيد قيود الميزانية الفردية
   • احتمالية العقود العشوائية
4. تعقيد الإثبات:
   • بعض الإثباتات تقنية للغاية (مثل Lemma 3.7)
   • محاكاة أوراكل الطلب ليست حدسية بما يكفي

التأثير

المساهمات النظرية:

• أول فصل واضح بين إعدادات الميزانية وغير الميزانية
• تحديد البديل الإجمالي كحد قابل للمعالجة
• توفير معيار للبحث اللاحق

القيمة المنهجية:

• إطار عمل تحليل أحادية الاستجابة الأفضل
• نمط تصميم Lemma تقليل الأبعاد
• تقنيات بناء الصعوبة

القيمة العملية:

• توجيه ممارسة تصميم العقود: تحديد الحالات القابلة للمعالجة
• تحذير من مخاطر تبسيط النماذج
• توفير حدود نظرية لتصميم خوارزميات التقريب

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

مناسب للتطبيق:

1. سيناريوهات البديل الإجمالي:
   • فريق بمهارات متكاملة (تخصصات مختلفة)
   • مشاكل تخصيص الموارد
   • تصميم السوق
2. سيناريوهات إضافية:
   • التمويل الجماعي للمهام المستقلة
   • آليات حافزة بسيطة

غير مناسب للتطبيق:

1. مهام بتكامل قوي (ينتهك البديل الإجمالي)
2. حالات بدون قيود ميزانية (توجد خوارزميات أفضل)
3. السيناريوهات التي تتطلب حلاً دقيقاً

المراجع الرئيسية

1. DEFK25 Dütting et al., "Multi-agent combinatorial contracts", SODA 2025
   • العمل الذي تمدده هذه الورقة مباشرة
2. FGPS25 Feldman et al., "Budget-feasible contracts", EC 2025
   • العقود ذات الميزانية تحت الإجراءات الثنائية
3. DEFK21 Dütting et al., "Combinatorial contracts", FOCS 2021
   • الأساس للإجراءات التوليفية لوكيل واحد
4. Car15 Carroll, "Robustness and linear contracts", AER 2015
   • الأساس النظري للعقود الخطية
5. Pae17 Paes Leme, "Gross substitutability: An algorithmic survey", GEB 2017
   • مسح شامل لخاصية البديل الإجمالي

الملخص

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