Welfare maximization
કલ્યાણ મહત્તમકરણ સમસ્યા એ અર્થશાસ્ત્ર અને કોમ્પ્યુટર વિજ્ઞાનમાં અભ્યાસ કરાયેલ ઓપ્ટિમાઇઝેશન સમસ્યા છે. તેનો ધ્યેય વિવિધ ઉપયોગિતા કાર્યો સાથે એજન્ટો વચ્ચે વસ્તુઓના સમૂહને વિભાજિત કરવાનો છે, જેમ કે કલ્યાણ-એજન્ટોની ઉપયોગિતાઓના સરવાળા તરીકે વ્યાખ્યાયિત-શક્ય તેટલું ઊંચું છે. બીજા શબ્દોમાં કહીએ તો, ધ્યેય ઉપયોગિતાવાદી નિયમને સંતોષતી વસ્તુની ફાળવણી શોધવાનો છે. સંયુક્ત હરાજીના સંદર્ભમાં સમકક્ષ સમસ્યાને વિજેતા નિર્ધારણ સમસ્યા કહેવામાં આવે છે. આ સંદર્ભમાં, દરેક એજન્ટ વસ્તુઓના સમૂહ પર બિડની સૂચિ રજૂ કરે છે, અને ધ્યેય એ નક્કી કરવાનું છે કે કઈ બિડ અથવા બિડ જીતવી જોઈએ, જેમ કે વિજેતા બિડનો સરવાળો મહત્તમ હોય. વ્યાખ્યાઓ m વસ્તુઓનો સમૂહ M છે, અને n એજન્ટોનો સમૂહ N છે. N માં દરેક એજન્ટ i નું ઉપયોગિતા કાર્ય હોય છે. કાર્ય વસ્તુઓના દરેક સંભવિત ઉપગણને વાસ્તવિક મૂલ્ય સોંપે છે. સામાન્ય રીતે એવું માનવામાં આવે છે કે યુટિલિટી ફંક્શન્સ એ મોનોટોન સેટ ફંક્શન્સ છે, જે સૂચવે છે. એવું પણ માનવામાં આવે છે. એકવિધતા સાથે, આ સૂચવે છે કે તમામ ઉપયોગિતાઓ બિન-નકારાત્મક છે. ફાળવણી એ વસ્તુઓને અલગ અલગ ઉપગણમાં ક્રમબદ્ધ વિભાજન છે, એજન્ટ દીઠ એક ઉપગણ, સૂચવવામાં આવે છે, જેમ કે. ફાળવણીનું કલ્યાણ એ એજન્ટોની ઉપયોગિતાઓનો સરવાળો છેઃ કલ્યાણ મહત્તમકરણની સમસ્યા છેઃ ફાળવણી X શોધો જે W (X) ને મહત્તમ કરે છે. કલ્યાણ મહત્તમકરણની સમસ્યામાં ઘણા પ્રકારો છે, જે માન્ય ઉપયોગિતા કાર્યોના પ્રકાર, અલ્ગોરિધમ ઉપયોગિતા કાર્યોને કેવી રીતે ઍક્સેસ કરી શકે છે અને માન્ય ફાળવણી પર વધારાના અવરોધો છે કે કેમ તેના આધારે છે. એડિટિવ એજન્ટમાં યુટિલિટી ફંક્શન હોય છે જે એડિટિવ સેટ ફંક્શન છેઃ દરેક એડિટિવ એજન્ટ i અને આઇટમ j માટે, એક મૂલ્ય હોય છે, જેમ કે વસ્તુઓના દરેક સેટ Z માટે. જ્યારે બધા એજન્ટો એડિટિવ હોય છે, ત્યારે કલ્યાણ મહત્તમકરણ એક સરળ બહુપદી-સમય અલ્ગોરિધમ દ્વારા કરી શકાય છેઃ દરેક વસ્તુને જે એજન્ટને આપો જેના માટે મહત્તમ છે (મનસ્વી રીતે સંબંધોને તોડવા). જ્યારે ફાળવણી પર વધારાની મર્યાદાઓ હોય ત્યારે સમસ્યા વધુ પડકારજનક બને છે. નિષ્પક્ષતાના અવરોધો વાજબી હોય તેવી તમામ ફાળવણીઓમાં કલ્યાણને મહત્તમ કરવા માંગે છે, ઉદાહરણ તરીકે, એક વસ્તુ (EF1) સુધી ઈર્ષ્યા મુક્ત, એક વસ્તુ (PROP1) સુધી પ્રમાણસર, અથવા એક વસ્તુ (EQ1) સુધી ન્યાયી. જ્યારે n ચલ હોય ત્યારે આ સમસ્યા મજબૂત રીતે NP-સખત હોય છે. કોઈપણ નિશ્ચિત n ≤ 2 માટે, સમસ્યા નબળી રીતે NP-સખત હોય છે, અને તેમાં ગતિશીલ પ્રોગ્રામિંગ પર આધારિત સ્યુડો-બહુપદી સમય અલ્ગોરિધમ હોય છે. n = 2 માટે, સમસ્યામાં સંપૂર્ણ બહુપદી-સમય અંદાજ યોજના છે. બહુપદી સમયમાં આ સમસ્યાને ઉકેલવા માટે એલ્ગોરિધમ્સ છે જ્યારે એજન્ટના થોડા પ્રકારો, વસ્તુના થોડા પ્રકારો અથવા નાના મૂલ્ય સ્તર હોય છે. આ સમસ્યાને બહુપદી સમયમાં પણ ઉકેલી શકાય છે જ્યારે એજન્ટોની એડિટિવ ઉપયોગિતાઓ દ્વિસંગી હોય છે (દરેક વસ્તુનું મૂલ્ય 0 અથવા 1 હોય છે), તેમજ સામાન્યીકૃત દ્વિસંગી તરીકે ઓળખાતી ઉપયોગિતાઓના વધુ સામાન્ય વર્ગ માટે. મેટ્રોઇડ અવરોધો ફાળવણી પર અન્ય અવરોધ એ છે કે બંડલ મેટ્રોઇડના સ્વતંત્ર સેટ હોવા જોઈએ. ઉદાહરણ તરીકે, દરેક બંડલમાં મહત્તમ k વસ્તુઓ હોવી જોઈએ, જ્યાં k એ એક નિશ્ચિત પૂર્ણાંક છે (આ એક સમાન મેટ્રોઇડને અનુરૂપ છે). અથવા, વસ્તુઓને શ્રેણીઓમાં વિભાજિત કરી શકાય છે, અને દરેક બંડલમાં દરેક શ્રેણી સીમાંથી મહત્તમ કેસી વસ્તુઓ હોવી આવશ્યક છે (આ પાર્ટીશન મેટ્રોઇડને અનુરૂપ છે). સામાન્ય રીતે, દરેક એજન્ટ માટે એક અલગ મેટ્રોઇડ હોઈ શકે છે, અને ફાળવણીમાં દરેક એજન્ટને એક સબસેટ ઝી આપવો આવશ્યક છે જે તેમના પોતાના મેટ્રોઇડનો સ્વતંત્ર સમૂહ છે. વિજાતીય મેટ્રોઇડ અવરોધો હેઠળ એડિટિવ ઉપયોગિતાઓ સાથે કલ્યાણ મહત્તમકરણ બહુપદી સમયમાં કરી શકાય છે, ભારિત મેટ્રોઇડ આંતરછેદ સમસ્યામાં ઘટાડો કરીને. કુલ-અવેજી એજન્ટો કુલ-અવેજી ઉપયોગિતાઓ એડિટિવ ઉપયોગિતાઓ કરતાં વધુ સામાન્ય છે. કુલ-અવેજી એજન્ટો સાથે કલ્યાણ મહત્તમકરણ બહુપદી સમયમાં કરી શકાય છે. આનું કારણ એ છે કે, કુલ-અવેજી એજન્ટો સાથે, વોલ્રાસિયન સંતુલન હંમેશા અસ્તિત્વમાં રહે છે, અને તે ઉપયોગિતાઓનો સરવાળો મહત્તમ કરે છે. બહુપદી સમયમાં વાલ્રાસિયન સંતુલન મળી શકે છે. સબમોડ્યુલર એજન્ટ એક સબમોડ્યુલર એજન્ટમાં યુટિલિટી ફંક્શન હોય છે જે સબમોડ્યુલર સેટ ફંક્શન છે. આનો અર્થ એ છે કે એજન્ટની ઉપયોગિતા ઘટી રહી છે. સબમોડ્યુલર ઉપયોગિતાઓ કુલ-અવેજી ઉપયોગિતાઓ કરતાં વધુ સામાન્ય છે. સબમોડ્યુલર એજન્ટો સાથે કઠોરતા કલ્યાણ મહત્તમકરણ એન. પી.-હાર્ડ છે. વધુમાં, જ્યાં સુધી P = NP ન હોય ત્યાં સુધી તેને (1-1/e) ≈ 0.632 કરતાં વધુ સારા પરિબળ તરીકે અંદાજિત કરી શકાતો નથી. વધુમાં, (1-1/e) અંદાજ કરતાં વધુ સારા માટે મૂલ્ય ઓરેકલ માટે ઘાતાંકીય સંખ્યાના પ્રશ્નોની જરૂર પડશે, પછી ભલે તે P = NP હોય. લોભી અલ્ગોરિધમ મહત્તમ કલ્યાણને નીચેના બહુપદી-સમય લોભી અલ્ગોરિધમ દ્વારા અંદાજિત કરી શકાય છેઃ X1 = X2 =. = Xn = ખાલી શરૂ કરો. દરેક વસ્તુ માટે g (મનસ્વી ક્રમમાં): ગણતરી કરો, દરેક એજિન i માટે, g માટે તેની સીમાંત ઉપયોગિતા, આ રીતે વ્યાખ્યાયિત થયેલ છેઃ ui (xi + g)-xi (xi). સૌથી મોટી સીમાંત ઉપયોગિતા ધરાવતા એજન્ટને આઇટમ જી આપો. લેહમેન, લેહમેન અને નિસાન સાબિત કરે છે કે લોભી અલ્ગોરિધમ 1/2-પરિબળ અંદાજ શોધે છે (તેઓ નોંધે છે કે આ પરિણામ ફિશર, નેમહાઉઝર અને વોલ્સીના મેટ્રોઇડ પર એક જ સબમોડ્યુલર મૂલ્યાંકનના મહત્તમકરણના પરિણામને અનુસરે છે). સાબિતીનો વિચાર નીચે મુજબ છે. ધારો કે અલ્ગોરિધમ કોઈ એજન્ટ i ને વસ્તુ g ફાળવે છે. આ કલ્યાણમાં અમુક રકમ v નો ફાળો આપે છે, જે તે સમયે i માટે g ની સીમાંત ઉપયોગિતા છે. ધારો કે, શ્રેષ્ઠ ઉકેલમાં, g અન્ય એજન્ટને આપવો જોઈએ, કહો કે k. જો આપણે g ને i થી k તરફ ખસેડીએ તો કલ્યાણ કેવી રીતે બદલાય છે તે ધ્યાનમાં લોઃ k ની ઉપયોગિતા તેની g ની સીમાંત ઉપયોગિતા દ્વારા વધે છે, જે લોભી પસંદગી દ્વારા મહત્તમ v છે. i ના બાકીના બંડલની સીમાંત ઉપયોગિતા મહત્તમ v વધે છે. આ સબમોડ્યુલરિટીથી અનુસરે છેઃ g ની સીમાંત ઉપયોગિતા, જ્યારે બાકીના બંડલમાં ઉમેરવામાં આવે છે, જ્યારે અલ્ગોરિધમ તેની પ્રક્રિયા કરે છે ત્યારે તેની સીમાંત ઉપયોગિતા કરતા વધારે ન હોઈ શકે. તેથી, અલ્ગોરિધમ કલ્યાણમાં v ના દરેક યોગદાન માટે, શ્રેષ્ઠ કલ્યાણમાં સંભવિત યોગદાન મહત્તમ 2v હોઈ શકે છે. તેથી, શ્રેષ્ઠ કલ્યાણ એલ્ગોરિધમ કલ્યાણ કરતાં વધુમાં વધુ 2 ગણું છે. લોભી અલ્ગોરિધમ માટે 2 નું પરિબળ ચુસ્ત છે. ઉદાહરણ તરીકે, ધારો કે ત્યાં બે વસ્તુઓ x, y છે અને મૂલ્યાંકન છેઃ શ્રેષ્ઠ ફાળવણી એલિસઃ {y}, જ્યોર્જઃ {x}, કલ્યાણ 2 સાથે છે. પરંતુ જો લોભી અલ્ગોરિધમ પહેલા x ફાળવે છે, તો તે તેને એલિસને ફાળવી શકે છે. પછી, Y કેવી રીતે ફાળવવામાં આવે છે તે ધ્યાનમાં લીધા વિના, કલ્યાણ માત્ર 1 છે. મૂલ્ય ઓરેકલનો ઉપયોગ કરતા અલ્ગોરિધમ્સ એ મૂલ્ય ઓરેકલ એ એક ઓરેકલ છે, જે વસ્તુઓનો સમૂહ આપવામાં આવે તો એજન્ટનું મૂલ્ય આ સમૂહને પરત કરે છે. આ મોડેલમાંઃ ડોબ્ઝિન્સ્કી અને શાપિરા પોલીટાઇમ-એપ્રોક્સિમેશન અલ્ગોરિધમ રજૂ કરે છે, અને ખાસ કેસ માટે (1-1/e) ≈ 0.632-approximation અલ્ગોરિધમ રજૂ કરે છે જેમાં એજન્ટોની ઉપયોગિતાઓ સેટ-કવરેજ કાર્યો છે. વોન્ડ્રાક અને કેલિનેસ્કુ, ચેકુરી, પાલ અને વોન્ડ્રાક એક રેન્ડમાઇઝ્ડ પોલીટાઇમ અલ્ગોરિધમ રજૂ કરે છે જે ઉચ્ચ સંભાવના સાથે (1-1/ઇ)-એપ્રોક્સિમેશન શોધે છે. તેમનું અલ્ગોરિધમ સતત-લોભી અલ્ગોરિધમનો ઉપયોગ કરે છે-એક અલ્ગોરિધમ જે લોભી દિશામાં (ઢાળ વંશની જેમ) અપૂર્ણાંક બંડલ (એક બંડલ જેમાં દરેક વસ્તુનો અપૂર્ણાંક pj હોય છે) વિસ્તરે છે. તેમના અલ્ગોરિધમને અપૂર્ણાંક બંડલના મૂલ્યની ગણતરી કરવાની જરૂર છે, જેને બંડલના અપેક્ષિત મૂલ્ય તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જ્યારે દરેક વસ્તુ જે સંભાવના pj સાથે સ્વતંત્ર રીતે પસંદ કરવામાં આવે છે. સામાન્ય રીતે, અપૂર્ણાંક બંડલના મૂલ્યની ગણતરી કરવા માટે મૂલ્ય ઓરેકલ પર 2 મી કોલની જરૂર પડી શકે છે; જો કે, રેન્ડમ સેમ્પલિંગ દ્વારા તેની ગણતરી લગભગ ઉચ્ચ સંભાવના સાથે કરી શકાય છે. આ રેન્ડમાઇઝ્ડ અલ્ગોરિધમ તરફ દોરી જાય છે જે ઉચ્ચ સંભાવના સાથે a (1-1/e)-એપ્રોક્સિમેશન પ્રાપ્ત કરે છે. એવા કિસ્સાઓમાં જ્યારે અપૂર્ણાંક બંડલ્સનું અસરકારક રીતે મૂલ્યાંકન કરી શકાય છે (દા. ત. જ્યારે યુટિલિટી ફંક્શન્સ સેટ-કવરેજ ફંક્શન્સ હોય), ત્યારે અલ્ગોરિધમને નિર્ધારક બનાવી શકાય છે. તેઓ એક ખુલ્લી સમસ્યા તરીકે ઉલ્લેખ કરે છે, શું સામાન્ય સબમોડ્યુલર કાર્યો માટે નિર્ધારક પોલીટાઇમ (1-1/ઇ)-એપ્રોક્સિમેશન અલ્ગોરિધમ છે. કલ્યાણ મહત્તમકરણની સમસ્યાને (n વિવિધ સબમોડ્યુલર કાર્યો સાથે) મેટ્રોઇડ અવરોધને આધિન એક સબમોડ્યુલર સમૂહ કાર્યને મહત્તમ કરવાની સમસ્યામાં ઘટાડી શકાય છેઃ m વસ્તુઓ અને n એજન્ટો સાથે એક ઉદાહરણ આપવામાં આવે તો, m * n (એજન્ટ, આઇટમ) જોડીઓ સાથે એક ઉદાહરણ બનાવો, જ્યાં દરેક જોડી એજન્ટને આઇટમની સોંપણીનું પ્રતિનિધિત્વ કરે છે. એક જ કાર્યની રચના કરો જે જોડીના દરેક સમૂહને અનુરૂપ ફાળવણીનું કુલ કલ્યાણ સોંપે છે. તે દર્શાવી શકાય છે કે, જો બધી ઉપયોગિતાઓ સબમોડ્યુલર હોય, તો આ કલ્યાણ કાર્ય પણ સબમોડ્યુલર છે. દરેક વસ્તુ મહત્તમ એક એજન્ટને ફાળવવામાં આવી છે તેની ખાતરી કરીને, પાર્ટીશન મેટ્રોઇડ અવરોધને આધિન આ કાર્યને મહત્તમ કરવું જોઈએ. ડિમાન્ડ ઓરેકલનો ઉપયોગ કરીને અલ્ગોરિધમ્સ એજન્ટોની ઉપયોગિતાઓને ઍક્સેસ કરવાની બીજી રીત ડિમાન્ડ ઓરેકલનો ઉપયોગ કરે છે (એક ઓરેકલ, જે પ્રાઇસ-વેક્ટર આપવામાં આવે છે, એજન્ટનું સૌથી ઇચ્છિત બંડલ પરત કરે છે). આ મોડેલમાંઃ ડોબ્ઝિન્સ્કી અને શાપિરા પોલીટાઇમ (1-1/ઇ)-એપ્રોક્સિમેશન અલ્ગોરિધમ રજૂ કરે છે. કેટલાક નાના હકારાત્મક ε માટે ફીજ અને વોન્ડ્રાક આને સુધારીને (1-1/e + ε) કરે છે (આ ઉપરોક્ત કઠિનતાના પરિણામ સાથે વિરોધાભાસી નથી, કારણ કે કઠિનતાનું પરિણામ માત્ર મૂલ્ય ઓરેકલનો ઉપયોગ કરે છે; કઠિનતાના ઉદાહરણોમાં, માંગ ઓરેકલને જ ઝડપથી ઘણા પ્રશ્નોની જરૂર પડશે). સબએડિટિવ એજન્ટો જ્યારે એજન્ટોની ઉપયોગિતાઓ સબએડિટિવ સેટ ફંક્શન્સ (સબમોડ્યુલર કરતાં વધુ સામાન્ય) હોય, ત્યારે અંદાજ માટે મૂલ્ય પ્રશ્નોની ઘાતાંકીય સંખ્યાની જરૂર પડશે. ફીજ આ સમસ્યાના એલ. પી. છૂટછાટ માટેના કોઈપણ અપૂર્ણાંક ઉકેલને ઓછામાં ઓછા અડધા અપૂર્ણાંક ઉકેલના મૂલ્ય સાથે કલ્યાણ સાથે શક્ય ઉકેલ માટે ગોળાકાર કરવાની રીત રજૂ કરે છે. આ સામાન્ય સબએડિટિવ એજન્ટો માટે 1/2-એપ્રોક્સિમેશન આપે છે, અને અપૂર્ણાંક-સબએડિટિવ મૂલ્યાંકનના વિશેષ કેસ માટે (1-1/ઇ)-એપ્રોક્સિમેશન આપે છે. સુપરએડિટિવ એજન્ટો જ્યારે એજન્ટોની ઉપયોગિતાઓ સુપરએડિટિવ સમૂહ કાર્યો (સુપરમોડ્યુલર કરતાં વધુ સામાન્ય) હોય, ત્યારે અંદાજ માટે મૂલ્ય પ્રશ્નોની સુપર-બહુપદી સંખ્યાની જરૂર પડશે. એક મનનો એજન્ટ એક મનનો એજન્ટ માત્ર વસ્તુઓનો ચોક્કસ સમૂહ ઇચ્છે છે. દરેક એકલ-વિચારશીલ એજન્ટ i માટે, માંગ કરેલ સમૂહ Di છે, અને મૂલ્ય Vi> 0 છે, જેમ કે. એટલે કે, એજન્ટને નિશ્ચિત હકારાત્મક ઉપયોગિતા પ્રાપ્ત થાય છે જો અને માત્ર ત્યારે જ જો તેમના બંડલમાં તેમની માંગ કરેલ સેટ હોય. એકલ વિચારધારાવાળા એજન્ટો સાથે કલ્યાણ મહત્તમકરણ એ એન. પી.-હાર્ડ છે, ભલે તે બધા માટે હોય. આ કિસ્સામાં, સમસ્યા સેટ પેકિંગની સમકક્ષ છે, જે એન. પી. હાર્ડ તરીકે ઓળખાય છે. વધુમાં, તેને કોઈ પણ સ્થિર પરિબળમાં અંદાજિત કરી શકાતો નથી (સબમોડ્યુલર એજન્ટોના કિસ્સામાં તેનાથી વિપરીત). સૌથી જાણીતું અલ્ગોરિધમ તેને એક પરિબળમાં અંદાજિત કરે છે. સામાન્ય એજન્ટો જ્યારે એજન્ટો મનસ્વી મોનોટોન ઉપયોગિતા કાર્યો (પૂરક વસ્તુઓ સહિત) ધરાવી શકે છે, ત્યારે કલ્યાણ મહત્તમકરણ કોઈપણ માટે પરિબળમાં અંદાજિત કરવું મુશ્કેલ છે. જો કે, સ્ટેટ સ્પેસ સર્ચ પર આધારિત એલ્ગોરિધમ્સ છે જે વ્યવહારમાં ખૂબ જ સારી રીતે કામ કરે છે. ઉપયોગિતા મહત્તમકરણ સમસ્યા સંદર્ભો ઓપ્ટિમાઇઝેશન અલ્ગોરિધમ્સ અને પદ્ધતિઓ પણ જુઓ.