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

अविभाज्य मिश्रित मन्ना का न्यायसंगत और कुशल आवंटन

मूल जानकारी

  • पेपर ID: 2507.03946
  • शीर्षक: अविभाज्य मिश्रित मन्ना का न्यायसंगत और कुशल आवंटन
  • लेखक: सिद्धार्थ बरमन (भारतीय विज्ञान संस्थान), विश्व प्रकाश HV (चेन्नई गणितीय संस्थान), अदिति सेठिया (भारतीय विज्ञान संस्थान), मशबत सुजुकी (UNSW सिडनी)
  • वर्गीकरण: cs.GT (कंप्यूटर विज्ञान - गेम सिद्धांत)
  • प्रकाशन समय: 15 अक्टूबर 2025 (arXiv प्रीप्रिंट संस्करण 2)
  • पेपर लिंक: https://arxiv.org/abs/2507.03946v2

सारांश

यह पेपर योगात्मक मूल्यांकन वाले एजेंटों के बीच अविभाज्य मिश्रित मन्ना (मिश्रित मन्ना) के न्यायसंगत आवंटन की समस्या का अध्ययन करता है। मिश्रित मन्ना उन वस्तुओं को संदर्भित करता है जिनका मूल्य सकारात्मक, नकारात्मक या शून्य हो सकता है। पेपर न्यायसंगतता (ईर्ष्या-मुक्तता के शिथिलीकरण पर आधारित) और पेरेटो दक्षता को एक साथ प्राप्त किए जा सकने के सैद्धांतिक गारंटी स्थापित करता है। विशेष रूप से, न्यायसंगतता गारंटी "k-पुनर्वितरण ईर्ष्या-मुक्तता" (EFR-k) की अवधारणा पर आधारित है: यदि अधिकतम k वस्तुओं का एक उपसमुच्चय R मौजूद है, जैसे कि प्रत्येक एजेंट i के लिए, R में वस्तुओं के पुनर्वितरण द्वारा i के लिए ईर्ष्या-मुक्त आवंटन A^i प्राप्त किया जा सकता है, तो आवंटन A, EFR-k है।

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

समस्या परिभाषा

न्यायसंगत आवंटन एक ऐसी समस्या है जो संपत्ति विभाजन, कार्य आवंटन, सीमा विवाद और ऋण आवंटन जैसे वास्तविक परिदृश्यों में बार-बार होती है। जब भाग लेने वाले एजेंटों के पास व्यक्तिगत प्राथमिकताएं होती हैं, तो "किसे क्या मिले" का प्रश्न व्यावहारिक तात्कालिकता और सैद्धांतिक समृद्धि दोनों रखता है।

अनुसंधान चुनौतियाँ

  1. मिश्रित मन्ना की जटिलता: शुद्ध वस्तुओं (goods) या घरेलू कामों (chores) के विपरीत, मिश्रित मन्ना में वस्तुओं का मूल्य चिन्ह एजेंट के अनुसार भिन्न हो सकता है, जो आवंटन को अधिक जटिल बनाता है।
  2. न्यायसंगतता और दक्षता का व्यापार: अविभाज्य वस्तुओं की सेटिंग में, पारंपरिक ईर्ष्या-मुक्तता (envy-freeness) अस्तित्व की गारंटी नहीं दे सकती है, उपयुक्त शिथिलीकरण शर्तों की खोज की आवश्यकता है।
  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 है, यदि और केवल यदि आकार अधिकतम k का एक उपसमुच्चय R ⊆ m मौजूद है, जैसे कि प्रत्येक एजेंट i के लिए, R में वस्तुओं के पुनर्वितरण द्वारा i के लिए ईर्ष्या-मुक्त आवंटन A^i प्राप्त किया जा सकता है।

मुख्य तकनीकी घटक

  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 कवरिंग को परिभाषित करें: KKM शर्त को संतुष्ट करने वाले बंद समुच्चय परिवार {Ci} का निर्माण करें
  3. KKM प्रमेय लागू करें: प्रतिच्छेदन w* ∈ ∩i Ci प्राप्त करें
  4. गणना तर्क: पुनर्वितरण समुच्चय R का आकार अधिकतम n-1 है, यह सिद्ध करें

एल्गोरिदम 1: वस्तुओं के लिए संघर्ष-जागरूक चयन अनुक्रम

शुद्ध वस्तुओं के मामले में, एक राउंड-रॉबिन आधारित एल्गोरिदम डिज़ाइन किया गया है:

  • संघर्ष समाधान चरण: कई एजेंटों द्वारा सबसे अधिक पसंद की जाने वाली समान वस्तुओं की पहचान करें, उन्हें पुनर्वितरण समुच्चय R में जोड़ें
  • चयन चरण: सक्रिय एजेंट शब्दकोशीय क्रम में सबसे अधिक पसंद की वस्तु का चयन करते हैं

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

  1. KKM प्रमेय का नया अनुप्रयोग: पहली बार शास्त्रीय KKM प्रमेय को असतत न्यायसंगत आवंटन समस्या पर लागू किया, जो मौजूदा बाजार-आधारित विधियों से पूरी तरह अलग तकनीकी पथ प्रदान करता है।
  2. विक्षोभ तकनीक: सावधानीपूर्वक डिज़ाइन किए गए मूल्यांकन विक्षोभ के माध्यम से गैर-अपक्षयी गुणों को सुनिश्चित करें, जिससे भारित सामाजिक कल्याण अधिकतमकरण समस्या अच्छे गुणों को प्राप्त करे।
  3. गणना तर्क: द्विपक्षीय ग्राफ की चक्रहीनता का उपयोग करके पुनर्वितरण समुच्चय के आकार की सीमा को सिद्ध करें।

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

सैद्धांतिक विश्लेषण ढांचा

चूंकि यह एक सैद्धांतिक पेपर है, मुख्य रूप से अनुभवजन्य प्रयोगों के बजाय गणितीय प्रमाणों के माध्यम से परिणामों को सत्यापित किया जाता है। पेपर निम्नलिखित विश्लेषण ढांचा अपनाता है:

  1. अस्तित्व प्रमाण: EFR-(n-1) और PO आवंटन के अस्तित्व को सिद्ध करने के लिए KKM प्रमेय का उपयोग करें
  2. कसी हुई विश्लेषण: सीमाओं की कसी हुई प्रकृति को सिद्ध करने के लिए प्रतिउदाहरण का निर्माण करें
  3. एल्गोरिदम जटिलता: एल्गोरिदम की समय जटिलता का विश्लेषण करें

जटिलता विश्लेषण

  • निश्चित एजेंट संख्या: EFR-(n-1) और PO आवंटन 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 के शास्त्रीय परिणाम दर्शाते हैं कि ईर्ष्या-मुक्तता और PO को एक साथ प्राप्त किया जा सकता है
  • अविभाज्य वस्तुएं: EF1 और PO का एक साथ कार्यान्वयन परिपक्व सिद्धांत है (Nash सामाजिक कल्याण अधिकतमकरण)

घरेलू कामों और मिश्रित मन्ना की चुनौतियां

  • घरेलू कामों का आवंटन: चार एजेंटों के मामले में भी EF1+PO अस्तित्व अनसुलझा है
  • मिश्रित मन्ना: तीन एजेंटों के मामले में EF1+PO अस्तित्व अभी भी एक खुली समस्या है
  • पद्धति संबंधी अंतर: घरेलू कामों के लिए EF1 की गारंटी देने वाले Nash सामाजिक कल्याण जैसे फलन मौजूद नहीं हैं

संबंधित शिथिलीकरण अवधारणाएं

  • EF1: एक वस्तु को हटाकर ईर्ष्या को समाप्त करना
  • EFX: किसी भी वस्तु को हटाकर ईर्ष्या को समाप्त करना
  • भिन्नात्मक आवंटन: अधिकतम (n-1) वस्तुओं के भिन्नात्मक आवंटन की ईर्ष्या-मुक्तता

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

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

  1. सैद्धांतिक सफलता: पहली बार सामान्य मिश्रित मन्ना सेटिंग के लिए न्यायसंगतता और दक्षता की एक साथ गारंटी प्रदान की गई है
  2. तकनीकी नवाचार: असतत न्यायसंगत आवंटन में KKM प्रमेय का अनुप्रयोग नई अनुसंधान दिशाएं खोलता है
  3. व्यावहारिक मूल्य: एल्गोरिदमिक परिणाम वास्तविक अनुप्रयोगों के लिए कम्प्यूटेशनल आधार प्रदान करते हैं

सीमाएं

  1. सीमा: EFR-(n-1) की सीमा अपेक्षाकृत बड़ी है, औसतन प्रत्येक एजेंट को लगभग 2 वस्तुओं का पुनर्वितरण करना पड़ता है
  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 प्रमेय को लागू करके, मिश्रित मन्ना के न्यायसंगत और कुशल आवंटन के लिए महत्वपूर्ण सैद्धांतिक गारंटी प्रदान करता है। हालांकि व्यावहारिकता के पहलुओं में कुछ सीमाएं हैं, लेकिन इसके सैद्धांतिक योगदान और तकनीकी नवाचार इसे न्यायसंगत आवंटन क्षेत्र में एक महत्वपूर्ण प्रगति बनाते हैं।