Egalitarian cake-cutting
સમતાવાદી કેક-કટિંગ એ એક પ્રકારનું વાજબી કેક-કટિંગ છે જેમાં નિષ્પક્ષતાનો માપદંડ સમતાવાદી નિયમ છે. કેક એક સતત સંસાધન (જેમ કે જમીન અથવા સમય) નું પ્રતિનિધિત્વ કરે છે, જે સંસાધનના ભાગો પર વિવિધ મૂલ્યાંકન ધરાવતા લોકો વચ્ચે ફાળવવામાં આવે છે. સમતાવાદી કેક-કટિંગનો ધ્યેય એજન્ટના સૌથી નાના મૂલ્યને મહત્તમ કરવાનો છે; આને આધિન, આગામી સૌથી નાના મૂલ્યને મહત્તમ કરો; અને તેથી વધુ. તેને લેક્સિમિન કેક-કટિંગ પણ કહેવામાં આવે છે, કારણ કે ઉપયોગિતાઓના વાહક પર લેક્સિમિન ક્રમનો ઉપયોગ કરીને ઓપ્ટિમાઇઝેશન કરવામાં આવે છે. સમતાવાદી કેક કાપવાની વિભાવનાનું વર્ણન સૌપ્રથમ ડબિન્સ અને સ્પાનિયર દ્વારા કરવામાં આવ્યું હતું, જેમણે તેને "શ્રેષ્ઠ પાર્ટીશન" ગણાવ્યું હતું. જ્યારે પણ ફાળવણીનો સમૂહ કોમ્પેક્ટ જગ્યા હોય ત્યારે અસ્તિત્વ લેક્સિમિન-ઓપ્ટિમલ ફાળવણીઓ અસ્તિત્વ ધરાવે છે. આ હંમેશા અલગ વસ્તુઓની ફાળવણી કરતી વખતે થાય છે, અને સતત સજાતીય સંસાધનોની મર્યાદિત સંખ્યાની ફાળવણી કરતી વખતે સાબિત કરવું સરળ છે. ડબિન્સ અને સ્પાનિયરે સાબિત કર્યું કે, સતત વિજાતીય સંસાધન ("કેક") સાથે, ફાળવણીનો સમૂહ સઘન છે. તેથી, લેક્સિમિન-શ્રેષ્ઠ કેકની ફાળવણી હંમેશા અસ્તિત્વમાં રહે છે. આ કારણોસર, લેક્સિમિન કેક-ફાળવણીના નિયમને કેટલીકવાર ડુબિન્સ-સ્પાનિયર નિયમ કહેવામાં આવે છે. ફેરફારો જ્યારે એજન્ટોના મૂલ્યાંકનને સામાન્ય કરવામાં ન આવે (એટલે કે, વિવિધ એજન્ટો સમગ્ર કેકને અલગ મૂલ્ય સોંપી શકે છે), ત્યારે ફાળવણીની સંપૂર્ણ ઉપયોગિતા રૂપરેખા (જ્યાં તત્વ i એ માત્ર એજન્ટ i ની ઉપયોગિતા છે) અને તેની સંબંધિત ઉપયોગિતા રૂપરેખા (જ્યાં તત્વ i એ એજન્ટ i ની ઉપયોગિતા છે જેને એજન્ટ i માટે કુલ મૂલ્ય દ્વારા વિભાજિત કરવામાં આવે છે) વચ્ચે તફાવત હોય છે. સંપૂર્ણ લેક્સિમિન નિયમ એવી ફાળવણી પસંદ કરે છે જેમાં સંપૂર્ણ ઉપયોગિતા રૂપરેખા લેક્સિમિન-મહત્તમ હોય અને સંબંધિત લેક્સિમિન નિયમ એવી ફાળવણી પસંદ કરે છે જેમાં સંબંધિત ઉપયોગિતા રૂપરેખા લેક્સિમિન-મહત્તમ હોય. ગુણધર્મો લેક્સિમિન નિયમના બંને પ્રકારો પેરેટો-ઓપ્ટિમલ અને પોપ્યુલેશન મોનોટોનિક છે. જો કે, તેઓ અન્ય ગુણધર્મોમાં અલગ પડે છેઃ નિરપેક્ષ-લેક્સિમિન નિયમ સંસાધન મોનોટોનિક છે પરંતુ પ્રમાણસર નથી; સંબંધિત-લેક્સિમિન નિયમ પ્રમાણસર છે પરંતુ સંસાધન-મોનોટોનિક નથી. ઈર્ષ્યા-સ્વતંત્રતા સાથેનો સંબંધ લેક્સિમિન નિયમના બંને પ્રકારો એવી ફાળવણી કરી શકે છે જે ઈર્ષ્યા-મુક્ત નથી. ઉદાહરણ તરીકે, ધારો કે ત્યાં 5 એજન્ટો છે, કેક 3 પ્રદેશો સાથે પીસવાઇઝ-હોમોજીનીયસ છે, અને એજન્ટોના મૂલ્યાંકન છે (ગુમ થયેલ મૂલ્યો શૂન્ય છે): બધા એજન્ટો સમગ્ર કેકને 15 પર મૂલ્ય આપે છે, તેથી એબ્સોલ્યુટ-લેક્સિમિન અને રિલેટિવ-લેક્સિમિન સમકક્ષ છે. સૌથી મોટું શક્ય લઘુતમ મૂલ્ય 5 છે, તેથી લેક્સિમિન ફાળવણીમાં તમામ એજન્ટોને ઓછામાં ઓછું 5 આપવું આવશ્યક છે. આનો અર્થ એ છે કે અધિકાર એજન્ટો C, D, E વચ્ચે સમાન રીતે વહેંચાયેલો હોવો જોઈએ અને મધ્ય સંપૂર્ણપણે એજન્ટ B ને આપવો જોઈએ. પરંતુ પછી એ ઈર્ષા કરે છે બી. ડબિન્સ અને સ્પાનિયરે સાબિત કર્યું કે, જ્યારે તમામ મૂલ્ય-પગલાં કડક રીતે હકારાત્મક હોય છે, ત્યારે દરેક સંબંધિત-લેક્સિમિન ફાળવણી ઈર્ષા મુક્ત હોય છે. વેલરે ઈર્ષ્યા-મુક્ત અને કાર્યક્ષમ કેકની ફાળવણી દર્શાવી જે સંબંધિત-લેક્સિમિન નથી. કેક છે [0,1], ત્યાં ત્રણ એજન્ટો છે, અને તેમના મૂલ્યના માપ ત્રિકોણાકાર વિતરણો છે જે અનુક્રમે 1/4,1/2 અને 3/4 પર કેન્દ્રિત છે. ફાળવણી ([0,3/8], [3/8,5 8], [5/8,1]) માં ઉપયોગિતા રૂપરેખા (3/8,7 16,7/16) છે. તે ઈર્ષ્યા મુક્ત અને ઉપયોગિતાવાદી-શ્રેષ્ઠ છે, તેથી પેરેટો-કાર્યક્ષમ છે. જો કે, લેક્સિમિન-બેટર યુટિલિટી પ્રોફાઇલ સાથે અન્ય ફાળવણી ([0,5/16], [5/16,11 16], [11/16,1]) છે. ગણતરી ડેલ 'એગ્લિયો લેક્સિમિન-શ્રેષ્ઠ સંસાધન ફાળવણીની ગણતરી કરવા માટે એક અલ્ગોરિધમ રજૂ કરે છે. ઇક્વિટેબલ કેક-કટિંગ પણ જુઓ-દરેક એજન્ટને સમાન ઉપયોગિતા આપતી ફાળવણી. ઘણીવાર, સમાનતાવાદી ફાળવણી ન્યાયી ફાળવણી સાથે મેળ ખાય છે, કારણ કે જો ઉપયોગિતાઓ અલગ હોય, તો મોટી ઉપયોગિતા સાથે એજન્ટ પાસેથી થોડી કેક ખસેડીને નાની ઉપયોગિતામાં સુધારો કરી શકાય છે. સમતાવાદી સમાનતા-સજાતીય સંસાધન ફાળવણીના સંદર્ભમાં સમાન ખ્યાલ. સંદર્ભો સમતાવાદ કેક-કટિંગ