2025-11-26T10:31:18.658822

One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

Feldman, Gal-Tzur, Ponitka et al.
We study multi-agent contract design with combinatorial actions, under budget constraints, and for a broad class of objective functions, including profit (principal's utility), reward, and welfare. Our first result is a strong impossibility: For submodular reward functions, no randomized poly-time algorithm can approximate the optimal budget-feasible value within \textit{any finite factor}, even with demand-oracle access. This result rules out extending known constant-factor guarantees from either (i) unbudgeted settings with combinatorial actions or (ii) budgeted settings with binary actions, to their combination. The hardness is tight: It holds even when all but one agent have binary actions and the remaining agent has just one additional action. On the positive side, we show that gross substitutes rewards (a well-studied strict subclass of submodular functions) admit a deterministic poly-time $O(1)$-approximation, using only value queries. Our results thus draw the first sharp separation between budgeted and unbudgeted settings in combinatorial contracts, and identifies gross substitutes as a tractable frontier for budgeted combinatorial contracts. Finally, we present an FPTAS for additive rewards, demonstrating that arbitrary approximation is tractable under any budget. This constitutes the first FPTAS for the multi-agent combinatorial-actions setting, even in the absence of budget constraints.
academic

एक क्रिया बहुत अधिक: बजटीय संयोजक अनुबंधों की अनुमानितता

मूल जानकारी

  • पेपर ID: 2511.20110
  • शीर्षक: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
  • लेखक: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (Tel Aviv University)
  • वर्गीकरण: cs.GT (खेल सिद्धांत)
  • प्रकाशन समय/सम्मेलन: ITCS 2026 (पूर्वमुद्रण संस्करण: 26 नवंबर 2025)
  • पेपर लिंक: https://arxiv.org/abs/2511.20110

सारांश

यह पेपर बजट बाधा के साथ बहु-एजेंट संयोजक क्रिया अनुबंध डिजाइन समस्या का अध्ययन करता है, जिसमें लाभ, पुरस्कार और कल्याण सहित व्यापक उद्देश्य कार्य शामिल हैं। मुख्य परिणाम हैं: (1) मजबूत अनुमानितता: सबमॉड्यूलर पुरस्कार कार्यों के लिए, यहां तक कि मांग ओरेकल पहुंच के साथ, कोई भी यादृच्छिक बहुपद समय एल्गोरिदम किसी भी परिमित कारक के भीतर इष्टतम बजट-व्यवहार्य मान को अनुमानित नहीं कर सकता; (2) सकारात्मक परिणाम: सकल विकल्प (gross substitutes) पुरस्कार कार्यों के लिए (सबमॉड्यूलर कार्यों का सख्त उपवर्ग), एक निर्धारक बहुपद समय O(1)-अनुमान एल्गोरिदम मौजूद है, जिसे केवल मूल्य प्रश्नों की आवश्यकता है; (3) FPTAS: योगात्मक पुरस्कार कार्यों के लिए, किसी भी बजट के तहत FPTAS मौजूद है, जो बहु-एजेंट संयोजक क्रिया सेटिंग में पहला FPTAS भी है। यह अनुसंधान पहली बार बजट बाधा और गैर-बजट बाधा सेटिंग को स्पष्ट रूप से अलग करता है और सकल विकल्प संपत्ति को व्यवहार्य सीमा के रूप में निर्धारित करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

1. अनुसंधान समस्या

यह पेपर बहु-एजेंट संयोजक क्रिया अनुबंध डिजाइन समस्या का अध्ययन करता है, मुख्य चुनौती यह है: जब प्रमुख (principal) को बजट बाधा का सामना करना पड़ता है, तो कई एजेंटों को उपयुक्त क्रिया संयोजन चुनने के लिए प्रेरित करने के लिए प्रोत्साहन अनुबंध कैसे डिजाइन करें, ताकि प्रमुख के उद्देश्य (लाभ, पुरस्कार या कल्याण) को अनुकूलित किया जा सके।

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 एजेंटों के पास केवल बाइनरी क्रिया है, शेष 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 या कोई क्रिया नहीं)
  • 1 विशेष एजेंट (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' होने पर कम हो जाती है
  • बजट बाधा यह सुनिश्चित करती है कि केवल सही n/2 एजेंटों को प्रेरित करके ही G को प्रेरित किया जा सकता है

चरण 3: सूचना-सैद्धांतिक निचली सीमा

  • उम्मीदवार समुच्चय A' के (n choose n/2) = 2^Ω(n) विकल्प हैं
  • बहुपद संख्या में प्रश्न गैर-नगण्य संभावना के साथ 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 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 2.2) लागू करें

समतुल्यता प्रमेय (Theorem 4.1)

अपघटन लेम्मा (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. इस पेपर का सापेक्ष लाभ

आयामसंबंधित कार्ययह पेपर
क्रिया स्थानबाइनरी FGPS25संयोजक
बजट बाधानहीं DEFK25हाँ
कार्य वर्गसबमॉड्यूलरसबमॉड्यूलर/सकल विकल्प को अलग करता है
परिणाम प्रकारसकारात्मकसकारात्मक और नकारात्मक दोनों

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. त्रि-आयामी बाधा: अनुमानितता केवल तीन गुणों के एक साथ होने पर दिखाई देती है:
    • सबमॉड्यूलर पुरस्कार कार्य
    • बजट बाधा
    • संयोजक क्रिया किसी भी दो गुणों का संयोजन स्थिर कारक अनुमान की अनुमति देता है (Figure 1)
  2. सकल विकल्प सीमा: सकल विकल्प संपत्ति बजट संयोजक अनुबंधों की व्यवहार्य सीमा है
  3. योगात्मक कार्य विशेषता: पूर्ण बहुपद समय अनुमान योजना मौजूद है

सीमाएं

  1. अनुमानितता की कसाई:
    • केवल n-1 बाइनरी एजेंट + 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)
    • मांग ओरेकल अनुकरण की आवश्यकता पर्याप्त सहज नहीं है

प्रभाव

सैद्धांतिक योगदान:

  • पहली बार बजट/गैर-बजट सेटिंग को स्पष्ट रूप से अलग करता है
  • सकल विकल्प को व्यवहार्य सीमा के रूप में स्थापित करता है
  • बाद के अनुसंधान के लिए बेंचमार्क प्रदान करता है

पद्धति मूल्य:

  • सर्वश्रेष्ठ प्रतिक्रिया एकरसता विश्लेषण ढांचा
  • आयाम-कमी लेम्मा की डिजाइन पैटर्न
  • कठोरता निर्माण तकनीक

व्यावहारिक मूल्य:

  • अनुबंध डिजाइन अभ्यास को निर्देशित करता है: व्यवहार्य मामलों की पहचान करता है
  • मॉडल को अत्यधिक सरल बनाने के जोखिम के बारे में चेतावनी देता है
  • अनुमान एल्गोरिदम डिजाइन के लिए सैद्धांतिक सीमा प्रदान करता है

लागू परिदृश्य

लागू करने के लिए उपयुक्त:

  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
    • सकल विकल्प संपत्ति सर्वेक्षण

सारांश

यह एक सैद्धांतिक गहराई उत्कृष्ट खेल सिद्धांत पेपर है, जो बजट बाधा संयोजक अनुबंधों की जटिलता सीमा को सटीक रूप से लक्षण वर्णित करके महत्वपूर्ण सैद्धांतिक योगदान देता है। पेपर का मुख्य अंतर्दृष्टि सर्वश्रेष्ठ प्रतिक्रिया गैर-एकरसता को जटिलता के स्रोत के रूप में है, और तंग कठोरता निर्माण और मिलान सकारात्मक एल्गोरिदम के माध्यम से समस्या को पूरी तरह से लक्षण वर्णित करता है। सकल विकल्प संपत्ति को बजट संयोजक अनुबंधों की व्यवहार्य सीमा के रूप में स्थापित किया जाता है, यह खोज बाद के अनुसंधान के लिए महत्वपूर्ण है। अनुभवजन्य अनुसंधान की कमी के बावजूद, इसका सैद्धांतिक मूल्य और पद्धति योगदान इसे एल्गोरिदमिक अनुबंध सिद्धांत क्षेत्र में एक महत्वपूर्ण कार्य बनाता है।