Fair allocation of items and money
વસ્તુઓ અને નાણાંની વાજબી ફાળવણી એ વાજબી વસ્તુની ફાળવણીની સમસ્યાઓનો એક વર્ગ છે, જેમાં ફાળવણી પ્રક્રિયા દરમિયાન, કેટલાક સહભાગીઓ પાસેથી નાણાં આપવાનું અથવા લેવાનું શક્ય છે. નાણાં વિના, અવિભાજ્ય વસ્તુઓની વાજબી રીતે ફાળવણી કરવી અશક્ય હોઈ શકે છે. ઉદાહરણ તરીકે, જો એક વસ્તુ અને બે લોકો હોય, અને વસ્તુ સંપૂર્ણપણે તેમાંથી એકને આપવી જ જોઇએ, તો ફાળવણી બીજા માટે અયોગ્ય રહેશે. નાણાકીય ચૂકવણીઓ નીચે વર્ણવ્યા મુજબ નિષ્પક્ષતા પ્રાપ્ત કરવાનું શક્ય બનાવે છે. બે એજન્ટો અને એક વસ્તુ બે એજન્ટો અને એક વસ્તુ સાથે, નીચેના સરળ અલ્ગોરિધમનો ઉપયોગ કરીને નિષ્પક્ષતા પ્રાપ્ત કરવી શક્ય છે (જે કટ એન્ડ ચૉઇસનો એક પ્રકાર છે): એલિસ કહે છે કે તે વસ્તુ માટે કિંમત પી ચૂકવવા તૈયાર છે. જ્યોર્જ પસંદ કરે છે કે શું વસ્તુ લેવી અને પી ચૂકવવી, અથવા વસ્તુ એલિસ પર છોડી દેવી જેથી એલિસ પી ચૂકવે. આ અલ્ગોરિધમ ધારે છે કે એજન્ટો પાસે અર્ધરેખીય ઉપયોગિતાઓ છે, એટલે કે, તેમની ઉપયોગિતા વસ્તુઓનું મૂલ્ય અને તેમની પાસેની રકમ છે. જો જ્યોર્જ વિચારે કે એલિસની કિંમત ઓછી છે (તે પી કરતાં વધુ ચૂકવવા તૈયાર છે), તો તે વસ્તુ લે છે અને પી ચૂકવે છે, અને તેની ઉપયોગિતા હકારાત્મક છે, તેથી તે એલિસની ઈર્ષ્યા કરતો નથી. એલિસ પણ જ્યોર્જને ઈર્ષ્યા કરતી નથી કારણ કે તેની ઉપયોગિતા-તેની નજરમાં-0 છે. તેવી જ રીતે, જો જ્યોર્જ વિચારે કે એલિસની કિંમત વધારે છે (તે પી અથવા વધુ ચૂકવવા તૈયાર છે), તો તે વસ્તુ એલિસને છોડી દે છે અને ઈર્ષ્યા કરતો નથી, કારણ કે તેની આંખોમાં એલિસની ઉપયોગિતા નકારાત્મક છે. ચૂકવેલ નાણાં પી પછીથી ખેલાડીઓ વચ્ચે સમાન રીતે વહેંચી શકાય છે, કારણ કે સમાન નાણાકીય સ્થાનાંતરણ સંબંધિત ઉપયોગિતાઓને અસર કરતું નથી. પછી, અસરકારક રીતે, ખરીદ એજન્ટ વેચાણ એજન્ટને પી/2 ચૂકવે છે. દરેક એજન્ટની કુલ ઉપયોગિતા વસ્તુ માટે તેની/તેણીની ઉપયોગિતાનો ઓછામાં ઓછો અડધો ભાગ છે. જો એજન્ટો પાસે જુદા જુદા હક હોય, તો ચૂકવેલ નાણાંને ભાગીદારો વચ્ચે તેમના હકના પ્રમાણમાં વહેંચવા જોઈએ. આ સરળ વિચારને બેથી વધુ ખેલાડીઓ અને વધુ જટિલ સેટિંગ્સ સુધી વિસ્તારતા વિવિધ કાર્યો છે. આ કૃતિઓમાં નિષ્પક્ષતાના મુખ્ય માપદંડ ઈર્ષ્યા-સ્વતંત્રતા છે. વધુમાં, કેટલીક કૃતિઓ એવી વ્યવસ્થાને ધ્યાનમાં લે છે જેમાં પરોપકારી તૃતીય પક્ષ ફાળવણીને સબસિડી આપવા તૈયાર હોય, પરંતુ ઈર્ષ્યા-સ્વતંત્રતાને આધિન સબસિડીની રકમને ઘટાડવા માંગે છે. આ સમસ્યાને લઘુતમ-સબસિડી ઈર્ષ્યા-મુક્ત ફાળવણી કહેવામાં આવે છે. યુનિટ-ડિમાન્ડ એજન્ટો યુનિટ-ડિમાન્ડ એજન્ટો મહત્તમ એક જ વસ્તુમાં રસ ધરાવે છે. ભાડાની સંવાદિતા આ સેટિંગનો એક ખાસ કેસ એ છે કે જ્યારે ભાડૂતો વચ્ચે એપાર્ટમેન્ટમાં ઓરડાઓનું વિભાજન કરવામાં આવે છે. તે ત્રણ જરૂરિયાતો દ્વારા વર્ગીકૃત થયેલ છેઃ (એ) એજન્ટોની સંખ્યા વસ્તુઓની સંખ્યા જેટલી હોય છે, (બી) દરેક એજન્ટને બરાબર એક વસ્તુ (ઓરડો) મળવી જોઈએ, (સી) એજન્ટો દ્વારા ચૂકવવામાં આવેલી કુલ રકમ નિશ્ચિત અચળાંક જેટલી હોવી જોઈએ, જે કુલ એપાર્ટમેન્ટ ભાડાનું પ્રતિનિધિત્વ કરે છે. આને ભાડાની સંવાદિતા સમસ્યા તરીકે ઓળખવામાં આવે છે. વધુ સામાન્ય સેટિંગ્સ સામાન્ય રીતે, અર્થશાસ્ત્રના સાહિત્યમાં, એવું માનવું સામાન્ય છે કે દરેક એજન્ટ બંડલ પર ઉપયોગિતા કાર્ય ધરાવે છે (બંડલ એ ઑબ્જેક્ટની જોડી અને ચોક્કસ રકમ છે). ઉપયોગિતા કાર્ય સતત હોવું જોઈએ અને નાણાંમાં વધવું જોઈએ. તે નાણામાં રેખીય હોવું જરૂરી નથી, પરંતુ "આર્કિમિડીયન" હોવું જરૂરી છે, એટલે કે, ત્યાં અમુક મૂલ્ય V અસ્તિત્વમાં છે, જેમ કે, દરેક બે પદાર્થો j અને k માટે, પદાર્થ j વત્તા V ની ઉપયોગિતા પદાર્થ k ની ઉપયોગિતા કરતાં મોટી હોવી જોઈએ (વૈકલ્પિક રીતે, મુક્ત રીતે પદાર્થ j મેળવવાની ઉપયોગિતા પદાર્થ k મેળવવાની અને V ચૂકવવાની ઉપયોગિતા કરતાં મોટી છે). ક્વાસિલીનિયર ઉપયોગિતા એ આર્કિમિડીયન ઉપયોગિતાનો એક વિશેષ કેસ છે, જેમાં V એ બે પદાર્થો વચ્ચેનો સૌથી મોટો મૂલ્ય-તફાવત (એક જ એજન્ટ માટે) છે. સ્વેન્સને સૌપ્રથમ સાબિત કર્યું કે, જ્યારે બધા એજન્ટો આર્કિમિડીયન હોય છે, ત્યારે ઈર્ષ્યા-મુક્ત ફાળવણી અસ્તિત્વમાં છે અને પેરેટો-શ્રેષ્ઠ છે. ડીમાંજ, ગેલ અને સોટોમાયરે કુદરતી ચડતી હરાજી દર્શાવી હતી જે એકમ માંગ એજન્ટો માટે નાણાકીય ચૂકવણીનો ઉપયોગ કરીને ઈર્ષા મુક્ત ફાળવણી પ્રાપ્ત કરે છે. જ્યારે કુલ નાણાં દાન (એન-1) વી કરતાં વધારે હોય ત્યારે માસ્કિને પેરેટો-શ્રેષ્ઠ ઈર્ષ્યા-મુક્ત ફાળવણીનું અસ્તિત્વ સાબિત કર્યું. પુરાવા સ્પર્ધાત્મક સંતુલનનો ઉપયોગ કરે છે. નોંધ લો કે (n-1) V ની સબસિડીની જરૂર પડી શકે છેઃ જો બધા એજન્ટો એક વસ્તુને V પર અને અન્ય વસ્તુઓને 0 પર મૂલ્ય આપે છે, તો ઈર્ષ્યા-સ્વતંત્રતાને દરેક એજન્ટ માટે V ની સબસિડીની જરૂર છે જે વસ્તુ પ્રાપ્ત કરતું નથી. ટેડેનુમા અને થોમસન ઈર્ષ્યા-મુક્ત ફાળવણીના નિયમોના કેટલાક સુસંગતતા ગુણધર્મોનો અભ્યાસ કરે છે. એરેગોન્સ ઈર્ષ્યા-સ્વતંત્રતા માટે જરૂરી સબસિડીની લઘુતમ રકમની લાક્ષણિકતા ધરાવે છે. આ લઘુતમ સબસિડીને પ્રાપ્ત કરતી ફાળવણી લગભગ અનન્ય છેઃ એજન્ટો સાથે વસ્તુઓને જોડવાનો એક જ રસ્તો છે, અને તમામ એજન્ટો તમામ લઘુતમ-સબસિડની ફાળવણીમાં ઉદાસીન છે. તે અલકન, ડિમાંજ અને ગેલના "મની-રૉલશિયન સોલ્યુશન" તરીકે ઓળખાતા ઉકેલ સાથે સુસંગત છે. તે બહુપદી સમયમાં, મહત્તમ-વજન મેળ શોધીને અને પછી ચોક્કસ પ્રેરિત આલેખમાં ટૂંકા માર્ગો શોધીને મળી શકે છે. Klijn સમાન સેટિંગ માટે અન્ય બહુપદી-સમય અલ્ગોરિધમ રજૂ કરે છે. તેમનું અલ્ગોરિધમ સાઇડ-પેમેન્ટના પોલીટોપનો ઉપયોગ કરે છે જે આપેલ ફાળવણીને ઈર્ષા-મુક્ત બનાવે છેઃ આ પોલીટોપ નોન એમ્પ્ટી છે જો મૂળ ફાળવણી પેરેટો-કાર્યક્ષમ હોય. દિશાહીન ઈર્ષ્યા આલેખનું જોડાણ આ પોલીટોપનાં આત્યંતિક બિંદુઓને દર્શાવે છે. આ અત્યંત ઈર્ષ્યા-મુક્ત ફાળવણી શોધવા માટેની પદ્ધતિ સૂચવે છે. એડિટિવ એજન્ટોને ઘણી વસ્તુઓ મળી શકે છે, તેથી ફાળવણીની સમસ્યા વધુ જટિલ બની જાય છે-ત્યાં ઘણી વધુ સંભવિત ફાળવણીઓ છે. નેસ્ટરની હરાજી વસ્તુઓ અને નાણાંની વાજબી ફાળવણી માટેની પ્રથમ પ્રક્રિયાની શોધ બ્રોનિસ્લો નેસ્ટર દ્વારા કરવામાં આવી હતી અને હ્યુગો સ્ટેઇનહાઉસ દ્વારા પ્રકાશિત કરવામાં આવી હતી. આ હરાજી નીચે મુજબ કામ કરે છે, દરેક વસ્તુ માટે અલગથીઃ દરેક એજન્ટ વસ્તુ પર બોલી રજૂ કરે છે. આ વસ્તુ સૌથી વધુ બોલી લગાવનારને આપવામાં આવે છે (મનસ્વી રીતે સંબંધ તોડીને). વિજેતા તેની બોલીમાંથી (એન-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) એમવીની સબસિડી સાથે હંમેશા ઈર્ષા મુક્ત ફાળવણી અસ્તિત્વમાં રહે છે. આ સબસિડી જરૂરી હોઈ શકે છે, ઉદાહરણ તરીકે જ્યારે બધી વસ્તુઓ એકસરખી હોય અને એક એજન્ટને તે બધી મળે. ફાળવણી પસંદ કરી શકાય છે. આ કિસ્સામાં, (n-1) V ની સબસિડી નીચેના કિસ્સાઓમાં પૂરતી છેઃ જ્યારે એજન્ટોના મૂલ્યાંકન દ્વિસંગી (0 અથવા 1) હોય. પછી, કોઈપણ મહત્તમ-ઉત્પાદન ફાળવણી અથવા લેક્સિમિન-શ્રેષ્ઠ ફાળવણી માટે મહત્તમ (એન-1) વી સબસિડીની જરૂર પડે છે, અને તે બહુપદી સમયમાં મળી શકે છે. ઇએફ હાંસલ કરવા માટે જરૂરી લઘુતમ સબસિડીની ગણતરી કરવી એ ઈર્ષા-મુક્ત ફાળવણીના અસ્તિત્વને ચકાસવા માટે ટ્યુરિંગ-સમકક્ષ છે, જે બિન-નકામી ફાળવણી સુધી મર્યાદિત હોય ત્યારે એનપી-હાર્ડ હોય છે. જ્યારે બધા એજન્ટો સમાન એડિટિવ વેલ્યુએશન ધરાવે છે. પછી, દરેક ફાળવણી ઈર્ષા-મુક્ત છે. મહત્તમ (એન-1) વી સબસિડીની જરૂર હોય તેવી ફાળવણી બહુપદી સમયમાં મળી શકે છે. ફાળવણી સબસિડીને ઘટાડે છે જો તે કોઈપણ એજન્ટની મહત્તમ ઉપયોગિતાને ઘટાડે છે. આવી ફાળવણીની ગણતરી કરવી એ એન. પી.-હાર્ડ છે, અને તેને મહત્તમ-ઉત્પાદન અલ્ગોરિધમ દ્વારા ઉકેલી શકાય છે. જ્યારે બે એજન્ટો હોય છે, ત્યારે ચોક્કસ એજન્ટ ઓર્ડર સાથે રાઉન્ડ-રોબિન આઇટમની ફાળવણી એવી ફાળવણી શોધે છે જે મહત્તમ વી. બ્રસ્ટલ, ડિપ્પલ, નારાયણ, સુઝુકી અને વેટ્ટા પર સબસિડી સાથે ઈર્ષા-મુક્ત હોય છે જે જરૂરી સબસિડી પર ઉપલી મર્યાદામાં સુધારો કરે છેઃ એડિટિવ વેલ્યુએશન સાથે, એજન્ટ દીઠ મહત્તમ વી અને સામાન્ય રીતે મહત્તમ (એન-1) વીની સબસિડી હંમેશા પૂરતી હોય છે. વધુમાં, આ મર્યાદાને પ્રાપ્ત કરવા માટે એક ફાળવણી છે જે EF1 અને સંતુલિત પણ છે (ફાળવવામાં આવેલા બંડલની મુખ્ય બાબતો વધુમાં વધુ એક વસ્તુથી અલગ પડે છે). તેની ગણતરી બહુપદી સમયમાં એક સરળ અલ્ગોરિધમ દ્વારા કરી શકાય છેઃ એજન્ટો-ઓબ્જેક્ટો દ્વિદલીય આલેખમાં પુનરાવર્તિત રીતે મહત્તમ-વજન મેળ શોધો. સામાન્ય મોનોટોન મૂલ્યાંકન સાથે, એજન્ટ દીઠ વધુમાં વધુ 2 (એન-1) વી અને વધુમાં વધુ ઓ (એન2વી) ની સબસિડી હંમેશા પૂરતી હોય છે. ખાસ કરીને, જરૂરી સબસિડી વસ્તુઓની સંખ્યા પર આધારિત નથી. આ સીમા પ્રાપ્ત કરતી ફાળવણીની ગણતરી મૂલ્ય-પ્રશ્નોનો ઉપયોગ કરીને બહુપદી સમયમાં કરી શકાય છે. કેરેજિયાનિસ અને આયોનિડિસ સબસિડી ઘટાડવાની ગણતરીની સમસ્યાનો અભ્યાસ કરે છેઃ એજન્ટોની સતત સંખ્યા માટે, તેઓ એક અલ્ગોરિધમ રજૂ કરે છે જે કોઈપણ જરૂરી ચોકસાઈમાં સબસિડીની લઘુતમ રકમનો અંદાજ કાઢે છે. કોઈપણ ε> 0 માટે, તે વધુમાં વધુ સબસિડી સાથે ફાળવણી શોધે છે, જ્યાં S એ મહત્તમ મૂલ્ય છે જે એજન્ટ તમામ વસ્તુઓને સોંપે છે. અલ્ગોરિધમ ગતિશીલ પ્રોગ્રામિંગનો ઉપયોગ કરે છે અને સમયસર ચાલે છે. એજન્ટોની ચલ સંખ્યા માટે, એક તુચ્છ અંદાજ અલ્ગોરિધમ પ્રાપ્ત થાય છે. જો કે, n થી સ્વતંત્ર અંદાજ પરિબળ પ્રાપ્ત કરવું મુશ્કેલ છેઃ સબસિડી સાથે ફાળવણીની ગણતરી કરવી NP-મુશ્કેલ છે. તેનો પુરાવો મહત્તમ 3-પરિમાણીય મેળના પ્રતિબંધિત પ્રકારમાંથી ઘટાડો કરીને છે, જેમાં દરેક શિરોબિંદુ બરાબર બે વાર દેખાય છે. નોંધ લો કે જો દરેક એજન્ટ પાસેથી નિશ્ચિત રકમ લેવામાં આવે તો સબસિડી સાથે ઈર્ષા મુક્ત ફાળવણી ઈર્ષા મુક્ત રહે છે. તેથી, સબસિડી વિનાની ફાળવણી શોધવા માટે સમાન પદ્ધતિઓનો ઉપયોગ કરી શકાય છેઃ દરેક એજન્ટ પાસેથી સરેરાશ ચુકવણી વસૂલવાથી ઈર્ષ્યા-મુક્ત ફાળવણી મળે છે જે બજેટ-સંતુલિત પણ હોય છે. સબસિડીને ઓછી કરવી એ કોઈપણ વ્યક્તિગત એજન્ટે ચૂકવવાની મહત્તમ રકમને ઓછી કરવા સમાન છે. નકારાત્મક સબસિડી (કર) નો ઉપયોગ કરવો પણ શક્ય છે, જ્યારે તમામ એજન્ટોએ ચૂકવવાની કુલ રકમને ઘટાડી શકાય છે. વધારાની પ્રક્રિયાઓ અલકન, ડિમાંજ અને ગેલ દર્શાવે છે કે જ્યારે નાણાંની રકમ પૂરતી મોટી હોય ત્યારે ઈર્ષા મુક્ત ફાળવણી હંમેશા અસ્તિત્વમાં રહે છે. જ્યારે વસ્તુઓનું નકારાત્મક મૂલ્યાંકન હોય ત્યારે પણ આ સાચું છે. મીર્ટન્સ, પોટર્ઝ અને રેઇજનિયર્સ મૂલ્યાંકન પર ખૂબ જ હળવી ધારણાઓ હેઠળ ઈર્ષ્યા-મુક્ત અને પેરેટો-શ્રેષ્ઠ ફાળવણીના અસ્તિત્વને સાબિત કરે છે (જરૂરી નથી કે અર્ધરેખીય હોય). કાવાલો ઈર્ષ્યા-સ્વતંત્રતા, પ્રમાણસરતા અને કાર્યક્ષમતા (કલ્યાણ) ના પરંપરાગત દ્વિસંગી માપદંડને 0 અને 1 ની વચ્ચેના ડિગ્રીના માપદંડમાં સામાન્ય બનાવે છે. કેનોનિકલ ફેર ડિવિઝન સેટિંગ્સમાં, કોઈપણ ફાળવણી-કાર્યક્ષમ પદ્ધતિ હેઠળ સૌથી ખરાબ-કેસ કલ્યાણ દર 0 છે અને અપ્રમાણસરતા દર 1 છે; બીજા શબ્દોમાં કહીએ તો, સૌથી ખરાબ-કેસ પરિણામો શક્ય તેટલા ખરાબ છે. તે એક એવી પદ્ધતિ શોધે છે જે વાજબી વિભાજન સેટિંગ્સના સ્પેક્ટ્રમમાં ઉચ્ચ કલ્યાણ, ઓછી ઈર્ષ્યા અને અપેક્ષાઓમાં ઓછી અસમાનતાને પ્રાપ્ત કરે છે. વીસીજી મિકેનિઝમ સંતોષકારક ઉમેદવાર નથી, પરંતુ બેઇલી અને કેવાલોની પુનઃવિતરણ મિકેનિઝમ છે. સંબંધિત સમસ્યાઓ ઈર્ષ્યા-મુક્ત કિંમત જ્યારે ખરીદદારોને વસ્તુઓ વેચવામાં આવે છે, ત્યારે ચૂકવણીનો સરવાળો અગાઉથી નક્કી કરવામાં આવતો નથી, અને ધ્યેય એ છે કે ઈર્ષ્યા-સ્વતંત્રતાને આધિન વિક્રેતાની આવક અથવા સામાજિક કલ્યાણને મહત્તમ બનાવવું. વધુમાં, વસ્તુઓની સંખ્યા એજન્ટોની સંખ્યા કરતાં અલગ હોઈ શકે છે, અને કેટલીક વસ્તુઓ કાઢી નાખવામાં આવી શકે છે. આને ઈર્ષ્યા-મુક્ત કિંમત નિર્ધારણ સમસ્યા તરીકે ઓળખવામાં આવે છે. બહુપરીમાણીય ઉદ્દેશો ઘણીવાર, નિષ્પક્ષતા ઉપરાંત કેટલાક અન્ય ઉદ્દેશો પ્રાપ્ત કરવા પડે છે. ઉદાહરણ તરીકે, એજન્ટોને કાર્યો સોંપતી વખતે, ઈર્ષ્યા ટાળવી અને મેકસ્પેન (-છેલ્લા એજન્ટનો પૂર્ણ થવાનો સમય) ઘટાડવું બંને જરૂરી છે. મુઆલેમ ઈર્ષ્યા-સ્વતંત્રતાની બાંયધરી સાથે ઓપ્ટિમાઇઝેશન સમસ્યાઓ માટે એક સામાન્ય માળખું રજૂ કરે છે જે કુદરતી રીતે નાણાકીય ચૂકવણીનો ઉપયોગ કરીને વાજબી વસ્તુની ફાળવણી કરે છે. અઝીઝ નાણાકીય સ્થાનાંતરણનો ઉપયોગ કરીને એવી ફાળવણી પ્રાપ્ત કરવાનું લક્ષ્ય રાખે છે જે ઈર્ષ્યા મુક્ત અને ન્યાયી બંને હોય. તેઓ માત્ર એડિટિવ પોઝિટિવ યુટિલિટીઝનો જ નહીં, પરંતુ કોઈપણ સુપરએડિટિવ યુટિલિટીઝ માટે પણ અભ્યાસ કરે છે, પછી ભલે તે પોઝિટિવ હોય કે નેગેટિવઃ સુપરએડિટિવ યુટિલિટીઝ માટે, એક બહુપદી-સમયનું અલ્ગોરિધમ છે જે ઈર્ષ્યા-સ્વતંત્રતા, સમાનતા અને બજેટ સંતુલન પ્રાપ્ત કરે છે (સબસિડી સાથે બજેટ-બેલેન્સની આપ-લે કરવી સરળ છે). જો આપેલ ફાળવણી EFEQ-કન્વર્ટિબલ હોય, તો તેને EF + EQ બનાવવા માટે જરૂરી લઘુત્તમ સબસિડી રેખીય સમયમાં મળી શકે છે. લઘુતમ સબસિડી સાથે EFEQ-કન્વર્ટિબલ હોય તેવી ફાળવણી શોધવી એ NP-હાર્ડ છે, અને કોઈ પણ સકારાત્મક પરિબળમાં અંદાજિત કરી શકાતી નથી. આનું કારણ એ છે કે EF ફાળવણી (જેને 0 સબસિડીની જરૂર હોય છે) ના અસ્તિત્વની તપાસ કરવી એ NP-હાર્ડ છે. મહત્તમ (એન-1) એમવીની સબસિડી હંમેશા પૂરતી હોય છે, અને ફાળવણી કરવામાં આવે કે નહીં તે જરૂરી હોઈ શકે છે. ઈર્ષ્યા-મુક્ત વસ્તુની ફાળવણી પણ જુઓ-નાણાકીય સ્થાનાંતરણ વિનાનું સેટિંગ. સંદર્ભો વાજબી વસ્તુની ફાળવણી