Egalitarian cake-cutting
समतावादी केक काटना एक प्रकार का उचित केक काटना है जिसमें निष्पक्षता का मानदंड समतावादी नियम है। केक एक निरंतर संसाधन (जैसे भूमि या समय) का प्रतिनिधित्व करता है, जिसे संसाधन के कुछ हिस्सों पर अलग-अलग मूल्यांकन वाले लोगों के बीच आवंटित किया जाना है। समतावादी केक काटने में लक्ष्य एक एजेंट के सबसे छोटे मूल्य को अधिकतम करना है; इसके अधीन, अगले सबसे छोटे मूल्य को अधिकतम करें; और इसी तरह। इसे लेक्सिमिन केक-कटिंग भी कहा जाता है, क्योंकि उपयोगिताओं के वैक्टर पर लेक्सिमिन क्रम का उपयोग करके अनुकूलन किया जाता है। समतावादी केक काटने की अवधारणा का वर्णन सबसे पहले डबिन्स और स्पैनियर ने किया था, जिन्होंने इसे "इष्टतम विभाजन" कहा था। अस्तित्व लेक्सिमिन-इष्टतम आवंटन तब मौजूद होते हैं जब आवंटन का सेट एक कॉम्पैक्ट स्थान होता है। यह हमेशा अलग-अलग वस्तुओं को आवंटित करते समय होता है, और निरंतर सजातीय संसाधनों की एक सीमित संख्या आवंटित करते समय साबित करना आसान होता है। डबिन्स और स्पैनियर ने साबित किया कि, एक निरंतर विषम संसाधन ("केक") के साथ, आवंटन का सेट कॉम्पैक्ट है। इसलिए, लेक्सिमिन-इष्टतम केक आवंटन हमेशा मौजूद रहता है। इस कारण से, लेक्सिमिन केक-आवंटन नियम को कभी-कभी डबिन्स-स्पैनियर नियम कहा जाता है। प्रकार जब एजेंटों के मूल्यांकन को सामान्य नहीं किया जाता है (यानी, विभिन्न एजेंट पूरे केक को एक अलग मूल्य निर्धारित कर सकते हैं), तो एक आवंटन के पूर्ण उपयोगिता प्रोफ़ाइल (जहां तत्व i केवल एजेंट i की उपयोगिता है), और इसके सापेक्ष उपयोगिता प्रोफ़ाइल (जहां तत्व i एजेंट की उपयोगिता है I को एजेंट i के कुल मूल्य से विभाजित किया जाता है) के बीच अंतर होता है। निरपेक्ष लेक्सिमिन नियम एक आवंटन चुनता है जिसमें निरपेक्ष उपयोगिता प्रोफ़ाइल लेक्सिमिन-अधिकतम है, और सापेक्ष लेक्सिमिन नियम एक आवंटन चुनता है जिसमें सापेक्ष उपयोगिता प्रोफ़ाइल लेक्सिमिन-अधिकतम है। गुण लेक्सिमिन नियम के दोनों रूप पेरेटो-इष्टतम और जनसंख्या एकरस हैं। हालाँकि, वे अन्य गुणों में भिन्न होते हैंः निरपेक्ष-लेक्सिमिन नियम संसाधन एकरस है लेकिन आनुपातिक नहीं है; सापेक्ष-लेक्सिमिन नियम आनुपातिक है लेकिन संसाधन एकरस नहीं है। ईर्ष्या-स्वतंत्रता से संबंध लेक्सिमिन नियम के दोनों रूपों से ऐसे आवंटन हो सकते हैं जो ईर्ष्या-मुक्त नहीं हैं। उदाहरण के लिए, मान लीजिए कि 5 एजेंट हैं, केक 3 क्षेत्रों के साथ पीसवाइस-होमोजीनियस है, और एजेंटों का मूल्यांकन है (लापता मान शून्य हैं): सभी एजेंट पूरे केक को 15 पर मान देते हैं, इसलिए एब्सोल्यूट-लेक्सिमिन और रिलेटिव-लेक्सिमिन बराबर हैं। सबसे बड़ा संभव न्यूनतम मूल्य 5 है, इसलिए एक लेक्सिमिन आवंटन में सभी एजेंटों को कम से कम 5 देना चाहिए। इसका मतलब है कि अधिकार को एजेंट सी, डी, ई के बीच समान रूप से विभाजित किया जाना चाहिए और मध्य पूरी तरह से एजेंट बी को दिया जाना चाहिए। लेकिन फिर ए ईर्ष्या बी. डबिन्स और स्पैनियर ने साबित किया कि, जब सभी मूल्य-उपाय सख्ती से सकारात्मक होते हैं, तो प्रत्येक सापेक्ष-लेक्सिमिन आवंटन ईर्ष्या-मुक्त होता है। वेलर ने एक ईर्ष्या-मुक्त और कुशल केक आवंटन दिखाया जो सापेक्ष-लेक्सिमिन नहीं है। केक है [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]) है। कम्प्यूटेशन डेल 'एग्लियो एक लेक्सिमिन-इष्टतम संसाधन आवंटन की गणना के लिए एक एल्गोरिथ्म प्रस्तुत करता है। इक्विटेबल केक-कटिंग भी देखें-एक आवंटन जो प्रत्येक एजेंट को एक समान उपयोगिता देता है। अक्सर, समतावादी आवंटन न्यायसंगत आवंटन के साथ मेल खाता है, क्योंकि यदि उपयोगिताएँ अलग हैं, तो बड़ी उपयोगिता वाले एजेंट से कुछ केक को स्थानांतरित करके छोटी उपयोगिता में सुधार किया जा सकता है। समतावादी समानता-सजातीय संसाधन आवंटन के संदर्भ में एक समान अवधारणा। संदर्भ समतावाद केक-कटिंग