Fair allocation of items and money
वस्तुओं और धन का उचित आवंटन उचित वस्तु आवंटन समस्याओं का एक वर्ग है जिसमें, आवंटन प्रक्रिया के दौरान, कुछ प्रतिभागियों से धन देना या लेना संभव है। धन के बिना, अविभाज्य वस्तुओं को निष्पक्ष रूप से आवंटित करना असंभव हो सकता है। उदाहरण के लिए, यदि एक वस्तु और दो लोग हैं, और वस्तु पूरी तरह से उनमें से एक को दी जानी चाहिए, तो आवंटन दूसरे के प्रति अनुचित होगा। मौद्रिक भुगतान निष्पक्षता प्राप्त करना संभव बनाते हैं, जैसा कि नीचे बताया गया है। दो एजेंट और एक वस्तु दो एजेंट और एक वस्तु के साथ, निम्नलिखित सरल एल्गोरिथ्म का उपयोग करके निष्पक्षता प्राप्त करना संभव है (जो कट एंड चॉइस का एक प्रकार है): एलिस एक मूल्य पी कहती है जो वह वस्तु के लिए भुगतान करने को तैयार है। जॉर्ज चुनता है कि क्या वस्तु को लेना है और पी का भुगतान करना है, या वस्तु को एलिस पर छोड़ देना है ताकि एलिस पी का भुगतान करे। यह एल्गोरिथ्म मानता है कि एजेंटों के पास अर्धरेखीय उपयोगिताएँ हैं, यानी उनकी उपयोगिता वस्तुओं का मूल्य और उनके पास मौजूद धन की राशि है। यदि जॉर्ज सोचता है कि एलिस की कीमत कम है (वह पी से अधिक भुगतान करने को तैयार है), तो वह वस्तु लेता है और पी का भुगतान करता है, और उसकी उपयोगिता सकारात्मक है, इसलिए वह एलिस से ईर्ष्या नहीं करता है। एलिस को भी जॉर्ज से ईर्ष्या नहीं होती क्योंकि उसकी उपयोगिता-उसकी नज़रों में-0 है। इसी तरह, अगर जॉर्ज सोचता है कि एलिस की कीमत अधिक है (वह पी या उससे अधिक भुगतान करने को तैयार है), तो वह उस वस्तु को एलिस के लिए छोड़ देता है और ईर्ष्या नहीं करता है, क्योंकि उसकी नज़रों में एलिस की उपयोगिता नकारात्मक है। भुगतान की गई राशि पी को बाद में खिलाड़ियों के बीच समान रूप से विभाजित किया जा सकता है, क्योंकि एक समान मौद्रिक हस्तांतरण सापेक्ष उपयोगिताओं को प्रभावित नहीं करता है। फिर, प्रभावी रूप से, खरीद एजेंट बिक्री एजेंट को पी/2 का भुगतान करता है। प्रत्येक अभिकर्ता की कुल उपयोगिता वस्तु के लिए उसकी उपयोगिता का कम से कम आधा है। यदि अभिकर्ताओं के पास अलग-अलग हक हैं, तो भुगतान की गई राशि को भागीदारों के बीच उनकी हकदारी के अनुपात में विभाजित किया जाना चाहिए। इस सरल विचार को दो से अधिक खिलाड़ियों और अधिक जटिल सेटिंग्स तक विस्तारित करने वाले विभिन्न कार्य हैं। इन कार्यों में मुख्य निष्पक्षता मानदंड ईर्ष्या-स्वतंत्रता है। इसके अलावा, कुछ कार्य एक ऐसी व्यवस्था पर विचार करते हैं जिसमें एक परोपकारी तृतीय-पक्ष आवंटन को सब्सिडी देने के लिए तैयार है, लेकिन ईर्ष्या-स्वतंत्रता के अधीन सब्सिडी की राशि को कम करना चाहता है। इस समस्या को न्यूनतम-सब्सिडी ईर्ष्या-मुक्त आवंटन कहा जाता है। यूनिट-डिमांड एजेंट यूनिट-डिमांड एजेंट अधिक से अधिक एक वस्तु में रुचि रखते हैं। किराये में सामंजस्य इस व्यवस्था का एक विशेष मामला किरायेदारों के बीच एक अपार्टमेंट में कमरों को विभाजित करते समय होता है। इसकी विशेषता तीन आवश्यकताएँ हैंः (ए) एजेंटों की संख्या वस्तुओं की संख्या के बराबर होती है, (बी) प्रत्येक एजेंट को बिल्कुल एक वस्तु (कमरा) मिलनी चाहिए, (सी) एजेंटों द्वारा भुगतान की गई कुल राशि एक निश्चित स्थिरांक के बराबर होनी चाहिए, जो कुल अपार्टमेंट किराए का प्रतिनिधित्व करती है। इसे किराया सद्भाव समस्या के रूप में जाना जाता है। अधिक सामान्य स्थितियाँ सामान्य रूप से, अर्थशास्त्र साहित्य में, यह मान लेना आम बात है कि प्रत्येक एजेंट का बंडलों पर एक उपयोगिता कार्य होता है (एक बंडल एक वस्तु की जोड़ी और एक निश्चित राशि होती है)। उपयोगिता कार्य निरंतर होना चाहिए और मुद्रा में बढ़ना चाहिए। यह धन में रैखिक नहीं होना चाहिए, लेकिन "आर्किमिडियन" होना चाहिए, यानी, कुछ मान V मौजूद है कि, प्रत्येक दो वस्तुओं जे और के के लिए, वस्तु जे प्लस वी की उपयोगिता वस्तु के की उपयोगिता से बड़ी होनी चाहिए (वैकल्पिक रूप से, वस्तु जे को मुफ्त में प्राप्त करने की उपयोगिता वस्तु के प्राप्त करने और वी का भुगतान करने की उपयोगिता से बड़ी है)। क्वासिलीनियर उपयोगिता आर्किमिडियन उपयोगिता का एक विशेष मामला है, जिसमें V दो वस्तुओं के बीच सबसे बड़ा मूल्य-अंतर (एक ही एजेंट के लिए) है। स्वेन्सन ने पहली बार साबित किया कि, जब सभी एजेंट आर्किमिडियन होते हैं, तो एक ईर्ष्या-मुक्त आवंटन मौजूद होता है और पारेटो-इष्टतम होता है। डीमांज, गेल और सोटोमेयर ने एक प्राकृतिक आरोही नीलामी दिखाई जो इकाई मांग एजेंटों के लिए मौद्रिक भुगतान का उपयोग करके एक ईर्ष्या-मुक्त आवंटन प्राप्त करती है। मास्किन ने एक पारेतो-इष्टतम ईर्ष्या-मुक्त आवंटन के अस्तित्व को साबित किया जब कुल धन निधि (एन-1) वी से अधिक है। ध्यान दें कि (एन-1) वी की सब्सिडी की आवश्यकता हो सकती हैः यदि सभी एजेंट किसी एक वस्तु को वी पर और अन्य वस्तुओं को 0 पर महत्व देते हैं, तो ईर्ष्या-स्वतंत्रता के लिए प्रत्येक एजेंट के लिए वी की सब्सिडी की आवश्यकता होती है जो वस्तु प्राप्त नहीं करता है। टाडेनुमा और थॉमसन ईर्ष्या-मुक्त आवंटन नियमों के कई सुसंगतता गुणों का अध्ययन करते हैं। एरागोन्स ईर्ष्या-स्वतंत्रता के लिए आवश्यक सब्सिडी की न्यूनतम राशि की विशेषता है। इस न्यूनतम सब्सिडी को प्राप्त करने वाला आवंटन लगभग अद्वितीय हैः एजेंटों के साथ वस्तुओं को जोड़ने का केवल एक ही तरीका है, और सभी एजेंट सभी न्यूनतम-सब्सिडी आवंटन के बीच उदासीन हैं। यह अलकन, डिमैंज और गेल के "मनी-रॉलशियन समाधान" नामक समाधान के साथ मेल खाता है। यह बहुपद समय में पाया जा सकता है, एक अधिकतम-वजन मिलान ढूंढकर और फिर एक निश्चित प्रेरित ग्राफ में सबसे छोटे मार्ग ढूंढकर। क्लिजन उसी सेटिंग के लिए एक और बहुपद-समय एल्गोरिथ्म प्रस्तुत करता है। उनका एल्गोरिथ्म साइड-पेमेंट्स के पॉलीटोप का उपयोग करता है जो दिए गए आवंटन को ईर्ष्या-मुक्त बनाता हैः यह पॉलीटोप गैर-खाली है यदि मूल आवंटन पारेटो-कुशल है। दिशाहीन ईर्ष्या ग्राफ की संयोजकता इस पॉलीटोप के चरम बिंदुओं को दर्शाती है। यह अत्यधिक ईर्ष्या-मुक्त आवंटन खोजने के लिए एक विधि का तात्पर्य है। एडिटिव एजेंट कई वस्तुओं को प्राप्त कर सकते हैं, इसलिए आवंटन समस्या अधिक जटिल हो जाती है-कई और संभावित आवंटन हैं। वस्तुओं और धन के उचित आवंटन की पहली प्रक्रिया का आविष्कार ब्रोनिस्लाव नैस्टर ने किया था और ह्यूगो स्टीनहॉस ने इसे प्रकाशित किया था। यह नीलामी प्रत्येक वस्तु के लिए अलग से इस प्रकार काम करती हैः प्रत्येक एजेंट वस्तु पर बोली लगाता है। यह वस्तु सबसे अधिक बोली लगाने वाले को दी जाती है (मनमाने ढंग से संबंध तोड़ना)। विजेता अपनी बोली का (एन-1)/एन का भुगतान करता है; अन्य एजेंटों में से प्रत्येक को अपनी बोली का 1/एन प्राप्त होता है; चूंकि विजेता सबसे अधिक बोली लगाने वाला होता है, इसलिए एक गैर-नकारात्मक अधिशेष होता है; अधिशेष को एजेंटों के बीच समान रूप से विभाजित किया जाता है। प्रत्येक अभिकर्ता की उपयोगिता उस मूल्य का कम से कम 1/n है जो वह वस्तुओं के पूरे समूह को देता है, इसलिए आवंटन आनुपातिक है। इसके अलावा, आवंटन उपयोगिताओं के योग को अधिकतम करता है, इसलिए यह पारेटो कुशल है। नैस्टर की नीलामी रणनीतिक रूप से सुरक्षित नहीं है। कुछ शोधकर्ताओं ने इसके प्रदर्शन का विश्लेषण किया जब एजेंट रणनीतिक रूप से खेलते हैंः एसेन साबित करता है कि संतुलन आवंटन अभी भी पेरेटो-कुशल है, लेकिन आनुपातिक पूर्व-पद नहीं हो सकता है। हालांकि, औसतन, एजेंटों को एक ही परिणाम मिलता है जैसे कि हर कोई सच्चा था। अर्थात्, तंत्र आनुपातिक एक्स-एंटे है। फ्रैगनेली और मरीना से पता चलता है कि, जो एजेंट असीम रूप से जोखिम-विरोधी हैं, वे भी अन्य एजेंटों की घोषणाओं की परवाह किए बिना, अपने मूल्यांकन की संयुक्त गलत रिपोर्टिंग के माध्यम से एक सुरक्षित लाभ प्राप्त कर सकते हैं। नैस्टर की नीलामी को वायरलेस चैनलों के उचित आवंटन के लिए अनुकूलित किया गया है। रैथ की नीलामी मथियास जी. रैथ ने नैस्टर की नीलामी पर एक संस्करण प्रस्तुत किया, जिसे उन्होंने "एडजस्टेड नैस्टर" कहा। जैसा कि नैस्टर की नीलामी में होता है, प्रत्येक वस्तु सबसे अधिक बोली लगाने वाले को दी जाती है। लेकिन भुगतान अलग-अलग होते हैं। भुगतान इस प्रकार निर्धारित किए जाते हैंः एक वस्तु जीतने वाला प्रत्येक एजेंट इस वस्तु के लिए अपनी बोली का भुगतान करता है; एजेंटों द्वारा भुगतान की गई कुल राशि को उनकी बोलियों के अनुपात में उनके बीच विभाजित किया जाता है। नैस्टर की नीलामी और रैथ की नीलामी के बीच के अंतर को स्पष्ट करने के लिए, निम्नलिखित मूल्यों के साथ दो वस्तुओं और दो एजेंटों के साथ एक सेटिंग पर विचार करेंः दोनों नीलामी में, जॉर्ज दोनों वस्तुओं को जीतता है, लेकिन भुगतान अलग-अलग होते हैंः नैस्टर की नीलामी में, जॉर्ज 90 का भुगतान करता है, एलिस 10 प्राप्त करता है, और 80 का अंतर समान रूप से विभाजित होता है, इसलिए शुद्ध उपयोगिताएँ 50,130 हैं। रायथ की नीलामी में जॉर्ज 180 का भुगतान करता है और इसे 20:180 = 1:9 के अनुपात में विभाजित किया जाता है, यानी एलिस को 18 और जॉर्ज को 162 मिलता है। ध्यान दें कि भुगतान की गणना एक बार में सभी वस्तुओं के लिए की जाती है-प्रत्येक वस्तु के लिए अलग से नहीं। मानव विषयों के साथ प्रयोगों में, यह पाया गया कि प्रतिभागी राइथ की नीलामी (एडजस्टेड नैस्टर) को पसंद करते हैं बजाय डिवाइड-एंड-चूज़ और आनुपातिक नैस्टर (एक प्रकार जिसमें प्रत्येक विजेता प्रत्येक हारने वाले को जीतने वाले का 1/n का भुगतान करता है; उपरोक्त उदाहरण में, जॉर्ज एलिस को 90 का भुगतान करता है, और शुद्ध उपयोगिताएँ 90,90 हैं)। क्षतिपूर्ति प्रक्रिया हाक्के, रैथ और सु क्षतिपूर्ति प्रक्रिया प्रस्तुत करते हैं। उनकी प्रक्रिया वस्तुओं के बंडल पर मनमाने प्रतिबंधों की अनुमति देती है, जब तक कि वे गुमनाम हैं (उनकी पहचान के आधार पर भागीदारों के बीच अंतर न करें)। उदाहरण के लिए, कोई बाधा नहीं हो सकती है, या एक बाधा हो सकती है जैसे कि "प्रत्येक भागीदार को कम से कम एक निश्चित संख्या में आइटम प्राप्त करने चाहिए", या "कुछ वस्तुओं को एक साथ बंडल किया जाना चाहिए" (जैसे। क्योंकि वे भू-भूखंड हैं जो जुड़े रहने चाहिए), आदि। "वस्तुओं" की सकारात्मक या नकारात्मक दोनों उपयोगिताएँ हो सकती हैं। एक भागीदार के लिए एक "योग्यता आवश्यकता" हैः उसकी बोलियों का योग कम से कम कुल लागत होना चाहिए। प्रक्रिया निम्नलिखित चरणों में काम करती है। एक अधिकतम (उपयोगितावादी) आवंटन खोजें-उच्चतम उपयोगिताओं के साथ एक आवंटन जो वस्तुओं के बंडल पर बाधाओं को संतुष्ट करता है। यदि कोई बाधा नहीं है, तो एक आवंटन जो प्रत्येक वस्तु को उच्चतम मूल्यांकन वाले भागीदार को देता है, वह अधिकतम राशि है। यदि बाधाएं हैं (जैसे कि "प्रति भागीदार कम से कम एक वस्तु"), तो अधिकतम राशि का आवंटन करना अधिक कठिन हो सकता है। प्रत्येक साथी से उसे आवंटित बंडल का मूल्य वसूल करें। इससे धन का प्रारंभिक भंडार बनता है। प्रारंभिक राशि से लागत का भुगतान करें। यदि सभी भागीदार योग्यता की आवश्यकता को पूरा करते हैं, तो पूल में पैसा पर्याप्त है, और कुछ अधिशेष शेष रह सकता है। ईर्ष्यालु भागीदारों को क्षतिपूर्ति देकर ईर्ष्या को दूर करें। मुआवजे के ज्यादातर दौर होते हैं। प्रक्रिया पूरी तरह से वर्णनात्मक है और स्पष्ट रूप से बताती है कि कौन सी क्षतिपूर्ति की जानी चाहिए, और किस क्रम में। इसके अलावा, इसे कंप्यूटर समर्थन के बिना किया जाना काफी सरल है। सभी दौरों में की गई क्षतिपूर्ति का योग सबसे छोटी राशि है जो ईर्ष्या को खत्म करने के लिए आवश्यक है, और यह कभी भी अधिशेष से अधिक नहीं होती है। यदि कुछ अधिशेष बचा रहता है, तो इसे किसी भी तरह से विभाजित किया जा सकता है जो ईर्ष्या पैदा नहीं करता है, उदाहरण के लिए, प्रत्येक साथी को समान राशि देकर (पेपर अन्य विकल्पों पर चर्चा करता है जिन्हें "बेहतर" माना जा सकता है)। जब कई आइटम और जटिल बाधाएं होती हैं, तो प्रारंभिक चरण-अधिकतम आवंटन खोजना-कंप्यूटर के बिना गणना करना मुश्किल हो सकता है। इस मामले में, क्षतिपूर्ति प्रक्रिया मनमाने ढंग से आवंटन के साथ शुरू हो सकती है। इस मामले में, प्रक्रिया एक आवंटन के साथ समाप्त हो सकती है जिसमें ईर्ष्या-चक्र शामिल हैं। इन चक्रों को चक्र के साथ-साथ बंडलों को स्थानांतरित करके हटाया जा सकता है, जैसा कि ईर्ष्या-ग्राफ प्रक्रिया में होता है। यह उपयोगिताओं की कुल राशि को सख्ती से बढ़ाता है। इसलिए, सीमित संख्या में पुनरावृत्तियों के बाद, एक अधिकतम आवंटन पाया जाएगा, और एक ईर्ष्या-मुक्त आवंटन बनाने के लिए प्रक्रिया ऊपर की तरह जारी रह सकती है। क्षतिपूर्ति प्रक्रिया कुछ भागीदारों से नकारात्मक भुगतान कर सकती है (यानी, भागीदारों को सकारात्मक राशि दें)। लेखकों का कहना हैः "हम इस संभावना को नहीं रोकते हैं कि किसी व्यक्ति को माल का एक बंडल लेने के लिए दूसरों द्वारा भुगतान किया जा सकता है। निष्पक्ष विभाजन के संदर्भ में, हम इसे बिल्कुल भी समस्याग्रस्त नहीं पाते हैं। वास्तव में, यदि कोई समूह अपने किसी भी सदस्य को बाहर नहीं करना चाहता है, तो कोई कारण नहीं है कि समूह को किसी सदस्य को अवांछित बंडल प्राप्त करने के लिए सब्सिडी नहीं देनी चाहिए। इसके अलावा, योग्यता की आवश्यकता इस बात की गारंटी देती है कि सब्सिडी कभी भी किसी खिलाड़ी द्वारा वितरित की जाने वाली वस्तुओं के पूरे सेट के अपर्याप्त मूल्यांकन का परिणाम नहीं है। न्यूनतम सब्सिडी प्रक्रियाएँ कुछ कार्य यह मानते हैं कि एक परोपकारी तृतीय-पक्ष आवंटन पर सब्सिडी देने के लिए तैयार है, लेकिन ईर्ष्या-स्वतंत्रता के अधीन सब्सिडी की राशि को कम करना चाहता है। इस समस्या को न्यूनतम-सब्सिडी ईर्ष्या-मुक्त आवंटन कहा जाता है। हेल्पर्न और शाह सामान्य वस्तु-आवंटन व्यवस्था में सब्सिडी को कम करने का अध्ययन करते हैं। वे दो मामलों पर विचार करते हैंः आवंटन अग्रिम रूप से दिया जाता है। इस मामले में, यह "ईर्ष्या-मुक्त" है यदि और केवल तभी जब यह एजेंटों को अपने बंडलों के सभी पुनर्वितरणों में उपयोगिताओं के योग को अधिकतम करता है, अगर और केवल तभी जब इसकी ईर्ष्या-ग्राफ का कोई चक्र न हो। न्यूनतम सब्सिडी के साथ एक ईर्ष्या-मुक्त मूल्य की गणना मजबूत बहुपद समय में की जा सकती है, भारित ईर्ष्या-ग्राफ का निर्माण करके और प्रत्येक एजेंट को, i से निकलने वाले पथ के अधिकतम वजन के बराबर मूल्य देकर। प्रत्येक पथ का वजन अधिक से अधिक m शब्दों का योग है, जिनमें से प्रत्येक कुछ अच्छे के लिए कुछ एजेंट का मूल्य है। विशेष रूप से, यदि प्रत्येक एजेंट के लिए प्रत्येक वस्तु का मूल्य अधिकतम V है, तो प्रत्येक पथ का वजन अधिकतम mV है। चूँकि हम हमेशा कीमतों को इस तरह कम कर सकते हैं कि एक एजेंट को शून्य सब्सिडी मिलती है, इसका मतलब है कि हमेशा अधिक से अधिक (एन-1) एम. वी. की सब्सिडी के साथ एक ईर्ष्या मुक्त आवंटन मौजूद रहता है। यह सब्सिडी आवश्यक हो सकती है, उदाहरण के लिए जब सभी सामान समान हों और एक एजेंट को वे सभी मिलें। आवंटन का चयन किया जा सकता है। इस मामले में, (एन-1) वी की सब्सिडी निम्नलिखित मामलों में पर्याप्त हैः जब एजेंटों का मूल्यांकन द्विआधारी (0 या 1) हो। फिर, किसी भी अधिकतम-उत्पाद आवंटन या लेक्सिमिन-इष्टतम आवंटन के लिए अधिकतम (एन-1) वी सब्सिडी की आवश्यकता होती है, और यह बहुपद समय में पाया जा सकता है। ई. एफ. प्राप्त करने के लिए आवश्यक न्यूनतम सब्सिडी की गणना करना एक ईर्ष्या-मुक्त आवंटन के अस्तित्व की जांच करने के लिए ट्यूरिंग-समतुल्य है, जो गैर-व्यर्थ आवंटन तक सीमित होने पर एन. पी.-कठिन है। जब सभी एजेंटों का योगात्मक मूल्यांकन समान होता है। फिर, प्रत्येक आवंटन ईर्ष्या-मुक्त होता है। एक आवंटन जिसके लिए अधिकतम (एन-1) वी सब्सिडी की आवश्यकता होती है, बहुपद समय में पाया जा सकता है। एक आवंटन सब्सिडी को कम करता है यदि यह किसी भी एजेंट के लिए अधिकतम उपयोगिता को कम करता है। इस तरह के आवंटन की गणना करना एन. पी.-कठिन है, और इसे अधिकतम-उत्पाद एल्गोरिदम द्वारा हल किया जा सकता है। जब दो एजेंट होते हैं, तो एक विशिष्ट एजेंट के आदेश के साथ राउंड-रॉबिन आइटम आवंटन में एक ऐसा आवंटन पाया जाता है जो सब्सिडी के साथ ईर्ष्या-मुक्त है। वी. ब्रस्टल, डिप्पल, नारायण, सुजुकी और वेट्टा आवश्यक सब्सिडी पर ऊपरी सीमा में सुधार करते हैंः योगात्मक मूल्यांकन के साथ, अधिकतम वी प्रति एजेंट की सब्सिडी, और सामान्य रूप से अधिकतम (एन-1) वी, हमेशा पर्याप्त होती है। इसके अलावा, इस सीमा को प्राप्त करने के लिए एक आवंटन है जो ई. एफ. 1 और संतुलित भी है (आवंटित बंडलों की प्रमुखताएं अधिक से अधिक एक वस्तु से भिन्न होती हैं)। इसकी गणना एक सरल एल्गोरिथ्म द्वारा बहुपद समय में की जा सकती हैः एजेंटों-वस्तुओं के द्विदलीय ग्राफ में एक अधिकतम वजन मिलान का पता लगाएं। सामान्य मोनोटोन मूल्यांकन के साथ, प्रति एजेंट अधिकतम 2 (एन-1) वी, और अधिकतम ओ (एन2वी) की सब्सिडी हमेशा पर्याप्त होती है। विशेष रूप से, आवश्यक सब्सिडी वस्तुओं की संख्या पर निर्भर नहीं करती है। इस सीमा को प्राप्त करने वाले आवंटन की गणना मूल्य-प्रश्नों का उपयोग करके बहुपद समय में की जा सकती है। कैराजियानिस और आयोनिडिस सब्सिडी को कम करने की कम्प्यूटेशनल समस्या का अध्ययन करते हैंः एजेंटों की एक निरंतर संख्या के लिए, वे एक एल्गोरिथ्म प्रस्तुत करते हैं जो किसी भी आवश्यक सटीकता के भीतर सब्सिडी की न्यूनतम राशि का अनुमान लगाता है। किसी भी ε> 0 के लिए, यह अधिक से अधिक सब्सिडी के साथ एक आवंटन पाता है, जहां S अधिकतम मूल्य है जो एक एजेंट सभी वस्तुओं को सौंपता है। एल्गोरिथ्म गतिशील प्रोग्रामिंग का उपयोग करता है और समय पर चलता है। एजेंटों की एक परिवर्तनीय संख्या के लिए, एक तुच्छ सन्निकटन एल्गोरिथ्म प्राप्त होता है। हालांकि, एन से स्वतंत्र एक सन्निकटन कारक प्राप्त करना कठिन हैः अधिक से अधिक सब्सिडी के साथ आवंटन की गणना करना एनपी-कठिन है। प्रमाण अधिकतम 3-आयामी मिलान के एक प्रतिबंधित संस्करण से घटाकर है, जिसमें प्रत्येक शीर्ष ठीक दो बार दिखाई देता है। ध्यान दें कि यदि प्रत्येक अभिकर्ता से एक निश्चित राशि ली जाती है तो सब्सिडी के साथ ईर्ष्या-मुक्त आवंटन ईर्ष्या-मुक्त रहता है। इसलिए, ऐसे आवंटन का पता लगाने के लिए इसी तरह के तरीकों का उपयोग किया जा सकता है जिन्हें सब्सिडी नहीं दी जाती हैः प्रत्येक एजेंट से औसत भुगतान लेने से एक ईर्ष्या-मुक्त आवंटन प्राप्त होता है जो बजट-संतुलित भी होता है। सब्सिडी को कम करना किसी भी व्यक्तिगत एजेंट द्वारा भुगतान की जाने वाली अधिकतम राशि को कम करने के बराबर है। सभी एजेंटों को भुगतान करने वाली कुल राशि को कम करते हुए नकारात्मक सब्सिडी (कर) का उपयोग करना भी संभव है। अतिरिक्त प्रक्रियाओं अलकन, डिमैंज और गेल ने दिखाया कि एक ईर्ष्या-मुक्त आवंटन हमेशा मौजूद रहता है जब धन की राशि पर्याप्त रूप से बड़ी होती है। यह तब भी सच है जब वस्तुओं का नकारात्मक मूल्यांकन हो सकता है। मीर्टेंस, पॉटर्स और रेजिनियर्स मूल्यांकन पर बहुत हल्की धारणाओं के तहत ईर्ष्या-मुक्त और पेरेटो-इष्टतम आवंटन के अस्तित्व को साबित करते हैं (जरूरी नहीं कि अर्धरेखीय)। कैवाल्लो 0 और 1 के बीच के डिग्री के उपायों के लिए ईर्ष्या-स्वतंत्रता, आनुपातिकता और दक्षता (कल्याण) के पारंपरिक द्विआधारी मानदंडों को सामान्यीकृत करता है। विहित निष्पक्ष विभाजन व्यवस्थाओं में, किसी भी आबंटन-कुशल तंत्र के तहत सबसे खराब-स्थिति कल्याण दर 0 है और अनुपातहीनता दर 1 है; दूसरे शब्दों में, सबसे खराब-स्थिति परिणाम जितना संभव हो उतना खराब हैं। वह एक ऐसे तंत्र की तलाश करता है जो निष्पक्ष विभाजन सेटिंग्स के एक स्पेक्ट्रम में उच्च कल्याण, कम ईर्ष्या और अपेक्षा में कम असमानुपात प्राप्त करता है। वी. सी. जी. तंत्र एक संतोषजनक उम्मीदवार नहीं है, लेकिन बेली और कैवालो का पुनर्वितरण तंत्र है। संबंधित समस्याएं ईर्ष्या-मुक्त मूल्य निर्धारण खरीदारों को वस्तुओं को बेचते समय, भुगतान की राशि पहले से तय नहीं की जाती है, और इसका लक्ष्य या तो विक्रेता के राजस्व को अधिकतम करना है, या सामाजिक कल्याण, ईर्ष्या-स्वतंत्रता के अधीन है। इसके अतिरिक्त, वस्तुओं की संख्या एजेंटों की संख्या से अलग हो सकती है, और कुछ वस्तुओं को त्याग दिया जा सकता है। इसे ईर्ष्या-मुक्त मूल्य निर्धारण समस्या के रूप में जाना जाता है। बहुआयामी उद्देश्य अक्सर निष्पक्षता के अलावा कुछ अन्य उद्देश्यों को प्राप्त करना पड़ता है। उदाहरण के लिए, एजेंटों को कार्य सौंपते समय, ईर्ष्या से बचने और मेकस्पैन को कम करने (-अंतिम एजेंट का पूरा होने का समय) दोनों की आवश्यकता होती है। मुआलेम ईर्ष्या-स्वतंत्रता की गारंटी के साथ अनुकूलन समस्याओं के लिए एक सामान्य ढांचा प्रस्तुत करता है जो स्वाभाविक रूप से मौद्रिक भुगतान का उपयोग करके उचित वस्तु आवंटन का विस्तार करता है। अज़ीज़ का लक्ष्य मौद्रिक हस्तांतरण का उपयोग करके एक ऐसा आवंटन प्राप्त करना है जो ईर्ष्या मुक्त और न्यायसंगत दोनों हो। वह न केवल योगात्मक सकारात्मक उपयोगिताओं का अध्ययन करते हैं, बल्कि किसी भी योगात्मक उपयोगिताओं के लिए भी, चाहे वह सकारात्मक हो या नकारात्मकः योगात्मक उपयोगिताओं के लिए, एक बहुपद-समय एल्गोरिदम है जो ईर्ष्या-स्वतंत्रता, समता और बजट संतुलन प्राप्त करता है (सब्सिडी के साथ बजट-संतुलन का आदान-प्रदान करना आसान है)। यदि दिया गया आवंटन ई. एफ. ई. क्यू.-परिवर्तनीय है, तो इसे ई. एफ. + ई. क्यू. बनाने के लिए आवश्यक न्यूनतम सब्सिडी रैखिक समय में पाई जा सकती है। ऐसे आवंटन का पता लगाना जो न्यूनतम सब्सिडी के साथ ई. एफ. ई. क्यू.-परिवर्तनीय हो, एन. पी.-कठिन है, और इसे किसी भी सकारात्मक कारक के भीतर अनुमानित नहीं किया जा सकता है। ऐसा केवल इसलिए है क्योंकि ई. एफ. आवंटन (जिसके लिए 0 सब्सिडी की आवश्यकता होती है) के अस्तित्व की जाँच करना एन. पी.-कठिन है। अधिकतम (एन-1) एम. वी. की सब्सिडी हमेशा पर्याप्त होती है, और यह आवश्यक हो सकता है कि आवंटन किया जाए या नहीं। ईर्ष्या-मुक्त वस्तु आवंटन-मौद्रिक हस्तांतरण के बिना सेटिंग भी देखें। संदर्भ उचित वस्तु आवंटन