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

अविभाज्य कार्यों का असमान एजेंटों को न्यायसंगत आवंटन

मूल जानकारी

  • पेपर ID: 2510.10698
  • शीर्षक: Fair Assignment of Indivisible Chores to Asymmetric Agents
  • लेखक: Masoud Seddighin, Saeed Seddighin
  • वर्गीकरण: cs.GT (कंप्यूटर विज्ञान - गेम थ्योरी)
  • प्रकाशन समय: 12 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.10698v1

सारांश

यह पेपर अधिकतम-न्यूनतम शेयर मूल्य (MMS) ढांचे के तहत विभिन्न अधिकारों वाले एजेंटों को अविभाज्य कार्यों के आवंटन की न्यायसंगत समस्या का अध्ययन करता है। हालांकि सममित सेटिंग में, वस्तुओं और कार्यों का स्थिरांक-MMS आवंटन/वितरण मौजूद होने की गारंटी है, लेकिन जब एजेंटों के पास विभिन्न अधिकार हों तो स्थिति अधिक जटिल हो जाती है। अविभाज्य वस्तुओं के आवंटन के लिए, n-WMMS (भारित MMS) गारंटी सर्वोत्तम साबित हुई है। हालांकि, अविभाज्य कार्यों के लिए, हाल ही में O(log n)-WMMS वितरण गारंटी की खोज की गई है। यह पेपर इस ऊपरी सीमा को स्थिरांक-WMMS गारंटी में सुधारता है, विशेष रूप से 20-WMMS वितरण के अस्तित्व को साबित करता है।

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

  1. मूल समस्या: यह पेपर असमान एजेंटों के बीच अविभाज्य कार्यों की न्यायसंगत आवंटन समस्या का अध्ययन करता है। शास्त्रीय "केक विभाजन" समस्या के विपरीत, यहाँ असतत, अविभाज्य कार्यों (chores) और विभिन्न अधिकारों वाले एजेंटों से निपटा जाता है।
  2. समस्या की महत्ता:
    • वास्तविक दुनिया में असमान अधिकारों की स्थिति बार-बार होती है, जैसे विभिन्न संस्कृतियों और धर्मों में विरासत कानून आमतौर पर असमान वितरण निर्दिष्ट करते हैं
    • प्राकृतिक संसाधनों (जैसे तेल, मत्स्य पालन) का वितरण आमतौर पर भौगोलिक, आर्थिक या राजनीतिक विचारों पर आधारित होता है
    • ये व्यावहारिक आवश्यकताएं असमान अधिकारों के तहत न्यायसंगत आवंटन के अध्ययन की महत्ता को उजागर करती हैं
  3. मौजूदा विधियों की सीमाएं:
    • सममित सेटिंग के तहत स्थिरांक सन्निकटन गारंटी विधियां सीधे लागू नहीं होती हैं, लेकिन असमान स्थिति अधिक चुनौतीपूर्ण है
    • वस्तु आवंटन के लिए, n-WMMS सर्वोत्तम गारंटी साबित हुई है
    • कार्य आवंटन के लिए, पिछला सर्वश्रेष्ठ परिणाम O(log n)-WMMS गारंटी है
  4. अनुसंधान प्रेरणा: कार्य आवंटन की सन्निकटन अनुपात को लॉगरिदमिक स्तर से स्थिरांक स्तर तक सुधारना, जो सैद्धांतिक रूप से एक बड़ी सफलता है।

मूल योगदान

  1. मुख्य सैद्धांतिक योगदान: असमान कार्य आवंटन समस्या में 20-WMMS वितरण के अस्तित्व को साबित किया, यह पहली स्थिरांक-WMMS गारंटी है
  2. एल्गोरिदम नवाचार: नई स्तरीय गतिशील चाकू एल्गोरिदम (Layered Moving Knife Algorithm) प्रस्तावित की, जो गतिशील चाकू विधि को असमान सेटिंग तक विस्तारित करती है
  3. छोटे पैमाने के मामलों का अनुकूलन: n=3 और n=4 के मामलों के लिए, log n+1 से बेहतर ऊपरी सीमाएं प्रदान की गई हैं
  4. कार्य-स्वतंत्र विश्लेषण: कार्य-स्वतंत्र विश्लेषण तकनीक विकसित की, जो छोटे पैमाने के एजेंट संख्या के तहत सीमाओं में सुधार करती है

विधि विवरण

कार्य परिभाषा

इनपुट:

  • N = {a₁, a₂, ..., aₙ}: n एजेंट
  • M = {b₁, b₂, ..., bₘ}: m कार्य
  • Vᵢ: एजेंट aᵢ का योजक लागत फलन
  • wᵢ: एजेंट aᵢ का अधिकार, जहाँ ∑wᵢ = 1

आउटपुट: कार्यों का एजेंटों को आवंटन, ताकि प्रत्येक एजेंट aᵢ को प्राप्त कार्य पैकेज Sᵢ संतुष्ट करे Vᵢ(Sᵢ) ≤ α·WMMSᵢ

मुख्य परिभाषाएं:

  • भारित अधिकतम-न्यूनतम शेयर मूल्य: WMMSᵢ = min⟨A₁,...,Aₙ⟩∈Π(M) maxⱼ∈N Vᵢ(Aⱼ)·(wᵢ/wⱼ)
  • α-WMMS वितरण: सभी एजेंटों की लागत उनके WMMS मूल्य के α गुना से अधिक नहीं है

मॉडल आर्किटेक्चर

1. पूर्व-प्रसंस्करण चरण

लेम्मा 4.1 (क्रमबद्ध कार्य सेटिंग कमी): यदि क्रमबद्ध कार्य सेटिंग में α-WMMS वितरण की गारंटी है, तो सामान्य स्थिति में भी α-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. P में प्रत्येक एजेंट aᵢ के लिए 2wᵢ/wminp प्रतियां बनाएं जो P' बनाती हैं
  3. चाकू अंतराल (ℓ,r) का उपयोग करें, अंतराल को तब तक विस्तारित करें जब तक कोई एजेंट की लागत ≤ 5wminp न हो
  4. अंतराल के भीतर सभी कार्यों को एक संतोषजनक एजेंट प्रति को आवंटित करें
  5. जब P' खाली हो, D, P, Q सेट को अपडेट करें

तकनीकी नवाचार बिंदु

  1. स्तरीय संरचना: तीन-स्तरीय एजेंट संरचना को बनाए रखकर, एल्गोरिदम की सुरक्षा और प्रभावशीलता सुनिश्चित करें
  2. प्रति तंत्र: प्रत्येक एजेंट के लिए कई प्रतियां बनाएं, विभिन्न अधिकारों के तहत आवंटन को संतुलित करें
  3. गतिशील चाकू विस्तार: शास्त्रीय गतिशील चाकू विधि को सममित से असमान सेटिंग तक विस्तारित करें
  4. क्रमिक आवंटन: कई दौरों के माध्यम से सभी एजेंटों को क्रमिक रूप से संभालें

प्रायोगिक सेटअप

सैद्धांतिक विश्लेषण सेटअप

यह पेपर मुख्य रूप से सैद्धांतिक विश्लेषण करता है, प्रायोगिक भाग केंद्रित है:

  1. छोटे पैमाने के मामलों का विश्लेषण: n=3,4 के लिए सटीक सीमा विश्लेषण
  2. अनुभवजन्य सत्यापन: 3≤n≤10 के मामलों के लिए, अधिकार सेटिंग के 10 बिलियन यादृच्छिक नमूने
  3. तुलनात्मक बेंचमार्क: पिछली log n+1 ऊपरी सीमा के साथ तुलना

मूल्यांकन मेट्रिक्स

  • सन्निकटन अनुपात: WMMS गारंटी का गुणक कारक
  • प्रयोज्यता सीमा: एल्गोरिदम लागू होने वाले एजेंट संख्या की सीमा
  • सैद्धांतिक गारंटी: सबसे खराब स्थिति में प्रदर्शन गारंटी

प्रायोगिक परिणाम

मुख्य परिणाम

सेटिंगपिछला कार्यइस पेपर का परिणाम
सामान्य nlog n+120
n=2(√3+1)/2-
n=3-≈2.1122
n=4-≈2.5404

मुख्य प्रमेय

प्रमेय 4.5: असमान कार्य आवंटन समस्या में 20-WMMS वितरण मौजूद है।

प्रमेय 5.4: 3 एजेंटों के लिए, हमेशा लगभग 2.1122-WMMS वितरण मौजूद है।

प्रमेय 5.5: 4 एजेंटों के लिए, हमेशा लगभग 2.5404-WMMS वितरण मौजूद है।

प्रायोगिक निष्कर्ष

  1. सैद्धांतिक सफलता: पहली बार ऊपरी सीमा को O(log n) से स्थिरांक तक सुधारा गया
  2. छोटे पैमाने का अनुकूलन: n≤10 के मामलों के लिए, कार्य-स्वतंत्र तकनीक बेहतर सीमाएं प्रदान करती है
  3. व्यावहारिक सीमा: स्थिरांक सीमा केवल n>2¹⁹=524288 होने पर लॉगरिदमिक सीमा से बेहतर है

संबंधित कार्य

मुख्य अनुसंधान दिशाएं

  1. शास्त्रीय न्यायसंगत विभाजन: 1948 में Steinhaus के केक विभाजन समस्या से शुरू
  2. अविभाज्य वस्तुओं का आवंटन: निरंतर संसाधनों से असतत वस्तुओं के आवंटन की ओर
  3. MMS अवधारणा: Budish द्वारा प्रस्तावित अधिकतम-न्यूनतम शेयर न्यायसंगतता के मापदंड के रूप में

इस पेपर का संबंधित कार्य से संबंध

  • Aziz et al. 4: असमान अधिकारों के तहत कार्य आवंटन का पहला अध्ययन
  • Wang et al. 27: O(log n)-WMMS ऊपरी सीमा की स्थापना
  • Huang et al. 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 et al. (2019): असमान कार्य आवंटन का अग्रणी कार्य
  3. Wang et al. (2024): पिछला सर्वश्रेष्ठ O(log n) परिणाम
  4. Huang et al. (2023): छोटे पैमाने के मामलों की सीमा विश्लेषण

समग्र मूल्यांकन: यह एक उच्च गुणवत्ता वाला सैद्धांतिक कंप्यूटर विज्ञान पेपर है, जो न्यायसंगत आवंटन क्षेत्र में एक महत्वपूर्ण सैद्धांतिक सफलता प्राप्त करता है। हालांकि व्यावहारिक अनुप्रयोग मूल्य सीमित है, लेकिन इसका सैद्धांतिक योगदान और विधि नवाचार इस क्षेत्र के विकास के लिए एक महत्वपूर्ण आधार स्थापित करते हैं। स्तरीय गतिशील चाकू एल्गोरिदम का डिजाइन लेखकों की गहरी सैद्धांतिक समझ और नवाचार क्षमता को प्रदर्शित करता है।