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]) রয়েছে। গণনা ডাল 'এগ্লিও একটি লেক্সিমিন-সর্বোত্তম সম্পদ বরাদ্দ গণনা করার জন্য একটি অ্যালগরিদম উপস্থাপন করে। আরও দেখুন ইকুইটেবল কেক-কাটিং-একটি বরাদ্দ যা প্রতিটি এজেন্টকে সমান উপযোগিতা দেয়। প্রায়শই, সাম্যবাদী বরাদ্দ ন্যায়সঙ্গত বরাদ্দের সাথে মিলে যায়, যেহেতু উপযোগিতাগুলি যদি আলাদা হয় তবে বৃহত্তর উপযোগিতাযুক্ত এজেন্টের কাছ থেকে কিছু কেক সরিয়ে ছোট উপযোগিতাকে উন্নত করা যেতে পারে। সমতাবাদী সমতা-সমজাতীয় সম্পদ বরাদ্দের প্রেক্ষাপটে একটি অনুরূপ ধারণা। তথ্যসূত্র সমতাবাদ কেক কাটা