Welfare maximization
कल्याण अधिकतमकरण समस्या अर्थशास्त्र और कंप्यूटर विज्ञान में अध्ययन की जाने वाली एक अनुकूलन समस्या है। इसका लक्ष्य विभिन्न उपयोगिता कार्यों वाले एजेंटों के बीच वस्तुओं के एक समूह को विभाजित करना है, जैसे कि कल्याण-एजेंटों की उपयोगिताओं के योग के रूप में परिभाषित-जितना संभव हो उतना अधिक हो। दूसरे शब्दों में, लक्ष्य उपयोगितावादी नियम को संतुष्ट करने वाली वस्तु का आवंटन करना है। संयुक्त नीलामी के संदर्भ में एक समतुल्य समस्या को विजेता निर्धारण समस्या कहा जाता है। इस संदर्भ में, प्रत्येक एजेंट वस्तुओं के सेट पर बोलियों की एक सूची प्रस्तुत करता है, और लक्ष्य यह निर्धारित करना है कि कौन सी बोली या बोलियां जीतना चाहिए, जैसे कि जीतने वाली बोलियों का योग अधिकतम हो। परिभाषाएँ m वस्तुओं का एक सेट M है, और n एजेंटों का एक सेट N है। एन में प्रत्येक एजेंट आई का एक उपयोगिता कार्य होता है। फलन वस्तुओं के प्रत्येक संभावित उपसमुच्चय को एक वास्तविक मूल्य प्रदान करता है। यह आमतौर पर माना जाता है कि उपयोगिता कार्य मोनोटोन सेट कार्य हैं, जिसका अर्थ है। ऐसा भी माना जाता है। एकरूपता के साथ, इसका तात्पर्य है कि सभी उपयोगिताएँ गैर-नकारात्मक हैं। एक आबंटन वस्तुओं को अलग-अलग उपसमुच्चय में एक क्रमबद्ध विभाजन है, प्रति अभिकर्ता एक उपसमुच्चय, इस तरह से दर्शाया गया है कि। एक आबंटन का कल्याण अभिकर्ताओं की उपयोगिताओं का योग हैः कल्याण अधिकतमकरण समस्या यह हैः एक आवंटन एक्स खोजें जो डब्ल्यू (एक्स) को अधिकतम करता है। कल्याण अधिकतमकरण समस्या के कई रूप हैं, जो अनुमत उपयोगिता कार्यों के प्रकार पर निर्भर करता है, जिस तरह से एल्गोरिथ्म उपयोगिता कार्यों तक पहुंच सकता है, और क्या अनुमत आवंटन पर अतिरिक्त बाधाएं हैं। योगात्मक एजेंट एक योगात्मक एजेंट का एक उपयोगिता कार्य होता है जो एक योगात्मक सेट फ़ंक्शन होता हैः प्रत्येक योगात्मक एजेंट i और आइटम j के लिए, एक मान होता है, जैसे कि वस्तुओं के प्रत्येक सेट Z के लिए। जब सभी कारक योगात्मक होते हैं, तो कल्याण अधिकतमकरण एक सरल बहुपद-समय एल्गोरिथ्म द्वारा किया जा सकता हैः प्रत्येक वस्तु को एक ऐसे एजेंट को दें जिसके लिए अधिकतम हो (मनमाने ढंग से संबंधों को तोड़ना)। समस्या तब और अधिक चुनौतीपूर्ण हो जाती है जब आवंटन पर अतिरिक्त बाधाएं होती हैं। निष्पक्षता की बाधाएं सभी उचित आवंटनों के बीच कल्याण को अधिकतम करना चाह सकते हैं, उदाहरण के लिए, एक वस्तु (ई. एफ. 1) तक ईर्ष्या-मुक्त, एक वस्तु (पी. आर. ओ. पी. 1) तक आनुपातिक, या एक वस्तु (ई. क्यू. 1) तक न्यायसंगत। यह समस्या दृढ़ता से एन. पी.-कठोर होती है जब एन. परिवर्तनीय होता है। किसी भी निश्चित n ≤ 2 के लिए, समस्या कमजोर रूप से NP-कठोर है, और इसमें गतिशील प्रोग्रामिंग पर आधारित एक छद्म-बहुपद समय एल्गोरिथ्म है। एन = 2 के लिए, समस्या में पूरी तरह से बहुपद-समय सन्निकटन योजना है। इस समस्या को बहुपद समय में हल करने के लिए एल्गोरिदम हैं जब कुछ एजेंट प्रकार, कुछ आइटम प्रकार या छोटे मूल्य स्तर होते हैं। इस समस्या को बहुपद समय में भी हल किया जा सकता है जब एजेंटों की योगात्मक उपयोगिताएँ द्विआधारी होती हैं (प्रत्येक वस्तु का मूल्य या तो 0 या 1 होता है), साथ ही उपयोगिताओं के एक अधिक सामान्य वर्ग के लिए जिसे सामान्यीकृत द्विआधारी कहा जाता है। आबंटन पर एक अन्य बाधा यह है कि बंडल एक मैट्रायड के स्वतंत्र सेट होने चाहिए। उदाहरण के लिए, प्रत्येक बंडल में अधिकतम के आइटम होने चाहिए, जहाँ के एक निश्चित पूर्णांक है (यह एक समान मैट्रायड से मेल खाता है)। या, वस्तुओं को श्रेणियों में विभाजित किया जा सकता है, और प्रत्येक बंडल में प्रत्येक श्रेणी सी से अधिकतम के. सी. आइटम होने चाहिए (यह एक विभाजन मैट्रायड से मेल खाता है)। सामान्य तौर पर, प्रत्येक एजेंट के लिए एक अलग मैट्रायड हो सकता है, और आवंटन में प्रत्येक एजेंट को एक सबसेट xi देना चाहिए जो उनके अपने मैट्रायड का एक स्वतंत्र सेट है। विषम मैट्रायड बाधाओं के तहत योगात्मक उपयोगिताओं के साथ कल्याण अधिकतमकरण बहुपद समय में किया जा सकता है, भारित मैट्रायड प्रतिच्छेदन समस्या को कम करके। सकल-विकल्प एजेंट सकल-विकल्प उपयोगिताएँ योगात्मक उपयोगिताओं की तुलना में अधिक सामान्य हैं। सकल-प्रतिस्थापन एजेंटों के साथ कल्याण अधिकतमकरण बहुपद समय में किया जा सकता है। ऐसा इसलिए है क्योंकि, सकल-प्रतिस्थापन एजेंटों के साथ, एक वाल्रासियन संतुलन हमेशा मौजूद रहता है, और यह उपयोगिताओं के योग को अधिकतम करता है। बहुपद समय में एक वाल्रासियन संतुलन पाया जा सकता है। सबमॉड्यूलर एजेंट एक सबमॉड्यूलर एजेंट का एक उपयोगिता कार्य होता है जो एक सबमॉड्यूलर सेट कार्य होता है। इसका मतलब है कि एजेंट की उपयोगिता कम हो रही है। सबमॉड्यूलर उपयोगिताएँ सकल-विकल्प उपयोगिताओं की तुलना में अधिक सामान्य हैं। सबमॉड्यूलर एजेंटों के साथ कठोरता कल्याण अधिकतमकरण एनपी-हार्ड है। इसके अलावा, इसे (1-1/e) ≈ 0.632 से बेहतर कारक के लिए अनुमानित नहीं किया जा सकता है जब तक कि P = NP न हो। इसके अलावा, (1-1/ई) से बेहतर सन्निकटन के लिए एक मूल्य दैवज्ञ के लिए प्रश्नों की एक घातीय संख्या की आवश्यकता होगी, भले ही पी = एनपी हो। लालची एल्गोरिथ्म अधिकतम कल्याण को निम्नलिखित बहुपद-समय लालची एल्गोरिथ्म द्वारा अनुमानित किया जा सकता हैः X1 = X2 =. = Xn = खाली आरंभ करें। प्रत्येक वस्तु जी के लिए (एक मनमाने क्रम में): गणना करें, प्रत्येक एजेन आई के लिए, जी के लिए उनकी सीमांत उपयोगिता, के रूप में परिभाषित हैः यूआई (एक्सआई + जी)-यूआई (एक्सआई)। सबसे बड़ी सीमांत उपयोगिता वाले एजेंट को आइटम जी दें। लेहमैन, लेहमैन और निसान यह साबित करते हैं कि लालची एल्गोरिदम एक/2-कारक सन्निकटन पाता है (वे ध्यान देते हैं कि यह परिणाम फिशर, नेमहाउसर और वोल्सी के एक मैट्रायड पर एकल सबमॉड्यूलर मूल्यांकन के अधिकतमकरण के परिणाम से मिलता है)। प्रमाण विचार इस प्रकार है। मान लीजिए कि एल्गोरिथ्म किसी वस्तु जी को किसी एजेंट i को आवंटित करता है। यह कल्याण में कुछ राशि v का योगदान देता है, जो उस समय i के लिए g की सीमांत उपयोगिता है। मान लीजिए कि, इष्टतम समाधान में, g को किसी अन्य एजेंट को दिया जाना चाहिए, मान लीजिए कि k। विचार करें कि यदि हम g को i से k में स्थानांतरित करते हैं तो कल्याण कैसे बदलता हैः k की उपयोगिता g की उसकी सीमांत उपयोगिता से बढ़ती है, जो कि लालची चयन द्वारा अधिकतम v है। i के शेष बंडल की सीमांत उपयोगिता अधिकतम v से बढ़ जाती है। यह सबमॉडुलरिटी से होता हैः g की सीमांत उपयोगिता, जब शेष बंडल में जोड़ी जाती है, तो एल्गोरिथ्म द्वारा संसाधित किए जाने पर इसकी सीमांत उपयोगिता से अधिक नहीं हो सकती है। इसलिए, एल्गोरिथ्म कल्याण में v के प्रत्येक योगदान के लिए, इष्टतम कल्याण में संभावित योगदान अधिकतम 2v हो सकता है। इसलिए, इष्टतम कल्याण एल्गोरिथ्म कल्याण का अधिकतम 2 गुना है। लालची एल्गोरिदम के लिए 2 का कारक कड़ा है। उदाहरण के लिए, मान लीजिए कि दो आइटम x, y हैं और मूल्यांकन हैंः कल्याण 2 के साथ इष्टतम आवंटन ऐलिसः {y}, जॉर्जः {x} है। लेकिन अगर लालची एल्गोरिथ्म पहले x आवंटित करता है, तो यह इसे एलिस को आवंटित कर सकता है। फिर, इस बात की परवाह किए बिना कि y कैसे आवंटित किया जाता है, कल्याण केवल 1 है। मूल्य दैवज्ञ का उपयोग करने वाले एल्गोरिदम एक मूल्य दैवज्ञ एक दैवज्ञ है जो वस्तुओं के एक समूह को देखते हुए, इस समूह को अभिकर्ता का मूल्य लौटाता है। इस मॉडल मेंः डॉब्ज़िंस्की और शापिरा एक पॉलीटाइम-एप्रॉक्सिमेशन एल्गोरिथ्म प्रस्तुत करते हैं, और विशेष मामले के लिए एक (1-1/ई) ≈ 0.632-approximation एल्गोरिथ्म प्रस्तुत करते हैं जिसमें एजेंटों की उपयोगिताएँ सेट-कवरेज कार्य हैं। वोंड्रक और कैलिनेस्कु, चेकुरी, पाल और वोंड्रक एक यादृच्छिक पॉलीटाइम एल्गोरिथ्म प्रस्तुत करते हैं जो उच्च संभावना के साथ एक (1-1/ई)-अनुकूलता पाता है। उनका एल्गोरिथ्म एक निरंतर-लालची एल्गोरिथ्म का उपयोग करता है-एक एल्गोरिथ्म जो एक लालची दिशा (ढाल वंश के समान) में एक आंशिक बंडल (एक बंडल जिसमें प्रत्येक वस्तु जे का एक अंश पीजे होता है) का विस्तार करता है। उनके एल्गोरिथ्म को भिन्नात्मक बंडलों के मूल्य की गणना करने की आवश्यकता होती है, जिसे बंडल के अपेक्षित मूल्य के रूप में परिभाषित किया जाता है जब प्रत्येक वस्तु जे को प्रायिकता pj के साथ स्वतंत्र रूप से चुना जाता है। सामान्य तौर पर, एक आंशिक बंडल के मूल्य की गणना करने के लिए एक मूल्य ओरेकल के लिए 2m कॉल की आवश्यकता हो सकती है; हालाँकि, यादृच्छिक नमूने द्वारा इसकी गणना लगभग उच्च संभावना के साथ की जा सकती है। यह एक यादृच्छिक एल्गोरिथ्म की ओर ले जाता है जो उच्च संभावना के साथ एक (1-1/ई)-अनुकूलता प्राप्त करता है। ऐसे मामलों में जब आंशिक बंडलों का कुशलता से मूल्यांकन किया जा सकता है (जैसे। जब उपयोगिता कार्य सेट-कवरेज कार्य होते हैं), तो एल्गोरिथ्म को निर्धारक बनाया जा सकता है। वे एक खुली समस्या के रूप में उल्लेख करते हैं कि क्या सामान्य सबमॉड्यूलर कार्यों के लिए एक निर्धारक पॉलीटाइम (1-1/ई)-एप्रॉक्सिमेशन एल्गोरिदम है। कल्याण अधिकतमकरण समस्या (एन अलग-अलग सबमॉड्यूलर कार्यों के साथ) को एक मैट्रायड बाधा के अधीन एकल सबमॉड्यूलर सेट फ़ंक्शन को अधिकतम करने की समस्या तक कम किया जा सकता हैः एम वस्तुओं और एन एजेंटों के साथ एक उदाहरण दिए जाने पर, एम * एन (एजेंट, आइटम) जोड़े के साथ एक उदाहरण का निर्माण करें, जहां प्रत्येक जोड़ी एक एजेंट को एक वस्तु के असाइनमेंट का प्रतिनिधित्व करती है। एक एकल कार्य का निर्माण करें जो जोड़े के प्रत्येक समूह को संबंधित आवंटन का कुल कल्याण प्रदान करता है। यह दिखाया जा सकता है कि, यदि सभी उपयोगिताएँ सबमॉड्यूलर हैं, तो यह कल्याणकारी कार्य भी सबमॉड्यूलर है। इस कार्य को एक विभाजन मैट्रायड बाधा के अधीन अधिकतम किया जाना चाहिए, यह सुनिश्चित करते हुए कि प्रत्येक वस्तु को अधिकतम एक एजेंट को आवंटित किया गया है। डिमान्ड ओरेकल का उपयोग करते हुए एल्गोरिदम एजेंटों की उपयोगिताओं तक पहुँचने का एक और तरीका डिमान्ड ओरेकल का उपयोग करना है (एक ओरेकल जो, एक मूल्य-वेक्टर दिए जाने पर, एजेंट का सबसे वांछित बंडल लौटाता है)। इस मॉडल मेंः डॉब्ज़िंस्की और शापिरा एक पॉलीटाइम (1-1/ई)-एप्रॉक्सिमेशन एल्गोरिथ्म प्रस्तुत करते हैं। फीज और वोंड्राक इसे कुछ छोटे सकारात्मक ε के लिए (1-1/e + ε) में सुधार करते हैं (यह उपरोक्त कठोरता परिणाम का खंडन नहीं करता है, क्योंकि कठोरता परिणाम केवल एक मान ओरेकल का उपयोग करता है; कठोरता उदाहरणों में, मांग ओरेकल को ही तेजी से कई प्रश्नों की आवश्यकता होगी)। जब एजेंटों की उपयोगिताएँ उप-योगात्मक समूह कार्य (उप-मॉड्यूलर की तुलना में अधिक सामान्य) होती हैं, तो एक सन्निकटन के लिए मूल्य प्रश्नों की एक घातीय संख्या की आवश्यकता होगी। फीज इस समस्या के एल. पी. छूट के लिए किसी भी आंशिक समाधान को कम से कम आधा आंशिक समाधान के मूल्य के कल्याण के साथ एक व्यवहार्य समाधान के लिए गोल करने का एक तरीका प्रस्तुत करता है। यह सामान्य उप-योजक अभिकर्त्ताओं के लिए 1/2-अनुकूलता देता है, और (1-1/ई)-आंशिक-उप-योजक मूल्यांकन के विशेष मामले के लिए अनुकूलता देता है। सुपरएडिटिव एजेंट जब एजेंटों की उपयोगिताएं सुपरएडिटिव सेट फंक्शन (सुपरमॉड्यूलर की तुलना में अधिक सामान्य) होती हैं, तो एक अनुमान के लिए मूल्य प्रश्नों की एक सुपर-बहुपद संख्या की आवश्यकता होगी। एकांगी एजेंट एकांगी एजेंट केवल वस्तुओं का एक विशिष्ट समूह चाहता है। प्रत्येक एकल-दिमाग वाले एजेंट i के लिए, एक मांग सेट Di है, और एक मान Vi> 0 है, जैसे कि। अर्थात्, अभिकर्ता को एक निश्चित सकारात्मक उपयोगिता तभी प्राप्त होती है जब उनके बंडल में उनकी मांग का सेट होता है। एकल-दिमाग वाले एजेंटों के साथ कल्याण अधिकतमकरण एन. पी.-कठिन है, भले ही सभी के लिए। इस मामले में, समस्या सेट पैकिंग के बराबर है, जिसे एन. पी. हार्ड के रूप में जाना जाता है। इसके अलावा, इसे किसी भी स्थिर कारक के भीतर अनुमानित नहीं किया जा सकता है (सबमॉड्यूलर एजेंटों के मामले के विपरीत)। सबसे प्रसिद्ध एल्गोरिथ्म इसे एक कारक के भीतर अनुमानित करता है। जब एजेंटों के मनमाने मोनोटोन उपयोगिता कार्य (पूरक वस्तुओं सहित) हो सकते हैं, तो किसी भी कारक के भीतर कल्याण अधिकतमकरण का अनुमान लगाना कठिन होता है। हालांकि, राज्य अंतरिक्ष खोज पर आधारित एल्गोरिदम हैं जो व्यवहार में बहुत अच्छी तरह से काम करते हैं। उपयोगिता अधिकतमकरण समस्या संदर्भ अनुकूलन एल्गोरिदम और विधियाँ भी देखें।